Зертханалық жұмыс

Ханой мұнараларындағы есепте сақиналардың қозғалу бірізділігін табу үшін рекурсивті емес бағдарламаны жазвңвз.

| var s: integer;

begin

| if i = 1 then begin

| end else begin

| | s:=6-m-n; {s – үшінші өзек: нөмірлер сомасы 6 тең}

| | move (i-1, m, s);

| | writeln ('қадам жасау ', m, '->', n);

| | move (i-1, s, n);

end;

begin

| стекқа үштілікті қою

| {инвариант: стектағы тапсырыстарды орындау қалды}

| while стек непуст do begin

| | жоғарғы элементті жою,оны

| | if j = 1 then begin ауыстыру

| | | writeln ('қадам жасау', p, '->', q);

| | end else begin

| | | s:=6-p-q;

| | | {s – үшінші өзек: номерлер сомасы 6 тең}

| | | стекқа үштерді қою , <1,p,q>,

| | end;

end;
(ең бірінші стекке үш қойылады, оны соңғы кезде орындау керек).

Стек үштіліктері жеке стектері ретінде іске асады. (Сонымен қоса, паскальдің арнайы түрі бар, оны "жазылу" деп атайды).

Тапсырма 1

(А.К.Звонкин Анджея Лисовскиге хабарлады). Ханой мұнаралары туралы есептерде рекурсивті емес алгоритмдер бар.

Олардың бірі: қондыру өзектері ( ауыстырулардан емес) барлық өзектер кезек бойынша болу керек . Келесі ереже: кезекпен ең аз сақиналарды және ең аз емес сақиналарды ауыстыру,сонымен ең азын шеңбер бойнша.
Тапсырма 2

Рекурсия орнына стекті қолдану. Толық санның ондық басылымның рекурсивті бағдарламасында тапсырмалар кейінге қалдырылған.

Екілік бұтақ төбелерінің барлығын жазатын рекурсивті емес бағдарламаны жазыңыз.

Не өзгереді, егерде бұтақтын екілік төбелерін жазбасақ, бірақта оның саның есептесек?

6 мүмкіндігі бар тәртіптер үшін кей жеңілдіктер болуы мүмкін, екі түрдегі стек элементтерінде керек емес сақталымдарды жасайды. Кейбіреулерін көрсетейік.