Algoritmlash p65. p65

Tashqi 
sikl  i
Ichki 
sikl j
Takrorlanishlar
soni
1  da
1  dan  N-1  gacha
1-(N-1)=N-1  ta
2 da
1  dan  N-2  gacha
1(N -2)=N -2ta
165

---

3  da
1  dan  N-3 
gacha
1(N -3)=N -3  ta
4 da
1  dan  N-4 gacha
1(N -4)=N -4ta
N-2 da
1  dan  2  gacha
1(N-(N-2))  = 1 2 = 2 ta
N-1  da
1  dan  1  gacha
1(N-(N-1))  =11=1  ta
Hammasi sikllardagi  bo‘lib 
qadamlar  soni
1+2+3+...+(N-3)+(N-2)+(N-1)=
N (N -1):2ta
8.14-m ashq
8.1-,  8.4-jadvaNardagi  tokchalar  uchun  algoritm ni  jadval
yordamida  tekshiring.
7-sharh
Tokchalardagi  kublar saralanganidan  keyin  eng k o ‘p   kubli yoki 
eng  kam   kubli  tokchani  topish  masalasi  ju d a   ham  oson  ishga 
aylanganini  k o ‘rish  m um kin.  H aqiqatan,  bu  m asalalarning 
yechimlari  saralangan  tokchalardagi  kubli  tokchalardan  yoki  o ‘ng 
tomondagi  oxirgi  tokchasi  yoki  chap  tomondagi  oxirgi  tokchasi 
b o ‘ladi.
U c h a la   u s u ln in g   s ik ld a g i  q a d a m la r  s o n in i  ta q q o sla b , 
«pufakcha»  usu lin in g   boshqa  usullarga  nisbatan  sam aradorligi 
kam   em asligini,  m ura kkabligi  esa  eng  kam   e ka n lig in i  k o ‘rish 
m um kin.
K o ‘rilg an  uchala  usulning  sam aradorligini  aniqlash  uchun 
bajariladigan  am allar  sonini  yuqori  chegarasini  hisoblaymiz  (*  - 
ko ‘paytirish  am ali):
1)  Joylashtirish  usulida:
A m allar  soni  = (N -1 )+ 2 *((N -1 )+ (N -2 )+ ...+ 1 )+ ((N -1 )+ (N - 
2 )+ ...+ 1 )+ (N -1 )=
= 2 *(N -1 )+ 3 *((N -1 )+ (N -2 )+ ...+ 1 )= 2 *(N -1 )+ 3 *N *(N -1 ):2 =
= (4 *(N -1 )+ 3 *N *(N -1 )):2 = (4 + 3 *N )*(N -1 ):2  ta
2)  Oddiy tanlov usulida:
A m allar soni = (N -1 )+ 2 *((N -1 )+ (N -2 )+ ...+ 1 )+ 2 *(N -1 ) =
=   3 *(N -1 )+ 2 *N *(N -1 ):2 = (6 *(N -1 )+ N *(N -1 )):2  =  (6 + N )*(N - 
1):2 ta
3)  Oddiy alm ashtirish usulida:
A m a lla r  soni  = 4 * ((N -1 ) + (N -2 ) + ... + 1 )= 4 *N *(N -1 ):2   = 
2 *N *(N -1 )
166

---

8 .1 5 -  mashq
Yuqorida  keltirilgan  amallar  sonining  to ‘g ‘riligini  o‘zingiz 
tekshirib  chiqing.