Сложение двух «длинных» чисел

Напишем подпрограмму сложения двух «длинных» положительных чисел, представленных в виде массивов а и b типа TLong, описанного выше.

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

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

Алгоритм процедуры сложения объясним на простом примере.

Пусть А = 870613029451, В = 3475912100517461.

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

I A[i] B[i] C[1] C[2] C[3] C[4]

1 451 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.

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

Var

A, B, C: Tlong;

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:=1 to k do

begin

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

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

end;

{производится сложение двух "длинных" чисел, причем целая часть от основания записывается в i+1 позицию, потому что в одном элементе массива хранится только четыре цифры}

if C[k+1]=0 then C[0]:=k {проверяется результат, выходит ли}

else C[0]:=k+1; {он за рамки разряда или нет}

end;

Begin

Assign (Input, ‘Input.txt');

{связывание файловой переменной с именем физического файла,

Input- имя файловой переменной, Input.txt- строковое выражение, определяющее имя физического файла}

Reset (Input); {открыть для ввода данных}

ReadLong (A); {обращение к процедурам ввода "длинных"}

ReadLong (B); {чисел А и В }

Close (Input); {закрыть файл}

SumLongTwo (A,B,C); {обращение к процедуре сложения двух "длинных" чисел}

Assign (Output, ‘Output. txt’);

{связывание файловой переменной с именем физического файла; Output - имя файловой переменной, Output.txt- строковое выражение, определяющее имя физического файла}

Rewrite (Output); {открыть для вывода на экран}

WriteLong (C); {обращение к процедурам вывода результата}

Close (Output); {закрыть файл}

end.

После изложения материала, слушателям предлагаются следующие вопросы для закрепления материала:

1. Что произойдет, если сумма A[i]+B[i] окажется больше максимально допустимого значения типа Tlong? Как можно этого избежать?

2. Напишите алгоритм сложения двух "длинных" чисел?

4. Умножение «длинного» числа на «короткое»

В подпрограмме для выполнения такого умножения будем использовать массив s, в качестве, как входного параметра, так и результата умножения. Массив имеет тип TLONG.

В первом элементе этого массива расположены четыре младшие цифры «длинного» числа. Переменная L будет содержать значение текущей длины этого массива.

«Короткое» число находится в целочисленной переменной п.

Несмотря на то, что и число п и элементы массива s можно представить в целом типе с максимальным числом разрядов (longint в Turbo-Pascal и long в С), максимального значения этого типа они достигать не могут, так как результат умножения любого ненулевого элемента массива s на п также не должен превышать максимальное значение того нее типа.

В приведенном ниже примере реализации подобной подпрограммы каждый элемент входного и выходного массива s должен быть меньше 10000, т.е. состоять не более чем из одной цифры 10000-ичной системы счисления (четырех десятичных цифр). Значение п нри этом может достигать 2³¹:10000 = 200000. При уменьшении количества цифр у элементов s, значение п может быть увеличено, и наоборот. Умножение производится последовательно от младшего разряда к старшему в 10000-ичной системе счисления, каждая цифра которой записывается как число в десятичной системе, смешанной с ней.

procedure Mult (var s: along; var L: longint; n: longint);

{умножаем массив s длины L на число n}

Var pr,i:longint;

Begin

pr:=0; {перенос в старший 10000-ичный разряд}

for i:= 1 to L do

begin

s[i]:= s[i]*n;

s[i]:= s[i]+pr;

pr:= s[i] div 10000;

s[i]:= s[i] mod 10000;

end;

while pr>0 do

begin

inc (L);

s[L]:= pr mod 10000;

pr:= pr div 10000

end

End;

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

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

Существует и другая возможность умножения “длинного” числа на “короткое”. Эта процедура очень похожа на процедуру сложения - точно так же моделируется вычислением в столбик, точно так же на каждом шаге определяется перенос в следующий разряд. Поэтому реализацию решения задачи можно вынести на самостоятельную работу учащимся.

Под “коротким” числом понимается целое число типа LongInt. "Длинное" чило располагается в массиве А типа TLong.

В первом элементе этого массива расположены четыре младшие цифры "длинного" числа.

Процедура будем иметь следующий вид:

Procedure Mul (Const A:TLong; Const K:LongInt; Var C:TLong);

Var i:Integer; {результат - значение переменной С}

Begin

FillChar (C, SizeOf (C), 0); {заполнение массива С нулями}

If K=0 Then Inc (C[0]) {умножение на ноль}

Else

Begin

For i:=1 To A[0] Do

Begin

{умножение длины массива А на чило K и "протаскивание" старшей цифры из C[i] в младшую цифру числа из C[i+1]}

C[i+1]:= (LongInt (A[i]*K+C[i]) Div Osn;

C[i]:= (LongInt (A[i]*K+C[i]) Div Osn;

End;

If C[A[0]+1] > 0 Then C[0]:=A[0]+1

Else C[0]:=A[0]

{определяем длину результат}

End;

End;

5. Умножение «длинного» числа на «длинное»

Для умножения двух «длинных» чисел существует несколько различных алгоритмов.

Один из них заключается в умножении каждой цифры первого множителя на каждую цифру второго и размещении каждого из таких произведений в соответствующем разряде результата. Если в каком-то разряде результата оказывается число, большее, чем максимальная цифра соответствующей системы счисления (9 в десятичной системе), то производится перенос в старший разряд. Такой алгоритм соответствует умножению двух чисел столбиком.

Приведем тексты программ, реализующих подобный алгоритм. Считывание «длинных» чисел производится из файла input.txt, а результат умножения помещается в файл output.txt. Входные данные в подобных задачах удобнее представлять в файле во избежание ошибки при вводе длинного числа с клавиатуры. Результат же по текстовому файлу проще анализировать.

Подпрограмма ReadData является примером ввода из файла «длинного» числа в случае, когда заранее неизвестна его длина. Применение в языке Turbo-Pascal логической функции SeekEoln вместо Eoln позволяет игнорировать пробелы в конце строки при вводе «длинного» числа. В языке С такую ситуацию требуется отслеживать самостоятельно.

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

Туре

Abyte = array [1..10000] of byte;

Tdest = array [0..20000] of word;

Var

aLen, hLen: word;

a, b: AByte;

с: ТDest;

Procedure ReadData;

var

с:char;

begin

Assign(input,'input.txt');

Reset(input);

aLen:=0;

bLen:=0;

while not SeekEoln do {пока не достигнут конец строки}

begin

read(с);

inc(aLen);

a [aLen]:=ord(c)-ord ('0')

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

end;

readln;

while not SeekEoln do

begin

read(c);

inc(bLen);

b[bLen]:= ord(c)-ord(' 0')

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

end;

Close(input)

end;

Procedure LongXLong;

var

i, j, p, q: word;

begin

p:=aLen+bLen;

FillChar (c, 2*(p+1), 0); {заполнение массива С нулями}

for i:= aLen downto 1 do

for j:=bLen downto 1 do

begin

{q — место в результате для произведения
i-ой и j-ой цифры каждого из множителей}

q:= p-i-j+1;

c[q]:= c[q]+a[i]+b[i];

if с[q]>9 then

begin

{перенос в следующий разряд}

c[q+1]:= c[q+l]+c[q] div 10;

c[q]:= c[q] mod 10

end

end;

{в с[0] поместим длину результата умножения}

if с[p]<>0 then c[0]:= p

else c[0]:= p-l

end;

Procedure WriteResult;

var

i: word;

begin

Assign(Output,'Output.txt');

Rewrite(Output);

for i:= c[0] downto i do write(c[i]);

Close(Output)

end;

{Основная программа}

Begin

ReadData;

LongXLong;

WriteResult

End.