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

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

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

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

13.12.2012, 20:16. Просмотров 2376. Ответов 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");
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
MrGluck
Модератор
Эксперт CЭксперт С++
7184 / 4350 / 634
Регистрация: 29.11.2010
Сообщений: 11,843
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;
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 между ними нет большой разницы, но да, первая запись предпочтительней, т.к меньше вероятность ошибки.

а все, понял, спасибо.
MrGluck
Модератор
Эксперт CЭксперт С++
7184 / 4350 / 634
Регистрация: 29.11.2010
Сообщений: 11,843
13.12.2012, 20:29     Задача про зерна на шахматной доске #4
CyberGenius, при а = а * 2; сначала создается копия объекта а.
CyberGenius
1 / 1 / 0
Регистрация: 23.08.2012
Сообщений: 100
13.12.2012, 20:30  [ТС]     Задача про зерна на шахматной доске #5
Цитата Сообщение от MrGluck Посмотреть сообщение
CyberGenius, при а = а * 2; сначала создается копия объекта а.
То есть, если я правильно понял, занимается лишняя память?
MrGluck
Модератор
Эксперт CЭксперт С++
7184 / 4350 / 634
Регистрация: 29.11.2010
Сообщений: 11,843
13.12.2012, 20:33     Задача про зерна на шахматной доске #6
Цитата Сообщение от CyberGenius Посмотреть сообщение
То есть, если я правильно понял, занимается лишняя память?
Да, а также операция копирования объекта требует времени.
ValeryS
Модератор
6552 / 5018 / 463
Регистрация: 14.02.2011
Сообщений: 16,739
13.12.2012, 20:34     Задача про зерна на шахматной доске #7
Цитата Сообщение от CyberGenius Посмотреть сообщение
int a = 1;//Кол-во зерен в последней ячейке
* * int b = 0;//Тут храним сумму всех зерен
вообще то в последней клетке количество зерен 2^63 общее количество 2^64-1
int явно не хватит
long long!!!
MrGluck
Модератор
Эксперт CЭксперт С++
7184 / 4350 / 634
Регистрация: 29.11.2010
Сообщений: 11,843
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;
}
ValeryS
Модератор
6552 / 5018 / 463
Регистрация: 14.02.2011
Сообщений: 16,739
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!!
согласен
MrGluck
Модератор
Эксперт CЭксперт С++
7184 / 4350 / 634
Регистрация: 29.11.2010
Сообщений: 11,843
13.12.2012, 20:40     Задача про зерна на шахматной доске #10
ValeryS, а так изменяется значение переменной без создания копии. И это не синонимы, просто конечный результат схож.
CyberGenius
1 / 1 / 0
Регистрация: 23.08.2012
Сообщений: 100
13.12.2012, 20:54  [ТС]     Задача про зерна на шахматной доске #11
Цитата Сообщение от ValeryS Посмотреть сообщение
a = 1<<k;
я не совсем понял, что делает данное выражение?
ValeryS
Модератор
6552 / 5018 / 463
Регистрация: 14.02.2011
Сообщений: 16,739
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
где создается копия????
как видишь код идентичный
prazuber
109 / 109 / 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]
Как видно, второй вариант работает медленнее, а так же менее читабелен.
ValeryS
Модератор
6552 / 5018 / 463
Регистрация: 14.02.2011
Сообщений: 16,739
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 Посмотреть сообщение
а так же менее читабелен.
для тех кто не знаком с двоичной арифметикой, да это темный лес
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
13.12.2012, 23:55     Задача про зерна на шахматной доске
Еще ссылки по теме:
C++ Геометрическая прогрессия на шахматной доске
C++ Просчет ходов Слона по шахматной доске
C++ Одного ли цвета клетки на шахматной доске?
Реализовать программу по распределению 8 слонов по шахматной доске C++
C++ Найти расстановку двенадцати коней на шахматной доске

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

Или воспользуйтесь поиском по форуму:
MrGluck
Модератор
Эксперт CЭксперт С++
7184 / 4350 / 634
Регистрация: 29.11.2010
Сообщений: 11,843
13.12.2012, 23:55     Задача про зерна на шахматной доске #15
ValeryS, пожалуй соглашусь, что записи эквиваленты по сути. Возможно, компилятор сам оптимизирует их к записи с совместным оператором сложения и присваиванием. Энивей, писать a = a + 2 следует только на блок-схемах.
Но вот применение сдвига, по-моему, не оправданно. Профита нет.
Yandex
Объявления
13.12.2012, 23:55     Задача про зерна на шахматной доске
Ответ Создать тему
Опции темы

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