Algoritmlash p65. p65

T artib  raqam lar
1
2
3
4
t1(*)
3
0
2
7
t2(*)
5
9
3
3
S= t1(1 )t2(1)+t1 (2)t2(2)+t1 (3)t2(3)+t1 (4)t2(4)=15+0+6+21=42
179

---

S= t1(1)t2(2)+t1 (2)t2(1 )+t1 (3)t2(4)+t1 (4)t2(3)=27+0+6+21=48
S= t1(1)t2(3)+t1 (2)t2(4)+t1 (3)t2(2)+t1 (4 )t2 (1 )= 9 + 0 + 1 8 + 3 5 = 6 2
S= t1(1)t2(4)+t1 (2)t2(2)+t1 (3)t2(1)+t1 (4 )t2 (3 )= 9 + 0 + 1 0 + 2 1 = 4 0
S =  t 1 ( 1 ) t 2 ( 1 ) + t 1  ( 2 ) t 2 ( 3 ) + t 1  ( 3 ) t 2 ( 4 ) + t 1  ( 4 ) t 2 ( 2 ) = 1 5 + 0 + 6 + 6 3 = 8 4
Yana  davom  ettirish  m um kin.  Lekin bu  usulda  hamma  h o ln i 
k o ‘rib   chiqish  ancha  m urakkab  b o ‘la r  ekan.  Shuning  uchun 
matematikaga  m urojaat  etamiz:
Agar A  <  B  va  C  <  D   bo ‘lsa,  u  holda
A   •  C  +  B  •  D   >  A   •  D   +  B  •  C
b o ‘ladi.
Haqiqatan,  A  -   B  <  0  va  C  -  D   <  0  b o ‘lgani  uchun:
(A  -   B)  •  (C  -   D )  >  0  о  A   •  (C  -   D )  -   B  •  (  C  -   D )  >  0  о  
о  A   •  C  +  B  •  D   -  A   •  D   -   B  •  C  >  0  о  A   •  C  +  B  •  D   > A   •
D   +  B  •  C
Dem ak, ju ftlik la r   k o ‘paytm asining  y ig ‘in d is i  eng  katta  q iy- 
m a tli b o ‘ lis h i uchun ju ftlik la rn i b ir x il ta rtib d a   (y o k i ikka la sin i 
o ‘ sish  ta rtib id a ,  y o k i  ikka la sin i  kam ayish  ta rtib id a )  saralash 
lo zim .
Bu  xulosaga  asosan  tuzilgan  algoritm   quyidagicha  bo‘ladi: 
TA K R O R LA N S IN  N -1  M AR TA 
1  D AN N -i G ACH A BAJAR 
AGAR  t1 (j)< t1 (j+ 1 )
{t1(*)-qavatdagi tokchalarni  saralash}
U  H O LD A
o‘tkaz  t1 (j+ 1 ),  Z t 
o‘tkaz  t1 (j),  t1 (j+ 1 ) 
o‘tkaz  Z t,  t1 (j)
T A M O M
AGAR  t2 (j)< t2 (j+ 1 )
{t2(*)-qavatdagi tokchalarni  saralash}
U  H O LD A
o‘tkaz  t2 (j+ 1 ),  Z t 
o‘tkaz  t2 (j),  t2 (j+ 1 ) 
o‘tkaz  Z t,  t2 (j)
180

---

T A M O M  
T A M O M  
T A M O M  
bo‘shat  S
TA K R O R LA N S IN  N  M A R TA  
o ‘tkaz  S + t1 (i)  •  t2 (i)  ,  S 
T A M O M
{yig‘in d in i hosil qilish}
9.17-m ashq
N  ta  tokchali  t1(*)  va  t2(*)  qavatlar  berilgan.  Saralovchi 
M  t1(i)-t2(j)  juftliklarni  shunday  tashkil  etib  S  tokchaga  yig‘ishi 
kerakki,  S  ning  qiymati  boshqa juftliklarga  nisbatan  eng  kichik 
b o ‘ lsin ,  y a ’ ni  t1 (*)  va  t2 (*)  q a va tla r  to k c h a la ri  t(i)- t( j)  
ko‘paytmalarining  yig‘indisi  eng  kichik  bo‘lsin.