Algoritmlash p65. p65

8.3-rasm
2-sharh
Bu masalada ham Bek N -M yoki M -N  tartib raqamli tokchalarni 
ishlata  olmaydi.
Barcha  hollam i  ko‘rib  chiqamiz.
1- 
hol.  M  
=N +1  bo‘lsin,  u  holda 
M>N. 
Demak,  yordam chi 
tokcha N —1 yoki M +1 bo‘ladi. Bu tokchalardan qaysi b iri ekanligini 
qanday  aniqlaym iz?  Agar  N>1  bo ‘lsa,  javob  N -1,  aks  holda, 
uchinchi  tokcha  m avjudligini  hisobga  olsak,  javob  M +1.
2- hol.  N  
= M + 1  bo‘lsin,  u  holda  N >M .  Demak,  yordam chi 
tokcha,  agar  M >1  b o ‘lsa:  M -1 ,  aks  holda,  u c h in c h i  tokcha 
m avjudligidan:  N+1.
Agar 
M  
= N + 1 ,  M —N = 1,  N —M =   —1  b ir  x il  sh a rtlig in i  va 
N — 
= M + 1 ,  N —M   =1,  M —N   =   —1  b ir  x il  shartligini  e’tiborga 
olsak, ko ‘rin ib  tu rib d iki, yonm a-yon turish sharti quyidagicha ekan:
(M -N ) 
• 
(N -M )=  
- 1 .
C ho‘zib  o‘tirmasdan  algoritm ni  yozishni boshlaymiz:
AGAR  (M -N ) 
• 
(N -M )=  
—1  {bu  holda 
N  
va 
M  
yonm a-yon} 
U HOLDA
AGAR 
M - N =  1 
{bu  holda 
M
= N + 1,  ya’n i 
M>N}
U HOLDA
AGAR 
N>1 
U HOLDA
o‘tkaz  tokcha(M ),  tokcha(N -l) 
o‘tkaz  tokcha(N),  tokcha(M)
AKS  HOLDA
o‘tkaz  tokcha(M ),  tokcha(M +1) 
o‘tkaz  tokcha(N),  tokcha(M)
TAMOM
AKS  HOLDA 
{bu  holda  N = M + 1 ,  ya’n i  N > M }
AGAR M>1 
U HOLDA
o‘tkaz  tokcha(M ),  tokcha(M -l) 
o‘tkaz  tokcha(N),  tokcha(M)
AKS  HOLDA
o‘tkaz  tokcha(M ),  tokcha(N+1) 
o‘tkaz  tokcha(N),  tokcha(M)
143

---

T A M O M  
T A M O M  
AKS  H O LD A
{N  
va 
M  
yonm a-yon emas}
T A M O M
Juda  ham  uzun-a!  Yaxshi  ham  o‘ngga  surish  orqali  algoritm  
qism iarini  ajratib  oldik.
3-sharh
B a ’zan  algoritmda  { va }  orasida  tushunish  oson  bo ‘lishi  uchun 
izohlar berib  boramiz.
3-hol. Tokchalar yonma-yon emas, ya’n i 
N
< >
M
+1 va 
M
< >
N
+1 
yoki (
M
-
N
)-(
N
-
M
)< > -1 .  Bu holda 
N
-tokcha va 
M
-tokcha orasida 
hech bo‘lmaganda b itta  tokcha bor.  M a ’lum ki, 
M + N  
va 
N
+
M
+1 
sonlardan  b iri  ju ft  bo ‘ladi.  U   holda  sonlarning  o ‘rta  arifm etigi 
haqidagi xossalarni va [a]  a sonining butun qism i ekanligini inobatga 
olsak,  quyidagi  tengsizlikdan b iri  o ‘rin li:
N
< [(
N
+
M
+ 1 ):2 ]<
M  
yoki 
M
< [(
N
+
M
+ 1 ):2 ]<
N
.
Demak, bu holda yordam chi tokcha [(
N
+
M
+1):2] bo‘lar ekan. 
E ndi  nuqtalar  o‘rniga  quyidagini  yozish  yetarli: 
o‘ tkaz  to kch a (M ),  to k c h a ([(N + M + 1 ):2 ]) 
o‘ tkaz  tokcha(N ),  tokcha(M )