Chiziqli, tarmoqlanuvchi va takrorlanuvchi algoritmlarga oid masalalar

MIRZO ULUG’BEK NOMIDAGI O’ZBEKISTON MILLIY UNIVERSITETI JIZZAX FILIALI AMALIY MATEMATIKA FAKULTETI AXBOROT TIZIMLARI VA TEXNOLOGIYALARI YO’NALISHI 2-BOSQICH TALABASI

ABDUG’OFUROV JALOLNING

ALGORITMIK TILLAR VA DASTURLASH FANIDAN

“CHIZIQLI, TARMOQLANUVCHI VA TAKRORLANUVCHI ALGORITMLARGA OID MASALALAR”

MAVZUSIDAGI

MUSTAQIL ISHI

Chiziqli, tarmoqlanuvchi va takrorlanuvchi algoritmlar ustida amallar

Algoritmlar berilishi va ifodalanishiga qarab: chiziqli, tarmoqlanuvchi va takrorlanuvchi turlarga bo’linadi. Algoritmning turlari bilan tanishtirganda, avvalo hyech qanday shart tekshirilmaydigan va tartib bilan faqat ketma-ket bajariladigan jarayonlarni ifodalaydigan chiziqli algoritmlar aytib o’tiladi.

Chiziqli algoritmlar

Chiziqli algoritmlar algoritmlarning eng sodda va oddiy ko’rinishi hisoblanadi. Unda bajariladigan amallar ham buyruqlar ham qanday tartibda berilgan bo’lsa shunday tartibda ketma- ket bajariladi, ya’ni hech qanday shart tekshirilmasdan chiziqli algoritmlarda buyruqlar ketma- ket tartib bilan bajariladi. Chiziqli algoritmlarni quyidagi ko’rinishda ifodalash mumkin.

Bu yerda A1,…, AN lar chiziqli algoritmlarda bajarilishi kerak bo’lgan buyruqlar ketma- ketligidir.

2- misol.  funksiyani x ning ixtiyoriy qiymatlarida xisoblash algoritmini tuzing.

Yechish. Algoritmning blok sxema ko’rinishda ifodalaymiz.

3 - misol.  Geron formulasidan foydalanib uchburchak yuzini hisoblash algoritmini tuzing.

Yechish. Algoritmni blok sxema ko’rinishda ifodalaymiz.

armoqlanuvchi algoritmlar.  Shunday hisoblash jarayonlari mavjud bo’ladiki, bunda qo’yilgan ayrim mantiqiy shartlarning bajarilishiga qarab, bu jarayonlar bir nechta tarmoqqa bo’linadi va shu tarmoqlardan hyech bo’lmaganda bittasi bajariladi. Ana shunday jarayonlar uchun algoritmlar tuzishda tarmoqlanuvchi algoritmlardan foydalaniladi.Tarmoqlanuvchi struktura odatda qandaydir mantiqiy shartni tekshirish blokini o’z ichiga oladi. Tekshirish natijasiga ko’ra, tarmoq deb ataluvchi u yoki bu amallar ketma-ketligi bajariladi.

Tarmoqlanuvchi algoritm to’la va qisqartirilgan ko’rinishda berilishi mumkin. Ular quyidagicha sxema orqali ifodalanadi:

ha yo’q ha yo’q

shart shart

1 - amal 2-amal amal

a) to’la ko’rinish b) qisqartirilgan ko’rinish

1-misol. Ixtiyoriy berilgan x va u sonlaridan eng kattasini topish algoritmini tuzing. boshlash

x,u ni kiritish

xa yuk

z = x x >= y z = y

z ni chiqarish

tamom

Takrorlanuvchi va murakkab jarayonlar uchun algoritmlar tuzish.

Takrorlanuvchi algoritmlar.

Shunday hisoblash jarayonlari mavjud bo’ladiki, bunda uning ayrim bo’laklarini bir necha marta takroran hisoblashga to’g’ri keladi. Bunday jarayonlar uchun algoritmlar tuzishda takrorlanuvchi algoritmlardan foydalaniladi.

Hisoblash jarayonining ko’p marta takrorlanadigan qismi ichki sikl tanasi (jismi) deb yuritiladi. Takrorlanuvchi algoritm 2 xil ko’rinishga ega bo’ladi:

Sikl - gacha takrorlanuvchi algoritm quyidagi ko’rinishga ega:

yo’q

sikl tanasi shart

ha

a) sikl - gacha ;

Bu ko’rinishdagi algoritmda avval sikl tanasi bajarilib, so’ngra sikldan chiqish sharti tekshiriladi, ya’ni sikl tanasi qo’yilgan shart bajarilib turguncha takrorlanaveradi.

Sikl - hozircha  takrorlanuvchi algoritm quyidagi ko’rinishga ega:

yo’q

ha

shart sikl tanasi

b) sikl - hozircha.

Bu ko’rinishdagi algoritmlarda avval shart tekshiriladi, so’ngra agar shart qanoatlantirsa, sikl tanasi bajariladi, aks holda hisoblash to’xtatiladi.

1-misol.  funksiyani x ning [a,b] oraliqda h=0.1 qadam bilan o’zgarish qiymatini hisoblash algoritmini tuzing.

Yechish.

1) Sikl-gacha 2) Sikl - hozircha

A,B,H A,B,H

X=A X=A

ha yo’q

y =√x³ + x²+ 1 X<=B

y ni chiqarish tamom

X = X + H

y =√x³ + x²+1

ha yo’q

X<=B tamom y ni chiqarish

X = X + H

Bundan tashqari murakkab ko’rinishdagi takrorlanuvchi jarayonlar uchun algoritmlar tuzishda ichma-ich joylashgan takrorlanuvchi algoritmlardan foydalaniladi.

Misol. ifodaning qiymatini hisoblash algoritmini tuzing.

Yechish. Bu yerda i bo’yicha takrorlanuvchi algoritm tashqi, j bo’yicha takrorlanuvchi algoritm ichki sikllar deb yuritiladi.

boshlash

S=0:P=1

i=1
j=1
P=P(i+j)/2

j =j+1 ha

ha yo’q

j<=3 S = S + P i=i+1 i<=5

yo’q

S ni chiqarish

tamom