Algoritmlash p65. p65

K n in g
qiym ati
Kunlarga mos shokoladlar soni
Yuqori
chegaraning
qiym ati
1
2
3
4
5
6
7
1
5
1
7
5
10
2
9
5
10
2
10
5
10
20
3
21
5
10
20
40
4
3 9
5
10
20
40
4
3 0 0
5
10
20
40
80
160
320
7
Demak,  K  qanchalik kattalashsa N  ham shunga bog‘liq  ravishda 
ortishi m um kin ekan. Y uqori chegara aniq bo‘lmaganda takrorlanish 
qanday tashkil  etiladi?
Bu  savolga  T O K I  —  BAJAR tuzilm asi javob  beradi: 
o‘ tkaz  1,  Ek 
o‘ tkaz  5,  t1 (E k)
T O K I  t1 (E k)  < =   K   BAJAR 
o‘tkaz  E k+1,  Ek 
o‘tkaz  2 t1 (E k -1 ),  t1 (E k)
T A M O M
A lg o ritm n i  is h la s h in i  K = 9 9   da  ja d va l  yordam ida  k o ‘ rib  
chiqamiz:
184

---

Ko‘ rsatm a
Ek
t1 (* )
Shart
qiym ati
Ek+1 Ek-1
o‘tkaz  1 ,Ek
1
-
-
-
-
o ‘t k a z 5 ,  t1(E k)
1
t1(1)=5
-
-
-
5 = t1 (E k )  < =   K =99
1
-
ROST
2
1
o ‘tkaz  Ek+1,  Ek
2
-
-
-
-
o‘tkaz2t1(Ek-1),t1(Ek)
2
t1(2)=2t1(1)=25=10
-
-
-
1 0 = t1 (E k )  < =   K =99
2
-
ROST
3
2
o ‘tkaz  Ek+1,  Ek
3
-
-
-
-
o‘tkaz2t1(Ek-1),t1(Ek)
3
t1(3)=2t1(2)=210=20
-
-
-
2 0 = t1 (E k )  < =   K =99
3
-
ROST
4
3
o ‘tkaz  Ek+1,  Ek
4
-
-
-
-
o‘tkaz2t1(Ek-1),t1(Ek)
4
t1(4)=2t1(3)=220=40
-
-
-
4 0 = t1 (E k )  < =   K =99
4
-
ROST
5
4
o ‘tkaz  Ek+1,  Ek
5
-
-
-
-
o‘tkaz2t1(Ek-1),t1(Ek)
5
t1(5)=2t1(4)=2-40=80
-
-
-
8 0 = t1 (E k )  < =   K =99
5
-
ROST
6
5
o ‘tkaz  Ek+1,  Ek
6
-
-
-
-
o‘tkaz2t1(Ek-1),t1(Ek)
6
t1(6)=2t1(5)=280=160
-
-
-
1 6 0 = t1 (E k )  < =   K =99
6
-
YOLG‘ON T o ‘xtaydi
Demak,  K =99  bo ‘lganda  Bek  ota-onasini  6-kun  mehmon 
qilgan.
9.23-m ashq
Saralovchi  M  uchun  Bek  ota-onasini  mehmon  qilganda 
nechta  shokoladi  borligini  aniqlovchi  algoritm  tuzing.
Qo‘shimcha  masalalar
Keling,  bu  bo ‘lim da  Saralovchi  M   n i biz  boshqaramiz. 
Quyidagicha talab  bilan  t1 (*)  ning  tokchalarini  to ‘ldiram iz:
t1(1)=0; t1(2)=1;
t1 (3 )=  t1 (1 )+ t1 (2 );  t1 (4 )=  t1 (2 )+ t1 (3 );
185

---

ya’ni,  keyingi  har  b ir  tokchadagi  son  oldingi  ik k ita   tokchadagi 
sonlarning  yig‘indisiga  teng.  Bu  usulda  hosil  qilinadigan  sonlarni 
Fibonachi  sonlari  deb  atashadi.
9 .1 6 -  masala
Saralovchi  M  b irin c h i  N  ta  Fibonachi  sonini  hosil  qilsin.
Yechim.  Fibonachi  sonlarining  ta ’rifig a   ko ‘ra  algoritm   tuzish 
yetarli:
o‘ tkaz  0,  t1 (1 ) 
o‘ tkaz  1,  tl( 2 )
3  D AN N   G ACHA BAJAR
o‘tkaz  t1 (i-2 )+ t1 (i-1 ),  t1 (i)
T A M O M
9.24-m ashq
Saralovchi  M  1  dan  50  gacha  bo‘lgan  sonlar  ichida  nechta
Fibonachi  soni  borligini  aniqlasin.
Q uyidagilarni  eslatib  o‘tamiz:
•  H   natural  son  N   natural  sonining  bo‘luvchisi  deb  ataladi, 
agar shunday G  natural son topilsaki, N = G -H  (yoki N /H = G ) 
shart  bajarilsa.
•  H  natural son natural N  va K  sonlarining umumiy bo‘luvchisi 
deb  ataladi,  agar H  son N  ning ham,  K  ning ham bo‘luvchisi 
bo ‘lsa.
•  H   natural  son  natural  N   va  K   sonlarining  eng katta umumiy 
bo‘luvchisi deb ataladi,  agar H  son N  va K  sonlarining um um iy 
bo‘luvchil ari  ichida  eng  kattasi  bo‘lsa.
•  H   natural  son  N   natural  sonining  ka rra lisi  deb  ataladi,  agar 
shunday  G   natural  son  topilsaki,  H = G -N   (yoki  H /N = G ) 
shart  bajarilsa.
•  H   natural  son  natural  N   va  K   sonlarining  umumiy  ka rra lisi 
deb  ataladi,  agar  H   son  N   ning  ham,  K   ning  ham  karralisi 
bo ‘lsa.
•  H   natural son natural N  va K  sonlarining  eng kich ik umumiy 
ka rra lisi deb  ataladi,  agar H   son N  va K  sonlarining um um iy 
ka rra lila ri ichida  eng  kich ig i bo‘lsa.