Мои школьные годы прошли в «эпоху микрокалькуляторов». И уже тогда среди моих сверстников считалось, что «уметь считать» сейчас вообще не нужно. Нажми на кнопку — получишь результат! Зачем зубрить «долбицу» умножения?! Кому нужно это сложение, вычитание, деление и умножение в столбик?!! Чего уж говорить о сегодняшних школьниках и студентах, ежедневно пользующихся компьютером. Но как это ни парадоксально, наиболее эффективную помощь компьютер может оказать именно тому, кто знает арифметику и умеет грамотно вычислять.
На занятиях по программированию я люблю давать своим ученикам две задачи, решение которых показывает, что умение программировать — это не столько знание языка, сколько умение им пользоваться.
Первая задача довольно широко известна (в узких кругах :-)): составить программу, меняющую местами значения целочисленных переменных a и b. Самые быстрые тут же строчат:
a := b; b := a;
Но самые внимательные сразу же замечают, что это неправильно, т.к. теряется значение переменной a. «А его сохранить где-то надо», — предлагают самые находчивые. Так появляется переменная c и код:
c := a; a := b; b := c;
Все, задача решена! Но тут я начинаю «вставлять палки в колеса»: а теперь решите эту задачу без использования дополнительной переменной! Вслед за тем обычно происходит примерно такой диалог между преподавателем (П) и учениками (У):
У: А где нам хранить значение переменной a?!
П: Нигде…
У: Но мы же его потеряем!!!
П: А вы попробуйте его так потерять, чтобы его можно было восстановить.
У: Как это?…
П: Арифметически.
На этом разговоры прекращаются, и по истечению некоторого времени рождается такое решение:
a := a + b; b := a – b; a := a – b;
Мораль: арифметика нужна — арифметика важна!
Вторая задача формулируется очень просто: вычислить факториал числа 100. После напоминания, что факториалом числа n называется произведение n! = 123…(n–1)n, самые шустрые быстренько пишут:
n := 1; for i := 1 to 100 do n := n * i;
Самые умные же понимают, что 100! — это ОЧЕНЬ большое число. Затем вспоминают, что самый широкий диапазон значений имеет целый тип Int64 (-263…263-1). Наконец, пытаются сравнить 100! со степенью числа 2, получают результат:
100! = 123…99100 > 2100
и говорят, что 100! вычислить невозможно.
Самые хитрые тихонько запускают стандартный Калькулятор Windows в инженерном режиме и выдают ответ
100! = 9,332621544394415268169923885627e+157
Самые пунктуальные возражают, что вместо точного результата компьютер выдал значение в нормализованной форме с потерей чуть ли не всех цифр! На что оптимисты говорят: но мы теперь знаем, что у числа 100! имеется 158 цифр. «А толку», — вздыхают пессимисты, — «Все равно в диапазон не помещается…»
И тут самый гениальный выдает: зато в массив поместится!!!
Все! Идея сгенерирована!! Необходимо работать с числом как с массивом цифр!!!
И вот здесь нам пригодится давно подзабытое умение умножать два числа в столбик. Только не такое, к какому мы привыкли в школе, а чуть модифицированное. В чем заключается эта модификация, проще объяснить на примере умножения числа 123 на число 456.
Умножим 456 на 3, получим 1368, 8 записываем, а 136 держим «в уме». Потом 456 умножим на 2, получим 912, прибавим «из ума» 136, получим 1048, 8 записываем, 104 держим «в уме». Наконец, 456 умножим на 1, получим 456 , прибавим «из ума» 104, получим 560 и записываем его. Окончательный результат: 123456=56088.
Все! Можно программировать.
Первое, что нам необходимо сделать, это научиться умножать число, записанное в виде массива (будем называть его числом-массивом), на обычное число. Как это реализовать, разберем все на том же примере 123456. Для хранения числа 123 заведем массив A : array [1..5] of integer. В массиве именно пять элементов, чтобы мы могли в нем записать ответ — 56088.
Чтобы держать «в уме» число, заведем целочисленную переменную r1. Естественно, что сначала у нас «в уме» пусто, т.е. r1 := 0. Еще нам понадобится целочисленная переменная L для хранения количества цифр в числе-массиве. Зачем, станет понятно чуть ниже. В нашем примере L := 3. Наконец, для умножения цифры числа-массива на число заведем целочисленную переменную r.
Приступим к умножению. Начинаем с первой цифры числа-массива:
r := A[1] * 456 + r1;
Здесь мы умножили 456 на 3 и прибавили из пустого «ума» 0. Получили r = 1368. Теперь нам надо записать 8 как элемент A[1], а 136 держать «в уме». Сначала поместим 136 «в ум»:
r1 := Round(Int(r/10));
Здесь мы разделили 1368 на 10, из полученного 136.8 выделили целую часть 136.0 и округлили ее до целого числа r1 = 136.
Теперь запишем 8 как элемент A[1]:
A[1] := r — r1 * 10;
Здесь мы умножили 136 на 10 и результат вычли из 1368. Получили A[1] = 8.
Все, первую цифру числа-массива мы обработали. Аналогично можно разобраться со второй и третьей цифрой числа-массива. Сначала запишем A[2] = 8 и держим «в уме» r1 = 104, а затем запишем A[3] = 0 и держим «в уме» r1 = 56.
Очевидно, что процесс умножения можно записать в виде цикла (напоминаю, что L=3):
for j := 1 to L do begin r := A[j] * 456 + r1; r1 := Round(Int(r/10)); A[j] := r — r1 * 10; end;
Теперь понятно, что переменная L нам понадобилась для организации цикла. Но не только для этого. На данный момент у нас остался еще один «хвост» в виде числа r1 = 56, которое мы держим пока «в уме». Чтобы получить результат умножения также в виде числа-массива, мы должны записать 6 как элемент A[4], а 5 — как элемент A[5].
Запишем сначала 6 как элемент A[4]. Для этого сперва увеличим значение переменной L, чтобы показать, что количество цифр в числе-массиве увеличилось:
L := L + 1;
Затем воспользуемся уже отработанным приемом выделения нужной цифры и ее записи в соответствующий элемент массива A:
r := Round(Int(r1/10)); A[L] := r1 — r*10; r1 := r;
В результате запишем A[4] = 6 и держим «в уме» r1 = 5.
Запись 5 как элемента A[5] производится аналогично. В результате «в уме» будем держать r1 = 0.
Заметим, что процесс размещения цифр в число-массив можно записать в виде цикла:
while r1 <> 0 do begin L := L + 1; r := Round(Int(r1/10)); A[L] := r1 — r*10; r1 := r; end;
Теперь решение задачи вычисления 100! почти очевидно. Для хранения цифр заведем массив A : array [1..158] of integer. Все его элементы перед началом работы необходимо обнулить. Собственно код приведен ниже:
A[1] := 1; L := 1; for i := 1 to 100 do begin r1 := 0; for j := 1 to L do begin r := A[j] * i + r1; r1 := Round(Int(r/10)); A[j] := r — r1 * 10; end; while r1 <> 0 do begin L := L + 1; r := Round(Int(r1/10)); A[L] := r1 — r*10; r1 := r; end; end;
Маленький комментарий: первоначально в массиве находится число 1, состоящее из одной цифры, а внешний цикл отвечает за вычисление произведения 123…99100.
Естественно, используя описанный метод, можно получить факториалы чисел, значительно больших 100. Для этого необходимо увеличить размер массива и во внешнем цикле for заменить число 100 на число, факториал которого требуется найти. Например, если заменить 100 на 1000 и удлинить массив до 2568 элементов, то можно получить значение 1000!.
Вот, собственно, и все! В заключение необходимо сказать, что идея описанного метода взята из статьи Касаткина В. Н. «Сколько цифр в числе 100!?», опубликованной в 1988 году в №7 научно-популярного физико-математического журнала «Квант». Знакомство с этим журналом во многом определило мой дальнейший жизненный путь, за что, пользуясь предоставленной мне возможностью, я хочу выразить искреннюю благодарность и признательность его издателям и авторам.
Хочется надеется, что и нынешние юные читатели «Моего компьютера» смогут в будущем сказать такие же слова в адрес издателей и авторов нашего любимого еженедельника «Мой компьютер».
P.S. Ответ на вторую задачу такой: 100! = 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000.