Lec_07

Вывод числа

14

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

Число 128400583274 будет в массиве Number представлено следующим образом:

Number [0] = 3

Number [1] = 3274

Number [2] = 58

Number [3] = 1284

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

Фрагмент кода на С++

15

1.// выводим последний элемент массива без дополнений

2.fprintf(f,"%d",Number[Number[0]]);

3.// цикл с предпоследнего элемента до первого

4.// (0-й элемент – это длина массива)

5.for (i = Number[0]-1; i>=1; i--)

6.{

7.osn = 10;

8.// дополняем незначащими нулями

9.// (цикл по разрядам основания)

10.while (Number[i]<(base/osn) && osn!=base){

11. fprintf(f,"0"); osn*=10;

12.}

13.// вывод значащих чисел элемента массива

14.fprintf(f,"%d",Number[i]);

15.}

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

16

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

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

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

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

Фрагмент кода на С++ (А+В)

17

int* SummaLongNumbers(int A[], int B[])

{

int *C = new int[MaxDig]; int k;

if (A[0]>B[0]) k=A[0]; else k=B[0]; for (int i=0; i<=k+1;i++) C[i]=0;

for (int i=1; i<=k;i++)

{

C[i+1]=(C[i]+A[i]+B[i])/base;

C[i]=(C[i]+A[i]+B[i])%base;

}

}

Фрагмент кода на Паскаль

19

{ Описание данных для длинной

арифметики }

const p=10;

lenit=30;

type

num=record it:array[1..lenit]of byte; len:integer;

end;

Фрагмент кода на Паскаль (А+В)

20

function sum(a,b:num):num; var div1,i,max:integer; begin

max:=a.len; if max<b.len then max:=b.len; for i:=a.len+1 to max do a.it[i]:=0;

for i:=b.len+1 to max do b.it[i]:=0; div1:=0;

for i:=1 to max do begin

sum.it[i]:=(a.it[i]+b.it[i]+div1) mod p; div1:=(a.it[i]+b.it[i]+div1) div p;

end;

i:=max;sum.it[i+1]:=div1;

if div1<>0 then sum.len:=i+1 else sum.len:=i; end;

Вычитание двух длинных чисел

21

Вычитание осуществляется аналогично сложению, с той лишь разницей, что осуществляется перенос “заимствования”.

Данный алгоритм реализован для условия A>B либо A=B.

Для A<B необходимо дополнительно реализовать алгоритм сравнения “длинных” чисел.

Алгоритм довольно простой:

Для каждого разряда мы добавляем 10, с учетом вычитания из старшего разряда — 1.

Это делается для упрощения вычитания разрядов.

Эта операция делается лишь в том случае, когда рассматриваемый разряд не является последним в массиве (первым в числе).

После вычитания разрядов мы проверяем получившееся число в данном разряде в массиве результата.

Ответ запишется в этот же массив, причем “зеркальным” способом