Дастурлашни ўҚитиш муаммолари: рекурсияни массивларга татбиқ Қилиш

Download 77.1 Kb.

1 2 3 4

Bog'liq
dasturlashni oqitish muammolari rekursiyani massivlarga tatbiq qilish

ДАСТУРЛАШНИ ЎҚИТИШ МУАММОЛАРИ: РЕКУРСИЯНИ МАССИВЛАРГА ТАТБИҚ ҚИЛИШ

Маълумки, турли ўлчам ва мазмунга эга бўлган массивларга оид масалалар дастурлашнинг каттагина қисмини ташкил қилади. Одатда бундай масалаларни ҳал қилиш учун компьютер дастур буйруқларида кўздла тутилган таққослаш, ўрин алмаштириш, эслаб қолиш билан боғлиқ бўлган катта сондаги амалларни бажариши лозим бўлади. Бу эса дастурнинг бажарилишги вақтини узайтириб юборади ҳамда амалиётда фойдаланганда иқтисодий ҳаражатларнинг катталашиб кетишига сабаб бўлиши мумкин.
Шунинг учун, дастурчи массивга оид масалаларни ҳал қилишда реккурент муносабатларни ўрнатиб, дастурлаш жараёнига рекурсияни татбиқ эта олса, бундай ноқулай вазиятларнинг олдини олиш мумкин бўлар эди.
Биз дастурчилар орасида маълум ва машҳур бўлган айрим масалаларни рекурсия ёрдамида ҳал қилишга уриниб кўрамиз.

Элементлари фақат 0 ва 1 бўлган А[40,40] массив берилган бўлсин. Бу массив бирор лабиринтни ифодалайди. Унда
A[k, m]=0 бўлса [k,m] катакка ўтиш мумкин
A[k, m]=1 бўлса [k,m] катакка ўтиш мумкин эмас.
Йўловчи бошланғич ҳолда ўтиш мумкин бўлган [i, j] катакда турибди. Агар йўловчининг лабиринтдан чиқиш йўли мавжуд бўлса, уни топинг. Акс ҳолда йўл мавжуд эмас деб ахборот беринг.
Ғояси. Йўловчи қўшни бўлган бир катакдан иккинчисига фақат бу катакларда ноллар турган ҳолда, яъни ўтиш йўли мавжуд бўлсагина ўта олади.
У массивнинг чегаравий сатри ёки устунига етган ҳолда ([k, m] катакнинг k ёки m координаталари 1 ёки 40 бўлганда) лабиринтдан чиққан ҳисобланади.
Масалани ечиш усули икки босқичдан иборат бўлади:
лабиринтдан чиқиш йўли изланади;
чиқишдан бошлаб йўловчининг турган ўрнигача бўлган йўл чоп этилади.

Download 77.1 Kb.

Do'stlaringiz bilan baham:

1 2 3 4