(CIDR) .
IP- CIDR , . CIDR , , . , . IP- 2 (. 15.5). , (32 - ) . .
, 51,52 53, . . :
--- ;
--- .
---, , .
3. . , . . .
. , , ( ) , . , , , . .
:
3.
.
.
i - (i = 1,..., N i):
i N ;
[i], i- .
N 1- A [N] .
, , () .
:
i 1 N 1
K: = i
max: = A [ i ]
j i + 1 N
A [ i ] > max
max: = A [ j ]
K: = j
A [ K ]: = A [ i ]
A [ i ]: = max
j i + 1 N i+1 N.
|
|
|
= {0, 1, 9, 2, 4, 3, 6, 5}.
.
1) 0, 1, 9, 2, 4, 3, 6, 5
2) 9, 1, 0, 2, 4, 3, 6, 5
3) 9, 6, 0, 2, 4, 3, 1, 5
4) 9, 6, 5, 2, 4, 3, 1, 0
5) 9, 6, 5, 4, 2, 3, 1, 0
6) 9, 6, 5, 4, 3, 2, 1, 0
7) 9, 6, 5, 4, 3, 2, 1, 0
8) 9, 6, 5, 4, 3, 2, 1, 0
, .
(N 1) , (N 2), (N 3),..., . :
N 1 + N 2 + N 3 +... + 1 = N (N 1) / 2 = (N2 N) / 2.
. . (N 1), , . . N. N (N 1) , , 2.
(N 1). .
, :
i- (i = 1,..., N 1) :
1. . , .
2. , ,.... Ni N i + 1, . i- .
N-e . , .
, .
.
:
i 1 N 1
j 1 N i
A [ j ] < A [ j + 1 ]
x: = A [ j ]
A [ j ]: = A [ j + l ]
A [ j + l ]: = x
A = {0, 1, 9, 2, 4, 3, 6, 5}.
1) 1, 9, 2, 4, 3, 6, 5, 0
2) 9, 2, 4, 3, 6, 5, 1, 0
3) 9, 4, 3, 6, 5, 2, 1, 0
4) 9, 4, 6, 5, 3, 2, 1. 0
5) 9, 6, 5, 4, 3, 2, 1, 0
6) 9, 6, 5, 4, 3, 2, 1, 0
7) 9, 6, 5, 4, 3, 2, 1, 0
(N 2 - N) / 2.
. ( ) , . . (N2N)/2.
* . , - , . , 0, .
() , . .
: =
: = N 1
=
: =
R: = K
j 1 R
A [ j ] < A [j + 1]
x: = A [ j ]
|
|
|
A [ j ]: = A [ j + l ]
A [ j + l ]: = x
: =
K: = j
, , . R , .
- ,
.
.
Ÿ : 0,
. , -1.
function SearchPer (Arr: array of Integer; n, v: Integer): Integer;
var
i: Integer;
begin
Result:= -1;
for i:= 1 to n do
if Arr [i] = v then begin
Result:= i;
Exit;
end;
end;
- .
: Up
(Up:= 0), Down -
(Down:= n, n - ), Mid - .
, Mid, ; Mid,
, Up Mid + 1;
, ,
, Down:= Mid - 1. ,
, , Up Doun.
function SearchBin (Arr: array of Integer; v, n: Integer): Integer;
var
Up, Down, Mid: Integer;
Found: Boolean;
begin
Up:= 0; Down:= n;
Found:= False; Result:= -1;
repeat
Mid:= Trunc ((Down - Up) / 2) + Up;
if Arr [Mid] = v then
Found:= True
else
if v < Arr [Mid] then
Down:= Mid - 1
else
Up:= Mid + 1;
until (Up > Down) or Found;
if Found then
Result:= Mid;
end;
