Algoritmlash p65. p65

yulduzchali  kataklarni  bo‘yab  o ‘tkazuvchi  algoritm  tuzing.
6.51-rasm.

---

VII  bob.  REKURSIYA
O ‘zini  chaqiradigan  protseduralar
7.1-m asala
Robot  kengligi  1  ga teng  va  devorlar bilan  o ‘ralgan gorizontal 
to ‘g‘r i  to ‘rtburchakning  chap  devoridan  b iro r  masofada  turibdi. 
R obotni o‘ng  devordan  shuncha masofada bo ‘lgan katakka o‘tka- 
zing (7.1-rasm).
Robot bu yerda 
turibdi
Robot bu yerga 
o‘tishi kerak
7.1-rasm
Masala  juda  sodda  bo‘lib   ko ‘rinadi.  Haqiqatan,  agar  Robot 
bilan chap devor orasidagi,  aytaylik, ikkita  katakni, bilsak u n i kerakli 
katakka jo ‘natish  qiyin  emas:  Robot  avval  o‘ng  devorgacha boradi 
keyin  ikkita   chapga  yuradi.  M urakkabligi  shundan  iboratki,  chap 
devorgacha bo‘lgan masofa ixtiyo riy bo‘lish i m um kin,  bizda esa bu 
masofani  o ‘lchash  uchun  b iro r  usul  ham,  o‘lchay  olsak  uning 
qiymatidan  foydalana  olish  im koniyati  ham  yo‘q.  Bu  vaziyatdan 
chiqish,  bunaqasi  tez-tez  bo‘lib   turadi,  kutkmaganda  sodir bo‘ldi.
Yechim. 
Q o‘yilgan  m asalani  yecha  oladigan  prorsedurani 
yozishga harakat qilam iz.  Bu protsedurani 
simmetriya 
deb ataymiz. 
Avvalo bizga masalani hech bo ‘lmaganda Robot chap devor oldida 
turgan  birgina  holatda  yechish  m um kin lig i  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
9 — Azamatov, A.R.
129

---

AKS  HOLDA
TAMOM
TAMOM
E n d i  R o b o tn i  chap  yonida  devor  b o ‘ lmasa,  nim a  q ilis h i 
kerakligi haqida o‘ylaym iz.  Keling,  chapga b ir qadam tashlaymiz, 
Robot bilan  chap  devor  orasidagi  masofa  qisqaradi.  B alki  masofa 
0  bo ‘lib   qolishi  ham  m um kin!  Bu  esa  sim m etriya  protsedurasi 
kerakli ishni bajarayotganini va biz u n i chaqirishim iz m um kinligini 
b ild ira d i.  Protsedura ishlashi tugaganidan keyin chapga b ir qadam 
yurish  kerak  bo‘ladi,  chunki  Robotdan  o ‘ng  devorgacha  bo‘lgan 
masofa  uning  boshlang‘ic h   jo yid a n   chap  devorgacha  b o ‘lgan 
masofaga teng  bo ‘lis h i  kerak.  M ana  nim a  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
B uni qarangki, yozilgan bu algoritm  har qanday sharoitda ham 
to ‘g‘r i  ishlar  ekan!  Q o‘yilgan  masalani  yechadigan  algoritm   esa 
juda  sodda  ko ‘rinishga  ega: 
simmetriya
N atijada  bizda  juda  g‘alati  protsedura  hosil  bo‘ld i:  u  o‘z in i 
o‘zi  chaqiradi.  Bunday  protseduralarni 
rekursiv 
deb  atashadi. 
E ’tib o r bilan  uning  ish in i  qadamba-qadam  o‘rganib  chiqamiz.
Robot  bilan  chap  devor  orasidagi  boshlang‘ich  masofa  0  ga 
teng  bo‘lganda  protsedura  to ‘g‘r i  ishlashini  ko ‘rdik.  Robot  bilan 
chap  devor  orasidagi  masofa b itta   katak bo‘lganda  qanday voqea 
ro ‘y berishini  ko ‘rib  chiqamiz.
Protsedura  boshida 
EMAS  chap  bo‘sh 
sharti 
YOLG‘O N
, 
shuning  uchun  protseduradagi  tarm oqlanish  tuzilm asining 
AKS 
HOLDA 
so‘zidan  keyingi  qism i  b a ja rila d i.  Bu  qismda  uchta 
ko ‘rsatma  bor:
130

---

chapga
simmetriya
chapga
B irin ch i ko‘rsatmani bajargach,  Robot chap devorga b itta  katak 
yaqinlashadi,  ya’n i  devor  yoniga  borib  qoladi.  K eyin 
simmetriya 
protsedurasi  bajariladi.  E ndi  vaziyat  o ‘zgardi:  Robot  chap  devor 
yonida  tu rib d i.  Bu  vaziyatda  protsedura  to ‘g‘r i  ishlashini  bilam iz 
va  u  o‘ng  devor  yoniga boradi.  U ch inch i 
chapga 
ko‘rsatmasi  uni 
o ‘ng  devordan b itta   chap  katakka  o ‘tkazadi,  ya’n i kerakli katakka 
tushadi va  protsedura  ishi  tugaydi.
Siz,  albatta,  Robot  bilan  chap  devor  orasidagi  masofa  ikkita  
katak bo‘lganda protsedura ishining to ‘g‘rilig in i qanday tekshirishni 
tushungan bo‘lsangiz  kerak. 
EMAS  chap bo‘sh 
sharti 
YOLG‘ON
, 
demak,  protsedurada  tarm oqlanish  tuzilm aning 
AKS  HOLDA 
so‘zidan  keyingi  qism i bajariladi.  B irin c h i  ko ‘rsatmani bajargach, 
Robot  chap  devorga  b itta   katak  yaqinlashadi,  ya’n i  devor  bilan 
u n i  orasida  b itta   katak  qoladi.  K eyin  sim m etriya  protsedurasi 
bajariladi va R obotni,  yuqorida ko ‘rib   o‘tganim izdek,  o‘ng  devor­
dan b itta  chap  katakka  o ‘tkazadi.  K eyingi  chapga ko ‘rsatmasi uni 
o‘ng devordan ikkita  chap katakka, ya’n i kerakli katakka o‘tkazadi.
M ulohaza yuritishning bu usuli —  induksiya bo‘yicha mulohaza 
— bizga b irin c h i marta duch kelishi emas.  U  bizga chap  devordan 
ix tiy o riy   boshlang‘ich   holatda  protsedura  ishining  to ‘g ‘rilig in i 
tekshirish im ko n in i beradi.