CFA LogoCFA Logo Computer
Новости Статьи Магазин Драйвера Контакты
Новости
RSS канал новостей
В конце марта компания ASRock анонсировала фирменную линейку графических ускорителей Phantom Gaming. ...
Компания Huawei продолжает заниматься расширением фирменной линейки смартфонов Y Series. Очередное ...
Компания Antec в своем очередном пресс-релизе анонсировала поставки фирменной серии блоков питания ...
Компания Thermalright отчиталась о готовности нового высокопроизводительного процессорного кулера ...
Компания Biostar сообщает в официальном пресс-релизе о готовности флагманской материнской платы ...
Самое интересное
Программаторы 25 SPI FLASH Адаптеры Optibay HDD Caddy Драйвера nVidia GeForce Драйвера AMD Radeon HD Игры на DVD Сравнение видеокарт Сравнение процессоров

АРХИВ СТАТЕЙ ЖУРНАЛА «МОЙ КОМПЬЮТЕР» ЗА 2003 ГОД

100!

Дмитрий ЕЛЬЧАНИНОВ

Мои школьные годы прошли в «эпоху микрокалькуляторов». И уже тогда среди моих сверстников считалось, что «уметь считать» сейчас вообще не нужно. Нажми на кнопку — получишь результат! Зачем зубрить «долбицу» умножения?! Кому нужно это сложение, вычитание, деление и умножение в столбик?!! Чего уж говорить о сегодняшних школьниках и студентах, ежедневно пользующихся компьютером. Но как это ни парадоксально, наиболее эффективную помощь компьютер может оказать именно тому, кто знает арифметику и умеет грамотно вычислять.

На занятиях по программированию я люблю давать своим ученикам две задачи, решение которых показывает, что умение программировать — это не столько знание языка, сколько умение им пользоваться.

Первая задача довольно широко известна (в узких кругах :-)): составить программу, меняющую местами значения целочисленных переменных a и b. Самые быстрые тут же строчат:

Но самые внимательные сразу же замечают, что это неправильно, т.к. теряется значение переменной a. «А его сохранить где-то надо», — предлагают самые находчивые. Так появляется переменная c и код:

Все, задача решена! Но тут я начинаю «вставлять палки в колеса»: а теперь решите эту задачу без использования дополнительной переменной! Вслед за тем обычно происходит примерно такой диалог между преподавателем (П) и учениками (У):

У: А где нам хранить значение переменной a?!

П: Нигде…

У: Но мы же его потеряем!!!

П: А вы попробуйте его так потерять, чтобы его можно было восстановить.

У: Как это?…

П: Арифметически.

На этом разговоры прекращаются, и по истечению некоторого времени рождается такое решение:

Мораль: арифметика нужна — арифметика важна!

Вторая задача формулируется очень просто: вычислить факториал числа 100. После напоминания, что факториалом числа n называется произведение n! = 123…(n–1)n, самые шустрые быстренько пишут:

Самые умные же понимают, что 100! — это ОЧЕНЬ большое число. Затем вспоминают, что самый широкий диапазон значений имеет целый тип Int64 (-263…263-1). Наконец, пытаются сравнить 100! со степенью числа 2, получают результат:

и говорят, что 100! вычислить невозможно.

Самые хитрые тихонько запускают стандартный Калькулятор Windows в инженерном режиме и выдают ответ

Самые пунктуальные возражают, что вместо точного результата компьютер выдал значение в нормализованной форме с потерей чуть ли не всех цифр! На что оптимисты говорят: но мы теперь знаем, что у числа 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.

Приступим к умножению. Начинаем с первой цифры числа-массива:

Здесь мы умножили 456 на 3 и прибавили из пустого «ума» 0. Получили r = 1368. Теперь нам надо записать 8 как элемент A[1], а 136 держать «в уме». Сначала поместим 136 «в ум»:

Здесь мы разделили 1368 на 10, из полученного 136.8 выделили целую часть 136.0 и округлили ее до целого числа r1 = 136.

Теперь запишем 8 как элемент A[1]:

Здесь мы умножили 136 на 10 и результат вычли из 1368. Получили A[1] = 8.

Все, первую цифру числа-массива мы обработали. Аналогично можно разобраться со второй и третьей цифрой числа-массива. Сначала запишем A[2] = 8 и держим «в уме» r1 = 104, а затем запишем A[3] = 0 и держим «в уме» r1 = 56.

Очевидно, что процесс умножения можно записать в виде цикла (напоминаю, что L=3):

Теперь понятно, что переменная L нам понадобилась для организации цикла. Но не только для этого. На данный момент у нас остался еще один «хвост» в виде числа r1 = 56, которое мы держим пока «в уме». Чтобы получить результат умножения также в виде числа-массива, мы должны записать 6 как элемент A[4], а — как элемент A[5].

Запишем сначала 6 как элемент A[4]. Для этого сперва увеличим значение переменной L, чтобы показать, что количество цифр в числе-массиве увеличилось:

Затем воспользуемся уже отработанным приемом выделения нужной цифры и ее записи в соответствующий элемент массива A:

В результате запишем A[4] = 6 и держим «в уме» r1 = 5.

Запись 5 как элемента A[5] производится аналогично. В результате «в уме» будем держать r1 = 0.

Заметим, что процесс размещения цифр в число-массив можно записать в виде цикла:

Теперь решение задачи вычисления 100! почти очевидно. Для хранения цифр заведем массив A : array [1..158] of integer. Все его элементы перед началом работы необходимо обнулить. Собственно код приведен ниже:

Маленький комментарий: первоначально в массиве находится число 1, состоящее из одной цифры, а внешний цикл отвечает за вычисление произведения 123…99100.

Естественно, используя описанный метод, можно получить факториалы чисел, значительно больших 100. Для этого необходимо увеличить размер массива и во внешнем цикле for заменить число 100 на число, факториал которого требуется найти. Например, если заменить 100 на 1000 и удлинить массив до 2568 элементов, то можно получить значение 1000!.

Вот, собственно, и все! В заключение необходимо сказать, что идея описанного метода взята из статьи Касаткина В. Н. «Сколько цифр в числе 100!?», опубликованной в 1988 году в №7 научно-популярного физико-математического журнала «Квант». Знакомство с этим журналом во многом определило мой дальнейший жизненный путь, за что, пользуясь предоставленной мне возможностью, я хочу выразить искреннюю благодарность и признательность его издателям и авторам.

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

P.S. Ответ на вторую задачу такой: 100! = 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000.

Рекомендуем ещё прочитать:






Данную страницу никто не комментировал. Вы можете стать первым.

Ваше имя:
Ваша почта:

RSS
Комментарий:
Введите символы или вычислите пример: *
captcha
Обновить





Хостинг на серверах в Украине, США и Германии. © sector.biz.ua 2006-2015 design by Vadim Popov