Algoritmlash p65. p65

N
K
Shart
Q iym ati
Shart
ROST,
y a ’ ni  u  holda
YOLG‘ON,
y a ’ ni  aks 
holda
15
15
15<>15
YOLG‘ON
EKUB=15
N
K
Shart
Q iym ati
Shart
ROST,
y a ’ ni  u  holda
YOLG‘ON,
y a ’ ni  aks 
holda
15
12
15<>12
ROST
15>12
N = 15-12=3
-
3
12
3<>12
ROST
3>12
-
K=12-3=9
3
9
3<>9
ROST
3>9
-
K=9-3=6
3
6
3<>6
ROST
3>6
-
K=6-3=3
3
3
3=3
YOLG‘ON
EKUB=3
188

---

N
K
Shart
Q iym ati
Shart
ROST,
y a ’ni  u  holda
YOLG‘ON, 
y a ’ni  aks 
holda
15
4
15<>16
ROST
15>4
N = 15-4=11
-
11
4
11<>4
ROST
11>4
N = 11-4=7
-
7
4
7<>4
ROST
7>4
N=7-4=3
-
3
4
3<>4
ROST
3>4
-
K=4-3=1
3
1
3<>1
ROST
3>1
N=3-1=2
-
2
1
2<>1
ROST
2>1
N=2-1=1
-
1
1
1=1
YOLG‘ON
EKUB=1
M ana  bu  boshqa  gap.  Faqat  takrorlanish  qadam ini  oldindan 
b ilm a y m iz ,  shuning  u ch u n   T O K I  —  B A JA R   tu z ilm a s id a n  
foydalanib  tuzilgan  Saralovchi  M   tushunadigan  algoritm   quyida- 
gicha  bo‘ladi:
T O K I  N   < >   K   BAJAR 
AGAR N > K  
U  H O LD A
o‘tkaz  N -K ,  N  
AKS  H O LD A
o‘tkaz  K -N ,  K 
T A M O M  
T A M O M  
o ‘tkaz  N ,  EKUB
Jadvalda va algoritm da takrorlash shartini E vklid algoritm idagi 
asosiy  shartdan  fa rq li  teng  emaslik  sharti  kabi  yozilishi  dasturni 
m urakkablik darajasini kam aytiradi.
9.24-m ashq
Evklid  algoritmini  algoritmdagi  teng  emaslik  shartini  tenglik
shartiga  almashtirib  tuzing.
9.18-m asala
Saralovchi  M   ik k ita   N   va  K   sonlarning  eng  kich ik  um um iy 
karralisi E K U K (N ,  K )  n i topsin.
Yechim .  E K U B   n in g   ta ’ r if   b o ‘yich a   to p is h   a lg o ritm in i 
k o ‘rding iz.  E K U K   n i  ham  ta ’r if   b o ‘yicha  topish  ham  ancha 
m urakkab.  S huning  uchu n,  E K U B   va  E K U K   n i  quyidag i 
bog‘lanishidan  foydalanish  maqsadga  m uvofiq:
189

---

E K U B (N ,  K )  •  E K U K (N ,  K )=   N   •  K
Bu bog‘lanishdan  quyidagini  hosil  qilam iz:
E K U K (N ,  K )  =   N   •  K  /   E K U B (N ,  K )
E K U B   n i  topishni  E vklid  algoritm idan  foydalanib  masalani 
hal  etamiz:
o‘tkaz  N   •  K ,  S 
T O K I  N   < >   K   BAJAR 
AGAR N > K  
U  H O LD A
o‘tkaz  N -K ,  N  
AKS  H O LD A
o‘tkaz  K -N ,  K 
T A M O M  
T A M O M  
o‘tkaz  N ,  EKUB 
o‘tkaz  S  /   EK U B ,  E K U K
A lg o ritm   bajarilish jarayonida  N   va  K   ning  qiym ati  kamayib 
boradi,  shuning uchun u la rn i boshlang‘ich qiymatiga mos ko ‘payt- 
m ani  S  tokchada  saqlab  turduk.
9.25-m ashq
Bo‘yi  96  m,  eni  esa  88  m  ga  teng  to ‘g ‘ri  to ‘ rtburchak 
shaklidagi  kartonni  teng  kvadratlarga  ajratishm oqchi.  Shu 
ma’noda  eng  katta  tomonli  kvadratning  tomoni  uzunligi  necha 
m  ga  teng  bo‘ladi?
B ird a n   fa rq li  n a tu ra l  sonni  faqat  ik k ita   b o ‘ lu vchiga  ega 
b o ‘lsa:  o ‘z i va b ir,  u tub  son  deyiladi.  Tub  sonlarning b irin c h is i 
2  ga  teng.
B u n i  qarangki,  2 yakkayu-yagona ju ft tub  son b o ‘ la r ekan. 
Boshqa  har  qanday ju ft  son  tub  b o ‘ la   olm a yd i,  c h u n ki  u ning 
hech  b o ‘lm aganda  yana  b ir  u c h in c h i  b o ‘lu v c h is i  2  b o r  (o ‘ zi 
va  b ird a n   ta shqari).  Q uyida  100  dan  k ic h ik   tub  sonlar  ke l- 
tirilg a n :
2,  3,  5,  7,  11,  13,  17,  19,  23,  29,  31,  37,  41,  43,  47,  53,  59,  61, 
67,  71,  73,  79,  83,  89,  97.
N   va  K   o ‘zaro  tub  sonlar  d e yila d i,  agar  E K U B (N ,  K )= 1  
b o ‘ lsa.  M a ’ lu m k i,  har qanday ik k ita  tub  son o‘ zaro tub b o ‘la di. 
Shu  yerda  Suvchi  uchun  b ir  xossani  aytib  o ‘tm o q ch im iz:
190

---

A  litrli  va  B   litrli  idishlar  bor.  Suvchi  fa q a t  A  va  B   dan 
oshmaydigan  EKUB(A,  B )  ga  karrali  har  qanday  hajmdagi suvni 
o ‘lchab  olishi  mumkin.
Ya’n i, masalan, A = 2  va B=8 bo‘lsa,  E K U B (2,  8)=2 va shuning 
uchun  Suvchi 2,  4,  6,  8  litr   suvni  o‘lchab  olishi m um kin,  1,  3,  5, 
7  litr   suvni  o‘lchab  ololm aydi.