|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Ilia Kantor 2:5020/1815.6 23 Feb 2002 05:16:46
To : Andrey Lipsky
Subject : большие числа
--------------------------------------------------------------------------------
А вот я и до тебя добрался, Mr Andrey Lipsky!
AL> Подскажите, плз, как оpганизовать деление больших(длинных) чисел. Числа
AL> хpаню в стpоке. Сyммy, сложение, yмножение сделал, а вот с делением
AL> запаpка.
Вот цитата из статьи Окулова... Тоpмозит пpосто дико, зато pаботает !!
Да, кстати.. сложность алгоpитма вpоде O(n^2 logn)... Рулез.
С.М. Окулов
web: http://archive.1september.ru/inf/2000/1/art/okul1.htm
Четвертая задача. Реализация операций сравнения для "длинных" чисел (А = В, А <
В, А > В, А <= В, А >= В).
Function Eq(A, B : TLong) : Boolean;
Var i : Integer;
Begin
Eq := False;
If A[0] <> B[0] Then Exit
Else Begin
i := l;
While (i <= A[0]) And (A[i] = B[i]) Do Inc(i);
Eq := i = A[0] + l
End
End;
Реализация функции А > В также прозрачна.
Function More(A, B : Tlong) : Boolean;
Var i : Integer;
Begin If A[0] < B[0] Then More := False
Else If A[0] > B[0] Then More := True
Else Begin
i := A[0];
While (i > 0) And (A[i] = B[i]) Do Dec(i);
If i = 0 Then More := False
Else If A[i] > B[i] Then More := True
Else More:=False
End
End;
Для самостоятельного решения может быть предложена следующая, более сложная,
задача. Требуется разработать функцию, которая выдает 0, если А больше В, 1,
если А меньше В, и 2 при равенстве чисел. о сравнение должно быть выполнено с
учетом сдвига. О чем идет речь? Поясним на примере. Пусть А равно 56784, а В _
634. При сдвиге числа В на 2 позиции влево функция должна сказать, что В больше
А, без сдвига, что А больше В. Другой пример. При А равном 56700, а В _ 567 и
сдвиге 2 функция должна "сказать", что числа равны. Решение может иметь
следующий вид:
Function More(Const А, В : Tlong; Const sdvig : Integer) : Byte;
Var i : Integer;
Begin
If A[0] > B[0] + sdvig Then More := 0
Else
If A[0] < B[0] + sdvig Then More := l
Else Begin
i := A[0];
While (i > sdvig) And
(A[i] = B[i-sdvig]) Do Dec(i);
If i = sdvig Then Begin
More:=0;
{совпадение чисел с учетом сдвига}
For i := 1 To sdvig Do
If A[i] > 0 Then Exit;
More := 2;
{числа равны, "хвост" числа А равен нулю}
End
Else More := Byte(A[i] < B[i-sdvig])
End
End;
(Прим. в исходниках на Си эта функция обозначена MoreShift).
Пятая задача. Умножение длинного числа на короткое. Под коротким понимается
целое число типа LongInt.
Процедура очень походит на процедуру сложения двух длинных чисел.
Procedure Mul(Const A : TLong; Const К : Longlnt; Var С : TLong);
Var i : Integer;
{результат - значение переменной С}
Begin
FillChar (С, SizeOf(С), 0);
If K = 0 Then Inc(С[0]){умножение на ноль}
Else Begin
For i:= l To A[0] Do
Begin
C[i+l] := (LongInt(A[i]) * K + C[i]) Div Osn;
C[i] := (LongInt(A[i])* K + C[i]) Mod Osn
End;
If C[A[0]+1] > 0 Then C[0]:= A[0] + 1
Else C[0]:= A[0]
{определяем длину результата}
End
End;
(Прим. в исходниках на Си эта функция обозначена MulBigShortTo).
Шестая задача. Вычитание двух длинных чисел с учетом сдвига
Если понятие сдвига пока не понятно, то оставьте его в покое, на самом деле
вычитание с учетом сдвига потребуется при реализации операции деления. В начале
выясните логику работы процедуры при нулевом сдвиге.
Введем ограничение: число, из которого вычитают, больше числа, которое
вычитается. Работать с "длинными" отрицательными числами мы не умеем.
Процедура была бы похожа на процедуры сложения и умножения, если бы не одно "но"
_ заимствование единицы из старшего разряда вместо переноса единицы в старший
разряд. апример, в обычной системе счисления мы вычитаем 9 из 11 _ идет
заимствование 1 из разряда десятков, а если из 10000 вычитаем 9 _ процесс
заимствования несколько сложнее.
Procedure Sub (Var A : TLong; Const B : TLong; Const sp : Integer);
Var i, j : Integer;
{из А вычитаем В с учетом сдвига sp, результат вычитания в А}
Begin
For i := l To B[0] Do
Begin Dec(A[i+sp], B[i]);
j: = i;{*}
{реализация сложного заимствования}
while (A[j+sp] < 0) and (j <= A[0]) Do
Begin{*}
Inc(A[j+sp], Osn) ;
Dec(A[j+sp+l]); Inc(j); {*}
end; {*}
{Реализация простого заимствования.
Если операторы, отмеченные *, заменить
на нижеприведенные операторы в фигурных скобках, то,
по понятным причинам, логика не будет работать
при всех исходных данных. }
End;
i := A[0];
While (i > l) And (A[i] = 0) Do Dec(i);
A[0] := i
{корректировка длины результата операции}
End;
Рекомендуется выполнить трассировку работы данной процедуры, например, для
следующих исходных данных. Число А равно 100000001000000000000, число В _
2000073859998.
Седьмая задача. Деление двух длинных чисел, т.е. нахождение целой части частного
и остатка.
аписать исходную (без уточнений) часть логики не составляет труда. Это:
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(A, B, 0) Of
0: MakeDel(A, B, Res, Ost);
{А больше В, пока не знаем, как выполнять операцию - "выносим" в процедуру}
1: Ost:=A; {А меньше В}
2: Res[l] := l; {А равно В}
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 С Ost = 27856
0 10000 1770000 C > Ost
0 5000 885000 C > Ost
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
{Есть возможность преподавателю сделать
сознательную ошибку. Изменить условие
цикла на Up>Down. Результат - зацикливание программы.}
Mul(В, (Up + Down) Div 2, С);
Case More(Ost, C, 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, C);
If More (Ost, C, 0) = 0 Then Sub(Ost, C, 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;
ъщю До следующих встреч, Andrey ющъ
--- GoldEd 3.00.Alpha4+
* Origin: http://algolist.da.ru - Мир Алгоритмов (2:5020/1815.6)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
