Форум программистов, компьютерный форум CyberForum.ru
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 18, средняя оценка - 4.67
CyberGenius
1 / 1 / 0
Регистрация: 23.08.2012
Сообщений: 100
#1

Задача про зерна на шахматной доске - C++

13.12.2012, 20:16. Просмотров 2481. Ответов 18
Метки нет (Все метки)

Математическая задача про пшеничные зернышки и шахматную доску. Когда на первую клетку кладется одно зернышко, на вторую – два, на третью - четыре и т.п. .

Собственно я набросал вот такой код, который позволяет нам выбрать кол-во заполненных зерном шахматных ячеек и выводит сумму всех зерен и кол-во зерен на последней ячейке.
Буду признателен если укажите на очевидные косяки кода и подскажите как можно было бы лучше написать код.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
    //Задача про зерна
    int i = 0; //Количество заполненных зерном ячеек
    int a = 1;//Кол-во зерен в последней ячейке
    int b = 0;//Тут храним сумму всех зерен
    cout <<"Введите кол-во заполненных зернами ячеек: "<<endl;
    cin>>i;
    //В цикле ниже вычисляем сумму всех зерен и кол-во зерен на последней ячейке
    for(int k=1; k<i; ++k){
        a = a*2;
        b += a;
        cout << k+1<< "\t"<< a<< endl;
    }
    //Пришлось ввести это условие, чтобы был корректный вывод суммы всех зерен в случае ввода О заполненных ячеек
    if (i == 0){
        b =-1;
        a = 0;
    }
    cout<<"кол-во зерен на "<< i<< " ячейке равно: "<< a<< " , сумма всех зерен: "<< b + 1<< endl;
 
    system("pause");
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
13.12.2012, 20:16
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Задача про зерна на шахматной доске (C++):

Задача о зернах на шахматной доске - C++
Математическая задача, в которой вычисляется, сколько будет зёрен на шахматной доске, если класть на каждую следующую клетку доски вдвое...

Числа на шахматной доске в С++ - C++
В клетках шахматной доски находятся целые числа. --- Определить в программе глобальные данные- константу N=8 и двумерный числовой массив...

Числа на шахматной доске - C++
В клетках шахматной доски находятся целые число. --- Определить в программе глобальные данные – константу N = 8 и двумерный числовой массив...

Ход на шахматной доске - C++
Поле шахматной доски определяется парой натуральных чисел, первое из которых задает номер вертикали, а второе - номер горизонтали. Данные...

Числа на шахматной доске - C++
В клетках шахматной доски находятся целые число. --- Определить в программе глобальные данные – константу N = 8 и двумерный числовой массив...

Замена фигур на шахматной доске - C++
задача. расставить случайным образом четырех коней на шахматной доске (два белых и два черных). вывести отдельно список полей под боем...

18
MrGluck
Модератор
Эксперт CЭксперт С++
7278 / 4439 / 650
Регистрация: 29.11.2010
Сообщений: 12,017
13.12.2012, 20:22 #2
for(int k=1; k<=i; ++k){

Добавлено через 20 секунд
a = a*2;
a *= 2;

Добавлено через 26 секунд
cout << k<< "\t"<< a<< endl;
0
CyberGenius
1 / 1 / 0
Регистрация: 23.08.2012
Сообщений: 100
13.12.2012, 20:26  [ТС] #3
Цитата Сообщение от MrGluck Посмотреть сообщение
for(int k=1; k<=i; ++k){

Добавлено через 20 секунд
a = a*2;
a *= 2;

Добавлено через 26 секунд
cout << k<< "\t"<< a<< endl;
a = a*2 и a*=2 между ними нет большой разницы, но да, первая запись предпочтительней, т.к меньше вероятность ошибки.

а все, понял, спасибо.
0
MrGluck
Модератор
Эксперт CЭксперт С++
7278 / 4439 / 650
Регистрация: 29.11.2010
Сообщений: 12,017
13.12.2012, 20:29 #4
CyberGenius, при а = а * 2; сначала создается копия объекта а.
0
CyberGenius
1 / 1 / 0
Регистрация: 23.08.2012
Сообщений: 100
13.12.2012, 20:30  [ТС] #5
Цитата Сообщение от MrGluck Посмотреть сообщение
CyberGenius, при а = а * 2; сначала создается копия объекта а.
То есть, если я правильно понял, занимается лишняя память?
0
MrGluck
Модератор
Эксперт CЭксперт С++
7278 / 4439 / 650
Регистрация: 29.11.2010
Сообщений: 12,017
13.12.2012, 20:33 #6
Цитата Сообщение от CyberGenius Посмотреть сообщение
То есть, если я правильно понял, занимается лишняя память?
Да, а также операция копирования объекта требует времени.
0
ValeryS
Модератор
6650 / 5059 / 470
Регистрация: 14.02.2011
Сообщений: 16,918
13.12.2012, 20:34 #7
Цитата Сообщение от CyberGenius Посмотреть сообщение
int a = 1;//Кол-во зерен в последней ячейке
* * int b = 0;//Тут храним сумму всех зерен
вообще то в последней клетке количество зерен 2^63 общее количество 2^64-1
int явно не хватит
long long!!!
0
MrGluck
Модератор
Эксперт CЭксперт С++
7278 / 4439 / 650
Регистрация: 29.11.2010
Сообщений: 12,017
13.12.2012, 20:36 #8
ValeryS, unsigned long long!!
C++
1
2
3
4
5
for(int k=1; k<=i; ++k){
    cout << k<< "\t"<< a<< endl;
    a *= 2;
    b += a;
}
0
ValeryS
Модератор
6650 / 5059 / 470
Регистрация: 14.02.2011
Сообщений: 16,918
13.12.2012, 20:39 #9
Цитата Сообщение от MrGluck Посмотреть сообщение
CyberGenius, при а = а * 2; сначала создается копия объекта а.
а так
C++
1
а *=   2;
не создается?
вообще то это синонимы
Цитата Сообщение от CyberGenius Посмотреть сообщение
for(int k=1; k<i; ++k){
a = a*2;
b += a;
cout << k+1<< "\t"<< a<< endl;
}
все проще
C++
1
2
3
4
5
for(int k=0; k<i; ++k){
     a = 1<<k;
      b += a;
     cout << k+1<< "\t"<< a<< endl;
 }
Добавлено через 56 секунд
Цитата Сообщение от MrGluck Посмотреть сообщение
ValeryS, unsigned long long!!
согласен
0
MrGluck
Модератор
Эксперт CЭксперт С++
7278 / 4439 / 650
Регистрация: 29.11.2010
Сообщений: 12,017
13.12.2012, 20:40 #10
ValeryS, а так изменяется значение переменной без создания копии. И это не синонимы, просто конечный результат схож.
0
CyberGenius
1 / 1 / 0
Регистрация: 23.08.2012
Сообщений: 100
13.12.2012, 20:54  [ТС] #11
Цитата Сообщение от ValeryS Посмотреть сообщение
a = 1<<k;
я не совсем понял, что делает данное выражение?
0
ValeryS
Модератор
6650 / 5059 / 470
Регистрация: 14.02.2011
Сообщений: 16,918
13.12.2012, 21:29 #12
Цитата Сообщение от CyberGenius Посмотреть сообщение
я не совсем понял, что делает данное выражение?
это сдвиг
в данном контексте возведение 2 в степень
для 0(первая клетка) 1<<0=1
для 1(вторая клетка) 1<<1=10(в двоичной) =2(десятичной)
для 2(третья клетка) 1<<2=100(в двоичной) =4 (десятичной)
ну и так далее

Добавлено через 4 минуты
тут можно вообще без цикла сосчитать
C++
1
2
3
4
5
6
7
unsigned long long a ;//Кол-во зерен в последней ячейке
unsigned long long  b = 0;//Тут храним сумму всех зерен
    cout <<"Введите кол-во заполненных зернами ячеек: "<<endl;
    cin>>i;
    
        a = 1<<(i-1);
        b = (1<<i )-1;
Добавлено через 22 минуты
Цитата Сообщение от MrGluck Посмотреть сообщение
ValeryS, а так изменяется значение переменной без создания копии. И это не синонимы, просто конечный результат схож.
смотрим
C++
1
2
3
4
int a=2;
int b=2;
a*=2;
b=b*2;
Assembler
1
2
3
4
5
6
7
8
9
10
11
12
;int a=2;
0127138E  mov         dword ptr [a],2 
;int b=2;
01271395  mov         dword ptr [b],2 
;a*=2;
0127139C  mov         eax,dword ptr [a] 
0127139F  shl         eax,1 
012713A1  mov         dword ptr [a],eax 
;b=b*2;
012713A4  mov         eax,dword ptr [b] 
012713A7  shl         eax,1 
012713A9  mov         dword ptr [b],eax
где создается копия????
как видишь код идентичный
1
prazuber
110 / 110 / 3
Регистрация: 29.04.2010
Сообщений: 240
13.12.2012, 22:10 #13
Цитата Сообщение от ValeryS Посмотреть сообщение
все проще
C++
1
2
3
4
5
for(int k=0; k<i; ++k){
     a = 1<<k;
      b += a;
     cout << k+1<< "\t"<< a<< endl;
 }
Я согласен что если нужно посчитать конечный результат, то цикла здесь не нужно. Тем не менее, пусть нам необходимо вывести количество зерен для каждой клетки. Я ради интереса скомпилил разные варианты выражения a*=2 с включенной оптимизацией в VS2012. Варианты a*=2 и a=a*2 дали абсолютно одинаковый код, но для a=1<<k код отличается. Так как код оптимизирован, то не удается выделить код для одной строки. Вместо этого, я наведу различия:
Assembler
1
2
3
4
5
6
7
8
9
; a *= 2
00B712B0  push        dword ptr ds:[0B73044h]  
00B712B6  mov         ecx,dword ptr ds:[0B7305Ch]  
00B712BC  lea         ebx,[ebx+esi*2]  
00B712BF  add         esi,esi  
00B712C1  push        esi  
00B712C2  inc         edi  
00B712C3  push        edi  
00B712C4  call        dword ptr ds:[0B73034h]
Assembler
1
2
3
4
5
6
7
8
9
10
11
; a = 1 << k;
00F412B0  push        dword ptr ds:[0F43044h]  
00F412B6  mov         ecx,edi  
00F412B8  mov         esi,1  
00F412BD  shl         esi,cl  
00F412BF  mov         ecx,dword ptr ds:[0F4305Ch]  
00F412C5  inc         edi  
00F412C6  push        esi  
00F412C7  push        edi  
00F412C8  add         ebx,esi  
00F412CA  call        dword ptr ds:[0F43034h]
Как видно, второй вариант работает медленнее, а так же менее читабелен.
0
ValeryS
Модератор
6650 / 5059 / 470
Регистрация: 14.02.2011
Сообщений: 16,918
13.12.2012, 22:38 #14
Цитата Сообщение от prazuber Посмотреть сообщение
включенной оптимизацией в VS2012.
С включеной оптимизацией чего???
там 100500 параметров
и потом если проводишь тесты выбрасывай вывод на экран

Цитата Сообщение от prazuber Посмотреть сообщение
Как видно, второй вариант работает медленнее,
мне например это не видно
если выбросить весь мусор то
Assembler
1
2
3
4
;a *= 2
 
  lea         ebx,[ebx+esi*2]  
  add         esi,esi
Assembler
1
2
3
4
5
 ; a = 1 << k;
 mov         ecx,edi  
  mov         esi,1  
 shl         esi,cl  
 add         ebx,esi
разница в два mov которые скорее всего исполнятся за один такт
и я не знаю сколько тактов занимает lea (некогда сейчас искать, но по моему её скорость зависит от аргумента)
а shl всего один такт
так что так огульно, без растактовки кто быстрее я бы не стал говорить

Цитата Сообщение от prazuber Посмотреть сообщение
а так же менее читабелен.
для тех кто не знаком с двоичной арифметикой, да это темный лес
0
MrGluck
Модератор
Эксперт CЭксперт С++
7278 / 4439 / 650
Регистрация: 29.11.2010
Сообщений: 12,017
13.12.2012, 23:55 #15
ValeryS, пожалуй соглашусь, что записи эквиваленты по сути. Возможно, компилятор сам оптимизирует их к записи с совместным оператором сложения и присваиванием. Энивей, писать a = a + 2 следует только на блок-схемах.
Но вот применение сдвига, по-моему, не оправданно. Профита нет.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
13.12.2012, 23:55
Привет! Вот еще темы с ответами:

Геометрическая прогрессия на шахматной доске - C++
Всем доброго времени суток.Отписывайтесь кто как решил. #include &quot;head.h&quot; void main() {//на поле 64 клетки ///сколько надо...

Расставить n ладей на шахматной доске n*n - C++
Вообщем нужно расставить n ладей на шахматной доске n*n Вот то что у меня получилось: #pragma argsused #include&lt;iostream.h&gt; int...

Одного ли цвета клетки на шахматной доске? - C++
Даны координаты двух полей шахматной доски (координаты клетки - это 2 числа от 1 до 8: номер столбца и номер строки) Одно ли цвета эти...

Просчет ходов Слона по шахматной доске - C++
Здравствуйте. Помогите, пожалуйста, с решением задачи на просчет ходов слона по шахматной доске. Функционал: Вводим: текущее...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
15
Yandex
Объявления
13.12.2012, 23:55
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru