Реферат: Задачи на длинную арифметику

Procedure Zero(Var A : DlChislo);

Var I : Integer;

Begin

For I := 1 To NMax Do A[I] := 0;

End;

Таким образом, длинное число записано в массив, где впереди (в качестве элементов с большими номерами) стоят незначащие нули. При выполнении действий и выводе ответа они не учитываются.

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

{Функция определения количества цифр в записи длинного числа}

Function Dlina(C : DlChislo) : Integer;

Var I : Integer;

Begin

I := NMax;

While (I > 1) And (C[I] = 0) Do I := I - 1;

Dlina := I

End;

При ее разработке было использовано следующее соображение: если число не равно нулю, то количество цифр в его записи равно номеру первой цифры, отличной от нуля, если просмотр числа осуществляется от старшего разряда к младшему. Если же длинное число равно нулю, то получается, что количество цифр в его записи равно одной, что и требовалось.

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

{Процедура умножения длинных чисел.

A, B — множители, C — произведение}

Procedure Multiplication(A, B : DlChislo; Var C : DlChislo);

Var I, J : Integer; P : Digit; VspRez : 0..99;

Begin

Zero(C);

For I := 1 To Dlina(A) Do {Цикл по количеству цифр

в первом числе}

Begin

P := 0; {Первоначально перенос равен нулю}

For J := 1 To Dlina(B) Do {Цикл по количеству цифр

во втором числе}