19874-1 (663006), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

Procedure SumLongTwo(A, B : Nlong; Var C : Tlong);

Var i, k : Integer;

Begin

FillChar(C, SizeOf (C), 0) ;

If A[0] > B[0] Then k := A[0] Else k : =B[0];

For i := l To k Do

Begin С [i+1] := (C[i] + A[i] + B[i]) Div Osn;

C[i] := (C[i] + A[i] + B[i]) Mod Osn

{Есть ли в этих операторах ошибка?}

End;

If C[k+l] = 0 Then C[0] := k Else C[0] := k + l

End;

Четвертая задача. Реализация операций сравнения для "длинных" чисел (А=В, А<В, А>В, А<=В, А>=В).

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;

Остальные функции реализуются через функции Eq и More.

Function Less(A, B : Tlong) : Boolean; {A < B}

Begin

Less := Not(More(A, B) Or Eq(A, B))

End;

Function More_Eq(A, B : Tlong) : Boolean; {A >= B}

Begin

More_Eq := More(A, B) Or Eq(A, B)

End;

Function Less_Eq(A, B : Tlong) : Boolean; {A <= B}

Begin

Less_Eq := Not More(A, B)

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;

Пятая задача. Умножение длинного числа на короткое. Под коротким понимается целое число типа 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;

Шестая задача. Вычитание двух длинных чисел с учетом сдвига

Если понятие сдвига пока не понятно, то оставьте его в покое, на самом деле вычитание с учетом сдвига потребуется при реализации операции деления. В начале выясните логику работы процедуры при нулевом сдвиге.

Введем ограничение: число, из которого вычитают, больше числа, которое вычитается. Работать с "длинными" отрицательными числами мы не умеем.

Процедура была бы похожа на процедуры сложения и умножения, если бы не одно "но" — заимствование единицы из старшего разряда вместо переноса единицы в старший разряд. Например, в обычной системе счисления мы вычитаем 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; {*}

{Реализация простого заимствования.

Если операторы, отмеченные *, заменить

на нижеприведенные операторы в фигурных скобках, то,

по понятным причинам, логика не будет работать

при всех исходных данных. Можно сознательно сделать

ошибку и предложить найти ее — принцип "обучение через ошибку"}

{If A[i+sp]<0 Then Begin Inc(A[i+sp], Osn);

Dec (A[i+sp+l]);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;

Методические рекомендации. Представленный материал излагается на четырех занятиях по известной схеме: 10-15-минутное изложение идей, а затем работа учащихся под руководством преподавателя.

1-е занятие. Ввод, вывод и сложение длинных чисел (задачи 1, 2, 3).

2-е занятие. Функции сравнения (задача 4).

3-е занятие. Умножение и вычитание длинных чисел (задачи 5, 6).

4-е занятие. Деление длинных чисел (задача 7). Безусловно, эта схема не догма. В зависимости от уровня подготовки учащихся на самостоятельное выполнение может быть вынесена значительная часть материала. Замечу только, что в силу сложившейся традиции в ряде случаев допускаются при изложении сознательные ошибки. В результате работы каждый учащийся должен иметь собственный модуль для работы с "длинными" числами.

Темы для исследований

1. Решение задач: поиск наибольшего общего делителя двух "длинных" чисел; поиск наименьшего общего кратного двух "длинных" чисел; извлечение квадратного корня из "длинного" числа и т.д.

2. "Длинные" числа могут быть отрицательными. Как изменятся описанные выше операции для этого случая?

3. Для хранения "длинных" чисел используется не массив, а стек, реализованный с помощью списка. Модифицировать модуль работы с "длинными" числами.

Список литературы

С.М. Окулов/ "Длинная" арифметика/

Для подготовки данной работы были использованы материалы с сайта http://www.comp-science.narod.ru/

Характеристики

Список файлов реферата