Algoritmlash p65. p65

Tashqi
1-ichki
2-ichki
Takrorlanishlar
sikl  i
sikl j
sikl  k
soni
1  da
2 dan  N  gacha
N  dan  2 gacha
2  (N-1) ta
2 da
3  dan  N  gacha
N  dan  2 gacha
2  (N-2) ta
3  da
4 dan  N  gacha
N  dan  2 gacha
2  (N-3) ta
4 da
5 dan  N  gacha
N  dan  2 gacha
2  (N-4) ta
158

---

8 .2 -ja d v a ln in g   d a vo m i
N-2 da
N-1  dan  N  gacha
N  dan  N-1  gacha
2  (N-(N-2))  =2 2 ta
N-1  da
N  dan  N  gacha
N  dan  N  gacha
2(N -(N -1))  =21  ta
Hammasi  bo‘lib sikNardagi 
qadamlar  soni
2(1+2+3+...+(N -3)+(N-2)+(N -1))= 
N  (N-1) ta
8.10-m ashq
8.2-jadvaldagi  qadamlar sonini  hisoblashda yuqori  chegara 
topildi.  Quyidagi  8.3-jadvaldagi  tokchalar  uchun  sikllam ing 
qadamlari  sonini  hisoblang  va  xulosa  yozing.
8.3-jadval
Tokcha ta rtib  raqami
1
2
3
4
5
Boshlang‘ich holatda  kublar  soni
1
3
7
12
49
8.10-m ashq
8.1-jadvaldagi  tokchalar  uchun  algoritmni  tekshiring.
Biz algoritm ni quyidagi jadvaldagi tokchalar uchun tekshiramiz:
8.4-jadval
Tokcha ta rtib  raqami
1
2
3
4
5
Boshlang‘ich holatda  kublar  soni
7
12
1
49
3
Qisqaroq  bo ‘lis h i  uchun jadvalda  tokcha(k)  o‘rniga  t(k )  kabi 
yozamiz.
Tash-
qi
sikl  i
O ‘tkazish
Ek
Ichki 
sikl j
Shart
tekshirish
Shart
qiymati
U HOLDA
o ‘tkazish
Ek
1
7=t(1)^
Zt=7
1
2
7=ZtROST
12=t(2)^
Zt=12
2
3
12=ZtYOLG‘ON
—
4
12=ZtROST
49 = t( 4)  ^  
Zt=49
4
5
49=ZtYOLG‘ON
-
Yangi 
sikl  k
O‘tkazish
3
1=t(3) ^  t(4)=1
159

---

‘ 
i
 
^ 
h
Bu amallardan keyin tokchalarda kublar quyidagicha joylashadi:
Tokcha ta rtib  raqami
1
2
3
4
5
Boshlang‘ich  holatda  kublar  soni
49
7
12
1
3
Davom   etamiz:
Tash-
qi sikl
0 ‘tkazish
Ek
Ichki
sikl j
Shart
tekshirish
Shart
qiymati
U H0LDA
o ‘tkazish
Ek
2
7=t(1)^
Zt=7
2
3
7=ZtROST
12=t(3)^
Zt=12
3
4
12=ZtYOLG‘ON
—
5
12=ZtYOLG‘ON
—
Yangi 
sikl  k
O‘tkazish
2
7=t(2) ^  t(3)=1
12=Zt
^t(2)=12
Shundan  keyin tokchalarda  kublar  quyidagicha joylashadi:
Tokcha ta rtib  raqami
1
2
3
4
5
Boshlang‘ich  holatda  kublar  soni
49
12
7
1
3
K eyingi  qadam:
Tash- 
qi  sikl
0 ‘tkazish
Ek
Ichki 
sikl j
Shart
tekshirish
Shart
qiymati
U  H0LDA
o ‘tkazish
Ek
3
7=t(3)^ Zt=7
3
4
7=ZtYOLG‘ON
—
3
5
12=Zt—
Yangi 
sikl  k
O‘tkazish
2
—
7=Zt ^t(3)=7
160

---

M a’lum ki,  2  dan  3  gacha  teskari  sanab  bo‘lm aydi.  Demak, 
yangi  ic h k i  siklda  birorta  ham  o‘tkazish  bajarilm aydi,  boshqacha 
aytganda yangi  ic h k i  sikl  ishlamaydi.  Jadval  o‘zgarmadi.
M ana  oxirgi  qadam:
Tash­
qi  sikl
O ‘tkazish
Ek
Ichki
sikl j
Shart
tekshirish
Shart
qiy-
mati
U HOLDA
o ‘tkazish
Ek
4
1=t(4)^Zt=1
4
5
1=ZtROST 3=t(5)^t(4)=3
5
Yangi 
sikl  k
O‘tkazish
4
1=t(4)^t(5)=1
3=Zt ^t(4)=3
M ana  endi  kerakli  ta rtib   o ‘rn a tild i:
Tokcha  tartib raqami
1
2
3
4
5
Boshlang‘ich holatda  kublar  soni
49
12
7
3
1
Bek  esa  quyidagicha  ish  tu td i:  1-tokchadan  N-tokchagacha 
eng  k o ‘p  kub  taxlangan  to k c h a n i  to p d i  va  1 -to kch a   b ila n  
alm ashtirdi;  2-tokchadan N-tokchagacha eng  ko ‘p  kub  taxlangan 
tokchani  topdi  va  2-tokcha  bilan  alm ashtirdi;  3-tokchadan  N - 
tokchagacha  eng  ko ‘p  kub  taxlangan  tokchani  to p d i va  3-tokcha 
bilan alm ashtirdi va shu kabi alm ashtirishlarni (N -1)-tokchagacha 
davom  e ttird i,  chunki  alm ashtirishlar  natijasida  N -tokchada  eng 
kam  sondagi  kublar  turgan bo‘ladi.
Bek  o‘zi  bilm agan  holda  oddiy  tanlov  deb  ataluvchi  usuldan 
foydalandi.  Bunda u ichm a-ich joylashgan sikl tashkil etdi.  Tashqi 
va  ic h k i  sikl b ir-b irid a n   farqlanishi uchun tokcha ta rtib   raqamida 
i  va  j   h a rfla rd a n   fo yd a la n d i.  T okch aning  o ‘ z i  b ila n   o ‘ z in i 
taqqoslamaslik uchun  ic h k i  sikln i  doim o  b itta   keyingi  tokchadan 
boshladi, ya’n i tashqi sikldagi i-tokcha uchun ich ki sikldagi sanoqni 
(i+ 1 ) -tokchadan  boshlash  to ‘g‘r i  bo‘ladi:
1  D AN N -1  G ACHA BAJAR 
o ‘tkaz  tokcha(i),  Z t 
i+ 1   D AN N   G ACHA BAJAR 
AGAR Z t< to kch a (j)
U  H O LD A
o ‘tkaz  tokcha(i),  Z t
11  — Azamatov, A.R.
161

---

T A M O M
T A M O M
o‘tkaz  to kcha(i),  tokcha(Ek) 
o‘tkaz  Z t,  tokcha(i)
T A M O M
Joylashtirish  usulidagi  kabi  oddiy  tanlov  usulida  ham  faqat 
siklla m ing  o ‘z i  necha  qadam ligini  jadval  yordam ida  hisoblab 
ko‘ramiz:
8.5-jadval