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

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

• Все журналы \ Номер 47/270 `2003 от 24.11.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-архиве.

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

Идёт загрузка...

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

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