Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг 4.62/13: Рейтинг темы: голосов - 13, средняя оценка - 4.62
Augusta Ada
0 / 0 / 0
Регистрация: 15.05.2014
Сообщений: 4
1

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

26.10.2014, 15:58. Просмотров 2535. Ответов 21
Метки нет (Все метки)

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

Вот мой код. В википедии написано, что ответ должен быть "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);
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
26.10.2014, 15:58
Ответы с готовыми решениями:

"О шахматной доске и зернах"
&quot;О шахматной доске и зернх&quot;. Известная индийская легенда утверждает, что когда...

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

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

Числа на шахматной доске
В клетках шахматной доски находятся целые число. --- Определить в программе...

Числа на шахматной доске
В клетках шахматной доски находятся целые число. --- Определить в программе...

21
Renji
2105 / 1545 / 471
Регистрация: 05.06.2014
Сообщений: 4,484
26.10.2014, 16:01 2
Ошибка в вычислениях такая, что grains надо инициализировать нулем. И выучить что икс в степени ноль равно единица (соответственно, первая итерация цикла кладет одно зернышко). Алсо, у pow вроде как нет версии long long. Надо в double считать (2 поменять на 2.0).
0
Augusta Ada
0 / 0 / 0
Регистрация: 15.05.2014
Сообщений: 4
26.10.2014, 16:15  [ТС] 3
Про то, что любое число в нулевой степени всегда равно единице, помню.
Пробовала менять тип на "long double", тогда выводит вроде как правильный ответ, но в экспоненциальном виде. Думала, что это можно как-то обойти.
0
Renji
2105 / 1545 / 471
Регистрация: 05.06.2014
Сообщений: 4,484
26.10.2014, 17:35 4
Ну, обойти как раз можно.
C++
1
2
3
unsigned long long grains=0,pow=1;
for(int i=0;i<64;++i,pow*=2)
    grains+=pow;
1
TheCalligrapher
С чаем беда...
Эксперт CЭксперт С++
4772 / 2429 / 679
Регистрация: 18.10.2014
Сообщений: 4,148
26.10.2014, 19:13 5
Цитата Сообщение от 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-битной мантиссой.

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

Пользуясь этим приемом вы в результате можете правильно решить задачу даже в рамках несчастного 32-битного типа 'float', при этом помня, что результат получается на единицу больше, чем надо: http://ideone.com/QSI7Y2
2
Augusta Ada
0 / 0 / 0
Регистрация: 15.05.2014
Сообщений: 4
26.10.2014, 19:14  [ТС] 6
Цитата Сообщение от 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);
}
0
TheCalligrapher
С чаем беда...
Эксперт CЭксперт С++
4772 / 2429 / 679
Регистрация: 18.10.2014
Сообщений: 4,148
26.10.2014, 20:40 7
Цитата Сообщение от Augusta Ada Посмотреть сообщение
Спасибо! Решение таким образом помогло
Ваше последнее решение арифметически неправильно и "работает" лишь по чистой машинно-зависимой случайности.

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

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

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

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

Добавлено через 5 минут
Цитата Сообщение от TheCalligrapher Посмотреть сообщение
...Плавающие типы 'float' и 'double' (в соотв. с IEE 754) не могут представить это целое значение точно, ибо ширина их мантиссы 24 и 53 бита соответственно. Представить это целое значение может только long float с его 64-битной мантиссой...
Под long float имелся в виду тип 'long double'
1
Haklag
34 / 34 / 37
Регистрация: 21.06.2012
Сообщений: 150
Завершенные тесты: 2
26.10.2014, 20:45 8
вот поизящнее код
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;
}
}
0
TheCalligrapher
С чаем беда...
Эксперт CЭксперт С++
4772 / 2429 / 679
Регистрация: 18.10.2014
Сообщений: 4,148
26.10.2014, 22:21 9
Цитата Сообщение от Haklag Посмотреть сообщение
вот поизящнее код
Ваш "поизящнее код" - это один из редких примеров того, как программа, содержащая несколько грубейших ошибок, тем не менее умудряется "попасть" в правильный ответ

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

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

1. Сначала к сумме добавляются значения 2, 4, 6 ... 230 (Не понимаю, почему вы решили начать с 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 ... 230 и затем снова это инфернальное значение '18446744071562067968' (это '1 << 63')

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

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

Чтобы ваш код работал правильно, сдвиг следует записывать как '1ull << i'. И суммирование начинать с 1, а не с 2. И итерировать до 63, а не до 64.
3
Augusta Ada
0 / 0 / 0
Регистрация: 15.05.2014
Сообщений: 4
27.10.2014, 02:03  [ТС] 10
Цитата Сообщение от TheCalligrapher Посмотреть сообщение
Ваше последнее решение арифметически неправильно и "работает" лишь по чистой машинно-зависимой случайности.
Свою ошибку поняла и исправила :)
Спасибо большое за такое замечание, сама бы я не увидела ошибки как раз таки из-за этой "машинно-зависимой случайности"
0
hailmary
0 / 0 / 0
Регистрация: 05.11.2014
Сообщений: 4
05.11.2014, 09:34 11
http://www.youtube.com/watch?v=swzUNfbWdQs вот здесь в конце урока описывается эта задача, только я не пойму как она работает. Если у кого есть возможность распишите по-подробнее её. Заранее благодарен.
0
TheCalligrapher
С чаем беда...
Эксперт CЭксперт С++
4772 / 2429 / 679
Регистрация: 18.10.2014
Сообщений: 4,148
05.11.2014, 11:30 12
Цитата Сообщение от hailmary Посмотреть сообщение
только я не пойму как она работает.
Она на самом деле содержит ту же ошибку, которую мы видели выше, только этот факт "замаскирован" через креативный выбор места для отладочной печати.

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

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

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

Добавлено через 2 часа 22 минуты
Всё, понял!
0
uchin
0 / 0 / 0
Регистрация: 09.09.2015
Сообщений: 7
09.09.2015, 11:25 14
Добрый день. Не хотел создавать тему заново. Надеюсь меня услышат. Про ошибку я понял, но могли бы пояснить зачем в задаче про зёрна (вариант из урока 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;
    }
0
Ilot
Эксперт С++
1831 / 1189 / 342
Регистрация: 16.05.2013
Сообщений: 3,139
Записей в блоге: 5
Завершенные тесты: 1
09.09.2015, 12:02 15
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.
0
uchin
0 / 0 / 0
Регистрация: 09.09.2015
Сообщений: 7
09.09.2015, 23:34 16
Спасибо Ilot за грамотно составленный вариант решения. Но могли бы пояснить какое действие выполняет pow <<= 1 ? Не встречал до этого " <<= ".

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

Добавлено через 9 часов 40 минут
Я не смогу перейти к массивам пока не пойму до конца циклы. Обьясните зелёному последовательность выполнения циклов хотя бы до 3 - 4 шахматной клетки. (14 пост) Был бы очень благодарен.
0
Ferrari F1
791 / 521 / 156
Регистрация: 27.01.2015
Сообщений: 3,025
Записей в блоге: 1
Завершенные тесты: 1
09.09.2015, 23:44 17
Цитата Сообщение от uchin Посмотреть сообщение
какое действие выполняет pow <<= 1
побитовый сдвиг влево с присваиванием т.е. было число 00000001, к нему применили сдвиг влево на одну позицию: 00000001 <<= 1. Получилось число 00000010.
Отлично, теперь переведите исходное и получившееся числа в десятичную систему счисления и увидите, что произошло умножение на 2. С каждым последующим сдвигом на 1 позицию влево, число в pow умножается на 2
0
Croessmah
++Ͻ
14630 / 8379 / 1582
Регистрация: 27.09.2012
Сообщений: 20,583
Записей в блоге: 2
Завершенные тесты: 1
10.09.2015, 04:05 18
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 ;
}
0
Ilot
10.09.2015, 07:26
  #19

Не по теме:

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

0
Croessmah
10.09.2015, 12:08     Задача о зернах на шахматной доске
  #20

Не по теме:

Цитата Сообщение от Ilot Посмотреть сообщение
украл мою идею
я вредный, мне можно!

0
10.09.2015, 12:08
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
10.09.2015, 12:08
Привет! Вот еще темы с ответами:

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

Расстановка ферзей на шахматной доске
Найти на кубической доске всевозможные расстановки 15 ферзей так, чтобы они не...

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


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

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Опции темы

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