>

Сьома задача. Ділення двох довгих чисел, тобто знаходження цілої частини частки і залишку.

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;

ЯндексРеклама на ЯндексеПомощьПоказатьЗакрыть
Рефераты