Сколько таки зёрен?
Не одно поколение читателей слышало об этой классической задаче:
Говорят, что когда изобретатель шахмат продемонстрировал Великому Султану эту игру, тот был настолько впечатлён, что пообещал мудрецу исполнить любое его желание. И услышал он в ответ такую просьбу:
«Пусть на первую клетку шахматной доски положат 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 [12314 просмотров]