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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 18, средняя оценка - 4.67
CyberGenius
 Аватар для CyberGenius
1 / 1 / 0
Регистрация: 23.08.2012
Сообщений: 100
13.12.2012, 20:16     Задача про зерна на шахматной доске #1
Математическая задача про пшеничные зернышки и шахматную доску. Когда на первую клетку кладется одно зернышко, на вторую – два, на третью - четыре и т.п. .

Собственно я набросал вот такой код, который позволяет нам выбрать кол-во заполненных зерном шахматных ячеек и выводит сумму всех зерен и кол-во зерен на последней ячейке.
Буду признателен если укажите на очевидные косяки кода и подскажите как можно было бы лучше написать код.
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");
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
13.12.2012, 20:16     Задача про зерна на шахматной доске
Посмотрите здесь:

C++ Числа на шахматной доске в С++
Числа на шахматной доске C++
C++ Числа на шахматной доске
C++ Замена фигур на шахматной доске
C++ Расставить n ладей на шахматной доске n*n
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
MrGluck
Ворчун
Эксперт С++
 Аватар для MrGluck
4927 / 2670 / 243
Регистрация: 29.11.2010
Сообщений: 7,427
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
 Аватар для 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
Ворчун
Эксперт С++
 Аватар для MrGluck
4927 / 2670 / 243
Регистрация: 29.11.2010
Сообщений: 7,427
13.12.2012, 20:29     Задача про зерна на шахматной доске #4
CyberGenius, при а = а * 2; сначала создается копия объекта а.
CyberGenius
 Аватар для CyberGenius
1 / 1 / 0
Регистрация: 23.08.2012
Сообщений: 100
13.12.2012, 20:30  [ТС]     Задача про зерна на шахматной доске #5
Цитата Сообщение от MrGluck Посмотреть сообщение
CyberGenius, при а = а * 2; сначала создается копия объекта а.
То есть, если я правильно понял, занимается лишняя память?
MrGluck
Ворчун
Эксперт С++
 Аватар для MrGluck
4927 / 2670 / 243
Регистрация: 29.11.2010
Сообщений: 7,427
13.12.2012, 20:33     Задача про зерна на шахматной доске #6
Цитата Сообщение от CyberGenius Посмотреть сообщение
То есть, если я правильно понял, занимается лишняя память?
Да, а также операция копирования объекта требует времени.
ValeryS
Модератор
6377 / 4843 / 442
Регистрация: 14.02.2011
Сообщений: 16,057
13.12.2012, 20:34     Задача про зерна на шахматной доске #7
Цитата Сообщение от CyberGenius Посмотреть сообщение
int a = 1;//Кол-во зерен в последней ячейке
* * int b = 0;//Тут храним сумму всех зерен
вообще то в последней клетке количество зерен 2^63 общее количество 2^64-1
int явно не хватит
long long!!!
MrGluck
Ворчун
Эксперт С++
 Аватар для MrGluck
4927 / 2670 / 243
Регистрация: 29.11.2010
Сообщений: 7,427
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
Модератор
6377 / 4843 / 442
Регистрация: 14.02.2011
Сообщений: 16,057
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
Ворчун
Эксперт С++
 Аватар для MrGluck
4927 / 2670 / 243
Регистрация: 29.11.2010
Сообщений: 7,427
13.12.2012, 20:40     Задача про зерна на шахматной доске #10
ValeryS, а так изменяется значение переменной без создания копии. И это не синонимы, просто конечный результат схож.
CyberGenius
 Аватар для CyberGenius
1 / 1 / 0
Регистрация: 23.08.2012
Сообщений: 100
13.12.2012, 20:54  [ТС]     Задача про зерна на шахматной доске #11
Цитата Сообщение от ValeryS Посмотреть сообщение
a = 1<<k;
я не совсем понял, что делает данное выражение?
ValeryS
Модератор
6377 / 4843 / 442
Регистрация: 14.02.2011
Сообщений: 16,057
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
108 / 108 / 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
Модератор
6377 / 4843 / 442
Регистрация: 14.02.2011
Сообщений: 16,057
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 Посмотреть сообщение
а так же менее читабелен.
для тех кто не знаком с двоичной арифметикой, да это темный лес
MrGluck
Ворчун
Эксперт С++
 Аватар для MrGluck
4927 / 2670 / 243
Регистрация: 29.11.2010
Сообщений: 7,427
13.12.2012, 23:55     Задача про зерна на шахматной доске #15
ValeryS, пожалуй соглашусь, что записи эквиваленты по сути. Возможно, компилятор сам оптимизирует их к записи с совместным оператором сложения и присваиванием. Энивей, писать a = a + 2 следует только на блок-схемах.
Но вот применение сдвига, по-моему, не оправданно. Профита нет.
ValeryS
Модератор
6377 / 4843 / 442
Регистрация: 14.02.2011
Сообщений: 16,057
14.12.2012, 00:20     Задача про зерна на шахматной доске #16
Цитата Сообщение от MrGluck Посмотреть сообщение
Но вот применение сдвига, по-моему, не оправданно. Профита нет.
здесь может быть (для скорости)
но для понимания что такое степень двойки (а шахматной доске как и в ханойской башне все на них завязано)
и как она связана со сдвигом ( в качестве обучения) надо было привести
чтобы потом когда попросят возвести 2 в 10 степень не писал
C++
1
2
3
int a=2;
for(int i=1;i<10;i++)
  a=a*2;
а написал
C++
1
 a = 1<<10;
Добавлено через 2 минуты

Не по теме:

кстати здесь по условиям задачи тоже нет цикла

Цитата Сообщение от CyberGenius Посмотреть сообщение
выводит сумму всех зерен и кол-во зерен на последней ячейке.
алгоритмы то сейчас вообще не проходят что ли
тупое кодирование?

MrGluck
14.12.2012, 00:35
  #17

Не по теме:

ValeryS, так бы и сказали, чисто в педагогических целях)


Не по теме:

А у нас до сдвигов то дело так и не дошло. Ни сдвигов, ни побитовых операций, ни потоков... Все самому

CyberGenius
 Аватар для CyberGenius
1 / 1 / 0
Регистрация: 23.08.2012
Сообщений: 100
14.12.2012, 09:58  [ТС]     Задача про зерна на шахматной доске #18
Цитата Сообщение от ValeryS Посмотреть сообщение
алгоритмы то сейчас вообще не проходят что ли
К сожалению не проходят... Как правильно заметил MrGluck, приходится учиться всему самому
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
14.12.2012, 12:45     Задача про зерна на шахматной доске
Еще ссылки по теме:

Ход на шахматной доске C++
C++ Задача о зернах на шахматной доске
C++ Геометрическая прогрессия на шахматной доске

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

Или воспользуйтесь поиском по форуму:
snw
10 / 10 / 0
Регистрация: 11.10.2012
Сообщений: 93
14.12.2012, 12:45     Задача про зерна на шахматной доске #19
Вообще это длинная арифметика, помню была задача с кучами золота. Посмотрите на длинную арифметику.
Yandex
Объявления
14.12.2012, 12:45     Задача про зерна на шахматной доске
Ответ Создать тему
Опции темы

Текущее время: 17:31. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru