Вход

"Длинная" арифметика

Реферат по программированию
Дата добавления: 16 января 2010
Язык реферата: Русский
Word, rtf, 260 кб (архив zip, 24 кб)
Реферат можно скачать бесплатно
Скачать
Не подходит данная работа?
Вы можете заказать написание любой учебной работы на любую тему.
Заказать новую работу

"Длинная" арифметика

Известно, что арифметические действия, выполняемые компьютером в ограниченном числе разрядов, не всегда позволяют получить точный результат. Более того, мы ограничены размером (величиной) чисел, с которыми можем работать. А если нам необходимо выполнить арифметические действия над очень большими числами, например,

30! = 265252859812191058636308480000000?

В таких случаях мы сами должны позаботиться о представлении чисел в машине и о точном выполнении арифметических операций над ними.

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

Организация работы с "длинными" числами во многом зависит от того, как мы представим в компьютере эти числа. "Длинное" число можно записать, например, с помощью массива десятичных цифр, количество элементов в таком массиве равно количеству значащих цифр в "длинном" числе. Но если мы будем реализовывать арифметические операции над этим числом, то размер массива должен быть достаточным, чтобы разместить в нем и результат, например, умножения.

Существуют и другие представления "длинных" чисел. Рассмотрим одно из них. Представим наше число

30! = 265252859812191058636308480000000

в виде:

30! = 2 * (104)8 + 6525 * (104)7 + 2859 * (104) + 8121 * (104)5 + 9105 * (104)4 + 8636 * (104)3 + 3084 * (104)2 + 8000 * (104)1 + 0000 * (104)0.

Это представление наталкивает на мысль о массиве, представленном в табл. 1.

Таблица 1

Номер элемента в массиве А

0

1

2

3

4

5

6

7

8

9

Значение

9

0

8000

3084

8636

9105

8121

2859

6525

2

Мы можем считать, что наше "длинное" число представлено в 10000-10 системе счисления (десятитысячно-десятичная система счисления, приведите аналогию с восьмерично-десятичной системой счисления), а "цифрами" числа являются четырехзначные числа.

Возникают вопросы. Что за 9 в А [0], почему число хранится "задом наперед"? Ответы очевидны, но подождем с преждевременными объяснениями. Ответы на вопросы будут ясны из текста.

Примечание. Мы работаем с положительными числами!

Первая задача. Ввести "длинное" число из файла. Решение задачи начнем с описания данных.

Const             MaxDig = 1000; {Максимальное количество цифр — четырехзначных!}

   Osn = 10000; {Основание нашей системы счисления,

                           в элементах массива храним четырехзначные числа}

Type             Tlong = Array[0..MaxDig] Of Integer;

   {Максимальное количество десятичных цифр в нашем числе}

Алгоритм ввода "длинного" числа из файла рассмотрим на конкретном примере.

Пусть в файле записано число 23851674 и основанием (Osn) является 1000 (храним по три цифры в элементе массива А). Изменение значений элементов массива А в процессе ввода (посимвольного в переменную Ch) отражено в табл. 2.

Таблица 2

А[0]

А[1]

А[2]

А[3]

Ch

Примечание

3

674

851

23

-

Конечное состояние

0

0

0

0

2

Начальное состояние

1

2

0

0

3

1-й шаг

1

23

0

0

8

2-й шаг

1

238

0

0

5

3-й шаг

2

385

2

0

1

4-й шаг: старшая цифра элемента А [1] перешла в пока "пустой" элемент А[2]

2

851

23

0

6

5-й шаг

2

516

238

0

7

6-й шаг

3

167

385

2

4

7-й шаг

3

674

851

23



Проанализируем таблицу (и получим ответы на поставленные выше вопросы).

1. В А[0] храним количество задействованных (ненулевых) элементов массива А — это уже очевидно.

2. При обработке каждой очередной цифры входного числа старшая цифра элемента массива с номером i становится младшей цифрой числа в элементе i+1, а вводимая цифра будет младшей цифрой числа из А[1]. В результате работы нашего алгоритма мы получили число, записанное "задом наперед".

Примечание (методическое): Можно ограничиться этим объяснением и разработку процедуры вынести на самостоятельное задание. Можно продолжить объяснение. Например, выписать фрагмент текста процедуры перенос старшей цифры из A[i] в младшую цифру А[i+1], т.е. сдвиг уже введенной части числа на одну позицию вправо:

   For i := A[0] DownTo 1 Do

   Begin

               A[i+l] := A[i+l] + (Longint(A[i]) * 10) Div Osn;

               A[i] := (LongInt(A[i]) * 10) Mod Osn;

   End;

Пусть мы вводим число 23851674 и первые 6 цифр уже разместили "задом наперед" в массиве А. В символьную переменную считали очередную цифру "длинного" числа — это "7". По нашему алгоритму эта цифра "7" должна быть размещена младшей цифрой в А[1]. Выписанный фрагмент программы "освобождает" место для этой цифры. В таблице отражены результаты работы этого фрагмента.

i

А[1]

А[2]

А[3]

ch

2

516

238

0

7

2

516

380

2


1

160

385

2


После этого остается только добавить текущую (считанную в ch) цифру "длинного" числа к А[1] и изменить значение А[0].

В конечном итоге процедура должна иметь следующий вид:

   Procedure ReadLong(Var A : Tlong);

   Var ch : char; i : Integer;

   Begin

               FillChar(A, SizeOf(A), 0) ;

               Read(ch);

               While Not(ch In ['0'..'9']) Do Read(ch);

               {пропуск не цифр во входном файле}

               While ch In ['0'..'9'] Do

               Begin

                           For i := A[0] DownTo 1 Do

                           Begin

                                       {"протаскивание" старшей цифры в числе из A[i]

                                       в младшую цифру числа из A[i+l]}

                                       A[i+l] := A[i+l] + (LongInt(A[i]) * 10) Div Osn;

                                       A[i] := (LongInt(A[i]) * 10) Mod Osn

                           End;

                           A[1] := A[l] + Ord(ch) - Ord('0');

                           {добавляем младшую цифру к числу из А[1]}

                           If A[A[0]+1] > 0 Then Inc(A[0]);

                           {изменяем длину, число задействованных элементов массива А}

                           Read(ch)

               End

   End;

Вторая задача. Вывод "длинного" числа в файл или на экран.

Казалось бы, нет проблем — выводи число за числом. Однако в силу выбранного нами представления "длинного" числа мы должны всегда помнить, что в каждом элементе массива хранится не последовательность цифр "длинного" числа, а значение числа, записанного этими цифрами. Пусть в элементах массива хранятся четырехзначные числа. Тогда "длинное" число 128400583274 будет в массиве А представлено следующим образом:

A[0]

A[1]

A[2]

A[3]

3

3274

58

1284

При выводе "длинного" числа из массива нам необходимо вывести 0058, иначе будет потеря цифр. Итак, незначащие нули также необходимо выводить. Процедура вывода имеет вид:

   Procedure WriteLong(Const A : Tlong);

   Var             ls, s : String; i : Integer;

   Begin

               Str(Osn Div 10, Is);

               Write(A[A[0]]; {выводим старшие цифры числа}

               For i := A[0] - l DownTo 1 Do

               Begin

                           Str(A[i], s);

                           While Length(s) < Length(Is) Do s := '0' + s;

                           {дополняем незначащими нулями}

                           Write(s)

               End;

               WriteLn

   End;

Третья задача. Предварительная работа по описанию способа хранения, вводу и выводу "длинных" чисел выполнена.

У нас есть все необходимые "кирпичики", например, для написания программы сложения двух "длинных" положительных чисел. Исходные числа и результат храним в файлах. Назовем процедуру сложения SumLongTwo.

Тогда программа ввода двух "длинных" чисел и вывода результата их сложения будет иметь следующий вид:

   Var A, B, C : Tlong;

   Begin

               Assign(Input, 'Input.txt'); Reset(Input);

               ReadLong(A); ReadLong(B) ;

               Close(Input);

               SumLongTwo(A, B, C);

               Assign(Output, 'Output.txt');

               Rewrite(Output);

               WriteLong(C);

               Close(Output)

   End.

Алгоритм процедуры сложения можно объяснить на простом примере. Пусть А=870613029451, В=3475912100517461.

i

A[i]

B[i]

C[1]

C[2]

C[3]

C[4]

1

9451

7461

6912

1

0

0

2

1302

51

6912

1354

0

0

3

8706

9121

6912

1354

7827

1

4

0

3475

6912

1354

7827

3476

Алгоритм имитирует привычное сложение столбиком, начиная с младших разрядов. И именно для простоты реализации арифметических операций над "длинными" числами используется машинное представление "задом наперед".

Результат: С = 3476782713546912.

Ниже приведен текст процедуры сложения двух "длинных" чисел.

   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>

                           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.ru/


© Рефератбанк, 2002 - 2017