Algoritmlash p65. p65

Samarador Oshiruvchi
Samarador algoritmlarni tuzish bizdan jiddiy aqliy tirishqoqlikni 
talab  etadi.  Bir  xususiy  holni  ko‘rib  chiqamiz:  Oshiruvchi  tomo- 
nidan 0  sonidan 729  sonini hosil qilish masalasi.
Birinchi  qadamda,  ravshanki,  1  ni  qo‘shish  kerak  —  0  ni 
ko‘paytirish befoyda.  Endi  1  soni hosil bo ‘ldi.  Ikkinchi qadamda 
2  soniga  ko‘paytirish  ham  1  sonini  qo‘shish  ham   mumkin  — 
natija  bir  xil  (ya’ni,  2)  b o ‘ladi.  Aniqlik  uchun  ko‘paytirishni 
tanlaymiz.
Endi ekranda qaysi  son yozilgan bo ‘lishidan  qat‘iy nazar,  1  ni 
qo‘shishdan  ko‘ra  2  ga  ko‘paytirish  729  soniga  yaqinlashishni 
tezlashtiradi.
Bir  qaraganda,  iloji  boricha  2  ga  ko‘paytir  dan  foydalanish 
kerakdek tuyuladi.  Tanlangan usul quyidagi sonlar ketma-ketligiga 
olib  keladi:  0  ^   1  ^  2  ^  4  ^   8  ^   16  ^   32  ^   64  ^   128  ^   256
69

---

^   512.  Agar  yana  bir  marta  2  ga  ko‘paytirsak,  marradan  o ‘tib 
ketamiz.  Shuning  uchun  biz  endi  1  ni  qo‘sh  ko‘rsatmasini  217 
marta  (729  —  512=  217)  bajarishimiz  kerak  bo‘ladi.  Juda  ham 
samarador  emas,  to ‘g‘rimi?
Biror-bir  tasodifan  tanlangan  oraliq  qadamda  1  ni  qo‘shdan 
foydalanishga  harakat  qilamiz.
Birinchi urinish:  1  ni 4  soniga qo‘shamiz  (shundan keyin 2  ga 
ko‘paytirdan  foydalanamiz):  0  ^   1  ^   2  ^   4  ^   5  ^   10  ^   20  ^  
40  ^   80  ^   160  ^   320  ^   640.  Bu holda  1  ni  qo‘sh ko‘rsatmasini 
89  marta  (729  —  640=  89)  bajarishimiz  kerak  bo ‘ladi.  Ancha 
yengillika erishdik!
Ikkinchi urinish:  1  ni 2  soniga qo‘shamiz  (shundan keyin 2 ga 
ko‘paytir dan foydalanamiz):  0  ^   1  ^   2  ^   3  ^   6  ^   12  ^   24  ^  
48  ^   96  ^   192  ^   384.  Bu  holda  1  ni  qo‘sh  ko‘rsatmasini  345 
marta (729 — 384=  345) bajarishimiz kerak bo‘ladi.  Endi ahvolimiz 
yomonlashdi-ku!
Bundan  tushunarliki,  1  ni  qo‘sh  ko‘rsatmasidan  o‘ziga  xos, 
ya’ni  «eng  yaxshi»  qadamda  foydalanishimiz  kerak.  Lekin  uni 
qanday topish  mumkin?
Quyidagi  fikr juda  ko‘p  o‘yinlarda  yordamga  keladi:  oxiridan 
boshlash.  Keling, yangi Ijrochini hosil qilamiz va uni Kamaytiruvchi 
deb  ataymiz.  Uning  ko‘rsatmalari  quyidagicha:
1  ni  ayir
2  ga bo‘l
Kamaytiruvchi  1  ni  ayir  ko‘rsatmasi  berilganda  ekrandagi 
sondan  birni  ayiradi.  Ekrandagi  son  0  ga  teng  b o ‘lganda  bu 
ko‘rsatma  Inkor  holatiga  olib  keladi.  Kamaytiruvchi  2  ga  bo‘l 
ko‘rsatmasi berilganda ekrandagi sonni teng ikkiga bo ‘ladi. Agar 
ekrandagi  son  toq  b o ‘lsa,  bu  ko ‘rsatm a  Inkor  holatiga  olib 
keladi.
Endi  729  sonidan  0  sonini  hosil  qilamiz.  Oshiruvchini  2  ga 
ko‘paytir  ko‘rsatmasi  1  ni  qo‘sh  ko‘rsatmasiga  nisbatan  natijaga 
yaqinlashishni tezlashtirsa,  Kamaytiruvchini 2  ga bo‘l  ko‘rsatmasi
1  ni  ayir  ko‘rsatmasiga  nisbatan  ham   jarayonni  tezlashtiradi. 
Shuning uchun ham imkon bo‘lganda (Kamaytiruvchi uchun)  har 
gal ikkiga bo‘lishni xohlaymiz.  Lekin endi ekrandagi  sonning  o ‘zi
2  ga  bo‘lish  mumkinligini  ko‘rsatib  beradi.  Ya’ni,  agar  son  juft 
bo‘lsa,  u  holda  uni  2  ga  bo‘lamiz,  agar  son  toq bo‘lsa,  bu  holda 
faqat undan  1  ni ayirishimiz mumkin  (natijada yana juft  son hosil 
b o ‘ladi).  Kamaytiruvchi  uchun  algoritmning  boshlanishi  quyi- 
dagicha:
70

---