Сьома задача. Ділення двох довгих чисел, тобто знаходження цілої частини частки і залишку.
Procedure Long_Div_Long(Const А, В: TLong; Var Res, Ost: TLong);
Begin
FillChar(Res, SizeOf(Res), 0);Res[0]:=1;
FillChar(Ost, SizeOf(Ost), 0);0st[0]:=1;
Case More(А, B, 0) of
0: Begin MakeDel(А, B, Res, Ost);
End; {А більше В, не знаємо, як робити - "виносимо" в процедуру}
1: Begin Ost:=A; End; {А менше В}
2: Begin Res[l]:=l; End; {А дорівнює В}
End;
End;
А далі починаються проблеми. Ділити стовпчиком вміємо. Наприклад:
1000143123567 | 73859998
73859998 | 13541 (Ціла частина частки)
261543143
221579994
399631495
369299990
303315056
295439992
78750647
73859998
4890649 (Залишок)
На кожному етапі підбиралася цифра (1, 3, 5 і т.д.), така, що добуток цієї цифри на дільник дає число менше, але найближче до числа... Якого? Це важко сказати словами, але з прикладу зрозуміло. Спростимо приклад, залишимо його для тестування логіки процедури, тим більше що і числа "довгі". Нехай число А буде менше В • 10, тоді в результаті (ціла частина ділення) буде одна цифра. Наприклад, А дорівнює 564, а В – 63 і використовується десяткова система числення. Спробуємо підібрати цифру результату, але не методом прямого перебору, а методом ділення відрізка навпіл. Нехай Down – верхня межа інтервалу зміни цифри, що підбирається, Up - нижня межа інтервалу, Ost дорівнює діленому.
|
Down |
Up |
С=В•( (Down+Up) Div 2) |
Ost=564 |
|
0 |
10 |
315 = 63 • ( (0 + 10) Div 2) |
C<Ost |
|
5 |
10 |
441 = 63 • ( (5 + 10) Div 2) |
C<Ost |
|
7 |
10 |
504 = 63 • ( (7 + 10) Div 2) |
C<Ost |
|
8 |
10 |
567 = 63 • ( (8 + 10) Div 2) |
C<Ost |
|
8 |
9 |
504 = 63 • ( (8 + 9) Div 2) |
C<Ost |
Отже, результат – ціла частина частки дорівнює (Up + Down) Div 2, залишок від деления—разниця між значеннями Ost і С. Нижню межу (Down) змінюємо, якщо результат (С) менший залишку, верхню (Up), якщо більший.
Ускладнимо приклад. Нехай А дорівнює 27856, а -В – 354. Основою системи числення є не 10, а 10000.
|
Down |
Up |
C |
Ost=27856 |
|
0 |
10000 |
1770000 |
С>Ost |
|
0 |
5000 |
885000 |
C>OOst |
|
0 |
2500 |
442500 |
C>Ost |
|
0 |
1250 |
221250 |
C>Ost |
|
0 |
625 |
110448 |
C>Ost |
|
0 |
312 |
55224 |
C>Ost |
|
0 |
156 |
27612 |
C<Ost |
|
78 |
156 |
41418 |
C>Ost |
|
78 |
117 |
34338 |
C>Ost |
|
78 |
97 |
30798 |
C>Ost |
|
78 |
87 |
29028 |
C>Ost |
|
78 |
82 |
28320 |
C>Ost |
|
78 |
80 |
27966 |
C>Ost |
|
78 |
79 |
27612 |
C<Ost |
Ціла частина частки дорівнює 78, залишок ділення – 27856 мінус 27612, тобто 244.
Перейдемо до процедури. Використовується: функція порівняння чисел (More) з врахуванням зсуву і функція множення довгого числа на коротке (Mul), описана вище.
Function FindBin(Var Ost: Tlong;Const В: TLong;Const sp: Integer): Longint;
Var Down, Up: Word;
C: TLong;
Begin
Down:=0; Up:=0sn;
{основа системи числення}
While Up-l>Down Do
Begin
Mul(В, (Up+Down) Div 2, С);
Case More(Ost, С, sp) of
0: Down:=(Down+Up) Div 2;
1: Up:= (Up+Down) Div 2;
2: Begin Up:=(Up+Down) Div 2;
Down:=Up;
End;
End;
End;
Mul(B, (Up+Down) Div 2, С);
If More (Ost.C,0)=0 Then Sub(Ost, С, sp)
{знаходимо залишок ділення}
Else begin
Sub (C,Ost,sp); Ost:=C;
end;
FindBin:=(Up+Down) Div 2;
{ціла частина частки}
End;
Залишилося розібратися із зсувом (значенням змінної sp). Повернемося до звичайної системи числення і спробуємо розділити, наприклад, 635 на 15. Спочатку ділимо 63 на 15 і підбираємо першу цифру результату.Це цифра 4, і це старша цифра результату. Змінимо залишок. Якщо спочатку він був 635, то зараз став 35. Віднімаємо з врахуванням зсуву. Знову підбираємо другу цифру результату. Це цифра 2 і залишок 5. Отже, результат (ціла частина) 42, залишок ділення 5. Що зміниться, якщо основою буде не 10, а 10000? Логіка залишається такою ж.
Procedure MakeDel(Const А, В: TLong; Var Res, Ost: TLong);
Var sp: Integer;
Begin
Ost:=A;
{перше значення залишку}
sp :=А[0] - В[0];
If More(А, В, sp)=l Then Dec(sp);
{B*Osn>A, в результаті одна цифра}
Res [0]:=sp+l;
While sp>=0 Do
Begin
{знаходимо чергову цифру результату}
Res [sp+1]:=FindBin(Ost, B, sp);
Dec(sp);
End;
End;