Algoritmlash

Oraliq protsedura orqali rekursiv chaqirish

bosBa'zan protseduralami yozganda uning o'ziniio‘zining ichida bo hqa protsedura orqali chaqirgan qulay. To‘g‘r to'rtburchakni

'yash masalasining rekursiv yechimini qaraymiz

7.8- masala

Robot devorlar bilan o'ralgan to'g'ri to'rtburchakning chap quyi burchagida turibdi. To‘g‘ri to'rtburchakning ichida devorlar

136

yo‘q. To‘g‘ri to‘rtburchakning barcha kataklarini bo'yash algoritmini tU2ing.

Yechim. Tkkita rekursiv protsedurani qo'llaydigan bo'yash

algoritmini yozamiz:

PROT to‘g‘ri to‘rtburchakni bo‘ya BOSHLANISH

AGAR EMAS bo‘yalgan

U HOLDA

yoMakni bo‘ya va qayt TAMOM

TAMOM

va

PROT yo‘iakni bo‘ya va qayt BOSHLANISH

TOKI yuqori bo‘sh BAJAR bo‘ya

yuqoriga TAMOM

TOKI quyi bo‘sh BAJAR quyiga

TAMOM

AGAR o‘ng bo‘sh U HOLDA

o‘ngga

to‘g‘ri to‘rtburchakni bo‘ya TAMOM

TAMOM

Endi algoritm bitta ko'rsatmadan iborat bo‘ladi.

to‘g‘ri to‘rtburchakni bo‘ya

_proBizning yechimimizda _v to‘g‘ri _pto‘rtburchakni bo‘ya

_{0 ‘} tsedurasi yoMakni bo‘ya_o‘a qayt _q rotsedurasini chaqiradi.

_to z_t navbatida, yo‘lakni_t b_d ya_sva _cayt _iprotsedurasi to‘g‘ri

_to‘r burchakni bo‘ya pro se ura_rini _e haq radi. _zShunday qilib,

_y ‘g‘ri _ito‘rtburchakni _rbo‘ya p_sots durasi o‘ ini-o‘zi oraliq

o‘lakn bo‘ya va qayt p otsedura i orqali, yoMakni bo‘ya va qayt

protsedurasi o'zini o‘zi oraliq to‘g‘ri to‘rtburchakni bo‘ya

protsedurasi orqali chaqiradi.

ula Bu holda ikkala tprotsedurani rekursiv deb hisoblaymiz va

r bilan oddiy pro sedura kabi muomala qilamiz.

137

Nazorat savollari va topshiriqlar

1. Qanday algoritmlar rekursiv deb ataladi?

2. Simmetriya protseduraxini izohiab bering.

3. Ikkilangan sakrash pmtsedurasini izohlab bering.

4. Rekursiya bilan yuzaga keladigan muammoiami so 'ziab bering.

5. Bohdagi barcha mashqlami bajaring.

Qo‘shimcha masalalar

R-l. Robot kengligi 1katak bo'lgan gorizontal yoMakda turibdi. Undan chapda qayerdadir bo‘yalgan katak bor Robotni tuigan katagidan bo'yalgan katakka borib, yana joyiga qaytarib keltiradigan algoritm tuzing.

R-2. Robot kengligi 1katak bo‘lgan yuqoridan va quyidan devor bilan chegaralangan gorizontal yoMakda turibdi. Undan o‘ngda qayerdadir bo'yalgan katak bor. Robot turgan katagiga bo‘ya!gan katakka nisbatan simmetrik bo'lgan chapdagi katakka horishi kerak (7.3-rasm). Mos algoritmni tuzing.

Robot bu yerda Robot bu yerga turibdi o'tishi kerak

7.3-rasm.
R-3. Robot kengligi I katakboMgan gorizontal yo'lakda turibdi. Undan chapda qayerdadirdevorbor. Robotni turgan katagidan dcvorgacha olib borib, yana joyiga qaytarib olib keladigan algoritm tuzing.

olibR-4. Robotni o‘zidan yuqorida joylashgan gorizontal devor yoniga keladigan rekursiv algoritm tuzing.

R-5. Robot o'tgan katagini bo'yab ketishi mumkin bo‘lsa, u holda

a) R-1

ma b) R-3 i rekursiyasiz yeching.

salalarn

cha K-l. Samarador Kamaytiruvchi uchun rekursiv protsedurani qiradigan algoritm tuzing.