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

C D

E

B

A F

В результате получен маршрут протяженности 50. Оптимальным является маршрут A, C, D, E, F, B, A, имеющий длину 48.39. Эвристический алгоритм привел к маршруту, который всего на 4 % больше оптимального.

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

Ниже приводится простой вариант процедур и функций длинной арифметики [2]. Такой подход неэкономичен как по памяти, так и по скорости. Память используется неэффективно, так как для записи каждой цифры используется полный байт. Длина числа не хранится, а находится при вычислениях либо просто не используется, что снижает скорость. К тому же все вычисления производятся в десятичной системе счисления. В системах счисления с основанием 2 операции целочисленного деления и нахождения остатка можно свести к битовым операциям сдвигов, которые выполняются быстрее. Тем не менее, приводимый вариант реализации длинной арифметики пригоден для большинства практических задач и прост в применении. Более полное описание проблем, связанных с длинной арифметикой, можно найти в [3].

Const

numlen = <максимальное количество знаков в длинных числах>;

{ для параметров циклов используются переменные integer,

если numlen>MaxInt, нужно использовать переменные типа word }

Type

number=array[1..numlen] of byte;

{ длинное число от младших разрядов к старшим;

переменной A типа number представлено число SUM(a[i]*10^(i-1))}

Procedure Set0(var n:number); {обнуление длинного числа}

Var

i: integer;

Begin

For i:=1 to numlen do

n[i]:=0;

End;

Procedure SetN(Var n: number; short: integer);

{занесение короткого числа в длинное}

Var

i: integer;

Begin

Set0(n); i:=1;

While short>0 do

begin

n[i]:=short mod 10;

short:=short div 10;

i:=i+1;

end;

End;

Procedure Move(n1:number; Var n2:number);

{пересылка длинного числа n2:=n1}

Var

i: integer;

Begin

For i:=1 to numlen do

n2[i]:=n1[i];

End;

Function Len(var n:number): integer;

{получение длины числа, для нуля длина 1 }

Var

i: integer;

Begin

For i:=numlen downto 1 do

if n[i]<>0 then

begin

Len:=i;

Exit;

end;

Len:=1;

End;

Procedure Show(var n:number);

{вывод числа и перевод строки }

Var

i: integer;

Begin

For i:=Len(n) downto 1 do

Write(n[i]);

WriteLn;

End;

Procedure AddShort(Var n: number; short: integer);

{прибавление короткого числа}

Var

i: integer;

Begin

i:=1;

While short>0 do

begin

short:=short+n[i];

n[i]:=short mod 10;

short:=short div 10;

i:=i+1;

end;

End;

Procedure MulShort(Var n: number; short: integer);

{умножение на короткое число}

Var

i,carry: integer;

Begin

carry:=0;

For i:=1 to numlen do

begin

carry:=carry+n[i]*short;

n[i]:=carry mod 10;

carry:=carry div 10;

end;

if carry<>0 then {диагностика переполнения}

Halt(1);

End;

Procedure DivShort(Var n: number; divisor: integer; Var rem: integer);

{деление на короткое число и получение остатка}

Var

i: integer;

Begin

rem:=0;

For i:=numlen downto 1 do

begin

rem:=rem*10+n[i];

n[i]:=rem div divisor;

rem:=rem mod divisor;

end;

End;

Procedure Add(Var n1,n2: number);

{прибавление длинного числа}

Var

i,carry: integer;

Begin

carry:=0;

For i:=1 to numlen do

begin

carry:=carry+n1[i]+n2[i];

n1[i]:=carry mod 10;

carry:=carry div 10;

end;

if carry<>0 then {диагностика переполнения}

Halt(1);

End;

Procedure Mul(Var n1,n2: number; Var n3: number);

{умножение длинных чисел}

Var

i1,i2,i3,len1,len2,carry: integer;

Begin

Set0(n3);

len1:=Len(n1);

len2:=Len(n2);

For i1:=1 to len1 do

For i2:=1 to len2 do

begin

i3:=i1+i2-1;

carry:=n1[i1]*n2[i2];

While carry>0 do

begin

carry:=carry+n3[i3];

n3[i3]:=carry mod 10;

carry:=carry div 10;

inc(i3);

end;

end;

End;

Function Cmp(Var n1,n2: number): integer;

{ сравнение чисел:

если n1<n2 выдает -1

если n1=n2 выдает 0

если n1>n2 выдает 1

}

Var

i: integer;

Begin

For i:=numlen downto 1 do

begin

if n1[i]<n2[i] then

begin

Cmp:=-1;

Exit;

end;

if n1[i]>n2[i] then

begin

Cmp:=1;

Exit;

end;

end

Cmp:=0;

End;

Дата добавления: 2014-01-11