.


:

:



,



( , )

:

































 

 

 

 
FAQ

..

⇐ 12345678 ⇒



, , , . , () , . , ,

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

                   
                   

, "" 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
        -
         
          1-
          2-
          3-
          4- : [1] "" [2]
          5-
          6-
          7-
           

( ).
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
         
         
         

( 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]
       

"" 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]
             
             
             
             

, . "" " ".

: = 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]) EndEnd;

. . 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
    315 = 63 * ((0 + 10) Div 2) C < Ost
    441 = 63 * ((5 + 10) Div 2) C < Ost
    504 = 63 * ((7 + 10) Div 2) C < Ost
    567 = 63 * ((8 + 10) Div 2) C > Ost
    504 = 63 * ((8 + 9) Div 2) C < Ost

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

. 27856, 354. 10, 10000.

Down Up Ost = 27856
      C > Ost
      C > Ost
      C > Ost
      C > Ost
      C > Ost
      C > Ost
      C < Ost
      C > Ost
      C > Ost
      C > Ost
      C > Ost
      C > Ost
      C > Ost
      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) EndEnd;

. : 10-15- , .

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

2- . ( 4).

3- . ( 5, 6).

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

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

2. "" . ?

3. "" , , . "" .

 

 

, .. . . , , .

( . ": ".) n. n. , , n , (, b) n. ( .) , ( ) log2 n ( C * log2 n C; log2 n , 2, n).

.

k:= n; b:= 1; c:= a; {a n = b * (c k)} while k <> 0 do begin if k mod 2 = 0 then begin k:= k div 2; c:= c * c end else begin k:= k - 1; b:= b * c end end;

( ) ( k , ), k .

( .., .. : . : . . 2- . .: , 1990. 416 .)

m, , . , .

1. m ( , ), . , m , () ; m , . .

2. , , , ; .

3. , , . A. , . x, ( 10 * a + x) x . x .

4. x A, , B. , b. y, y B. y .

4- . , .

.

. : 13'83'84 , , . 3, 32 < 13, 42 > 13. 9 13, 4. 4 , A = 483. , . . 3, a = 6. x, x 483. 7, 67 * 7 = 469 483, 68 * 8 = 544 483. , 7.

469 483, 14. , b = 1484. , .. 37, B = 74. y, y 1484. 2, 742 * 2 = 1484. 2 . 372.

, , 00. ; , .

(, ): 1) ; 2) ; 3) ; 4) ; 5) , (, , , , , ).

:

Type Tsifra = 0..9; Chislo = Array[1..1000] Of Tsifra;

. .

(, ): 1) ; 2) ; 3) ; 4) ; 5) , (, , , , , ).

:

Type Tsifra = 0..9; Chislo = Record Znak: 0..1; {0 - "", 1 - ""} Ch: Array [1..1000] Of Tsifra End;

. .

⇐ 12345678 ⇒


:

: 2017-02-11; !; : 563 |

:

:

, .
==> ...

1546 - | 1401 -


© 2015-2024 lektsii.org - -

: 0.059 .