1. . , , , ? . , , . n . n . , log2n. , , .
. . :
( );
;
.
, Xoapa ( ), , .
, n ( ); ' .
. . , , . '.
: , , , .
1, a2,..., n, n . , .
2. . . (a1 > 2), . , , . . ϳ n , , . , , .. . , . .
n , -1 ( ).
ʳ n-1 1. n(n-l)/2, O(n2/2). ʳ n2/2.
|
|
|
' (n = 5) ' :
4,2,7,9, 1. .
ϳ (j = 1) :
1- : 4 > 2 , 4 2 , 2,4,7,9, 1;
2- : 4 > 7 , , : 2, 4, 7, 9, 1;
3- : 7 > 9 , 2, 4, 7, 9, 1;
4- : 9 > 1, 9 1 , 2, 4, 7, 1, 9.
ϳ n - 1 .
j = 2 (2, 4, 7, 1) , 2, 4, 1, 7, 9.
j = 3 . 2,1,4, 7,9.
j = 4 1, 2,4, 7, 9.
.
program MetodObminu;
Uses
crt;
Const
n = 10; { -}
Var
: array [l..n] of integer; {mun }
, j: integer;
c: integer;
Begin
clrscr;
for i:= 1 to n do
Begin
write (' ');
readln(a[i]);
end;
for j:= 1 to n - 1 do
for i:= 1 to n -j do
if a[i] > a[i + 1] then
Begin
c:= a[i + 1];
a[i + l]:=a[i];
a[i]:= c;
end;
writeln(' ');
for i:= 1 to n do writeln(a[i]);
End.
1. . . ' Turbo Pascal Delphi.
3. . , . , . I n-l . .
n , -1 ( ). .
ʳ O(n2/2). ʳ n.
' (4,2, 7, 9, 1) .
ϳ (j = 1) 1 (4). , 1, 2, 7, 9, 4. .
(j = 2) (2, 7, 9, 4) . 1,2,7, 9,4.
j = 3 1, 2,4,9,7.
j = 4 , 1, 2, 4, 7, 9.
.
program MetodMinEl;
Uses
crt;
Const
n = 10;
Var
a: array [l..n] of integer;
i,j, min, c: integer;
Begin
clrscr;
for i:= 1 to n do
Begin
write (' ');
readln(a[i]);
end;
for j:= 1 to n- 1 do
Begin
min:= j;
for i:= j + 1 to n do
If a[min] >a[i] then
|
|
|
Begin
c:= a[min];
a[min]:= a[i];
a[i]:= c;
end;
end;
writeln( ');
for i:= 1 to n do writeln(a[i]);
readln
end.
2. . .
4. . , . . '. , , , . , . , . I , . ..
O(n2/4).
4, 2, 9, 7, 1 .
ϳ (j = 1) :
1- : 4 > 2, ' 2 4, 4 , 2 4. 2, 4, 9, 7, 1;
2- : 2 > 9 , 2, 4, 9, 7, 1;
3- : 2 > 7 , 2, 4, 9, 7, 1;
4- : 2 > 1, ' 1 2; 2, 4, 9, 7 , 1 2. 1, 2, 4, 9, 7.
2, 4, 9, 7 ..
.
program MetodVstavok;
Uses
crt;
Const
n = 10;
Var
: array [1.. n] of integer;
i,j, k, c: integer;
Begin
clrscr;
for i:= 1 to n do
Begin
write (' ');
readln(a[i]);
end;
for i:= 2 to n do
Begin
c:= a[i]: [ }
j:=l;
while c > a[j] do [ )
j:= j + i;
for k:= i - 1 downto j do
a[k + 1]:= a[k];
[j]:=c;
end;
writeln('opoa ');
for i:= 1 to n do write(a[i],' ');
readln
end.
. . , . .
