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 ГОД

Один, два, три... много!

Андрей КОВАЛЕНКО uant@ukr.net

Именно так, если верить хрестоматиям, считали наши далекие предки. Туго было с устным счетом у праотцев. К счастью, прогрессивное человечество изобрело компьютер, а предприимчивый Билл Гейтс создал горячо всеми любимую операционную систему Windows, в состав которой издавна входила программа calc.exe, умеющая складывать, умножать, брать логарифм и (это существенно для нашей статьи!) считать факториал числа. Так что навык устного счета скоро станет ненужным, и будет забавным атавизмом вроде умения работать с логарифмической линейкой (с помощью которой, кстати, Королев рассчитывал свои ракеты) или занятий физкультурой (есть ведь жиросжигатели и пояса для похудения, которые вам доставят на дом).

Однако даже гениальный виндовый калькулятор зайдет в тупик, если вы попросите его посчитать факториал от числа, большего 29. Вернее, вы зайдете в тупик, а он как всегда выкрутится, показав, что 50! = 3.0414…e+64. (Напомним на всякий случай: n!=1*2*3*…*n.) Итак, число 50! содержит шестьдесят пять цифр, а калькулятьор покажет вам только первые 32 из них.

А как быть, если вам необходимо узнать, сколько цифр содержится в числе 1000!? А сколько среди этих цифр нулей? А единиц? Мы сейчас задаем вопросы, на которые не Евклид, ни Лагранж, ни гений вычислений Эйлер при всем желании не смогли бы дать ответа (впрочем, насчет последнего мы ручаться не станем — уж очень силен был дядька в счете :-)). А вы сможете — если, конечно, у вас хватит терпения дочитать эту статью.

Может возникнуть встречный вопрос — а кому оно надо, это количество цифр в огромных числах? Ну, что вы из этого количества шубу не сошьете, это точно, но зато попробуете свои силы в решении пусть не очень сложной, но нетривиальной задачи.

Задача

Итак, позвольте вступление на этом завершить и приступить непосредственно к постановке задачи, которая будет звучать так: вычислить факториал числа 1000, т.е. найти 1000!=1*2*3*…*999*1000.

Вычисление факториала — задача совсем несложная, и ее решение прямо следует из определения. Вот реализация для Паскаля (или Delphi):

Напомним, что 0!=1 по определению, и наша функция fact это учитывает. Более компактную (и более красивую) реализацию можно привести в пример, использовав рекурсию. Вот образчик текста на C:

Но оба метода не годятся для решения нашей задачи, и дело тут не в алгоритмах (они абсолютно корректны), а в аппаратных средствах компьютера. Для хранения длинного целого (в Паскале —longint, в C —long) в системах семейства x86 используется четыре байта, и максимальное целое, представимое таким образом, равно 4 294 967 295, да и то при условии, что используются беззнаковые целые, как во втором примере. А значение 13! превышает 6 миллиардов, так что функция fact(13) в лучшем случае вызовет ошибку выполнения, а в худшем даст неправильный ответ. Почему первый случай более предпочтителен? Да потому что отсутствие информации лучше любой дезинформации, не верите — спросите любого шпиона :-).

Итак, классический алгоритм вычисления факториала нам не подходит. Вернее, не подходит тип целого, предоставляемого системой. Слишком мал! Аналогично нам не подходят типы с плавающей точкой, хоть float, хоть double, хоть long double. Точность этих типов не превышает 16 значащих цифр, а верхний предел значений типа double — 10^308 (десять в степени 308). Правда, в Delphi поддерживается еще десятибайтовый тип extended, верхний предел которого — порядка 10^4932, но мантисса (значащие цифры) имеет максимальную длину 20, а мы-то хотим увидеть все цифры заветного числа 1000!, а не первые двадцать!

Уже пора задавать вечный вопрос: что делать? Ответ очевиден — создавать свой целочисленный тип данных! В самом деле, что такое целое десятичное число? Это последовательность цифр. А как можно представить последовательность цифр? Ну конечно же, массивом.

Создаем собственный числовой тип

Итак, мы введем свой числовой тип данных, который в памяти компьютера будет представляться массивом символов (цифр). Естественно, нам придется самим определять арифметические операции над экземплярами этого типа. Сначала определим сложение для двух чисел, потом — умножение, а с помощью операции умножения вычислим факториал.

Нашу программу будем писать на Delphi. Вообще говоря, для поставленной задачи больше подошел бы C++ с его мощным механизмом переопределения операторов, но учитывая, что среди читателей МК наверняка много начинающих программистов, для которых С++ пока еще кажется сложным, остановим свой выбор на простом в понимании и достаточно выразительном Delphi.

Итак, первое, что мы сделаем, создав новый проект large, это добавим в него модуль uCore.pas, который будет содержать всю вычислительную функциональность нашей программы. Для тех, кто любит заглядывать в конец задачника до решения задачи, сообщаем адрес, по которому находится архив с проектом large: http://uant.narod.ru/misc/pro/large1.rar. Чтобы скомпилировать и выполнить этот проект, нужна версия Delphi не ниже 6.

Сразу встает вопрос: какой длины должен быть массив, в котором будут храниться наши «большие числа»? В идеале, программа должна задавать размер массива динамически, в зависимости от длины чисел, с которыми мы собираемся производить операции. Например, если мы хотим умножить число порядка 10^120 на число порядка 10^98, ясно, что под результат надо отвести 120+98+1=219 знаков. Почему на единицу больше, чем просто сумма порядков (218)? Потому что произведение может увеличить количество разрядов на 1. Например, 10*10=100 (3 цифры), а 90*90=8100 (4 цифры).

Однако динамическое задание длины массивов усложняет программу, не внося в нее принципиальных изменений — по крайней мере, это актуально для нашего примера. Поэтому в нашей программе мы будем использовать массивы фиксированной длины. Итак, какой длины взять массив? Очевидно, число 1000! не может превышать 1000^1000=10^3000, следовательно, массива длиной 3000 байт будет достаточно. Итак, число, которое мы ищем, не превышает десять в степени три тысячи. Забегая вперед, скажем, что оно и не намного меньше этого числа, всего лишь на каких-то :-) 442 порядка. Десять в трехтысячной степени! Вас это число не впечатляет? Тогда, может быть, вам будет интересно узнать, что число атомов во Вселенной учеными оценивается порядка 10^100. Все равно не впечатляет? Вас трудно чем-то удивить… разве что, может быть, Биллом Гейтсом, носящим майку с изображением пингвина :-).

Итак, объявляем константу, задающую длину массива, и новый тип, который описывает этот массив:

Для удобства, наши большие числа будем представлять экземплярами класса TLargeNum, в котором будут приватные (private) переменные-члены Len (длина) и Value (значение):

В переменной Len будет храниться текущая длина нашего большого числа (будем называть их также БЧ), а в массиве Value — цифры числа. Например, если переменная (экземпляр) LargeNum1 представляет число 27453, то LargeNum.Len равен 5, а массив LargeNum1.Value — (3, 5, 4, 7, 2, …) Обратите внимание: цифры в массиве записываются в обратной последовательности.

Класс TLargeNum содержит два конструктора Create. Один из них вызывается для инициализации создаваемого экземпляра целым числом, а второй — объектом типа TLargeNum. Вот их реализации:

Методы AssignNumber (присвоить значение) описаны ниже. Обратите внимание, что некоторые из методов нашего класса объявлены как перегружаемые (overload), что позволяет унифицировать работу с нашими БЧ. Например, для прибавления к данному БЧ всегда используется метод Add, аргументом которого может быть целое, БЧ или строка, в зависимости от того, как мы представляем второе слагаемое — в виде целого, другого БЧ или строкового представления числа. Например:

Метод Clear обнуляет БЧ:

Чтобы присваивать нашим «большим числам» реальные числовые значения, определим метод AssignNumber (присвоить число):

Функция CharToByte переводит символ в строку и сложностей не вызывает:

Функция IsDigit(c: char) возвращает true, если c — цифра, и false в противном случае:

Метод-функция GetDigit возвращает i-ю цифру нашего БЧ:

Для вывода БЧ на экран неплохо иметь возможность конвертировать БЧ в строку:

Функция ByteToChar переводит байт в его символьное представление:

Методы TLargeNum.AssignNumber(n: string) и TLargeNum.AssignNumber(n: TLargeNum) реализуются аналогично TLargeNum.AssignNumber(n:integer): для первого — символы строки n преобразуются в цифры и копируются в массив Value, а во втором — массив n.Value копируется в массив Self.Value. Безусловно, написание этих методов не вызовет у вас трудностей, а у кого вызовет — посмотрите исходники в упомянутом zip-архиве.

Продолжение следует

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






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

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

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





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