Сколько таки зёрен?

Не одно поколение читателей слышало об этой классической задаче:

Говорят, что когда изобретатель шахмат продемонстрировал Великому Султану эту игру, тот был настолько впечатлён, что пообещал мудрецу исполнить любое его желание. И услышал он в ответ такую просьбу:
«Пусть на первую клетку шахматной доски положат 1 зерно, на вторую — 2, на третью — 4, и так далее, на каждую следующую вдвое больше, чем на предыдущую.»
Султан был удивлен таким скромным пожеланием, но пообещал его выполнить. Сколько зёрен должен был получить изобретатель?

В "Весёлых задачах" Перельмана эта задачка подробно разбирается и приводится точный ответ 18 446 744 073 709 551 515 (примерно 12000 кубических километров зерна :)

В состоянии ли точно вычислить это значение обычная "персоналка"? Ниже приведён скриншот расчёта в Mathcad 14/15, сделанного тремя способами:

• "прямое" вычисление через оператор суммы и формулу (нетрудно заметить, что ответ - общее количество зёрен - равен 264-1);
• вычисление с помощью подпрограммы-функции Sum;
• символьное оценивание суммы и формулы.

Количество зерён, полагающихся изобретателю шахмат - расчёт в MathCAD тремя способами (правильный ответ - способ 3)

Легко увидеть, что Mathcad ошибается и здесь при численном подходе, но правильно решает символьно. Хотя ответ отличается от Перельмана ровно на 100.

Какой из вариантов верен? Попробуем получить точный ответ на учебных C++ и Паскале. Вот программа на консольном С++:

#include <stdio.h>

void main () {
 double s=0,d=1;
 for (int i=0; i<64; i++) {
  s+=d; d*=2;
 }
 printf ("\n%.0lf",s);
}

Она выдала ответ 18 446 774 073 709 551 600, то есть, неправильно.

Консольный Паскаль с подключённой компиляцией "длинных" типов, увы, выдаст то же число, оказавшись в данном случае не точнее всех.

{$N+}
var s,d:extended;
 i:integer;
begin
 s:=0; d:=1;
 for i:=0 to 63 do begin
  s:=s+d; d:=d*2;
 end;
 writeln (d:30:0);
end.

А вот в Нигме легко получить правильный ответ 18 446 744 073 709 551 615. Так что ошибается таки Перельман... ну или наборщик :)

20.04.2013, 12:10 [12121 просмотр]