Умова
Написати програму, яка за значенням N! визначатиме значення N (1<=N<=2000).
Вхідні дані # 5040
Вихідні дані # 7
Вхідні дані # 5040
Вихідні дані # 7
Розв'язання
Вчитаємося ще раз в умову задачі: задано достатньо велике ціле число F (наскільки велике - поки що невідомо), яке дорівнює факторіалу деякого цілого числа N (вже не такого великого, N в діапазоні 1 - 2000). Тобто маємо задачу, обернену до задачі обчислення факторіала, яку розв'язують у шкільному курсі інформатики. Що ж до нашої задачі, то її розв'язання можливе лише із застосуванням інших методів - так званої "довгої арифметики".
Задача на перший погляд здається нескладною. Алгоритм повинен забезпечити послідовне обчислення факторіалів цілих чисел до отримання потрібного результату. Він може бути таким:
- прочитати значення N! з файла в змінну F;
- почати змінну N з нуля;
- збільшити значення N на одиницю та обчислити N!;
- якщо N! не дорівнює F, то виконати пункт 3, інакше вивести N.
Розглянемо програму, яка реалізує цей алгоритм. Щодо обчислення N!, звичайно, можна створити відповідну функцію, в такому випадку для обчислення кожного факторіала буде виконуватись N множень, а вже обчислені на якомусь етапі факторіали будуть обчислюватись ще і ще раз для більших значень N. Кількість операцій такого алгоритму буде мати порядок
N2 , що не є надто ресурсоємним для сучасної комп'ютерної техніки, але ознакою добротного стилю програмування є саме економія ресурсів програми.
Тому використовуємо рекурентну формулу N!=N*(N-1)! й обчислюємо N! за одну операцію множення. Значення поточного факторіалу буде зберігатися у змінній R, у яку послідовно записуватимемо значення 1!, 2!, 3!, .... поки не з'явиться потрібний результат.
var
N:word; шукане ціле число
F:longint; потрібне значення N!
R:longint; поточне значення N!
Fi:text; файлова змінна
begin
assign(Fi, 'input.txt');
reset(Fi);
readln(Fi,F); читаємо значення F з файлу
close(Fi);
N:=0;
R:=1; ініціалізація N та R
repeat
inc(N); збільшити N на одиницю
R:=R*N; обчислити N!
until R=F; перевірка закінчення циклу
writeln(N); виведення знайденого значення N
end.
Тест, наведений в умові задачі, програма проходить відмінно. Також маємо абсолютно нормальні результати для всіх значень факторіалів чисел від 1 до 12, тобто алгоритм розв'язання задачі складений правильно, і програма, якщо не зважати на умову N<=2000, працює правильно.
Цікаво, як буде вести себе програма при більших значеннях N? Пропонуємо у файлі даних число 6227020800, яке дорівнює факторіалу 13, - замість результату маємо повідомлення про хибний числовий формат. Справді, найбільше значення, яке підтримує стандартний LongInt, дорівнює 2147483647, і тому Паскаль відмовляється читати в змінних типу LongInt більші значення.
Вихід із цього становища може бути достатньо простим: замінити в програмі тип значень N та R на real. Тепер програма працює нормально для всіх факторіалів чисел до 27 включно. Повідомлення про переповнення під час операції з дійсним числом виникає за спроби обробити 28! Справа в тому, що стандартний тип real коректно обслуговує 11-12 цифр мантиси дійсного числа. Тому, за відомими лише програмістам фірми Borland причинами, внутрішні процедури мови програмування Паскаль читають з файлу записане там натуральне число 304888344611713860501504000000 як 304888344611629183000000000000, а обчислення цього значення факторіала 28! дає іншу величину:
304888344611917414000000000000.
Значення F та R не збігаються і алгоритм зациклюється, тобто обчислення продовжується, виходить за межі стандартного типу real і Паскаль повідомляє про переповнення.
Як обійти цю проблему? Можна запропонувати порівнювати значення U та R наближено, aбо порівнювати не самі числа, а їх порядки (порядок дійсного числа можна знайти, обчисливши його десятковий логарифм).
Виправляючи рядок умови виходу з циклу на until Abs(Ln(R)-Ln(F))<0.01, матимемо позитивний результат для факторіалів чисел 28, 29, 30, 31, 32, 33. Якщо прочитати з файлу число 34! (найбільше значення стандартного типу real 1.7е38<34!), отримаємо знайоме повідомлення про переповнення під час виконання операції з дійсним числом.
У таблиці дійсних типів вибираємо найбільший можливий тип Extended (найбільше значення - 1.1е4932) і вважаємо, що тепер успіх вже дуже близько. Нова версія програми читається так:
var
N:word;
F,R:extended;
Fi:text;
begin
assign (Fi, 'input.txt');
reset(Fi);
readln(Fi,F);
close(Fi);
N:=0;
R:=1;
repeat
inc(N);
R:=R*N;
until Ln(R)/Ln(10)=Ln(F)/Ln(10);
writeln(N);
end.
Ця програма ставить своєрідний рекорд і працює нормально для факторіалів чисел від 1 до 49. Програма сходить з дистанції при N=50. Виявляється, процедура readln(X:extended) читає з файлу не більше ніж 64 знаки, а наступні цифри просто ігноруються.
Число 50!, яке має 65 цифр, читається в змінну як 3.04140932017134е+0063, тому знову маємо зациклювання і повідомлення про переповнення під час операції з дійсним числом.
Настав час зробити деякі висновки: запропонований алгоритм розв'язування задачі працює правильно, але всі спроби реалізувати його на стандартних числових типах мови Паскаль не принесли потрібного результату. Програма не працює навіть для 50!, не кажучи вже про 2000!. Але витрачені зусилля не були марними. З'явився досвід, який підказує, що потрібно обійти стандартний числовий тип.
Для цього необхідно створити свій числовий тип даних та написати відповідні процедури опрацювання змінних такого типу. Достатньо відомим в інформатиці є метод емуляції так званої 'довгої арифметики', коли невід'ємне ціле число розглядається у програмі у вигляді масиву своїх цифр. Вводимо свій тип даних.
type
TNumber=Record
L:word; кількість цифр у числі
масив цифр числа
C:array [1..7000] of byte;
end.
Наприклад, число 10!=3628800 буде розміщено в змінній A:TNumber у такий спосіб:
A.L:=7;
A.C[1]:=0;
A.C[2]:=0;
A.C[3]:=8;
A.C[4]:=8;
A.C[5]:=2;
A.C[6]:=6;
A.C[7]:=3.
Усі наступні елементи масиву цифр числа необхідно обнулити, що забезпечить більш комфортну роботу зі змінними типу TNumber під час виконання арифметичних операцій додавання та множення. Конструктивна будова даних такого типу є очевидною, тому залишилося написати декілька процедур опрацювання змінних типу TNumber для того, щоб набути деякого досвіду.
У першу чергу навчимося читати змінні типу TNumber з файлу. Можна було б насамперед розглянути процедуру введення з клавіатури, але в нашому випадку такої необхідності немає (уявляєте введення з клавіатури такого собі число 100!, яке складається з 158 цифр, або 1000! - 2568 цифр?!). Тому вважатимемо, що всі цифри числа знаходяться в одному рядку текстового файлу, який закінчується кодом EoLn. Для введення з файлу будемо виконувати посимвольне читання цифр числа в змінну w:char та послідовно присвоювати їх елементам масиву в числовому вигляді, використовуючи той факт, що байтові значення символів цифр відрізняються від самих чисел на 48, тобто Ord('0')=48, Ord('1')=49 тощо.
Процедура, яка прочитає значення факторіалу в змінну F з файлу, може бути такою:
procedure InputTNumber (var F:TNumber);
var
w:char;
z:array [1..7000] of byte;
i,U:word;
begin
FillChar (F.C, SizeOf(F.C), 0);
U:=0; Обнулити кількість прочитаних цифр
repeat
читаємо наступну цифру з файлу та записуємо її числове значення наступним елементом масиву Z
inc(U);
read(Fd,w);
Z[U]:=byte(w)-48;
until EoLn(Fd); цикл до кінця рядка у файлі
readln(Fd);
переписуємо масив Z у масив цифр F.C у зворотному порядку
for i:=1 to U do F.C[i]:=Z[U-i+1];
заповнюємо поле кількості цифр
F.L:=U;
end;
Тепер пишемо процедуру для збільшення на одиницю заданого числа A:TNumber, тобто аналог процедури Inc. Почнемо з наймолодшого розряду числа і спробуємо збільшити поточну цифру на одиницю. Якщо цього зробити неможливо, то обнулимо поточний розряд і повторимо аналогічну операцію для наступних розрядів.
procedure incTNumber (var A:TNumber);
var i:word;
begin
i:=1; {Почнемо з наймолодшого розряду}
while A.C[i]=9 do {Якщо неможливо збільшити поточну цифру, то обнулити її і перейти}
begin {до наступного розряду}
A.C[i]:=0; inc(i);
end;
inc(A.C[i]); {інкремент поточної цифри}
if i>A.L then A.L:=i: {Скоригувати довжину числа}
end.
Лише для того, щоб закріпити набутий досвід, пишемо процедуру знаходження суми двох змінних типу TNumber. Будемо користуватися алгоритмом обчислення суми двох багатоцифрових чисел, відомим з арифметики. Отже, послідовно рахуємо суми відповідних цифр операндів, починаючи з молодших розрядів до довжини найбільшого числа (незначущі цифри в старших розрядах меншого числа замінені нулями).
procedure AddTNumber (A,B:TNumber; var M:TNumber);
var R, K, i:word;
begin
FillChar (M.C, 7000, 0); {обнулити масив цифр М}
if A.L>B.L then K:=A.L else K:=B.L; {К - кількість додавань}
for i:=1 to K do
begin {цикл по К цифрах А та В}
R:=M.C[i] + A.C[i] + B.C[i]; {знайти результат додавання двох поточних цифр}
M.C[i]:=R mod 10; {та записати цифру одиниць до поточного розряду результату, а цифру десятків - до наступного}
M.C[i+1]:=R div 10;
end;
if M.C[K+1]>0 then M.L:=K+1 else M.L:=K; {заповнити поле кількості цифр результату залежно від переносу до К+1 розряду}
end;
Наступною буде процедура множення двох змінних А, В типу TNumber з отриманням результату М такого ж типу. Процедура MultTNumber використовує алгоритм множення двох багатоцифрових чисел у стовпчик.
procedure MultTNumber (A, B:TNumber; var M:TNumber);
var R, i, j:word;
begin
FillChar(M.C, 7000, 0);
for i:=1 to A.L do
for j:=1 to B.L do
begin
R:=M.C[i + j - 1] + A.C[i]*B.C[j];
M.C[i + j - 1]:=R mod 10;
M.C[i + j]:=M.C[i + j] + R div 10;
end;
M.L:=A.L+B.L-1;
if M.C[A.L+B.L]>0 then M.L:=A.L+B.L;
end;
І нарешті, функція порівняння двох змінних типу TNumber:
function CompTNumber (X,Y:TNumber):boolean;
var
i:word;
F:boolean;
begin
if X.L=Y.L then
begin
F:=true;
for i:=1 to X.L do F:=F and (X.C[i]=Y.C[i]);
end
else F:=false;
Comp:=F;
end.
Цього матеріалу вже достатньо, щоб написати головний модуль програми для розв'язку поставленої задачі. Проте метод емуляції довгої арифметики не є найкращим у цьому випадку.
Проте нам корисно створити програму для запису у файл N! (1<=N<=2000), адже нам необхідно створювати текстові файли, бо обчислювати факторіали в інший спосіб для великих N є досить проблематично.
uses Crt;
type
TNumber=Record
L:word;
C:array [1//7000] of byte;
end;
var
R, A:TNumber;
N, i:word;
procedure incTNumber (var A:TNumber);
var i:word;
begin
i:=1;
while A.C[i]=9 do
begin
A.C[i]:=0;
inc(i);
end;
inc(A.C[i]);
if i>A.L then A.L:=i;
end;
procedure MultTNumber(A , B:TNumber; var M:TNumber);
var R, i, j:word;
begin
FillChar (M.C, 7000, 0);
for i:=1 to A.L do
for j:=1 to B.L do
begin
R:=M.C[i + j - 1] + A.C[i]*B.C[j];
M.C[i + j - 1]:=R mod 10;
M.Ci + j]:=M.C[i + j] + R div 10;
end;
if M.C[A.L+B.L]>0 then M.L:=A.L+B.L else M.L:=A.L+B.L-1;
end;
procedure OutToFile(A:TNumber);
var
Fd:text;
i:word;
begin
assign(Fd, 'input.txt');
rewrite(Fd);
for i:=A.L downto 1 do write(Fd, A.C[i]);
close(Fd);
end;
begin
clrscr;
write('N=');
readln(N);
FillChar(A.C, 7000, 0);
A.C[1]:=0;
A.L:=1;
FillChar(R.C, 7000, 0);
R.C[1]:=1;
R.L:=1;
for i:=1 to N do
begin
incTNumber(A);
MultTNumber(A, R, R);
end;
OutToFile(R);
end.
Тепер, коли ми маємо можливість обчислити факторіал будь-якого з чисел 1<=N<=2000, поставимо таке запитання: чим у першу чергу відрізняється 99! і 100!? Відповідь правильна - кількістю цифр. Оскільки у файлі дійсно знаходиться факторіал деякого числа, то є логічним наступне запитання: чи є необхідність перевіряти всі цифри факторіала, якщо порядки чисел збігаються? Ні - достатньо перевірити декілька перших цифр. То навіщо взагалі читати з файлу всі цифри факторіалу?
Наближаємося до розв'язання даної задачі! Програма буде використовувати новий тип даних, у нашому випадку це емуляція дійсного числового типу:
type
TReal=record
L:word; {порядок числа}
C:real; {мантиса числа}
end.
Перед виконанням арифметичних і логічних операцій з такими числами вони мають бути нормалізованими, тобто поле С має бути не меншим від 1 і меншим від 10. Відповідна процедура нормалізації може бути такою:
procedure NormalTReal(var X:TReal);
begin
while X.C>10 do {поки мантиса числа перевищує 10}
begin
X.C:=X.C/10; {понизити порядок мантиси і}
inc(X.L); {збільшити на 1 порядок числа}
end;
end.
Процедура читання з файлу числа і розміщення його в змінній типу TNumber є доволі цікавою. Нагадаємо, що нам потрібні декілька (наприклад, 8) перших цифр числа та кількість його цифр (навіть не враховуючи перші вісім, адже ми завжди зможемо нормалізувати змінну типу TReal).
Зауважимо, що початковий алгоритм розв'язання задачі залишився незмінним, а кожен з етапів цього розв'язання випробував інший числовий тип даних на цьому алгоритмі. Отже, правильно вибрана структура даних для програми - це запорука успіху.
type
TReal=record
L:word;
C:real;
end;
var
A, F:TReal;
N:word;
Fd:text;
T,k:byte;
function Comp(X, Y:TReal):boolean;
var i:word;
begin
Comp:=(X.L=Y.L) and (Abs(X.C-Y.C)<0.000001);
end;
procedure Normal (var X:TReal);
begin
while X.C>10 do
begin
X.C:=X.C/10;
inc(X.L);
end;
end;
procedure Input (var X:TReal);
var
w:char;
i:word;
begin
X.L:=0;
X.C:=0;
i:=0;
repeat
read(Fd, w);
inc(i);
if i<9 then X.C:=X.C*10 + byte(w) - 48 else inc(X.L);
until EoLn(Fd);
readln(Fd);
Normal(X);
end;
begin
assign(Fd, 'input.txt');
reset(Fd);
input(F);
N:=0;
A.C:=1;
A.L:=0;
repeat
inc(N);
A.C:=A.C*N;
normal(A);
until Comp(A, F);
writeln(N);
close(Fd);
end.
Цікаво, як буде вести себе програма при більших значеннях N? Пропонуємо у файлі даних число 6227020800, яке дорівнює факторіалу 13, - замість результату маємо повідомлення про хибний числовий формат. Справді, найбільше значення, яке підтримує стандартний LongInt, дорівнює 2147483647, і тому Паскаль відмовляється читати в змінних типу LongInt більші значення.
Вихід із цього становища може бути достатньо простим: замінити в програмі тип значень N та R на real. Тепер програма працює нормально для всіх факторіалів чисел до 27 включно. Повідомлення про переповнення під час операції з дійсним числом виникає за спроби обробити 28! Справа в тому, що стандартний тип real коректно обслуговує 11-12 цифр мантиси дійсного числа. Тому, за відомими лише програмістам фірми Borland причинами, внутрішні процедури мови програмування Паскаль читають з файлу записане там натуральне число 304888344611713860501504000000 як 304888344611629183000000000000, а обчислення цього значення факторіала 28! дає іншу величину:
304888344611917414000000000000.
Значення F та R не збігаються і алгоритм зациклюється, тобто обчислення продовжується, виходить за межі стандартного типу real і Паскаль повідомляє про переповнення.
Як обійти цю проблему? Можна запропонувати порівнювати значення U та R наближено, aбо порівнювати не самі числа, а їх порядки (порядок дійсного числа можна знайти, обчисливши його десятковий логарифм).
Виправляючи рядок умови виходу з циклу на until Abs(Ln(R)-Ln(F))<0.01, матимемо позитивний результат для факторіалів чисел 28, 29, 30, 31, 32, 33. Якщо прочитати з файлу число 34! (найбільше значення стандартного типу real 1.7е38<34!), отримаємо знайоме повідомлення про переповнення під час виконання операції з дійсним числом.
У таблиці дійсних типів вибираємо найбільший можливий тип Extended (найбільше значення - 1.1е4932) і вважаємо, що тепер успіх вже дуже близько. Нова версія програми читається так:
var
N:word;
F,R:extended;
Fi:text;
begin
assign (Fi, 'input.txt');
reset(Fi);
readln(Fi,F);
close(Fi);
N:=0;
R:=1;
repeat
inc(N);
R:=R*N;
until Ln(R)/Ln(10)=Ln(F)/Ln(10);
writeln(N);
end.
Ця програма ставить своєрідний рекорд і працює нормально для факторіалів чисел від 1 до 49. Програма сходить з дистанції при N=50. Виявляється, процедура readln(X:extended) читає з файлу не більше ніж 64 знаки, а наступні цифри просто ігноруються.
Число 50!, яке має 65 цифр, читається в змінну як 3.04140932017134е+0063, тому знову маємо зациклювання і повідомлення про переповнення під час операції з дійсним числом.
N
|
N!
|
10
|
3628800
|
11
|
39916800
|
12
|
479001600
|
13
|
6227020800
|
14
|
87178291200
|
15
|
1307674368000
|
16
|
20922789888000
|
17
|
355687428096000
|
18
|
6402373705728000
|
19
|
121645100408832000
|
20
|
2432902008176640000
|
21
|
51090942171709440000
|
22
|
1124000727777607680000
|
23
|
25852016738884976640000
|
24
|
620448401733239439360000
|
25
|
15511210043330985984000000
|
26
|
403291461126605635584000000
|
27
|
10888869450418352160768000000
|
28
|
304888344611713860501504000000
|
29
|
8841761993739701954543616000000
|
30
|
265252859812191058636308480000000
|
31
|
8222838654177922817725562880000000
|
32
|
263130836933693530167218012160000000
|
33
|
8683317618811886495518194401280000000
|
34
|
295232799039604140847618609643520000000
|
35
|
10333147966386144929666651337523200000000
|
36
|
371993326789901217467999448150835200000000
|
37
|
13763753091226345046315979581580902400000000
|
38
|
523022617466601111760007224100074291200000000
|
39
|
20397882081197443358640281739902897356800000000
|
40
|
815915283247897734345611269596115894272000000000
|
41
|
33452526613163807108170062053440751665152000000000
|
42
|
1405006117752879898543142606244511569936384000000000
|
43
|
60415263063373835637355132068513997507264512000000000
|
44
|
2658271574788448768043625811014615890319638528000000000
|
45
|
119622220865480194561963161495657715064383733760000000000
|
46
|
5502622159812088949850305428800254892961651752960000000000
|
47
|
258623241511168180642964355153611979969197632389120000000000
|
48
|
12413915592536072670862289047373375038521486354677760000000000
|
49
|
608281864034267560872252163321295376887552831379210240000000000
|
50
|
30414093201713378043612608166064768844377641568960512000000000000
|
Настав час зробити деякі висновки: запропонований алгоритм розв'язування задачі працює правильно, але всі спроби реалізувати його на стандартних числових типах мови Паскаль не принесли потрібного результату. Програма не працює навіть для 50!, не кажучи вже про 2000!. Але витрачені зусилля не були марними. З'явився досвід, який підказує, що потрібно обійти стандартний числовий тип.
Для цього необхідно створити свій числовий тип даних та написати відповідні процедури опрацювання змінних такого типу. Достатньо відомим в інформатиці є метод емуляції так званої 'довгої арифметики', коли невід'ємне ціле число розглядається у програмі у вигляді масиву своїх цифр. Вводимо свій тип даних.
type
TNumber=Record
L:word; кількість цифр у числі
масив цифр числа
C:array [1..7000] of byte;
end.
Наприклад, число 10!=3628800 буде розміщено в змінній A:TNumber у такий спосіб:
A.L:=7;
A.C[1]:=0;
A.C[2]:=0;
A.C[3]:=8;
A.C[4]:=8;
A.C[5]:=2;
A.C[6]:=6;
A.C[7]:=3.
Усі наступні елементи масиву цифр числа необхідно обнулити, що забезпечить більш комфортну роботу зі змінними типу TNumber під час виконання арифметичних операцій додавання та множення. Конструктивна будова даних такого типу є очевидною, тому залишилося написати декілька процедур опрацювання змінних типу TNumber для того, щоб набути деякого досвіду.
У першу чергу навчимося читати змінні типу TNumber з файлу. Можна було б насамперед розглянути процедуру введення з клавіатури, але в нашому випадку такої необхідності немає (уявляєте введення з клавіатури такого собі число 100!, яке складається з 158 цифр, або 1000! - 2568 цифр?!). Тому вважатимемо, що всі цифри числа знаходяться в одному рядку текстового файлу, який закінчується кодом EoLn. Для введення з файлу будемо виконувати посимвольне читання цифр числа в змінну w:char та послідовно присвоювати їх елементам масиву в числовому вигляді, використовуючи той факт, що байтові значення символів цифр відрізняються від самих чисел на 48, тобто Ord('0')=48, Ord('1')=49 тощо.
Процедура, яка прочитає значення факторіалу в змінну F з файлу, може бути такою:
procedure InputTNumber (var F:TNumber);
var
w:char;
z:array [1..7000] of byte;
i,U:word;
begin
FillChar (F.C, SizeOf(F.C), 0);
U:=0; Обнулити кількість прочитаних цифр
repeat
читаємо наступну цифру з файлу та записуємо її числове значення наступним елементом масиву Z
inc(U);
read(Fd,w);
Z[U]:=byte(w)-48;
until EoLn(Fd); цикл до кінця рядка у файлі
readln(Fd);
переписуємо масив Z у масив цифр F.C у зворотному порядку
for i:=1 to U do F.C[i]:=Z[U-i+1];
заповнюємо поле кількості цифр
F.L:=U;
end;
Тепер пишемо процедуру для збільшення на одиницю заданого числа A:TNumber, тобто аналог процедури Inc. Почнемо з наймолодшого розряду числа і спробуємо збільшити поточну цифру на одиницю. Якщо цього зробити неможливо, то обнулимо поточний розряд і повторимо аналогічну операцію для наступних розрядів.
procedure incTNumber (var A:TNumber);
var i:word;
begin
i:=1; {Почнемо з наймолодшого розряду}
while A.C[i]=9 do {Якщо неможливо збільшити поточну цифру, то обнулити її і перейти}
begin {до наступного розряду}
A.C[i]:=0; inc(i);
end;
inc(A.C[i]); {інкремент поточної цифри}
if i>A.L then A.L:=i: {Скоригувати довжину числа}
end.
Лише для того, щоб закріпити набутий досвід, пишемо процедуру знаходження суми двох змінних типу TNumber. Будемо користуватися алгоритмом обчислення суми двох багатоцифрових чисел, відомим з арифметики. Отже, послідовно рахуємо суми відповідних цифр операндів, починаючи з молодших розрядів до довжини найбільшого числа (незначущі цифри в старших розрядах меншого числа замінені нулями).
procedure AddTNumber (A,B:TNumber; var M:TNumber);
var R, K, i:word;
begin
FillChar (M.C, 7000, 0); {обнулити масив цифр М}
if A.L>B.L then K:=A.L else K:=B.L; {К - кількість додавань}
for i:=1 to K do
begin {цикл по К цифрах А та В}
R:=M.C[i] + A.C[i] + B.C[i]; {знайти результат додавання двох поточних цифр}
M.C[i]:=R mod 10; {та записати цифру одиниць до поточного розряду результату, а цифру десятків - до наступного}
M.C[i+1]:=R div 10;
end;
if M.C[K+1]>0 then M.L:=K+1 else M.L:=K; {заповнити поле кількості цифр результату залежно від переносу до К+1 розряду}
end;
Наступною буде процедура множення двох змінних А, В типу TNumber з отриманням результату М такого ж типу. Процедура MultTNumber використовує алгоритм множення двох багатоцифрових чисел у стовпчик.
procedure MultTNumber (A, B:TNumber; var M:TNumber);
var R, i, j:word;
begin
FillChar(M.C, 7000, 0);
for i:=1 to A.L do
for j:=1 to B.L do
begin
R:=M.C[i + j - 1] + A.C[i]*B.C[j];
M.C[i + j - 1]:=R mod 10;
M.C[i + j]:=M.C[i + j] + R div 10;
end;
M.L:=A.L+B.L-1;
if M.C[A.L+B.L]>0 then M.L:=A.L+B.L;
end;
І нарешті, функція порівняння двох змінних типу TNumber:
function CompTNumber (X,Y:TNumber):boolean;
var
i:word;
F:boolean;
begin
if X.L=Y.L then
begin
F:=true;
for i:=1 to X.L do F:=F and (X.C[i]=Y.C[i]);
end
else F:=false;
Comp:=F;
end.
Цього матеріалу вже достатньо, щоб написати головний модуль програми для розв'язку поставленої задачі. Проте метод емуляції довгої арифметики не є найкращим у цьому випадку.
Проте нам корисно створити програму для запису у файл N! (1<=N<=2000), адже нам необхідно створювати текстові файли, бо обчислювати факторіали в інший спосіб для великих N є досить проблематично.
uses Crt;
type
TNumber=Record
L:word;
C:array [1//7000] of byte;
end;
var
R, A:TNumber;
N, i:word;
procedure incTNumber (var A:TNumber);
var i:word;
begin
i:=1;
while A.C[i]=9 do
begin
A.C[i]:=0;
inc(i);
end;
inc(A.C[i]);
if i>A.L then A.L:=i;
end;
procedure MultTNumber(A , B:TNumber; var M:TNumber);
var R, i, j:word;
begin
FillChar (M.C, 7000, 0);
for i:=1 to A.L do
for j:=1 to B.L do
begin
R:=M.C[i + j - 1] + A.C[i]*B.C[j];
M.C[i + j - 1]:=R mod 10;
M.Ci + j]:=M.C[i + j] + R div 10;
end;
if M.C[A.L+B.L]>0 then M.L:=A.L+B.L else M.L:=A.L+B.L-1;
end;
procedure OutToFile(A:TNumber);
var
Fd:text;
i:word;
begin
assign(Fd, 'input.txt');
rewrite(Fd);
for i:=A.L downto 1 do write(Fd, A.C[i]);
close(Fd);
end;
begin
clrscr;
write('N=');
readln(N);
FillChar(A.C, 7000, 0);
A.C[1]:=0;
A.L:=1;
FillChar(R.C, 7000, 0);
R.C[1]:=1;
R.L:=1;
for i:=1 to N do
begin
incTNumber(A);
MultTNumber(A, R, R);
end;
OutToFile(R);
end.
Тепер, коли ми маємо можливість обчислити факторіал будь-якого з чисел 1<=N<=2000, поставимо таке запитання: чим у першу чергу відрізняється 99! і 100!? Відповідь правильна - кількістю цифр. Оскільки у файлі дійсно знаходиться факторіал деякого числа, то є логічним наступне запитання: чи є необхідність перевіряти всі цифри факторіала, якщо порядки чисел збігаються? Ні - достатньо перевірити декілька перших цифр. То навіщо взагалі читати з файлу всі цифри факторіалу?
Наближаємося до розв'язання даної задачі! Програма буде використовувати новий тип даних, у нашому випадку це емуляція дійсного числового типу:
type
TReal=record
L:word; {порядок числа}
C:real; {мантиса числа}
end.
Перед виконанням арифметичних і логічних операцій з такими числами вони мають бути нормалізованими, тобто поле С має бути не меншим від 1 і меншим від 10. Відповідна процедура нормалізації може бути такою:
procedure NormalTReal(var X:TReal);
begin
while X.C>10 do {поки мантиса числа перевищує 10}
begin
X.C:=X.C/10; {понизити порядок мантиси і}
inc(X.L); {збільшити на 1 порядок числа}
end;
end.
Процедура читання з файлу числа і розміщення його в змінній типу TNumber є доволі цікавою. Нагадаємо, що нам потрібні декілька (наприклад, 8) перших цифр числа та кількість його цифр (навіть не враховуючи перші вісім, адже ми завжди зможемо нормалізувати змінну типу TReal).
Зауважимо, що початковий алгоритм розв'язання задачі залишився незмінним, а кожен з етапів цього розв'язання випробував інший числовий тип даних на цьому алгоритмі. Отже, правильно вибрана структура даних для програми - це запорука успіху.
type
TReal=record
L:word;
C:real;
end;
var
A, F:TReal;
N:word;
Fd:text;
T,k:byte;
function Comp(X, Y:TReal):boolean;
var i:word;
begin
Comp:=(X.L=Y.L) and (Abs(X.C-Y.C)<0.000001);
end;
procedure Normal (var X:TReal);
begin
while X.C>10 do
begin
X.C:=X.C/10;
inc(X.L);
end;
end;
procedure Input (var X:TReal);
var
w:char;
i:word;
begin
X.L:=0;
X.C:=0;
i:=0;
repeat
read(Fd, w);
inc(i);
if i<9 then X.C:=X.C*10 + byte(w) - 48 else inc(X.L);
until EoLn(Fd);
readln(Fd);
Normal(X);
end;
begin
assign(Fd, 'input.txt');
reset(Fd);
input(F);
N:=0;
A.C:=1;
A.L:=0;
repeat
inc(N);
A.C:=A.C*N;
normal(A);
until Comp(A, F);
writeln(N);
close(Fd);
end.
Немає коментарів:
Дописати коментар