: : и при виде задачи первая мысль была:
: : "Как её решить?", а не "Нафига это делать?".
: : Один из нас притащил эту функцию, и сказал,
: : что по слухам она какая-то необычная.
: : Разумеется, никто не поверил - что за функция,
: : которая всего-то и может прибавлять единичку
: : к аргументу? Ну, ещё сама себя вызывает,
: : да пусть хоть обвызывается, на одних единицах
: : сильно не вырастешь. Тут же, на листе бумаги
: : было подсчитано F(1,1), и, после некоторого
: : геморроя - F(2,2). Начали было считать F(3,3),
: : но быстро надоело и за дело взялся компьютер.
: : Он блестяще подтвердил наши ручные расчёты,
: : после чего получил задание посчитать F(10,10).
: : Эх, знали бы мы тогда с чем связались!
: : Сначала был stack overflow, и счётчик глубины
: : рекурсии подтвердил, что функция "уходит в себя"
: : по самое нехочу. К слову, стандартный размер
: : стека тогда был 4K, а 20 мегов можно было найти
: : разве что на винчестере. Завели массив вроде
: : long[10][1000], как раз по размеру сегмента,
: : для хранения промежуточных результатов,
: : и немедленно повисли, так как индекс мгновенно
: : выскочил за границу. Прикрутили библиотеку
: : для работы с массивами неограниченной длины,
: : (кстати, один из моих первых опытов на C :),
: : и опять вылетели, на этот раз по out of memory,
: : так как неограниченной памяти у нас не было.
: : Не сдались, заменили вызовы F для тривиальных
: : случаев (вроде (1,n)) на аналитические выражения,
: : но тут выяснилось, что переменные переполняются,
: : после чего пришлось отступить. Стало ясно,
: : что компьютер здесь нам не помощник, это скорее мы
: : тщетно пытаемся ему помочь. Тогда, от безысходност,
: : были выведены формулы для F(3,n) и даже для F(4,n),
: : и мы поняли, наконец, КАКАЯ бездна разверзлась впереди.
: : Уже для записи F(4,n) пришлось использовать новоизобретенную
: : функцию P(n)=2^(n^(n...^n)) n раз. А от том, чтобы
: : сохранить все эти дурацкие тройки, пятёрки и семёрки
: : в качестве коэффицентов для F(5,n) и речи не было.
: : Даже если их все выбросить нафиг, и оставить лишь "ядро",
: : которое в основном определяет характер роста, воображения
: : хватало разве чтобы представить себе внешний вид F(5,n).
: : Это чем-то напоминало исходную двойку в центре
: : многомерного пространства, которое увеличивало свою размерность
: : на каждом шаге, со всех сторон окруженную символами n,
: : возводящими друг друга в степень - кошмар полный.
: : А как же тогда выглядит F(6,n), если тут уместно слово "выглядит"?
: : И что творится дальше?
: : Не скрою - я был потрясён.
: : Какая красота! Какая мощь! Какое коварство!
: : Если представить себе значения F(m,n) на плоскости
: : и объединить их в последовательности при фиксированном m,
: : то получится набор функций F1(n), F2(n) и т. д.
: : По идее - это всё сёстры, ведь формула одна на всех,
: : лишь параметр меняется, а какая разница!
: : F0 ведёт себя тише воды, ниже травы - просто натуральные числа.
: : F1 недалеко ушла - всего лишь на 2 больше соседки.
: : А вот F2 заметно резвее - скорость роста увеличилась вдвое.
: : И вдруг - бабах - F3 уже растёт экспоненциально.
: : Про F4 и говорить нечего, если с F3 ещё как-то можно работать,
: : то F4 переполнит любую переменную и любую память.
: : И ведь это только начало!
: : Функция F определена для любых положительных m и n,
: : следовательно, есть вполне конкретное натуральное число,
: : соответствующее, скажем, F(100,100). Я не могу выразить словами
... у нас уже есть число Драука (ну помните задачу про 17-ти значное число, у которого переставили двойку из последний позийии в первую), а теперь вот появилось число Плюса... хм...
что дальше?
| Про F - Plus , 01.12.2004 01:52 MSK |
