Algoritmlash p65. p65

9 .1 7 -  masala
Saralovchi  M   ik k ita   N   va  K   sonlarni  eng  katta  um um iy 
bo‘luvchisi  E K U B (N ,  K )  n i topsin.
186

---

Yechim.  1-usul. Bu masalani yechishni ta ’r if  bo‘yicha bajarishga 
harakat  qilish  m um kin,  ya’n i  sonlar  teng  bo ‘lsa  E K U B = N ,  aks 
h o ld a   ik k a la   so n n i  b ir  chekkadan  n a tu ra l  sonlarga  b o ‘ lib  
boraveramiz va  har  qadamda ikkala  sonning bo‘luvchisini  E K U B  
deb  olaveram iz,  bu  holda  jarayon  b o ‘lu vch i  bo ‘linuvchilardan 
kichigiga  teng  b o ‘lis h i  b ila n   to ‘xta tila d i.  L e kin   bu  usulda  b ir 
muammo bor: bo‘lin ish  shartini Saralovchi M  tushunadigan tarzda 
qanday  yozish  m um kin.  Biz  biladigan  bo‘lin ish   shartlari  (qoldiq 
nolga tengligi  —  N   mod  i  =   0  yoki butun bo‘lin ish   sharti  -  [N /i] 
=   N /i,  bu yerda  [a]  —  a  sonini butun  qism i)  Saralovchi M  uchun 
tushunarli  emas.
B o‘lin ish   degan  am alni  boshqa  mazmuniga  e’tib o r  beramiz: 
agar  D  soni  H  soniga bo‘linsa,  u  holda  shunday  G son  m avjudki, 
D  dan  G marta  H  n i  ayirsak  0  hosil  bo‘ladi.  Haqiqatan,  agar  D 
soni  H  soniga bo ‘linsa,  u  holda
D = G- H  = H  + H  + H + H  + ... + H
^--------------------V------------------- '
yoki 
G ta
D - ( H  + H  + H + H  + ... + H  = 0
'-------------------- V-------------------- '
G ta
Shuni e’tiborga  olib  N   sonini i ga bo‘lgandagi  qoldiqni topish 
uchun  quyidagi  algoritm ni  tuzamiz: 
o ‘tkaz  N ,  Q oldiqN 
T O K I  Q oldiqN   > = i  BAJAR
o ‘tkaz  Q oldiqN   -  i,  Q oldiqN 
T A M O M
E ndi bu  algoritm ni  qo‘llab  masalani  hal  eta  olamiz:
AGAR N   =   K 
U  H O LD A
o ‘tkaz  N ,  EKU B 
{E K U B   aniqlandi}
AKS  H O LD A
AGAR N > K  
{sonlardan k ich ig in i aniqlash}
U  H O LD A
o‘tkaz  N ,  S 
AKS  H O LD A
o‘tkaz  K ,  S 
T A M O M
o‘tkaz  1,  EKUB
{har  qanday  son  1  ga bo‘lin a d i}
187

---

2  D AN  S  G ACHA BAJAR
{bo‘luvchilar  qadami} 
o‘tkaz  N ,  Q oldiqN 
T O K I  Q oldiqN   > = i  BAJAR
o ‘tkaz  Q oldiqN   -  i,  Q oldiqN 
T A M O M  
o‘tkaz  K ,  Q oldiqK 
T O K I  Q oldiqK  > = i  BAJAR
o ‘tkaz  Q oldiqK  -  i,  Q oldiqK 
T A M O M
AGAR  Q oldiqN   =   0  VA Q oldiqK  =   0 
U  H O LD A
o ‘tkaz  i,  EKUB 
T A M O M  
T A M O M  
T A M O M
Bu yerda S sonlardan k ic h ig in i aniqlaydi.  L ekin algoritm  juda 
uzun  va  sam aradorligi  past.  E K U B   to p ish   m uam m o  b o ‘lib  
qoldiku!
2-usul.  Lekin m uam moni eramizdan avvalgi I I I  asrda yashagan 
m atematik E vklid osongina hal q ilib  qo‘ygan ekan.  U ning algoritm i 
deyarli  quyidagicha  ifodalanadi:
Evklid  algoritm i:  agar  N   va  K   sonlar  teng  b o ‘lsa,  u  holda 
E K U B = N ;  aks  holda  kattasidan  kich ig in i  ayirib  kattasini  o‘rniga 
qabul  qilam iz  va  algoritm ni  yana boshidan  boshlaymiz.
E vklid  a lgoritm ini  m isollarda ko ‘ramiz: