Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.85/41: Рейтинг темы: голосов - 41, средняя оценка - 4.85
 Аватар для CyberGenius
1 / 1 / 1
Регистрация: 23.08.2012
Сообщений: 100

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

13.12.2012, 20:16. Показов 8410. Ответов 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
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
13.12.2012, 20:16
Ответы с готовыми решениями:

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

Задача про зерна на шахматной доске
Задача про зерна на шахматной доске. Задача о зёрнах на шахматной доске — математическая задача, в которой вычисляется, сколько будет...

Задачка про игру на шахматной доске
Двух королей ставят на некое шахматное поле, некоторые клетки которого являются недостижимыми. Короли делают ходы по очереди, начиная с...

18
Форумчанин
Эксперт CЭксперт С++
 Аватар для MrGluck
8216 / 5047 / 1437
Регистрация: 29.11.2010
Сообщений: 13,453
13.12.2012, 20:22
for(int k=1; k<=i; ++k){

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

Добавлено через 26 секунд
cout << k<< "\t"<< a<< endl;
0
 Аватар для CyberGenius
1 / 1 / 1
Регистрация: 23.08.2012
Сообщений: 100
13.12.2012, 20:26  [ТС]
Цитата Сообщение от 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
Форумчанин
Эксперт CЭксперт С++
 Аватар для MrGluck
8216 / 5047 / 1437
Регистрация: 29.11.2010
Сообщений: 13,453
13.12.2012, 20:29
CyberGenius, при а = а * 2; сначала создается копия объекта а.
0
 Аватар для CyberGenius
1 / 1 / 1
Регистрация: 23.08.2012
Сообщений: 100
13.12.2012, 20:30  [ТС]
Цитата Сообщение от MrGluck Посмотреть сообщение
CyberGenius, при а = а * 2; сначала создается копия объекта а.
То есть, если я правильно понял, занимается лишняя память?
0
Форумчанин
Эксперт CЭксперт С++
 Аватар для MrGluck
8216 / 5047 / 1437
Регистрация: 29.11.2010
Сообщений: 13,453
13.12.2012, 20:33
Цитата Сообщение от CyberGenius Посмотреть сообщение
То есть, если я правильно понял, занимается лишняя память?
Да, а также операция копирования объекта требует времени.
0
Модератор
Эксперт по электронике
8979 / 6745 / 921
Регистрация: 14.02.2011
Сообщений: 23,857
13.12.2012, 20:34
Цитата Сообщение от CyberGenius Посмотреть сообщение
int a = 1;//Кол-во зерен в последней ячейке
* * int b = 0;//Тут храним сумму всех зерен
вообще то в последней клетке количество зерен 2^63 общее количество 2^64-1
int явно не хватит
long long!!!
0
Форумчанин
Эксперт CЭксперт С++
 Аватар для MrGluck
8216 / 5047 / 1437
Регистрация: 29.11.2010
Сообщений: 13,453
13.12.2012, 20:36
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
Модератор
Эксперт по электронике
8979 / 6745 / 921
Регистрация: 14.02.2011
Сообщений: 23,857
13.12.2012, 20:39
Цитата Сообщение от 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
Форумчанин
Эксперт CЭксперт С++
 Аватар для MrGluck
8216 / 5047 / 1437
Регистрация: 29.11.2010
Сообщений: 13,453
13.12.2012, 20:40
ValeryS, а так изменяется значение переменной без создания копии. И это не синонимы, просто конечный результат схож.
0
 Аватар для CyberGenius
1 / 1 / 1
Регистрация: 23.08.2012
Сообщений: 100
13.12.2012, 20:54  [ТС]
Цитата Сообщение от ValeryS Посмотреть сообщение
a = 1<<k;
я не совсем понял, что делает данное выражение?
0
Модератор
Эксперт по электронике
8979 / 6745 / 921
Регистрация: 14.02.2011
Сообщений: 23,857
13.12.2012, 21:29
Цитата Сообщение от 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
114 / 114 / 13
Регистрация: 29.04.2010
Сообщений: 240
13.12.2012, 22:10
Цитата Сообщение от 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
Модератор
Эксперт по электронике
8979 / 6745 / 921
Регистрация: 14.02.2011
Сообщений: 23,857
13.12.2012, 22:38
Цитата Сообщение от 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
Форумчанин
Эксперт CЭксперт С++
 Аватар для MrGluck
8216 / 5047 / 1437
Регистрация: 29.11.2010
Сообщений: 13,453
13.12.2012, 23:55
ValeryS, пожалуй соглашусь, что записи эквиваленты по сути. Возможно, компилятор сам оптимизирует их к записи с совместным оператором сложения и присваиванием. Энивей, писать a = a + 2 следует только на блок-схемах.
Но вот применение сдвига, по-моему, не оправданно. Профита нет.
0
Модератор
Эксперт по электронике
8979 / 6745 / 921
Регистрация: 14.02.2011
Сообщений: 23,857
14.12.2012, 00:20
Цитата Сообщение от 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 Посмотреть сообщение
выводит сумму всех зерен и кол-во зерен на последней ячейке.
алгоритмы то сейчас вообще не проходят что ли:(
тупое кодирование?

0
14.12.2012, 00:35

Не по теме:

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


Не по теме:

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

0
 Аватар для CyberGenius
1 / 1 / 1
Регистрация: 23.08.2012
Сообщений: 100
14.12.2012, 09:58  [ТС]
Цитата Сообщение от ValeryS Посмотреть сообщение
алгоритмы то сейчас вообще не проходят что ли
К сожалению не проходят... Как правильно заметил MrGluck, приходится учиться всему самому
0
10 / 10 / 4
Регистрация: 11.10.2012
Сообщений: 93
14.12.2012, 12:45
Вообще это длинная арифметика, помню была задача с кучами золота. Посмотрите на длинную арифметику.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
14.12.2012, 12:45
Помогаю со студенческими работами здесь

Задача о шахматной доске.
Здравствуйте, помогите,пожалуйста, решить задачу. В прологе я 0 полный(((. Вот такая задачка: Восемь шахматных фигур (без пешек)...

Задача о Шахматной доске
Шахиншах на каждую шахматную клетку кладет вдвое больше зерен, чем на предыдущую. На первую клетку - 1 зерно, на вторую - 2 зерна, на...

Задача о муравьях на шахматной доске
Есть доска в клеточку 10 на 10, на каждой клетке стоит муравей. Муравей может сместиться на соседнюю клетку, но не по диагонали. 2 муравья...

Задача о зёрнах на шахматной доске
Здравствуйте дорогие форумчани, помогите пожалуйста решить задачу, задача такова, один старик должен разложить на шахматную доску зерен,...

Задача с конями на шахматной доске
Долго думаю над задачей и все еще не знаю даже с чего начать. На шахматной доске размером N*N находятся некоторое количество коней. Их...


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

Или воспользуйтесь поиском по форуму:
19
Ответ Создать тему
Новые блоги и статьи
Загрузка PNG-файла с альфа-каналом с помощью библиотеки SDL3_image на Android
8Observer8 27.01.2026
Содержание блога SDL3_image - это библиотека для загрузки и работы с изображениями. Эта пошаговая инструкция покажет, как загрузить и вывести на экран смартфона картинку с альфа-каналом, то есть с. . .
влияние грибов на сукцессию
anaschu 26.01.2026
Бифуркационные изменения массы гриба происходят тогда, когда мы уменьшаем массу компоста в 10 раз, а скорость прироста биомассы уменьшаем в три раза. Скорость прироста биомассы может уменьшаться за. . .
Воспроизведение звукового файла с помощью SDL3_mixer при касании экрана Android
8Observer8 26.01.2026
Содержание блога SDL3_mixer - это библиотека я для воспроизведения аудио. В отличие от инструкции по добавлению текста код по проигрыванию звука уже содержится в шаблоне примера. Нужно только. . .
Установка Android SDK, NDK, JDK, CMake и т.д.
8Observer8 25.01.2026
Содержание блога Перейдите по ссылке: https:/ / developer. android. com/ studio и в самом низу страницы кликните по архиву "commandlinetools-win-xxxxxx_latest. zip" Извлеките архив и вы увидите. . .
Вывод текста со шрифтом TTF на Android с помощью библиотеки SDL3_ttf
8Observer8 25.01.2026
Содержание блога Если у вас не установлены Android SDK, NDK, JDK, и т. д. то сделайте это по следующей инструкции: Установка Android SDK, NDK, JDK, CMake и т. д. Сборка примера Скачайте. . .
Использование SDL3-callbacks вместо функции main() на Android, Desktop и WebAssembly
8Observer8 24.01.2026
Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .
моя боль
iceja 24.01.2026
Выложила интерполяцию кубическими сплайнами www. iceja. net REST сервисы временно не работают, только через Web. Написала за 56 рабочих часов этот сайт с нуля. При помощи perplexity. ai PRO , при. . .
Модель сукцессии микоризы
anaschu 24.01.2026
Решили писать научную статью с неким РОманом
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru