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



Yüklə 0,69 Mb.
səhifə4/5
tarix24.08.2023
ölçüsü0,69 Mb.
#140374
1   2   3   4   5
Laboratoriya

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= 123⋅⋅⋅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= Pi 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= Pi - 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 = xn 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 = x1 /1! + x 2 /2! + + xn / 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 i , 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 <= n ) shart bajarilguncha S = S + a i munosabat qiymati ketma-ket hisoblanadi.


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

Yüklə 0,69 Mb.

Dostları ilə paylaş:
1   2   3   4   5




Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©azkurs.org 2024
rəhbərliyinə müraciət

gir | qeydiyyatdan keç
    Ana səhifə


yükləyin