close

Вход

Забыли?

вход по аккаунту

?

Zapiska

код для вставкиСкачать
??????????
1 ?????? ?1.7_______________________________________________3
1.1. ?????????? ?????? ? ?? ??????________________________
1.2. ???????? ???????? ??????___________________________
1.3. ?????????????? ?????????__________________________
1.4. ?????????? ????????????_____________________________
2 ?????? ?2.45_______________________________________________6
2.1. ?????????? ?????? ? ?? ??????________________________
2.2. ???????? ???????? ??????___________________________
2.3. ?????????????? ?????????__________________________
2.4. ?????????? ????????????_____________________________
3 ?????? ?3.14______________________________________________12
3.1. ?????????? ?????? ? ?? ??????________________________
3.2. ???????? ???????? ??????___________________________
3.3. ?????????????? ?????????__________________________
3.4. ?????????? ????????????_____________________________
4 ?????? ?4.21______________________________________________18
4.1. ?????????? ?????? ? ?? ??????________________________
4.2. ???????? ???????? ??????___________________________
4.3. ?????????????? ?????????__________________________
4.4. ?????????? ????????????____________________________
?????? ?????????????? ??????????_______________________21
1 ?????? ?1.7
1.1 ?????????? ?????? ? ?? ??????
??????? : ??? ??????????????? ??????. ??????????? ??? ???????? ?? ???????????. ??? ???????? ???????? ?????? ????? ?????. ????? ??????????? ???????? ????? ???????????? ?????????? ?????????.
1.2 ???????? ???????? ??????
??? ?????????? ?????? ????????? ????? ???????????? ??????????????? ?????? ?? ????????? ??????????:
type sp=^uk;
uk=record;
data: integer;
next,pred:sp;
end;
????????? ???????? ?????????????? ???? data(?????? ????? ?????), ? ????? ???? next ? prev - ????????? ?? ????????? ? ?????????? ???????? ??????.
1.3 ?????????????? ?????????
??? ??????? ?????? ???????? ????????? ?????????: create_twodirectlist(???????? ??????), sort(??????????), printf(?????? ??????). ?????? ????????? ??? ?????? ?????? ???????. ???????????? ?????? ???????? ? ??????????, ?????????? ????? ??????? 0.
??? ???????? ?????? ??????????? ????????? create_twodirectlist.
??????? ????????? create_twodirectlist:
procedure create_twodirectlist(var head,ends: sp;s: integer);
var x,p: sp;
begin
if head=nil then
begin
new(x);
x^.data:=s;
x^.next:=nil;
x^.pred:=nil;
head:=x;
end_sp:=x;
p:=head;
end
else
begin
new(x^.next);
x:=x^.next;
x^.data:=s;
x^.next:=nil;
x^.pred:=p;
p:=x^.next;
end_sp^.next^.pred:=end_sp;
end_sp:=end_sp^.next;
end_sp^.next:=nil;
end;
end;
????? ????????? ?????? ?????????? ? ????????? sort, ??????? ????????? ???????? ?????????:
procedure sort(p: sp);
var buf:sp;
inf: integer;
begin
while p<>nil do
begin
buf:=p^.next;
while buf<>nil do
begin
if p^.data>buf^.data then
begin
inf:=buf^.data;
buf^.data:=p^.data;
p^.data:=inf;
end;
buf:=buf^.next;
end;
p:=p^.next;
end;
end;
1.4 ?????????? ????????????
????????? ?????????? ???????? ?? ??????? 1.
??????? 1 - ?????? ????? ??????????
2 ?????? ?2.45
2.1 ?????????? ?????? ? ?? ??????
???????: ???????? ?????????? ??????? ??? ?????? ? ?????? ??????? ????? ?????. ????????????? ????????: ????????, ?????????, ?????????, ???????. ??????????? ????? ??????????? ? ???? ????? ????.
?????? ????? ????????? ????? ??? ??????, ????? ??????????????? ? ????? ? ???????? ? ?????? ????.
??? ??????? ?????? ?????? ???????? ??????, ?????????? ????????? ????????? ???????? ??? ???????. ????? ?????????? ??????????? ???????? ????????? ??? ?????? ? ?????.
2.2 ???????? ???????? ??????
??? ?????????? ?????? ????????? ?????????? ???????????? ???, ??????? ????????? ?????????:
type long=^el;
el = record
data:integer;
next,prev:long;
end;
????????? ???????? ?????????????? ???? data(?????? ????? ?????), ? ????? ???? next ? prev - ????????? ?? ????????? ? ?????????? ???????? ????.
2.3 ?????????????? ?????????
?????? ??????? ?????? operations, ??????? ????? ???????? ?? ????????, ??????????? ???????? ??? ???????(summ,dec,double,delenie).
???????, ????????, ???????? ???????? (????????? summ). ??? ????? - ??????? ??????. ???? ?????????: ???? ?? 2-? ????? ? ????????? ??????????????? ????????, ??? ???????? ????? "? ???" ?????? ?????????????? ??????????. ??????? ???? ? ??? ????????? ????????. ??? ??????????? ???????? ??????? ??????? ??????.
??????? ?????? operations:
unit operations;
interface
implementation
type long=^el;
el = record
data:integer;
next,pred:long;
end;
procedure insert(var b:long; c:integer);
var t:long;
begin
new(t);
t^.data:=c;
t^.next:=b;
t^.pred:=nil;
b:=t;
end;
procedure summ(a,b:long; var up:long);
var x,y,z:integer;
begin
z:=0;
up:=nil;
while (a<>nil) or (b<>nil) or (z<>0) do
begin
if a<>nil then
begin
x:=a^.data;
a:=a^.next;
end
else
x:=0;
if b<>nil then
begin
y:=b^.data;
b:=b^.next;
end
else
y:=0;
insert(up,(x+y+z) mod 10);
z:=(x+y+z) div 10;
end;
end;
procedure dec(a,b:long; var up:long);
var x,y,z:integer;
begin
z:=0;
up:=nil;
while (a<>nil) or (b<>nil) or (z<>0) do
begin
if a<>nil then
begin
x:=a^.data;
a:=a^.next;
end
else
x:=0;
if b<>nil then
begin
y:=b^.data;
b:=b^.next;
end
else
y:=0;
insert(up,(x-y-z) mod 10);
z:=(x-y-z) div 10;
end;
end;
procedure double(a:long; b:byte; var up:long);
var x,y,z:integer;
begin
z:=0;
up:=nil;
while (a<>nil) do
begin
if a<>nil then
begin
x:=a^.data;
a:=a^.next;
end;
y:=b;
insert(up,(x*y+z) mod 10);
z:=(x*y+z) div 10;
end;
if z<>0 then insert(up,z);
end;
procedure delenie(a,b:long; var up:long);
var x,y,z:integer;
begin
z:=0;
up:=nil;
while (a<>nil) or (b<>nil) or (z<>0) do
begin
if a<>nil then
begin
x:=a^.data;
a:=a^.next;
end
else
x:=0;
if b<>nil then
begin
y:=b^.data;
b:=b^.next;
end
else
insert(up,(x div y+z) mod 10);
z:=(x div y+z) div 10;
end;
end;
begin
end.
?????? ???????????? ?????? ? ?????????? 2 ????? ????? ?????.
??? ??????????? ??? ??? ??????. ? ??????? ????????? init ??????? ? ??? ??????????????? ?????? ? ?????. ??????? ????????? init:
procedure init(var b:long);
var c:string;
i:integer;
begin
readln(c);
for i:=1 to length(c) do
insert(b,ord(c[i])-ord('0'));//????????? ?????????? ? ???
end;
????? ???????????? ???????????? ????? ???????? ??? ???????. ? ???????????? ? ??????? ??????????? ??????????????? ????????. 2.4 ?????????? ????????????
???????????? ?????? 2 ????? ????? ?????. ????? ???????? ????????.
????????? ?????????? ????????? ???????? - ??????? 2,3,4,5
??????? 2 - ?????????? ???????? ???????? ?????
??????? 3 - ?????????? ???????? ????????? ?????
??????? 4 - ?????????? ???????? ????????? ?????
??????? 5 - ?????????? ???????? ??????? ?????
3 ?????? ?3.14
3.1 ?????????? ?????? ? ?? ??????
??????: ???? ??? ??????. ??????? ???????? ????????? ?????????? [a,b].
??? ??????? ?????? ?????? ?????????? ??????????? ????????? ?????????? ? ???????? ????????? ??????. ??? ???? ????? ????????? ????????? ??????? ? ??? ??????.
3.2 ???????? ???????? ??????
? ?????? ????????? ?????????? ??????????? ??? ??????. ???????? ??? ????????? ???????????? ????:
type
TKey = integer;
TBalance = -1..1;
AVLTree = ^AVLNode;
AVLNode = record
key: TKey;
left, right: AVLTree;
balance: TBalance;
end;
????????? ???????? ?????????????? ???? key, ? ????? ???? left ? right - ????? ?????? ???????. ??? ???????? ??????? ????? ?????????????? ???? ???????? ?????? ??????.
3.3 ?????????????? ?????????
??????? ????????? ????????? : DelTree(???????? ????????? ?? ????????? ??????????), InsertNode(??????? ???????? ? ??????), Lkp(????????? ?????? ??????, ?????? ?????).
?????????? ?????? ?????????.
InsertNode - ????????? ??????? ????????. ?????????? ???????? ? ??? ?????? ?????????????? ??? ? ? ????????, ??????????? ?????? ? ???, ??? ????? ????????????? ????????? ???????????? ? ??????. ??????? ?????? ?????????? ??????????, ??????? ?????????? ???????? ?? ???????, ???? ??, ?? ??????? ???? ???????. ???? ?????????, ????? ??????? ??? ??????????: ???? ?? ????? ? ?????? ??????(???? LL, LR; ???? RR,RL).
??????? ????????? InsertNode:
procedure InsertNode(var Tree: AVLTree; const dat: type_data; var flag: boolean);
var node1,node2:AVLTree;
begin
if tree=nil then
begin
new(tree);
flag:=true;
with tree^ do
begin
data:=dat;
left:=nil;
right:=nil;
balance:=0;
end;
end
else
if tree^.data>dat then
begin
InsertNode(tree^.left,dat,flag);
if flag then
case tree^.balance of
1: begin tree^.balance:=0; flag:=false; end;
0: tree^.balance:=-1;
-1: //??????? ??????
begin
node1:=tree^.left;
if node1^.balance=-1 then //??? ?????????? LL
begin
tree^.left:=node1^.right;
node1^.right:=tree;
tree^.balance:=0;
tree:=node1;
end
else
//????? LR
begin
node2:=node1^.right;
node1^.right:=node2^.left;
node2^.left:=node1;
tree^.left:=node2^.right;
node2^.right:=tree;
if node2^.balance=-1 then
tree^.balance:=1
else
tree^.balance:=0;
if node2^.balance=1 then
node1^.balance:=-1
else
node1^.balance:=0;
tree:=node2;
end;
tree^.balance:=0;
flag:=false;
end
end
end
else if tree^.data<dat then
begin
InsertNode(tree^.right,dat,flag);
if flag then
case tree^.balance of
-1: begin tree^.balance:=0; flag:=false; end;
0: tree^.balance:=1;
1: //??????? ??????
begin
node1:=tree^.right;
if node1^.balance=1 then// ??? ?????????? RR
begin
tree^.right:=node1^.left;
node1^.left:=tree;
tree^.balance:=0;
tree:=node1;
end
else // ????? RL
begin
node2:=node1^.left;
node1^.left:=node2^.right;
node2^.right:=node1;
tree^.right:=node2^.left;
node2^.left:=tree;
if node2^.balance=1 then
tree^.balance:=-1
else
tree^.balance:=0;
if node2^.balance=-1 then
node1^.balance:=1
else
node1^.balance:=0;
tree:=node2;
end;
tree^.balance:=0;
flag:=false
end
end
end
end;
DelTree - ???????? ?????????? ??? ? ????????, ????????. ? ?????? (?????????????? ?????????). ??? ? ? ????????? ?????????? ???????? ??????? ??????? ?? ??????.
3.4 ?????????? ????????????
??????? ???????????? ?????? ?????????? ????????? ??????, ????? ???????, ?? ??????? ?????????? ??????? ????????. ????????? ?????? ???????? ??????? ?? ??????? 6.
??????? 6 - ????????? ???????? ????????? ??? ??????
4 ?????? 4.21
4.1 ?????????? ?????? ? ?? ??????
???????: ?????????? ?????????? ????? ?????????????????????. ???????????? ???????? ?? ????? ???????, ??? 318.
?????? ???????? ??????? ?? ????????? ???????????? ????????????????. ??????????? ?? ? ?????????:
????? ???? ??? ??????????????????. ??? ?????????? ??? ??????????:
?????????????????? 1 ???????? ????? ???????? ???????, ? ?????????????????? 2 ??? ????????? ???????. 2) ??????? ????? ????? ???????? ?????? ??????? ? ?????? ??????. 3) ???? ??????? ??????? a. 4) ? ???????? ??????? a[i,j] ????? ???????? ????? ?????????? ????? ????????????????????? ??? ??????????????????? x[1..i] ? y[1..j].
??????? ??????? a[i,j] ????? ???????? ?? ???????????? ???????:
{�(0, ???? i=0 ??? j=0@a[i-1,j-1]+1 , ???? x[i]=y[j] @max?(a[i-1,j],a[i,j-1]), ???? x[i]?y[j] )�
3.2 ???????? ???????? ??????
? ?????? ????????? ?????????? ??????????? ????????? ??????, ??????? ????? ????????? ?????????? ????????? ?????????
var x,y,z:string;//x ? y -??????????????????, z - ????? ????????? ??? a:array[0..100,0..100] of byte;//?. ? ? ??????? ?? ?????? ???????????? ?????? ???????????????????, ?? ????? ??????? ??? ?????????????????? ?? ????????? 100 ?????????
i,j:byte;//???????? ?????? ? ???????
4.3 ?????????????? ?????????
????????? ?????? ?????? ????????? ???????: ???????????? ?????? ??? ?????????????????? ? ?????????? (??? ?????? - ??????). ????? ??????? ?????? ?????????? ? ????????? lcs, ? ??????? ?? ????????? ??????? ?? ???????????? ??????? ??????????? ???? ? ????? "????????" ??? ???????? ?????????? ????????.
??????? ????????? lcs:
procedure lcs(a:array[0..100,0..100] of byte; x,y: string); begin
for j:=1 to length(x)+1 do //???????? ?????? ?????? ? ??????? ??????
begin
a[1,j]:=0;
end;
for i1:=2 to length(y) do
begin
a[i1,1]:=0;
end;
for i:=2 to (length(x)+1) do
for j:=1 to (length(y)+1) do
begin
if (x[i]=y[j]) then
a[i,j]:=a[i-1,j-1]+1
else
if (a[i-1,j]>=a[i,j-1]) then
a[i,j]:=a[i-1,j]
else
a[i,j]:=a[i,j-1];//????? ??? ????????? ? ????????? ????????
end;
z:='';//???????? ???
i:=length(x);
j:=length(y);
while (i>0) and (j>0) do
if x[i]=y[j] then
begin
z:=x[i]+z; i:=i-1; j:=j-1
end
else
if a[i-1,j]>=a[i,j-1] then
i:=i-1
else j:=j-1;
writeln('???----> ');
write(z);
end;
4.4 ?????????? ????????????
????????? ???????????? - ??????? 7.
??????? 7 - ?????????? ??? ???? ???????????????????
?????? ?????????????? ??????????
?. ??????, ?. ?????? - ?????????. ?????????? ? ??????. - 318 ?.
?????? ?. ?. ???????????????? ? ??????????, 2004
2
Документ
Категория
Без категории
Просмотров
9
Размер файла
513 Кб
Теги
zapiska
1/--страниц
Пожаловаться на содержимое документа