Шестаков А.П.

Реализация работы с длинными числами с помощью абстрактного типа данных "Список"

{Организовать умножение длинных чисел,
 представив длинное число в виде списка;
 вычислить степень, используя такое представление.}

Program Sp_Ex1;
Type Uk = ^Zveno;
     Tsifra = 0..9;
     Zveno = Record
	       A : Tsifra;
	       B : Uk
	     End;
     Chislo = Uk;
Var  First, Second, Therd : Pointer;
     A, B, C : Chislo;
     S : String;

{Количество цифр в записи длинного числа}
Function Dlina(A : Pointer) : LongInt;
Var Vsp : LongInt;
    K : Chislo;
Begin
   K := A;
   Vsp := 0;
   While K <> Nil Do
   Begin
      Vsp := Vsp + 1;
      K := K^.B
   End;
   Dlina := Vsp
End;

Procedure ReadI(A : Pointer; N : LongInt; Var C : Tsifra);
Var I : LongInt;
    L : Chislo;
Begin
    I := 1;
    L := A;
    While I <= N Do
    Begin
       C := L^.A;
       I := I + 1;
       L := L^.B
    End;
End;

Procedure WriteI(Var A : Pointer; N : LongInt; C : Tsifra);
Var I : LongInt;
    L : Chislo;
Begin
    I := 1;
    L := A;
    While I < N Do
    Begin
       I := I + 1;
       L := L^.B
    End;
    L^.A := C
End;

Procedure Vvod(S : String; Var K : Pointer);
Var L, M : Chislo;
    Code, I : Integer;
Begin
    New(K);
    K := Nil;
    New(L);
    Val(S[1], L^.A, Code);
    L^.B := K;
    K := L;
    I := 2;
    While I <= Length(S) Do
     Begin
	M := L;
	New(L);
	Val(S[I], L^.A, Code);
	L^.B := M^.B;
	M^.B := L;
	I := I + 1
     End;
End;

{Вывод длинного числа на экран}
Procedure WriteDlinnoe(K : Pointer);
Var L : Chislo;
Begin
   L := K;
   While L <> Nil Do
   Begin
       Write(L^.A : 1);
       L := L^.B
   End;
   WriteLn
End;

{Умножение длинных чисел, цифры которых хранятся в списке}
Procedure Multiplication(A, B : Pointer; Var C : Pointer);
Var L, M : Chislo;
    Perenos, Perenos1 : Tsifra;
    AA, BB, Cc : Tsifra;
    I, J : LongInt;
Begin
    New(C);
    C := Nil;
  For I := 1 To Dlina(B) Do
  Begin
    New(L);
    L^.A := 0;
    L^.B := C;
    C := L;
  End;
    For I := 1 To Dlina(A) Do
     Begin
       Perenos := 0;
       ReadI(A, Dlina(A) - I + 1, Aa);
       For J := 1 To Dlina(B) Do
	 Begin
	   ReadI(B, Dlina(B) - J + 1, Bb);
	   ReadI(C, Dlina(C) - (I + J - 1) + 1, Cc);
	   Perenos1 := (Cc + Perenos + Bb * Aa) Div 10;
	   Cc := (Cc + Perenos + Bb * Aa) Mod 10;
	   Perenos := Perenos1;
	   WriteI(C, Dlina(C) - (I + J - 1) + 1, Cc);
	End;
	New(L);
	L^.A := 0;
	L^.B := C;
	C := L;
	WriteI(C, Dlina(C) - (I + J) + 1, Perenos);
    End;
    L := C;
    While (L^.A = 0) And (L^.B <> Nil) Do
    Begin
	C := L^.B;
	Dispose(L);
	L := C
    End;
End;

Function MensheRavno(A, B : Pointer) : Boolean;
Var M, N : Chislo;
Begin
     M := A;
     N := B;
     If Dlina(A) < Dlina(B)
     Then MensheRavno := True
     Else Begin
	      While (M^.A = N^.A) And (M^.B <> Nil) Do
	      Begin
		  M := M^.B;
		  L := L^.B
	      End;
	      MensheRavno := M^.A <= N^.A
	  End;
End;

Procedure Add(Var S : Pointer);
Var Perenos : 0..1;
    L : Chislo;
    N : LongInt;
Begin
    Perenos := 0;
    L := S;
    N := Dlina(S);
    ReadI(S, N, 
End;


Procedure Stepen(A, B : Pointer; Var C : Pointer);
Var L, M : Chislo;
    I : Pointer;
Begin
    New(C);
    C := Nil;
    New(L);
    L^.A := 1;
    L^.B := C;
    C := L;
    New(I);
    I := Nil;
    New(M);
    M^.A := 1;
    M^.B := I;
    I := M;
    While MensheRavno(I, B) Do
    Begin
       Multiplication(A, C, C);
       Adding(I)
    End;
End;

  {Основная программа}
Begin
  Write('Введите первое число:');
  ReadLn(S);
  Vvod(S, First);
  {WriteDlinnoe(First);}
  Write('Введите первое число:');
  ReadLn(S);
  Vvod(S, Second);
  Stepen(First, Second, Therd);
  WriteDlinnoe(Therd);
End.

 

Более подробно про списки и другие абстрактные типы данных можно прочесть в данном разделе.

 


Рейтинг ресурсов УралWeb

 

© Шестаков А.П., 1999-2009
Сайт создан в системе uCoz