Мысалы
Ханой мұнараларындағы есепте сақиналардың қозғалу бірізділігін табу үшін рекурсивті емес бағдарламаны жазвңвз.
Шешімі. Рекурсивті бағдарламаны еске түсірейік, -ді ауыстырып қоятын жоғарғы сақиналары с нен :
procedure move(i,m,n: integer);
| var s: integer;
begin
| if i = 1 then begin
| | writeln ('қадам жасау ', m, '->', n);
| end else begin
| | s:=6-m-n; {s – үшінші өзек: нөмірлер сомасы 6 тең}
| | move (i-1, m, s);
| | writeln ('қадам жасау ', m, '->', n);
| | move (i-1, s, n);
| end;
end;
Біз көретіндей, "-ші өзекке m-нің жоғарғы дискін –ге ауыстыру" есебі сол үлгідегі үш есепке әкеледі: екі есепке -1 дисктермен бір есепке жалғыз дискпен.Бұл есептермен айналысқанда, тағы не істеу керек екенін ұпытпау керек.
Бұл үшін қалтарылған стек есептерін жасайық.Олардың элементтері үштіліктер болып келеді.Әр үштілік тапсырыс ретінде интерпретациаланады "жоғарғы дисктерін -ші өзектен -ге ауыстырылсын" . Тапсырыстар олардың орындалу талаптарына сәйкес жасалған: ең жедел – стек биіктігі.Мынадай бағдарлама аламыз:
procedure move(i,m,n: integer);
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;
end;
(ең бірінші стекке үш қойылады, оны соңғы кезде орындау керек).
Стек үштіліктері жеке стектері ретінде іске асады. (Сонымен қоса, паскальдің арнайы түрі бар, оны "жазылу" деп атайды).
Тапсырма 1
(А.К.Звонкин Анджея Лисовскиге хабарлады). Ханой мұнаралары туралы есептерде рекурсивті емес алгоритмдер бар.
Олардың бірі: қондыру өзектері ( ауыстырулардан емес) барлық өзектер кезек бойынша болу керек . Келесі ереже: кезекпен ең аз сақиналарды және ең аз емес сақиналарды ауыстыру,сонымен ең азын шеңбер бойнша.
Тапсырма 2
Рекурсия орнына стекті қолдану. Толық санның ондық басылымның рекурсивті бағдарламасында тапсырмалар кейінге қалдырылған.
Тапсырма 3
Екілік бұтақ төбелерінің барлығын жазатын рекурсивті емес бағдарламаны жазыңыз.
Тапсырма 4
Не өзгереді, егерде бұтақтын екілік төбелерін жазбасақ, бірақта оның саның есептесек?
Тапсырма 5
6 мүмкіндігі бар тәртіптер үшін кей жеңілдіктер болуы мүмкін, екі түрдегі стек элементтерінде керек емес сақталымдарды жасайды. Кейбіреулерін көрсетейік.
Ескерту. Бұтақтын барлық төбелерін жазудағы басқа бағдарламасын бұтақты айналу бағдарламасы негізінде құруға болады (тиісті тарауда қарастырылған) Онда "төмен" командасы орындалады. Енді барлық төбелер тізімін түбірден ағымдағы төбеге бару жолын сақтау керек Сонымен қоса графтағы алгоритмдар туралы тараудан қараңыз.
Достарыңызбен бөлісу: |