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

[kat297]

1) Составить программу деления числа a на число b, если a, b — многозначные числа.
2) Вычислить 100! + 2^100.

[Don Karleone]

Свои наработки.
А вообще http://programmersforum.ru/showthread.php?t=117978
я там книжку выкладывал, там найдете ответы на свои вопросы.

[kat297]

За книгу, конечно, спасибо. Надеюсь поможет...

[Don Karleone]

Сообщение от kat297

За книгу, конечно, спасибо. Надеюсь поможет...

Обязательно поможет. Только не забудте ее почитать.

[Kingdom_Reborn]

Задача для первого курса. Вот решение:

program example;

{$APPTYPE CONSOLE}

uses
  SysUtils;

const
  MaxLen = 1000;
  BASE = 10000;
  BASE_DIG = 4;

type
  TLong = record
    Length: Longint;
    Coef: Array[0..MaxLen] of Integer;
  end;

// Обнуляет число типа TLong
procedure Zero(var A: TLong);
begin
  FillChar(A.Coef, SizeOf(A.Coef), 0);
  A.Length := 1;
end;

// возвращает A + B
function Add(const A, B: TLong): TLong;
var
  C: TLong;
  I: Integer;
begin
  if A.Length < B.Length then
  begin
    Add := Add(B, A);
    Exit;
  end;
  Zero(C);
  for I := 0 to A.Length - 1 do
    C.Coef[I] := A.Coef[I] + B.Coef[I];
  for I := 0 to A.Length - 1 do
  begin
    Inc(C.Coef[I + 1], C.Coef[I] div BASE);
    C.Coef[I] := C.Coef[I] mod BASE;
  end;
  C.Length := A.Length;
  if C.Coef[A.Length] <> 0 then Inc(C.Length);
  Add := C;
end;

// возвращает произведение длинного числа на короткое
function Mul(const A: TLong; const B: Longint): TLong;
overload;
var
  C: TLong;
  I: Integer;
begin
  Zero(C);
  for I := 0 to A.Length - 1 do
    C.Coef[I] := A.Coef[I] * B;
  for I := 0 to A.Length - 1 do
  begin
    Inc(C.Coef[I + 1], C.Coef[I] div BASE);
    C.Coef[I] := C.Coef[I] mod BASE;
  end;
  C.Length := A.Length;
  if C.Coef[A.Length] <> 0 then Inc(C.Length);
  Mul := C;
end;

// возвращает произведение двух длинных чисел
function Mul(const A, B: TLong): TLong;
overload;
var
  C: TLong;
  I, J: Integer;
  temp, carry: Integer;
begin
  Zero(C);
  for I := 0 to A.Length - 1 do
  begin
    carry := 0;
    for J := 0 to B.Length - 1 do
    begin
      temp := A.Coef[I] * B.Coef[J] + C.Coef[I + J] + carry;
      carry := temp div BASE;
      C.Coef[I + J] := temp - carry * BASE;
    end;
    C.Coef[I + B.Length] := carry;
  end;
  I := A.Length + B.Length - 1;
  while (I > 0) and (C.Coef[I] = 0) do
    Dec(I);
  C.Length := I + 1;
  Mul := C;
end;

// деление длинного числа на короткое. Q - частное, R - остаток от деления
procedure Divide(const A: TLong; const B: Longint; var Q: TLong; var R: Integer);
overload;
var
  I: Integer;
  temp: Longint;
begin
  Zero(Q);
  R := 0;
  for I := A.Length - 1 downto 0 do
  begin
    temp := R * BASE + A.Coef[I];
    Q.Coef[I] := temp div B;
    R := temp - Q.Coef[I] * B
  end;
  I := A.Length - 1;
  while (I > 0) and (Q.Coef[I] = 0) do
    Dec(I);
  Q.Length := I + 1;
end;

не вместилось в один пост, см. далее

[Kingdom_Reborn]

// деление двух длинных чисел. Q - частное, R - остаток от деления
procedure Divide(A, B: TLong; var Q, R: TLong);
overload;
var
  N, M, I, J, K, junk: Longint;
  temp1, temp2, temp: Longint;
  scale, // коэффициент нормализации
  Guess, _r, // догадка для частного и соответствующий остаток
  borrow, carry: Integer;  // переносы
begin
  // если делитель больше делимого.
  if A.Length < B.Length then
  begin
    Zero(Q);
    R := A;
    Exit;
  end;
  // если делитель – число базового типа.
  if B.Length = 1 then
  begin
    Divide(A, B.Coef[0], Q, R.Coef[0]);
    R.Length := 1;
    Exit;
  end;
  Zero(Q);
  Zero(R);
  Inc(A.Length);
  A.Coef[A.Length] := 0;
  N := B.Length;
  M := A.Length - B.Length;
  scale := BASE div (B.Coef[N - 1] + 1);
  if scale > 1 then // нормализация
  begin
    A := Mul(A, scale);
    B := Mul(B, scale);
  end;
  I := M;
  J := N + I;
  while I > 0 do
  begin
    Dec(I);
    Dec(J);
    Guess := (A.Coef[J] * BASE + A.Coef[J - 1]) div B.Coef[N - 1];
    _r := (A.Coef[J] * BASE + A.Coef[J - 1]) mod B.Coef[N - 1];
    while _r < BASE do
    begin
      temp2 := B.Coef[N - 2] * Guess;
      temp1 := _r * BASE + A.Coef[J - 2];
      if (temp2 > temp1) or (Guess = BASE) then
      begin
        Dec(Guess);
        Inc(_r, B.Coef[N - 1]);
      end
      else Break;
    end;
    carry := 0;
    borrow := 0;
    for K := 0 to N - 1 do
    begin
      temp1 := B.Coef[K] * Guess + carry;
      carry := temp1 div BASE;
      Dec(temp1, carry * BASE);
      temp2 := A.Coef[K + I] - temp1 + borrow;
      if temp2 < 0 then
      begin
        A.Coef[K + I] := temp2 + BASE;
        borrow := -1;
      end
      else
      begin
        A.Coef[K + I] := temp2;
        borrow := 0;
      end;
    end;
    temp2 := A.Coef[N + I] - carry + borrow;
    if temp2 < 0 then
    begin
      A.Coef[N + I] := temp2 + BASE;
      borrow := -1;
    end
    else
    begin
      A.Coef[N + I] := temp2;
      borrow := 0;
    end;
    if borrow = 0 then
      Q.Coef[I] := Guess
    else
    begin
      Q.Coef[I] := Guess - 1;
      carry := 0;
      for K := 0 to N - 1 do
      begin
        temp := A.Coef[K + I] + B.Coef[K] + carry;
        if temp >= BASE then
        begin
          A.Coef[K + I] := temp - BASE;
          carry := 1;
        end
        else
        begin
          A.Coef[K + I] := temp;
          carry := 0;
        end;
      end;
      A.Coef[N + I] := A.Coef[N + I] + carry - BASE;
    end;
    K := A.Length - 1;
    while (K > 0) and (A.Coef[K] = 0) do
      Dec(K);
    A.Length := K + 1;
  end;
  while (M > 0) and (Q.Coef[M] = 0) do
    Dec(M);
  Q.Length := M + 1;
  if scale > 1 then
  begin
    Divide(B, scale, B, junk);
    Divide(A, scale, R, junk);
  end
  else R := A;
end;

// Возвращает n!
function Factorial(const N: Byte): TLong;
var
  I: Integer;
  F: TLong;
begin
  Zero(F);
  F.Coef[0] := 1;
  for I := 2 to N do
    F := Mul(F, I);
  Factorial := F;
end;

// конвертация строки в число типа TLong
function Convert(S: String): TLong;
var
  I, K, d: Integer;
  _S: String;
  C: TLong;
begin
  Zero(C);
  d := Length(S);
  while d mod BASE_DIG <> 0 do  // добавляем нули слева
  begin
    S := '0' + S;
    Inc(d);
  end;
  K := 0;
  _S := '';
  for I := d downto 1 do
  begin
    _S := Concat(S[I], _S);
    if (I - 1) mod BASE_DIG = 0 then
    begin
      C.Coef[K] := StrToInt(_S);
      Inc(K);
      _S := '';
    end;
  end;
  C.Length := K;
  Convert := C;
end;

опять не вместилось, см. далее...

[Kingdom_Reborn]

// печать длинного числа
procedure Print(const A: TLong);
var
  I: Integer;
  d: Integer;
begin
  for I := A.Length - 1 downto 0 do
  begin
    if I <> A.Length - 1 then
    begin
      d := Length(IntToStr(A.Coef[I]));
      if d < BASE_DIG then
        while d <> BASE_DIG do
        begin
          Write('0');
          Inc(d)
        end;
    end;
    Write(A.Coef[I]);
  end;
  WriteLn;
end;

// декремент
procedure LongDec(var A: TLong);
var
  I: Integer;
begin
  Dec(A.Coef[0]);
  for I := 0 to A.Length - 1 do
    if A.Coef[I] < 0 then
    begin
      Inc(A.Coef[I], BASE);
      if I <> A.Length - 1 then Dec(A.Coef[I + 1]);
    end;
  if (A.Coef[A.Length - 1] = 0) and (A.Length > 1) then Dec(A.Length);
end;

// возвращает A^K
function Pow(A, K: TLong): TLong;
var
  B, Q: TLong;
  R: Integer;
begin
  Zero(B);
  B.Coef[0] := 1;
  while not ((K.Length = 1) and (K.Coef[0] = 0)) do
  begin
    Divide(K, 2, Q, R);
    if R = 0 then
    begin
      K := Q;
      A := Mul(A, A)
    end
    else
    begin
      LongDec(K);
      B := Mul(B, A)
    end;
  end;
  Pow := B;
end;

var
  A, B, Q, R, N, M, K, L: TLong;
  S: String;
begin
  WriteLn('A:');
  ReadLn(S); // вводим A
  A := Convert(S); 
  WriteLn('B:');
  ReadLn(S); // вводим B
  B := Convert(S);
  Divide(A, B, Q, R);
  WriteLn;
  WriteLn('Q:');
  Print(Q); // печатаем частное от деления A на B
  WriteLn('R:');
  Print(R); // печатаем остаток
  N := Factorial(100);
  M := Convert('2');
  K := Convert('100');
  M := Pow(M, K);
  L := Add(N, M);
  WriteLn('100! + 2^100:');
  Print(L); // печатаем 100! + 2^100
  ReadLn;
end.

P. S. Писал на Delphi 7.
P. P. S. Хоть и немного коряво написано, но работает

[kat297]

О Боже... О_О

[Kingdom_Reborn]

Сообщение от kat297

О Боже... О_О

Ну а вы что думали?
Длинная арифметика она на то и длинная

Это правильное решение, все функции я проверял на тестах.