Комбинаторные алгоритмы для программистов

             

Стеки - часть 2


procedure start; var i:integer;grD,grM: Integer; begin clrscr;write('Enter the number of rings, please.');readln(number); for i:=1 to 3 do ster[i]:=nil; for i:=1 to number do begin new(p);p^.n:=i;p^.next:=ster[1];ster[1]:=p;end; nhod:=0; grD:=Detect;{InitGraph(grD,grM,'');}InitGraph(grD,grM,'c:\borland\tp\bgi'); th:=20;l:=round(50/number); setfillstyle(1,4);setcolor(4); for i:=1 to number do begin fillellipse(160,460-(i-1)*th,(number- i+1)*l,10);end; end;

begin start; {readkey;} hod(number,1,3); {closegraph;} end.

Программа 2. Ханойская башня.

На стержне

A
в исходном порядке находится
N

дисков, уменьшающихся по размеру снизу вверх. Диски должны быть переставлены на стержень в исходном порядке при использовании в случае необходимости промежуточного стержня

B
для временного хранения дисков. В процессе перестановки дисков обязательно должны соблюдаться правила: одновременно может быть переставлен только один самый верхний диск ( с одного из стержней на другой); ни в какой момент времени диск не может находиться на другом диске меньшего размера.

Программа реализована с помощью абстрактного типа данных – стек для произвольного числа дисков.

{Программа написана на языке программирования Turbo-Pascal}

uses crt,graph; type PEl=^El; El=record n:byte; next:PEl; end;

var ster:array[1..3] of PEl; number: byte; p:PEl; th,l: integer; i:integer; nhod:word; s:string;

procedure hod(n,f,t:integer); begin if n>1 then begin hod(n-1,f,6-(f+t)); hod(1,f,t); hod(n-1,6-(f+t),t); end else begin p:=ster[f]; ster[f]:=ster[f]^.next; p^.next:=ster[t]; ster[t]:=p; inc(nhod); str(nhod,s); {**********************************************************} setfillstyle(1,0);bar(0,0,50,10); setcolor(2);outtextxy(0,0,s); setfillstyle(1,0);setcolor(0);p:=ster[f];i:=1; while p<>nil do begin p:=p^.next;inc(i);end; fillellipse(160*f,460-(i-1)*th,(number-ster[t]^.n+1)*l,10); setfillstyle(1,4);setcolor(4);p:=ster[t];i:=1; while p<>nil do begin fillellipse(160*t,460-(i-1)*th,(number- ster[t]^.n+1)*l,10);inc(i);p:=p^.next;end; {**********************************************************} { readkey;}{delay(50);} end; end;

procedure start; var i:integer;grD,grM: Integer; begin clrscr;write('Enter the number of rings, please.');readln(number); for i:=1 to 3 do ster[i]:=nil; for i:=1 to number do begin new(p);p^.n:=i;p^.next:=ster[1];ster[1]:=p;end; nhod:=0; grD:=Detect;{InitGraph(grD,grM,'');}InitGraph(grD,grM,'c:\borland\tp\bgi'); th:=20;l:=round(50/number); setfillstyle(1,4);setcolor(4); for i:=1 to number do begin fillellipse(160,460-(i-1)*th,(number- i+1)*l,10);end; end;

begin start; {readkey;} hod(number,1,3); {closegraph;} end.




Содержание  Назад  Вперед