Mavzu: Algoritm haqida umumiy intuitive ta’rif

Mavzu: Umumiy algoritmlar nazariyasiga doir asosiy kashfiyotlar. Rekursiya prinsipi.

O‘zini chaqiradigan protseduralar

masala


Robot bu yerda Robot bu yerga
turibdi o‘tishi kerak
Robot kengligi 1 ga teng va devorlar bilan o‘ralgan gorizontal to‘g‘ri to‘rtburchakning chap devoridan biror masofada turibdi. Robotni o‘ng devordan shuncha masofada bo‘lgan katakka o‘tka- zing
Masala juda sodda bo‘lib ko‘rinadi. Haqiqatan, agar Robot bilan chap devor orasidagi, aytaylik, ikkita katakni bilsak uni kerakli katakka jo‘natish qiyin emas: Robot avval o‘ng devor- gacha boradi, keyin ikkita chapga yuradi. Murakkabligi shundan iboratki, chap devorgacha bo‘lgan masofa ixtiyoriy bo‘lishi mumkin, bizda esa bu masofani o‘lchash uchun biror usul ham, o‘lchay olsak uning qiymatidan foydalana olish imkoniyati ham yo‘q. Bu vaziyatdan chiqish, bunaqasi tez-tez bo‘lib turadi, kutilmaganda sodir bo‘ldi.
Yechim. Qo‘yilgan masalani yecha oladigan prorsedurani yozishga harakat qilamiz. Bu protsedurani simmetriya deb ataymiz. Avvalo bizga masalani hech bo‘lmaganda Robot chap devor oldida turgan birgina holatda yechish mumkinligi yordam beradi. Bu holda Robot o‘ng devor oldiga borib to‘xtashi kerak:
PROT simmetriya BOSHLANISH
AGAR EMAS chap bo‘sh U HOLDA
TOKI o‘ng bo‘sh BAJAR o‘ngga TAMOM
AKS HOLDA
TAMOM
TAMOM
Endi Robotning chap yonida devor bo‘lmasa, nima qilishi kerakligi haqida o‘ylaymiz. Keling, chapga bir qadam tash- laymiz, Robot bilan chap devor orasidagi masofa qisqaradi. Balki masofa 0 bo‘lib qolishi ham mumkin! Bu esa simmetriya protsedurasi kerakli ishni bajarayotganini va biz uni chaqi- rishimiz mumkinligini bildiradi. Protsedura ishlashi tuga- ganidan keyin chapga bir qadam yurish kerak bo‘ladi, chunki Robotdan o‘ng devorgacha bo‘lgan masofa uning boshlang‘ich joyidan chap devorgacha bo‘lgan masofaga teng bo‘lishi kerak. Mana nima hosil bo‘ladi:
PROT simmetriya BOSHLANISH
AGAR EMAS chap bo‘sh U HOLDA
TOKI o‘ng bo‘sh BAJAR o‘ngga TAMOM AKS HOLDA
chapga
simmetriya
chapga
TAMOM
TAMOM
Buni qarangki, yozilgan bu algoritm har qanday sharoitda ham to‘g‘ri ishlar ekan! Qo‘yilgan masalani yechadigan algoritm esa juda sodda ko‘rinishga ega: simmetriya
Natijada bizda juda g‘alati protsedura hosil bo‘ldi: u o‘zini o‘zi chaqiradi. Bunday protseduralarni rekursiv deb atashadi. E’tibor bilan uning ishini qadam-baqadam o‘rganib chiqamiz.
Robot bilan chap devor orasidagi boshlang‘ich masofa 0 ga teng bo‘lganda protsedura to‘g‘ri ishlashini ko‘rdik. Robot bilan chap devor orasidagi masofa bitta katak bo‘lganda qanday voqea ro‘y berishini ko‘rib chiqamiz.
Protsedura boshida EMAS chap bo‘sh sharti YOLG‘ON, shuning uchun protseduradagi tarmoqlanish tuzilmasining AKS
HOLDA so‘zidan keyingi qismi bajariladi. Bu qismda uchta ko‘rsatma bor:
chapga
simmetriya
chapga
Birinchi ko‘rsatmani bajargach, Robot chap devorga bitta katak yaqinlashadi, ya’ni devor yoniga borib qoladi. Keyin simmetriya protsedurasi bajariladi. Endi vaziyat o‘zgardi: Robot chap devor yonida turibdi. Bu vaziyatda protsedura to‘g‘ri ishlashini bilamiz va u o‘ng devor yoniga boradi. Uchinchi chap­ga ko‘rsatmasi uni o‘ng devordan bitta chap katakka o‘tkazadi, ya’ni kerakli katakka tushadi va protsedura ishi tugaydi.
Siz, albatta, Robot bilan chap devor orasidagi masofa ikkita katak bo‘lganda protsedura ishining to‘g‘riligini qanday tekshi- rishni tushungan bo‘lsangiz kerak. EMAS chap bo‘sh sharti YOLG‘ON, demak, protsedurada tarmoqlanish tuzilmaning AKS HOLDA so‘zidan keyingi qismi bajariladi. Birinchi ko‘rsatmani bajargach, Robot chap devorga bitta katak yaqinlashadi, ya’ni devor bilan uni orasida bitta katak qoladi. Keyin simmetriya protsedurasi bajariladi va Robotni, yuqorida ko‘rib o‘tganimizdek, o‘ng devordan bitta chap katakka o‘tkazadi. Keyingi chapga ko‘rsatmasi uni o‘ng devordan ikkita chap katakka, ya’ni kerakli katakka o‘tkazadi.
Mulohaza yuritishning bu usuli — induksiya bo‘yicha mulohaza — bizga birinchi marta duch kelishi emas. U bizga chap devordan ixtiyoriy boshlang‘ich holatda protsedura ishi­ning to‘g‘riligini tekshirish imkonini beradi.
mashq
Nima uchun oxirgi chapga ko‘rsatmasidan oldingi simmetriya
protsedurasiga chap bo‘sh shartini tekshirmasa ham bo‘ladi?

2. 
   mashq
   

Robotning 7.2-rasmdagi holatlari uchun simmetriya protsedurasi




masala
Robot devorlar bilan o‘ralgan to‘g‘ri to‘rtburchakning ichida turibdi. Robotni boshlang‘ich holatidan to‘g‘ri to‘rtburchak mar- kaziga nisbatan simmetrik bo‘lgan katakka o‘tkazuvchi algoritm tuzing.

1. 
   masala
   

Robot kengligi 1 ga teng gorizontal yo‘lakda turibdi. Yo‘lak chap tomondan devor bilan chegaralangan, o‘ng tomon — cheksiz. Robotni shunday katakka o‘tkazingki, bu katakdan chap devorgacha bo‘lgan masofa boshlang‘ish katakdan chap devorgacha bo‘lgan masofadan ikki marta katta bo‘lsin.
Yechim. Bu masalada Robot chap devor yonida turgan bo‘lsa, nima qilish tushunarli: u o‘z joyida qolishi kerak. Quyidagicha protsedura tuzamiz:
PROT ikkilangan sakrash BOSHLANISH
AGAR EMAS chap bo‘sh U HOLDA
AKS HOLDA
TAMOM
TAMOM
Nuqtalar o‘rniga qanday ko‘rsatmalar qo‘yilishi kerak? Birinchi bo‘lib, devorgacha bo‘lgan masofani kamaytirish, ya’ni vaziyatni soddalashtirish uchun chapga ko‘rsatmasini bajarish kerakdir. Keyin yana ikkilangan sakrash protsedurasini chaqirish lozim. So‘ngra — devorgacha bo‘lgan masofa ikki marta katta bo‘lishi uchun o‘ngga ikki qadam tashlash kerak bo‘ladi.
Demak, har bir chapga bir qadam uchun o‘ngga ikki qadam yurish mos keladi.
mashq

1. 
   Ikkilangan sakrash protsedurasini oxirigacha yozib chiqing.
   
2. 
   EMAS chap bo‘sh shartini chap bo‘sh sharti bilan almashtirib, boshqa ikkilangan sakrash protsedurasi variantini yozing.
   
3. 
   Agar Robotning chap devorgacha boshlang‘ich masofasi quyidagicha bo‘lsa, Robotni ikkilangan sakrash protsedurasini bajarishidagi qadamlari ketma-ketligini yozib chiqing:
   

a) ikkita katak; b) uchta katak.
Rekursiyadan chiqish
Rekursiv protseduralami har qanday Ijrochi uchun yozish mumkin. Masalan, Robotni kvadrat bo‘ylab yurishi uchun rekursiv protsedura yozaylik.
masala
Tomoni 5 ga teng kvadratni chizish rekursiv protsedurasini yozing.
Javob.
PROT rekursiv kvadrat BOSHLANISH oldinga oldinga oldinga oldinga oldinga o‘ngga
rekursiv kvadrat TAMOM
Bu protsedura qanday ishlashini ko‘rib chiqamiz. Demak, rekursiv kvadrat protsedurasi chaqirilganda oldinga oldinga oldinga oldinga oldinga o‘ngga
ko‘rsatmalari bajariladi. Bunda Robot kvadratning tomoni bo‘ylab yurib 90 gradusga buriladi. Keyin yana rekursiv kvadrat protsedurasi chaqiriladi. Robot kvadratning boshqa tomoni bo‘ylab yurib o‘ngga buriladi. Keyin yana rekursiv kvadrat protsedurasi chaqiriladi. Yana ikki tomon o‘tilgach kvadrat bo‘ylab yurish yakunlanadi. Lekin nimadir bo‘ldi? Robot to‘xta- masdan yana shu kvadrat bo‘ylab yurishni davom ettirmoqda. Bu esa cheksiz davom etadi — algoritm siklga tushib qoldi. Vaziyat yoqimsiz. Biz doimo siklga tushib qolmaslikka harakat qilar edik. Bu holda undan qutulishning chorasi bormikan? Taas- sufki, yo‘q. Haqiqatan, rekursiv protseduraning chaqirilishi cheksiz davom etmasligi uchun protseduraga chaqirilish yuzaga kelmaydigan shart kiritish kerak. Lekin bu Robotda bunday
shart yo‘q. Robotning algoritmi uning holatidan qa’tiy nazar, bir xilda bajarilaveradi.
Shu kabi, Dehqon, Suvchi, Chigirtka, Oshiruvchi, Zohid kabi Ijrochilarda shart yo‘q. Bu Ijrochilar uchun rekursiv protseduraning qo‘llanishi yoki siklga tushib qolinadi yoki keyingi ko‘rsatmani bajarish mumkin bo‘lmay qolib, INKOR yuzaga keladi. Shuning uchun