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

@Augusta Ada · Регистрация: 15.05.2014

Студворк — интернет-сервис помощи студентам

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

Вот мой код. В википедии написано, что ответ должен быть "18 446 744 073 709 551 615", а программа выводит "9 223 372 036 854 775 808", значит есть ошибка в вычислениях, но я пока не могу понять какая. А если просто умножить это число на 2, то выводит 0, значит нужное число просто не помещается в тип "unsigned long long". Подскажите как исправить, чтобы выводило правильный ответ.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <conio.h>
#include <math.h>
 
using namespace std;
 
int main()
{
    unsigned long long grains(1);
    const int n = 64;
 
    for (int i(0); i < n; i++)
    {
        grains += pow(2,i);
    }
 
    cout << grains;
 
    _getch();
    return(0);
}

@Renji · 26.10.2014, 16:01

Ошибка в вычислениях такая, что grains надо инициализировать нулем. И выучить что икс в степени ноль равно единица (соответственно, первая итерация цикла кладет одно зернышко). Алсо, у pow вроде как нет версии long long. Надо в double считать (2 поменять на 2.0).

@Augusta Ada · 26.10.2014, 16:15 **[ТС]**

Про то, что любое число в нулевой степени всегда равно единице, помню.

Пробовала менять тип на "long double", тогда выводит вроде как правильный ответ, но в экспоненциальном виде. Думала, что это можно как-то обойти.

@Renji · 26.10.2014, 17:35

Ну, обойти как раз можно.

C++
1
2
3
unsigned long long grains=0,pow=1;
for(int i=0;i<64;++i,pow*=2)
    grains+=pow;

@TheCalligrapher · 26.10.2014, 19:13

Сообщение от Renji

Алсо, у pow вроде как нет версии long long. Надо в double считать (2 поменять на 2.0).

Если реализация и предоставляет перегруженные версии функции 'pow' для целочисленных аргументов (С++11), то такая реализация обязана внутренне приводить любые целочисленные аргументы к типу 'double'. Поэтому никакого смысла делать такое приведение в пользовательском коде нет.

Добавлено через 38 минут

Сообщение от Augusta Ada

Пробовала менять тип на "long double", тогда выводит вроде как правильный ответ...

Если вы поменяете тип 'grains' на 'long double', но суммировать по прежнему будете с единицы, то ответ, понятное дело, у вас получится не правильный, а на единицу больше, чем надо.

Кстати, суммирование начиная с "лишней" единицы в 'grains' имеет свои интересные свойства, которые как раз таки могут быть полезны при использовании плавающих типов для представления этой суммы.

Если решать эту задачу "в лоб", т.е. суммировать начиная с нуля, то двоичное представление суммы будет становиться все шире и шире с каждой итерацией '1', '11', '111' и т.д. вплоть до набора единиц шириной в 64 бита. Плавающие типы 'float' и 'double' (в соотв. с IEE 754) не могут представить это целое значение точно, ибо ширина их мантиссы 24 и 53 бита соответственно. Представить это целое значение может только long float с его 64-битной мантиссой.

Однако если начинать суммирование с "лишней" единицы, то на каждом этапе сумма будет равна 2ⁿ. Мантисса такого числа состоит из одного единственного единичного бита и, поэтому, такое число представляется точно абсолютно любым плавающим типом, включая 'float'.

Пользуясь этим приемом вы в результате можете правильно решить задачу даже в рамках несчастного 32-битного типа 'float', при этом помня, что результат получается на единицу больше, чем надо: http://ideone.com/QSI7Y2

@Augusta Ada · 26.10.2014, 19:14 **[ТС]**

Сообщение от Renji

Ну, обойти как раз можно.

C++
1
2
3
unsigned long long grains=0,pow=1;
for(int i=0;i<64;++i,pow*=2)
    grains+=pow;

Спасибо! Решение таким образом помогло

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <conio.h>
 
using namespace std;
 
int main()
{
    unsigned long long sum(1), grains(1);
    const int n = 64;
 
    for (int i(0); i < n; i++)
    {
        grains *= 2;
        sum += grains;
    }
 
    cout << sum;
 
    _getch();
    return(0);
}

@TheCalligrapher · 26.10.2014, 20:40

Сообщение от Augusta Ada

Спасибо! Решение таким образом помогло

Ваше последнее решение арифметически неправильно и "работает" лишь по чистой машинно-зависимой случайности.

Вы начинаете суммирование с 1 в 'sum' и затем в цикле прибавляете 2, 4, 8 и т.д. вплоть до 2⁶⁴. Разумеется, это неправильно, ибо суммировать вы должны только до 2⁶³. Ваш код на самом деле фактически пытается вычислить, сколько зерен будет на 65-клеточной "шахматной доске".

Ваш ответ совпал с правильным только потому, что когда вы вычисляли 2⁶⁴ (т.е. умножали последнее значение 'grains' на 2) произошло беззнаковое арифметическое переполнение в рамках 64-битного целого типа (unsigned long long), результат которого оказался равен нулю. Т.е. на последней итерации цикла вы прибавляете в вашу сумму лишний бессмысленный ноль.

При таком способе вычисления (с единицы), вам надо делать только 63 итерации, а не 64. Либо убавьте 'n', либо начинайте итерации c 'i = 1'.

P.S. Воспользовавшись типом '__uint128_t' в gcc мы может посмотреть, что же именно ваш код вычисляет: http://coliru.stacked-crooked.... 7744f8b5d9 Как видите, на правильный ответ это совсем не похоже.

Добавлено через 5 минут

Сообщение от TheCalligrapher

...Плавающие типы 'float' и 'double' (в соотв. с IEE 754) не могут представить это целое значение точно, ибо ширина их мантиссы 24 и 53 бита соответственно. Представить это целое значение может только long float с его 64-битной мантиссой...

Под long float имелся в виду тип 'long double'

@Haklag · 26.10.2014, 20:45

вот поизящнее код

C++
1
2
3
4
5
6
7
8
9
10
11
int main(void)
{
    unsigned long long sum(0);
    char i = 0;
    
    while(i++!=64)
        sum += 1<<i;
    std::cout << sum;
    return 0;
}
}

@TheCalligrapher · 26.10.2014, 22:21

Сообщение от Haklag

вот поизящнее код

Ваш "поизящнее код" - это один из редких примеров того, как программа, содержащая несколько грубейших ошибок, тем не менее умудряется "попасть" в правильный ответ

Во-первых, литерал '1' в языке С++ имеет знаковый тип 'int'. Поэтому выражение '1 << i' будет вычисляться в рамках знакового типа 'int' и, разумеется, радостно переполнится, когда 'i' превысит ширину типа 'int' (на самом деле - приводит к неопределенному поведению). Ширина 'int' не фиксирована спецификацией языка, но на большинстве платформ равна 32.

Поэтому если вы внимательно посмотрите, что суммирует ваша программа (т.е. значения выражения '1 << i'), то суммирует она вот что (подразумевая 32-битный int):

1. Сначала к сумме добавляются значения 2, 4, 6 ... 2³⁰ (Не понимаю, почему вы решили начать с 2)

2. Когда i становится равно 31. поведение программы не определено. Формально, в этом месте ваша программа накрылась медным тазом. В реальности же на платформе x86 выражение '1 << 31' порождает значение '-2147483648'. Когда вы приплюсовываете это значение к беззнаковой переменной 'sum' типа 'unsigned long long' это значение трансформируется в страшное '18446744071562067968' ('0xFFFFFFFF80000000'), которое вы прибавляете в сумму.

3. Язык С++ запрещает выполнять сдвиг на ширину, большую или равную битовой ширине типа (неопределенное поведение), т.е. чему будет равно '1 << 32' и т.д. никто не знает. Но на платформе x86 величина 32-битового сдвига рассматривается по модулю 32, т.е. '1 << 32' эквивалентно '1 << 0', '1 << 33' это '1 << 1' и т.д. Таким образом вы опять прибавляете к сумме последовательность слагаемых: 1, 2, 4, 6 ... 2³⁰ и затем снова это инфернальное значение '18446744071562067968' (это '1 << 63')

4. Ну и под занавес вы добавляете в сумму '1 << 64', т.е. просто 1.

Как видите, вычисления были произведены бессмысленные. Однако так сложилось, то вклад в сумму вот этих двух страшных слагаемых со значением '0xFFFFFFFF80000000' аккуратно компенсировал ошибочность всех остальных слагаемых и ответ получился "правильный"

Это можно детально объяснить, но тратить на это время нет смысла.

Чтобы ваш код работал правильно, сдвиг следует записывать как '1ull << i'. И суммирование начинать с 1, а не с 2. И итерировать до 63, а не до 64.

@Augusta Ada · 27.10.2014, 02:03 **[ТС]**

Сообщение от TheCalligrapher

Ваше последнее решение арифметически неправильно и "работает" лишь по чистой машинно-зависимой случайности.

Свою ошибку поняла и исправила :)
Спасибо большое за такое замечание, сама бы я не увидела ошибки как раз таки из-за этой "машинно-зависимой случайности"

@hailmary · 05.11.2014, 09:34

http://www.youtube.com/watch?v=swzUNfbWdQs вот здесь в конце урока описывается эта задача, только я не пойму как она работает. Если у кого есть возможность распишите по-подробнее её. Заранее благодарен.

@TheCalligrapher · 05.11.2014, 11:30

Сообщение от hailmary

только я не пойму как она работает.

Она на самом деле содержит ту же ошибку, которую мы видели выше, только этот факт "замаскирован" через креативный выбор места для отладочной печати.

Автор кода в видео вычисляет сумму 1 + 2 + 4 + 8 + ... + 2⁶³ + 2⁶⁴, т.е. умудряется прибавить к ней лишнее слагаемое 2⁶⁴ на последней итерации. Это слагаемое, при вычислении в рамках 64-беззнакового типа, получается равным нулю и результат не портит. Так как печать результата в цикле там сделана до вычисления нового значения суммы, мы не замечаем, что на последней итерации сумма не меняется.

Код в видео почти работоспособен. Надо только исправить содержащуюся в нем ошибку, как я описывал в предыдущих ответах (см. сообщение #7)

@hailmary · 05.11.2014, 14:24

Я пока ещё слишком далёк от с++, чтоб такие ошибки искать. У меня вопрос попроще. Как происходит сложение во втором цикле? Если я напишу "j(1)" то будет просто умножение на 2 предыдущего результата, а сложения не будет. Почему?

Добавлено через 2 минуты

Добавлено через 2 часа 22 минуты
Всё, понял!

@uchin · 09.09.2015, 11:25

Добрый день. Не хотел создавать тему заново. Надеюсь меня услышат. Про ошибку я понял, но могли бы пояснить зачем в задаче про зёрна (вариант из урока http://www.youtube.com/watch?v=swzUNfbWdQs ) в конце тела второго for автор дописал pow = 1 ? Ведь в таком случае в начале тела (где pow *=2; ) каждый раз на 2 будет умножаться единица (раз её присвоили в конце). И уже на трёх первых клетках поля получется 5 зёрен а не 7?
Но программа отображает правельно..

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
//Фрагмент задачи
 
    const int N = 64; //kletok na saxmatnom pole
    unsigned long long rezultat = 1,pow = 1;
 
    for(int i(1); i <= 64; i++)
    {
        for(int j(0); j < i; j++)
            pow *=2;
        cout << "V summe na " << i << " kletke prixoditsa " << rezultat << " zeren!\n";
        rezultat += pow;
        pow = 1;
    }

Ilot · 09.09.2015, 12:02

uchin, потому, что руки нужно поотбивать этому любителю писать уроки:

C++
1
2
3
4
5
6
7
8
9
10
#include <iostream>
 
int main() {
    const int N = 64;
    unsigned long long rezultat = 0, pow = 1;
    for(int i = 0; i < N; ++i, pow <<= 1) {
        rezultat += pow;
        std::cout << "V summe na " << i + 1 << " kletke prixoditsa " << rezultat << " zeren!\n";
    }
}

Хотя в данном случае лучше воспользоваться формулой арифмитической прогрессии, либо можно стразу заметить, что ответ есть 0xFF FF FF FF FF FF FF FF.

@uchin · 09.09.2015, 23:34

Спасибо Ilot за грамотно составленный вариант решения. Но могли бы пояснить какое действие выполняет pow <<= 1 ? Не встречал до этого " <<= ".

И по поводу предыдущего моего поста. Хотелось бы узнать последователность выполнения циклов так как в моём понимание pow = 1 в конце должно портить ответы. Мне в той задаче важно понять принцип выполнения.

Добавлено через 9 часов 40 минут
Я не смогу перейти к массивам пока не пойму до конца циклы. Обьясните зелёному последовательность выполнения циклов хотя бы до 3 - 4 шахматной клетки. (14 пост) Был бы очень благодарен.

@Ferrari F1 · 09.09.2015, 23:44

Сообщение от uchin

какое действие выполняет pow <<= 1

побитовый сдвиг влево с присваиванием т.е. было число 00000001, к нему применили сдвиг влево на одну позицию: 00000001 <<= 1. Получилось число 00000010.
Отлично, теперь переведите исходное и получившееся числа в десятичную систему счисления и увидите, что произошло умножение на 2. С каждым последующим сдвигом на 1 позицию влево, число в pow умножается на 2

Croessmah · 10.09.2015, 04:05

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
#include <climits>
#include <cassert>
#include <cstdint>
 
 
 
 
 
int main() {
    unsigned N = 64;
    uint64_t result = ~0 ; //unsigned long long , -1
    unsigned int shift_result = CHAR_BIT * sizeof(result) - N ;
    assert ( shift_result >= 0 ) ;
    result >>= shift_result ;
    std::cout << result ;
}

Ilot · 10.09.2015, 07:26

Не по теме:

Croessmah, украл мою идею ]:->

Croessmah · 10.09.2015, 12:08

Не по теме:

Сообщение от Ilot

украл мою идею

я вредный, мне можно!

Новые блоги и статьи Все статьи Все блоги /
Модель микоризы: классовый агентный подход 3 anaschu 06.01.2026 aa0a7f55b50dd51c5ec569d2d10c54f6/ O1rJuneU_ls https:/ / vkvideo. ru/ video-115721503_456239114	Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ФедосеевПавел 06.01.2026 Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ВВЕДЕНИЕ Введу сокращения: аналоговый ПИД — ПИД регулятор с управляющим выходом в виде числа в диапазоне от 0% до. . .	Модель микоризы: классовый агентный подход 2 anaschu 06.01.2026 репозиторий https:/ / github. com/ shumilovas/ fungi ветка по-частям. коммит Create переделка под биомассу. txt вход sc, но sm считается внутри мицелия. кстати, обьем тоже должен там считаться. . . .	Расчёт токов в цепи постоянного тока igorrr37 05.01.2026 / * Дана цепь постоянного тока с сопротивлениями и напряжениями. Надо найти токи в ветвях. Программа составляет систему уравнений по 1 и 2 законам Кирхгофа и решает её. Последовательность действий:. . .
Новый CodeBlocs. Версия 25.03 palva 04.01.2026 Оказывается, недавно вышла новая версия CodeBlocks за номером 25. 03. Когда-то давно я возился с только что вышедшей тогда версией 20. 03. С тех пор я давно снёс всё с компьютера и забыл. Теперь. . .	Модель микоризы: классовый агентный подход anaschu 02.01.2026 Раньше это было два гриба и бактерия. Теперь три гриба, растение. И на уровне агентов добавится между грибами или бактериями взаимодействий. До того я пробовал подход через многомерные массивы,. . .	Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Programma_Boinc 28.12.2025 Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Налог на собак: https:/ / ********/ gallery/ V06K53e Финансовый отчет в Excel: https:/ / ********/ gallery/ bKBkQFf Пост отсюда. . .	Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США. Programma_Boinc 26.12.2025 Нашел на реддите интересную статью под названием Anyone know where to get a free Desktop or Laptop? Ниже её машинный перевод. После долгих разбирательств я наконец-то вернула себе. . .

@Renji 2784 / 1937 / 570 Регистрация: 05.06.2014 Сообщений: 5,602
	26.10.2014, 16:01
	Ошибка в вычислениях такая, что grains надо инициализировать нулем. И выучить что икс в степени ноль равно единица (соответственно, первая итерация цикла кладет одно зернышко). Алсо, у pow вроде как нет версии long long. Надо в double считать (2 поменять на 2.0). 0

@Augusta Ada 0 / 0 / 0 Регистрация: 15.05.2014 Сообщений: 4
	26.10.2014, 16:15 [ТС]
	Про то, что любое число в нулевой степени всегда равно единице, помню. Пробовала менять тип на "long double", тогда выводит вроде как правильный ответ, но в экспоненциальном виде. Думала, что это можно как-то обойти. 0

@hailmary 0 / 0 / 0 Регистрация: 05.11.2014 Сообщений: 4
	05.11.2014, 09:34
	http://www.youtube.com/watch?v=swzUNfbWdQs вот здесь в конце урока описывается эта задача, только я не пойму как она работает. Если у кого есть возможность распишите по-подробнее её. Заранее благодарен. 0

@hailmary 0 / 0 / 0 Регистрация: 05.11.2014 Сообщений: 4
	05.11.2014, 14:24
	Я пока ещё слишком далёк от с++, чтоб такие ошибки искать. У меня вопрос попроще. Как происходит сложение во втором цикле? Если я напишу "j(1)" то будет просто умножение на 2 предыдущего результата, а сложения не будет. Почему? Добавлено через 2 минуты Добавлено через 2 часа 22 минуты Всё, понял! 0

@uchin 0 / 0 / 0 Регистрация: 09.09.2015 Сообщений: 7
	09.09.2015, 23:34
	Спасибо Ilot за грамотно составленный вариант решения. Но могли бы пояснить какое действие выполняет pow <<= 1 ? Не встречал до этого " <<= ". И по поводу предыдущего моего поста. Хотелось бы узнать последователность выполнения циклов так как в моём понимание pow = 1 в конце должно портить ответы. Мне в той задаче важно понять принцип выполнения. Добавлено через 9 часов 40 минут Я не смогу перейти к массивам пока не пойму до конца циклы. Обьясните зелёному последовательность выполнения циклов хотя бы до 3 - 4 шахматной клетки. (14 пост) Был бы очень благодарен. 0

Ilot
	10.09.2015, 07:26
	Не по теме: Croessmah, украл мою идею ]:-> 0