Yoki savol shaklida bo‘ladi. Masalan, «Kvadrat tenglamani yechish», «Dengizda nechta tomchi suv bor?», «Ikki karra ikki necha bo‘ladi?» kabi

Takrorlanuvchi algoritmlar



Agar biror masalani yechish uchun zarur bo‘lgan amallar ketma-ketligining ma’lum bir qismi biror parametrga bog‘liq holda ko‘p marta qayta bajarilsa, bunday jarayon takrorlanuvchi algoritm deyiladi. Takrorlanuvchi algoritmlarga misol sifatida odatda qatorlarning yig‘indisi yoki ko‘paytmasini hisoblash jarayonlarini qarash mumkin.

• 
  misol. Birdan n gacha bo‘lgan natural sonlarning yig‘indisini hisoblash algoritmini tuzaylik. Masalaning matematik modeli quyidagicha:
  

n


S =1+ 2 + 3+...+ n =∑i


i=1


Bu yig‘indini hisoblash uchun, avvalo, natiga boshlangich qiymatini S=0 va indeksning boshlangich qiymatini i =1 deb olamiz va joriy amallar S = S + i va i = i + 1 hisoblanadi. Bu erda birinchi va ikkinchi qadamlar uchun yig‘indi hisoblandi va keyingi qadamda i parametr yana bittaga orttiriladi va navbatdagi qiymat avvalgi yig‘indi S ga qo‘shiladi. Mazkur jarayon shu tartibda indeksning joriy qiymati i≤ n sharti bajarilmaguncha davom ettiriladi va natijada, izlangan yig‘indiga ega bo‘lamiz. Ushbu fikrlarni quyidagi so‘zlar orqali ifodalangan algoritm bilan ifodalash mumkin:


kiritish (n);


S= 0 - natijaning boshlang‘ich qiymati; i= 1 - indeksning boshlang‘ich qiymati;
S= S + i - natijaning joriy qiymatini hisoblang; i= i+ 1- indeksning joriy qiymatini hisoblang;
agar (i ≤ n) sharti tekshirilsin va u bajarilsa => (4) ; 7) muhrlash (S).
Bu jarayonga mos keladigan blok-sxemaning ko‘rinishi 1.13-rasmda tasvirlangan.



1.13-rasm. 1 dan n-gacha bo‘lgan sonlar yig‘indisini hisoblash blok-sxemasi


Yuqorida keltirilgan so‘zlar asosida ifodalangan algoritm va blok-sxemadan ko‘rinib turibdiki, amallar ketma-ketligining ma’lum qismi parametr i ga nisbatan n marta takrorlanadi.

• 
  misol. Quyidagi ko‘paytmani hisoblash algoritmi va blok-sxemasini tuzaylik: P= 1⋅2⋅3⋅⋅⋅n = n!
  

(odatda, 1 dan n gacha bo‘lgan natural sonlarning


ko‘paytmasi n! ko‘rinishda belgilanadi va “en” faktorial deb ataladi: P=n! n
( jarayonning matematik modeli: P =∏i ) [2, 57-58 b.].


i=1


Ko‘paytmani hosil qilish algoritmi ham yig‘indini hosil qilish algoritmiga o‘xshash, faqat ko‘paytmani hosil qilish uchun, avvalo, i=1 da P= 1 deb olinadi, so‘ngra i= i +1 da P= P∗i munosabatlar hisoblanadi. Keyingi qadamda i parametrning qiymati yana bittaga orttiriladi va navbatdagi qiymat avvalgi hosil bo‘lgan ko‘paytma - P ga ko‘paytiriladi. Bu jarayon shu tartibda


to i ≤ n sharti bajarilmaguncha davom ettiriladi va natijaviy ko‘paytmaning qiymatiga ega bo‘lamiz. Quyidagi so‘zlar orqali ifodalangan algoritmda bu fikrlar o‘z aksini topgan:


kiritish (n);


P= 1 - natijaning boshlang‘ich qiymati; 3) i= 1 - indeksning boshlang‘ich qiymati;


P= P∗i - natijaning joriy qiymatini hisoblash;


i= i+1 - indeksning joriy qiymatini hisoblash;


agar (i <= n) shart bajarilsa, u holda => (4); 7) muhrlash (P).


Bu algoritmga mos blok-sxema 1.14-rasmda keltirilgan.



1.14-rasm. 1 dan n gacha bo‘lgan sonlar ko‘paytmasini hisoblash blok-sxemasi


Yuqorida ko‘rilgan yig‘indi va ko‘paytmalarning blok-sxemalaridagi takrorlanuvchi qismlariga (punktir chiziqlar ichiga olingan) 1.14 rasmdagi sharti keyin berilgan takrorlanuvchi struktura mos kelishini ko‘rish mumkin.

• 
  misol. Yuqoridagi blok-sxemalarda shartni oldin tekshiriladigan holatda n
  

chizish mumkin edi. Masalan, S =∑i yig‘indini xisoblash algoritmi tadqiqi i=1


keltiriladi. Bu masalani yechishda algoritmning takrorlanuvchi qismiga quyidagi sharti oldin berilgan takrorlanuvchi strukturaning mos kelishini ko‘rish mumkin.


kiritish (n); S=0;
i = 0;
agar ( i > n ) => (8); i = i + 1;
S = S + i ;


shartsiz o‘tish=> (4); 8) muhrlash (S).
Bu algoritmga mos blok-sxema 1.15- rasmda keltirilgan.



1.15-rasm. 1 dan n gacha bo‘lgan sonlar yig‘indisini hisoblash blok-sxemasi 4-misol. Haqiqiy x sonining n chi darajasini hisoblash masalasi ko‘riladi.
Uning matematik modeli: q = xⁿ ko‘rinishga ega.


Takrorlanuvchi jarayonni tashkil etish quyidagidan farqli, yuqoridagilar bilan bir xil:


- ko‘paytirish jarayoni uchun boshlang‘ich qiymat berilishi: q = 1 ; - joriy natijani hisoblash: q = q * x ifoda bo‘yicha amalga oshiriladi.
Shunday qilib, x ning n chi darajasini hisoblash uchun takrorlanuvchi jarayonni tashkil etish blok-sxemasi 1.16-rasmda keltirilgan.



1.16-rasm. Hisoblash blok-sxemasi

• 
  misol. Quyidagi munosabatni hisoblash kerak bo‘lsin [2, 55-56 b.]: n x i
  

S = ∑ .


^{i =1 i!}


Munosabatni ochib, quyidagi ko‘rinishda yozish mumkin: s = x¹ /1! + x ² /2! + ^… + xⁿ / n! .


Masalani yechish algoritmida boshlang‘ich qiymat sifatida s=0 ni olamiz, chunki ifodada yig‘indi belgisi mavjud. Yig‘indi belgisi ostidagi munosabat kasr sonni anglatadi: suratda - x ⁱ , mahrajda - i


!. Ularning har biri uchun boshlang‘ich va joriy munosabatlar shakllantiriladi:

	surat	mahraj	natija
boshlang‘ich munosabat	q = 1	p = 1	s=0

joriy munosabat

q = q * x

p = p * i

s = s + q / p

1.17-rasm. Hisoblash blok-sxemasi


Bu jarayonni shakllantirish uchun i indeks-parametri ishlatiladi. Indeks-parametrni boshqarish amallari quyidagicha:
i = 1 – parametrning boshlang‘ich qiymati,


i = i + 1 – parametrning orttirmasi (orttirma h=1),
i ≤ n – jarayon yakunlanish sharti.


Bunga muvofiq, masalani yechish blok-sxemasi quyidagi 1.17-rasmdagi ko‘rinishga ega bo‘ladi.

• 
  ^{misol. A={ai} (i=1, 2, …, n) massiv elementlarining yig‘indisini hisoblash jarayonini aks ettiradigan algoritm yarating.}
  

n


^{Masalaning matematik modeli quyidagidan iborat: S=∑ai .}
i=1


Yig‘indini hisoblash uchun S o‘zgaruvchidan foydalanamiz va uning boshlang‘ich qiymati deb S
^{= 0 olinadi. So‘ngra indeksning} i = 1 qiymatidan boshlab, uning i = i + 1 orttirmasi bilan to ( i <= <sup>n ) shart bajarilguncha S = S + a i munosabat qiymati ketma-ket hisoblanadi.


Quyidagi algoritmda jarayon amallari bajarilishi ketma-ketligi keltiriladi: kiritish (n, a i );</sup>