« »

www.erudition.ru /
Программирование, базы данных /


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

""

, , , . , () , . , ,

30! = 265252859812191058636308480000000?

.

, , "". "" " ".

"" , . "" , , , "" . , , , , .

"" . .

30! = 265252859812191058636308480000000

:

30! = 2 * (104)8 + 6525 * (104)7 + 2859 * (104) + 8121 * (104)5 + 9105 * (104)4 + 8636 * (104)3 + 3084 * (104)2 + 8000 * (104)1 + 0000 * (104)0.

, . 1.

1

0

1

2

3

4

5

6

7

8

9

9

0

8000

3084

8636

9105

8121

2859

6525

2

, "" 10000-10 (- , - ), "" .

. 9 [0], " "? , . .

. !

. "" . .

Const MaxDig = 1000; { !}

Osn = 10000; { ,

}

Type Tlong = Array[0..MaxDig] Of Integer;

{ }

"" .

23851674 (Osn) 1000 ( ). ( Ch) . 2.

2

[0]

[1]

[2]

[3]

Ch

3

674

851

23

-

0

0

0

0

2

1

2

0

0

3

1-

1

23

0

0

8

2-

1

238

0

0

5

3-

2

385

2

0

1

4- : [1] "" [2]

2

851

23

0

6

5-

2

516

238

0

7

6-

3

167

385

2

4

7-

3

674

851

23

( ).

1. [0] () .

2. i i+1, [1]. , " ".

(): . . , A[i] [i+1], .. :

For i := A[0] DownTo 1 Do

Begin

A[i+l] := A[i+l] + (Longint(A[i]) * 10) Div Osn;

A[i] := (LongInt(A[i]) * 10) Mod Osn;

End;

23851674 6 " " . "" "7". "7" [1]. "" . .

i

[1]

[2]

[3]

ch

2

516

238

0

7

2

516

380

2

1

160

385

2

( ch) "" [1] [0].

:

Procedure ReadLong(Var A : Tlong);

Var ch : char; i : Integer;

Begin

FillChar(A, SizeOf(A), 0) ;

Read(ch);

While Not(ch In ['0'..'9']) Do Read(ch);

{ }

While ch In ['0'..'9'] Do

Begin

For i := A[0] DownTo 1 Do

Begin

{"" A[i]

A[i+l]}

A[i+l] := A[i+l] + (LongInt(A[i]) * 10) Div Osn;

A[i] := (LongInt(A[i]) * 10) Mod Osn

End;

A[1] := A[l] + Ord(ch) - Ord('0');

{ [1]}

If A[A[0]+1] > 0 Then Inc(A[0]);

{ , }

Read(ch)

End

End;

. "" .

, . "" , "" , , . . "" 128400583274 :

A[0]

A[1]

A[2]

A[3]

3

3274

58

1284

"" 0058, . , . :

Procedure WriteLong(Const A : Tlong);

Var ls, s : String; i : Integer;

Begin

Str(Osn Div 10, Is);

Write(A[A[0]]; { }

For i := A[0] - l DownTo 1 Do

Begin

Str(A[i], s);

While Length(s) < Length(Is) Do s := '0' + s;

{ }

Write(s)

End;

WriteLn

End;

. , "" .

"", , "" . . SumLongTwo.

"" :

Var A, B, C : Tlong;

Begin

Assign(Input, 'Input.txt'); Reset(Input);

ReadLong(A); ReadLong(B) ;

Close(Input);

SumLongTwo(A, B, C);

Assign(Output, 'Output.txt');

Rewrite(Output);

WriteLong(C);

Close(Output)

End.

. =870613029451, =3475912100517461.

i

A[i]

B[i]

C[1]

C[2]

C[3]

C[4]

1

9451

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.

"" .

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 := l To k Do

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

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

{ ?}

End;

If C[k+l] = 0 Then C[0] := k Else C[0] := k + l

End;

. "" (=, <, >, <=, >=).

Function Eq(A, B : TLong) : Boolean;

Var i : Integer;

Begin

Eq := False;

If A[0] <> B[0] Then Exit

Else Begin

i := l;

While (i <= A[0]) And (A[i] = B[i]) Do Inc(i);

Eq := i = A[0] + l

End

End;

> .

Function More(A, B : Tlong) : Boolean;

Var i : Integer;

Begin If A[0] < B[0] Then More := False

Else If A[0] > B[0] Then More := True

Else Begin

i := A[0];

While (i > 0) And (A[i] = B[i]) Do Dec(i);

If i = 0 Then More := False

Else If A[i] > B[i] Then More := True

Else More:=False

End

End;

Eq More.

Function Less(A, B : Tlong) : Boolean; {A < B}

Begin

Less := Not(More(A, B) Or Eq(A, B))

End;

Function More_Eq(A, B : Tlong) : Boolean; {A >= B}

Begin

More_Eq := More(A, B) Or Eq(A, B)

End;

Function Less_Eq(A, B : Tlong) : Boolean; {A <= B}

Begin

Less_Eq := Not More(A, B)

End;

, , . , 0, , 1, , 2 . . ? . 56784, 634. 2 , , , . . 56700, 567 2 "", . :

Function More(Const , : Tlong; Const sdvig : Integer) : Byte;

Var i : Integer;

Begin

If A[0] > B[0] + sdvig Then More := 0

Else

If A[0] < B[0] + sdvig Then More := l

Else Begin

i := A[0];

While (i > sdvig) And

(A[i] = B[i-sdvig]) Do Dec(i);

If i = sdvig Then Begin

More:=0;

{ }

For i := 1 To sdvig Do

If A[i] > 0 Then Exit;

More := 2;

{ , "" }

End

Else More := Byte(A[i] < B[i-sdvig])

End

End;

. . LongInt.

.

Procedure Mul(Const A : TLong; Const : Longlnt; Var : TLong);

Var i : Integer;

{ - }

Begin

FillChar (, SizeOf(), 0);

If K = 0 Then Inc([0]){ }

Else Begin

For i:= l To A[0] Do

Begin

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

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

End;

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

Else C[0]:= A[0]

{ }

End

End;

.

, , . .

: , , , . "" .

, "" . , 9 11 1 , 10000 9 .

Procedure Sub (Var A : TLong; Const B : TLong; Const sp : Integer);

Var i, j : Integer;

{ sp, }

Begin

For i := l To B[0] Do

Begin Dec(A[i+sp], B[i]);

j: = i;{*}

{ }

while (A[j+sp] < 0) and (j <= A[0]) Do

Begin{*}

Inc(A[j+sp], Osn) ;

Dec(A[j+sp+l]); Inc(j); {*}

end; {*}

{ .

, *,

, ,

,

.

" "}

{If A[i+sp]<0 Then Begin Inc(A[i+sp], Osn);

Dec (A[i+sp+l]);End;}

End;

i := A[0];

While (i > l) And (A[i] = 0) Do Dec(i);

A[0] := i

{ }

End;

, , . 100000001000000000000, 2000073859998.

. , .. .

( ) . :

Procedure Long_Div_Long(Const , : TLong; Var Res, Ost : TLong);

Begin

FillChar(Res, SizeOf(Res), 0); Res[0] := 1;

FillChar(Ost, SizeOf(Ost), 0); 0st[0] := 1;

Case More(A, B, 0) Of

0: MakeDel(A, B, Res, Ost);

{ , , - "" }

1: Ost:=A; { }

2: Res[l] := l; { }

End;

End;

? . . ,

1000143123567 |73859998

- 73859998 |----------

--------- |13541 ( )

261543143

- 221579994

----------

399631495

- 369299990

---------

303315056

- 295439992

----------

78750647

- 73859998

--------

4890649 ()

? (1, 3, 5 ..), , , ... ? , . , . , , "". *10, ( ) . , 564, 63 . , , . Down , Up , Ost .

Down

Up

= * ( (Down + Up) Div 2)

Ost = 564

0

10

315 = 63 * ( (0 + 10) Div 2)

C < Ost

5

10

441 = 63 * ( (5 + 10) Div 2)

C < Ost

7

10

504 = 63 * ( (7 + 10) Div 2)

C < Ost

8

10

567 = 63 * ( (8 + 10) Div 2)

C > Ost

8

9

504 = 63 * ( (8 + 9) Div 2)

C < Ost

, (Up + Down) Div 2, Ost . (Down) , () , (Up), .

. 27856, 354. 10, 10000.

Down

Up

Ost = 27856

0

10000

1770000

C > Ost

0

5000

885000

C > Ost

0

2500

442500

C > Ost

0

1250

221250

C > Ost

0

625

110448

C > Ost

0

312

55224

C > Ost

0

156

27612

C < Ost

78

156

41418

C > Ost

78

117

34338

C > Ost

78

97

30798

C > Ost

78

87

29028

C > Ost

78

82

28320

C > Ost

78

80

27966

C > Ost

78

79

27612

C < Ost

78, 27856 27612, .. 244.

. "": (More) (Mul) .

Function FindBin(Var Ost : Tlong; Const : TLong; Const sp : Integer) : Longint;

Var Down, Up : Word; C : TLong;

Begin

Down := 0;Up := 0sn;

{ }

While Up - l > Down Do

Begin

{

.

Up>Down. - .}

Mul(, (Up + Down) Div 2, );

Case More(Ost, C, sp) Of

0: Down := (Down + Up) Div 2;

1: Up := (Up + Down) Div 2;

2: Begin Up := (Up + Down) Div 2; Down := Up End;

End;

End;

Mul(B, (Up + Down) Div 2, C);

If More (Ost, C, 0) = 0 Then Sub(Ost, C, sp)

{ }

Else begin Sub (C, Ost, sp); Ost := C end;

FindBin := (Up + Down) Div 2;

{ }

End;

, sp . , , 635 15. ? 63 15 , . . 4, . . 635, 35. . . . 2 5. , ( ) 42, 5. , 10, 10000? , , .

Procedure MakeDel(Const , : TLong; Var Res, Ost : TLong);

Var sp : Integer;

Begin

Ost := A; { }

sp := [0] - [0];

If More(, , sp) = l Then Dec(sp);

{B * Osn > A, }

Res[0] := sp + l;

While sp >= 0 Do

Begin

{ }

Res[sp + 1] := FindBin(Ost, B, sp);

Dec(sp)

End

End;

. : 10-15- , .

1- . , ( 1, 2, 3).

2- . ( 4).

3- . ( 5, 6).

4- . ( 7). , . . , . "" .

1. : "" ; "" ; "" ..

2. "" . ?

3. "" , , . "" .

.. / "" /

http://www.comp-science.narod.ru/


?
?
?





Copyright © 2003—2005 «» 
    - Hostland.Ru