Urganch davlat universiteti axborot texnologiyalari kafedrasi

Masalaning  tahlili:  n=1  da  +1  ni;  n=2  da  +1+2  chaqirish  kerak.  faraz  qilaylik  n≥3 

bo‘lsin, n ta katakni to‘ldirish uchun, qandaydir bir paytda n- katakni band qilish zarur. Agar (n-

1)  ikki  katak  band  bo‘lsa  qolgan  1  dan  (n-2)  gacha  raqamlarni  barcha  kataklar  bo‘sh  bo‘lsalar 

buni  bajarishga  imkon  beradi.  Demak,  shunday  qilish  kerakki  faqat  (n-1)  –katak  band  bo‘lishi 

kerak,  keyin  shashkani  n-  katakka  qo‘yiladi,  keyin  esa  1  dan  (n-2)  gacha  raqamli  kataklar 

to‘ldiriladi.  Shunday  qilib  “faqat  n-1  inchi  katakni  to‘ldirish”  masala  osti  paydo  bo‘ladi  va 

rekursiv  masalaosti  “n-2  kataklarni  to‘ldirish”.  “n  kataklarni  to‘ldirish”  va  “faqat  n  –  katakni 

toldirish” masalalarini mos holda, fill(n) va filllOnly(n) singari belgilaymiz, shunda n≥3 ga fill(n) 

quyidagilarni bildiradi. 

 

fillOnly(n-

1

); 

write(

'+'

,n); 

fill(n-

2

)

 

 

FillOnly(n)  masalasi  bilan  shug‘ullanamiz.  Agar  n=1  bo‘lsa  i+1  ni  kiritish  kerak.  N≥2 

bo‘lsin  fill(n)  masalasida  bo‘lgani  kabi  avval  fillOnly(n-1)  masalasini  yechish  va  n  -  katakni 

egallashi  kerak.  Biroq  keyin  (n-1)  inchi  katakni  bo‘shatish  kerak  bo‘ladi.  Ushbu  yangi 

masalaostining free(n-1) belgilaymiz. Shunday qilib, n≥2 da fillOnly(n) quyidagilarni bildiradi.  

 

fillOnly(n-

1

); 

write(

'+'

,n); 

fill(n-

1

)

 

 

free(n) masalaostini qarab chiqaylik.  n=1 da  -1 ni chiqarish  kerak, n≥2 da esa n katakni 

bo‘sh  qoyish  uchun,  yana  avvalo  fillOnly(n-1)  masalasini  yechish  kerak, biroq  keyin  n  katakni 

egallamay balki uni bo‘sh qo‘yish  kerak, keyin esa rekursiv ravishda (n-1) -  katakni bo‘shatish 

kerak. Shunday qilib n≥2 da free(n) quyidagularni bildiradi  

 

fillOnly(n-

1

); 

write(

'-'

,n); 

fill(n-

1

)