Именно так, если верить хрестоматиям, считали наши далекие предки. Туго было с устным счетом у праотцев. К счастью, прогрессивное человечество изобрело компьютер, а предприимчивый Билл Гейтс создал горячо всеми любимую операционную систему 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):
function fact(n: longint): longint; var tmp: longint; i: integer; begin tmp := 1; for i := 1 to n do tmp := tmp*i; fact := tmp; end;
Напомним, что 0!=1 по определению, и наша функция fact это учитывает. Более компактную (и более красивую) реализацию можно привести в пример, использовав рекурсию. Вот образчик текста на C:
unsigned long fact(unsigned long n) { if (n == 0) return 1; return n >= 1? n*fact(n-1) : 1; };
Но оба метода не годятся для решения нашей задачи, и дело тут не в алгоритмах (они абсолютно корректны), а в аппаратных средствах компьютера. Для хранения длинного целого (в Паскале —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. Все равно не впечатляет? Вас трудно чем-то удивить… разве что, может быть, Биллом Гейтсом, носящим майку с изображением пингвина :-).
Итак, объявляем константу, задающую длину массива, и новый тип, который описывает этот массив:
const _maxlen = 3000; {длина массива} type TLargeArr = array[1.._maxlen] of byte; {массив из байтов}
Для удобства, наши большие числа будем представлять экземплярами класса TLargeNum, в котором будут приватные (private) переменные-члены Len (длина) и Value (значение):
TLargeNum = class(TObject) // большое число — БЧ private Len: integer; // длина числа Value: TLargeArr; // массив символов-цифр public constructor Create(n: integer); overload; // создание с инициализацией числом constructor Create(n: TLargeNum); overload; // создание с инициализацией числом procedure Clear(); // обнулить procedure AssignNumber(n: integer); overload; procedure AssignNumber(n: TLargeNum); overload; procedure AssignNumber(n: string); overload; // присвоить значение function Add(n: TLargeNum):TLargeNum; overload; function Add(n: integer):TLargeNum; overload; // прибавить БЧ или целое function Sub(n: TLargeNum):TLargeNum; overload; function Sub(n: integer):TLargeNum; overload; // вычесть БЧ или целое function MulByDigit(n: byte):TLargeNum; // умножить на цифру function Mul(n: TLargeNum):TLargeNum; overload; function Mul(n: integer):TLargeNum; overload; // умножить на БЧ или целое function Fact(): TLargeNum; // вычислить факториал (ура!) function ShiftLeft(cnt: integer): TLargeNum; // сместить влево function ShiftRight(cnt: integer): TLargeNum; // сместить вправо function TruncZeroes(): TLargeNum; // отбросить нули function Equ(Num2: TLargeNum): boolean; overload; function Equ(Num2: integer): boolean; overload; // сравнение с БЧ или целым function GetDigit(apos: integer): byte; // получить цифру function ToString(): WideString; // перевести в строку function ToInteger(): integer; // перевести в целое function GetLen(): integer; // длина БЧ end;
В переменной Len будет храниться текущая длина нашего большого числа (будем называть их также БЧ), а в массиве Value — цифры числа. Например, если переменная (экземпляр) LargeNum1 представляет число 27453, то LargeNum.Len равен 5, а массив LargeNum1.Value — (3, 5, 4, 7, 2, …) Обратите внимание: цифры в массиве записываются в обратной последовательности.
Класс TLargeNum содержит два конструктора Create. Один из них вызывается для инициализации создаваемого экземпляра целым числом, а второй — объектом типа TLargeNum. Вот их реализации:
constructor TLargeNum.Create(n: TLargeNum); begin inherited Create(); // вызываем конструктор предка — TObject AssignNumber(n); // инициализируем БЧ’ом end; constructor TLargeNum.Create(n: integer); begin inherited Create(); // вызываем конструктор предка AssignNumber(n); // инициализируем целым end;
Методы AssignNumber (присвоить значение) описаны ниже. Обратите внимание, что некоторые из методов нашего класса объявлены как перегружаемые (overload), что позволяет унифицировать работу с нашими БЧ. Например, для прибавления к данному БЧ всегда используется метод Add, аргументом которого может быть целое, БЧ или строка, в зависимости от того, как мы представляем второе слагаемое — в виде целого, другого БЧ или строкового представления числа. Например:
MyNum1.AssignNumber(20); // MyNum1 = <20> Aonther.AssignNumber(’5’); // Antother = <5> MyNum1.Add(10); // MyNum1 = <30> MyNum1.Add(’23’); // MyNum1 = <53> MyNum1.Add(Another); // MyNum1 = <58>
Метод Clear обнуляет БЧ:
procedure TLargeNum.Clear; begin Len := 1; // число 0 имеет длину 1 FillChar(Value, _maxlen, 0); // заполняем массив нулями end;
Чтобы присваивать нашим «большим числам» реальные числовые значения, определим метод AssignNumber (присвоить число):
procedure TLargeNum.AssignNumber(n: integer); var st: string; i: integer; begin Self.Clear(); // обнуляем Str(n, st); // преобразуем n в строку Len := Length(st); for i := 1 to Len do Value[i] := CharToByte(st[Len + 1 -i]); end;
Функция CharToByte переводит символ в строку и сложностей не вызывает:
function CharToByte(c: char): byte; begin if (not IsDigit(c)) then raise Exception.Create('Wrong digit'); // Ошибка! Вызываем исключение Result := byte(c)-48; // 48 — это ASCII-код символа (0) end;
Функция IsDigit(c: char) возвращает true, если c — цифра, и false в противном случае:
function IsDigit(c: char): boolean; begin Result := (c >= '0') and (c <= '9'); end;
Метод-функция GetDigit возвращает i-ю цифру нашего БЧ:
function TLargeNum.GetDigit(apos: integer): byte; begin Result := (Value[apos]); end;
Для вывода БЧ на экран неплохо иметь возможность конвертировать БЧ в строку:
function TLargeNum.ToString(): WideString; var st: string; i: integer; begin SetLength(st, Len); //Установить длину строки for i := 1 to len do st[i] := ByteToChar(Value[Len + 1 — i]); Result := st; end;
Функция ByteToChar переводит байт в его символьное представление:
function ByteToChar(b: byte): char; begin Result := char(b + 48); end;
Методы TLargeNum.AssignNumber(n: string) и TLargeNum.AssignNumber(n: TLargeNum) реализуются аналогично TLargeNum.AssignNumber(n:integer): для первого — символы строки n преобразуются в цифры и копируются в массив Value, а во втором — массив n.Value копируется в массив Self.Value. Безусловно, написание этих методов не вызовет у вас трудностей, а у кого вызовет — посмотрите исходники в упомянутом zip-архиве.
Продолжение следует