Algoritmlash p65. p65

9 .1 2 -  masala
Saralovchi M  N  ta tokchali t1 (*) va t2 (*)  n i barcha sonlarini S 
tokchaga  yig ‘sin.
9 .1 3 -  masala
Saralovchi  M   N   ta  tokch a li  t1 (*)  n i  tokchalaridagi  barcha 
sonlarning  o ‘rta  arifm etigini  S  tokchaga yig‘sin.
181

---

9.19-m ashq
Informatika  fanidan  har  kuni  olgan  ballaringizni  tokchlarga
ta rtib   bilan  jo y la s h tirib   ch iq ib ,  yakuniy  natija  b alin gizni
aniqlovchi  algoritm  tuzing.
9.14-m asala
Saralovchi  M   berilgan  N   uchun  2  ning  darajalarini  t1 (*)  n i 
tokchalariga jo ylashtirib,  keyin u la rn i  S  tokchaga yig ‘sin.
Yechim.  Masala shartiga ko‘ra Bek algoritm ida t1(1)  tokchaga 
2 ning  1-darajasini joylash tirdi;  t1(2)  tokchaga 2 ning 2-darajasini 
jo yla sh tird i va  hokazo:
1  D AN N   G ACHA BAJAR 
o ‘tkaz  2*,  t1 (i)
T A M O M
yoki  boshqacha takrorlanish tuzilm asi  orqali  yozsak: 
TA K R O R LA N S IN  N  M A R TA  
o ‘tkaz  2i,  t1 (i)
T A M O M
Bunday masalalarda  keyingi  qadam ni b itta   o ld in g i  qadamga 
bog‘liq   ravishda  hisoblash  ham  m um kin:  t1(1 )  tokchaga  2  ning 
1 -d a ra ja s in i  jo y la s h tira m iz ;  t1 (2 )  tokchaga  t1 (1 )  n i  2  ga 
ko ‘p a y tirib  jo yla ym iz,  ya’n i 2  n i 2 ga k o ‘p a ytirib  t1 (2 )  tokchaga 
joylashtiram iz; t1(3) tokchaga t1(2) n i 2 ga ko ‘pa ytirib  joylaym iz, 
ya’n i  2-2  n i  2  ga  ko ‘p a ytirib   t1(3 )  tokchaga jo yla sh tira m iz  va 
hokazo:
o‘tkaz  2,  t1 (1 )
2  DAN N   G ACHA BAJAR 
o‘tkaz  2 -t1 (i-1 ),  t1 (i)
T A M O M
yoki  boshqacha takrorlanish tuzilm asi  orqali  yozsak: 
o‘tkaz  2,  t1 (1 )
T AKRO R LA N S IN  N -1  M A R TA  
o‘tkaz  2 -t1 (i),  t1 (i+ 1 )
T A M O M
Bu  usulning  samaradorligi  avvalgi  Bekning  usuli bilan b ir x il, 
m urakkabligi esa Bekning usulidan bittaga ortiq, le kin asosiy yutuq 
algoritm da  darajaga  ko ‘tarish  am ali  ish tiro k  etmayapti.
A lg o ritm ika d a   bu  kabi  keyingi  qadam ni  avvalgi  qadamga 
bog‘laydigan  usul  iteratsiya  usuli  deb  ataladi.
E ndi barcha tokchalardagi  sonlarni  S  tokchaga yig‘ amiz: 
bo‘shat  S
182

---

TA K R O R LA N S IN  N  M AR TA 
o‘tkaz  S + t1 (i),  S 
T A M O M
A lg o ritm n i iteratsiya usuli yordam ida yozilgan to ‘liq  ko ‘rin ish i 
quyidagicha:
o ‘tkaz  2,  t1 (1 )
2  DAN  N   G ACHA BAJAR 
o‘tkaz  2 -t1 (i-1 ),  t1 (i)
T A M O M  
bo‘shat  S
TA K R O R LA N S IN  N  M AR TA 
o‘tkaz  S + t1 (i),  S 
T A M O M
Agar  o x irg i  a lg o ritm n in g   sam aradorligin i  saqlagan  holda 
m urakkabligini  kam aytirm oqchi  bo‘lsak,  quyidagicha  yozishim iz 
mumkin:
o ‘tkaz  2,  t1 (1 )
o ‘tkaz  t1 (1 ),  S 
2  DAN  N   G ACHA BAJAR 
o‘tkaz  2 -t1 (i-1 ),  t1 (i)
o‘tkaz  S + t1 (i),  S 
T A M O M
yoki boshqacha takrorlanish  tuzilm asi  orqali yozsak: 
o ‘tkaz  2,  t1 (1 ) 
o ‘tkaz  t1 (1 ),  S
T AKRO R LA N S IN  N -1  M A R TA  
o‘tkaz  2 -t1 (i),  t1 (i+ 1 ) 
o‘tkaz  S + t1 (i+ 1 ),  S 
T A M O M
Y ig‘ish uchun ishlatilayotgan S tokchani avvallari bo‘shatib olardik. 
Bu  ikkala  algoritmda  esa  bo‘shatib  olganimiz  yo‘q.  Buni  sababini 
o‘zingiz  izohlang.