1.1 .
, .
:
;
;
.
1936 . , . , , , [1]. .
:
1) , , () . . , , ;
2) , ;
3) , () , . .
, , ( ) .
( 1) , , [2].
( 2) , [3].
, .
1 , 2, .
.
, , . (), , , . , [3]. , .
:
( );
|
|
; , ;
.
( ), -, .
1.2 [1]:
1) ;
2) (); , ;
3) ;
4) , , . ( ) () , ;
5) ( ) , ;
6) , .
.
1.3 . .
, , , , . , , , . : , . ( . ), , , .. . , , ( , -), , ( ). , .
, ( , , ), (), " ". :
() , ;
.
|
|
, , . , . () ..
, . [3]:
;
( ) : .
. , . , , .
() ( ) .
1.4 .
.
, . , . , , ( ) . , .
"".
. () . .
, ( ) , .
" " (input size) . , . , .. , .
" " " ", . , ( ) .
" " (rate of growth) " " (order of growth).
, , .
" " . , , . , , , , .
1.5 .
. , . .
|
|
. . 1.1.
1.1
. . | ||
. | ||
. : | ||
. | ||
. : |
. 1.1 :
1. -. , .
2. -.
, .
.
O
.
:
:
"":
, :
, , , (.. ).
, (. " " ).
( )
. , .. , , . " " "greatest common divisor", :
( " " , .. " " " ")
, , , , . , ( ), . : , .
, , .
:
int gcd (int a, int b) {
if (b == 0)
return a;
else
return gcd (b, a % b);
}
C++, :
int gcd (int a, int b) { return b? gcd (b, a % b): a;}
, :
int gcd (int a, int b) { while (b) { a %= b; swap (a, b); } return a;}
, :
, .
, , . . , .
|
|
, ( ), , .
.
.
1.6 .
. , . 1.1.
1.1
template <class T>
void bubbleSort(vector<T> &v) {
int in, out, tmp;
for(out = v.size()-1; out>0; --out) {
for(in = 0; in<out; ++in) {
if(v[in] > v[out]) {
tmp = v[in];
v[in] = v[out];
v[out] = tmp;
} } } }
, 1.1, . : .
( ) .
1.1 , 1- , 2- , .. , ( ) . , 45. , -, , .
, , , . , -, .. , . , . .
.
.
́ ́ n, [1]. , , , . , ( ) .
n, , :
- n (2, 3, 4, , n).
- p .
- 2 p n p ( p: 2 p, 3 p, 4 p, ).
- , p, p .
- 3 4, .
, . 3 p 2, . , , , p 2 , n. [2] , p 2 , 2 p, p 2.
: n A , 2 n, true. i:= 2, 3, 4,..., i 2 n: A [ i ] = true: j:= i 2, i 2 + i, i 2 + 2 i,..., j n: A [ j ]:= false : i, A [ i ] = true - 2 n.
/++
int n;vector<bool> prime (n+1, true);prime[0] = prime[1] = false;for (int i=2; i*i<=n; ++i) // valid for n < 46340^2 = 2147395600 if (prime[i]) for (int j=i*i; j<=n; j+=i) prime[j] = false;
˳:
1. .. : . / .. . : , 2005. 143 .
2. .. : . / .. . : , 2003. 108 .
3. . : / . , . , . , . ; . ., . .. . [3- .]. .: , 2013. 1328 .
|
|
4. . Java / . ; . . [2- .]. .: , 2013. 704 .