Mavzu: Algoritmning asosiy turlari Maqsad:

Mavzu: Algoritmning asosiy turlari

Maqsad:

1) ta’limiy: O`quvchilarga algoritmning asosiy turlari haqida ma’lumot berish;

2) tarbiyaviy: O`quvchilarga iqtisodiy tarbiya berish;

3) rivojlantiruvchi: O`quvchilarga algoritmlash ko`nikmalarini rivojlantirish.

DTS: Algoritmning asosiy turlarini bilish.

I. Tashkiliy qism

II. Takrorlash

1. Qanday algoritmlar chiziqli algoritm deb ataladi?

2. Qanday algoritmlar tarmoqlanuvchi algoritm deb ataladi?

1. Qanday algoritmlar takrorlanuvchi algoritm deb ataladi?

III. Yangi mavzuni o`rganish

Har qanday algoritm mantiqiy tuzilishiga, ya’ni bajarilish tartibiga qarab uch asosiy turga bo‘linadi: chiziqli (ergashish), tarmoqlanuvchi va takrorlanuvchi.

Chiziqli algoritmlar. Barcha ko‘rsatmalari ketma-ket joylashish tartibida bajarib boriladigan algoritmlar chiziqli algoritmlar deyiladi. “Choy damlash”, doira yuzini hisoblash algoritmlari chiziqli algoritmlarga misol bo‘ladi. Lekin hayotimizdagi juda ko‘p jarayonlar shartlar asosida boshqariladi.

Tarmoqlanuvchi algoritmlar. Shartga muvofiq bajariladigan ko‘rsatmalar ishtirok etgan algoritmlar tarmoqlanuvchi algoritmlar deb ataladi. Algoritmlarning bu turi hayotimizda har kuni va har qadamda uchraydi. Eshikdan chiqishimiz eshik ochiq yoki yopiqligiga, ovqatla­nishimiz qornimiz och yoki to‘qligiga yoki taomning turiga, ko‘chaga kiyinib chiqishimiz ob-havoga, biror joyga borish uchun transport vositasini tanlashimiz to‘lash imkonimiz bo‘lgan pulga bog‘liqdir. Demak, tarmoqlanuvchi algoritmlar chiziqli algoritmlardan tanlanish imkoniyati bilan farqlanar ekan. Avvalgi darslardagi kvadrat tenglamani yechish, ikki sonning EKUBini topish algoritmlari tarmoqlanuvchi algoritmlarga misol bo‘ladi.

1–misol. Algoritmi formula yordamida berilgan funksiyani qiymatini hisoblashga doir tarmoqlanuvchi algoritmni blok-sxema yordamida tasvirlaymiz:

2 –misol. Berilgan ikkita A va B sonlardan kattasini topish uchun (IKT nomi bilan ataluvchi) algoritm tuzing.

Bu misoldan quyidagicha xulosa qilish mumkin: agar A B shart bajarilsa 4-banddagi ko‘rsatma qaralmaydi, aks holda, ya’ni A B bo‘lganda 3-banddagi ko‘rsatma qaralmaydi. IKT algoritmi tarmoqlanishni yaqqol tasavvur qilish imkoniyatini beradi.

Takrorlanuvchi (siklik) algoritmlar. Masalalarni tahlil etish jarayonida algoritmdagi ba’zi ko‘rsatmalar takroran bajarilishini kuzatish mumkin. Masalan, eng katta kvadratlar kesib olish masalasi (4-dars 5-misol), Evklid algoritmi (5-dars 2-misol). Hayotimizda ham juda ko‘p jarayonlar takrorlanadi. Masalan, darslarning har hafta takrorlanishi, har kuni nonushta qilish yoki maktabga borish va hokazo. Ko‘rsatmalari takroriy bajariladigan algoritmlar takrorlanuv­chi algoritmlar deb ataladi.

Takrorlanuvchi algoritmlar “ I := I + 1 ”, “ S := S + I ” yoki “ P := P * I ” ko‘rinishidagi ko‘rsatmalarning ishtiroki bilan ajralib turadi (* – ko‘paytirish amali). Bunday ko‘rsatmalarning mazmunini tushunish uchun takrorlanishning bir nechta qadamini ko‘rib chiqish lozim.

Odatda yig‘indi uchun boshlang‘ich qiymat (inglizchadan SUMM, ya’ni yig’indi ma’noli so’zning bosh harfi) S:=0 va ko‘paytma uchun (inglizchadan PRODUCT, ya’ni ko’paytma ma’noli so’zning bosh harfi) P: = 1 deb olinadi, chunki bu qiymatlar, ya’ni 0 va 1 lar, mos ravishda, yig‘indi va ko‘paytmaning natijasiga ta’sir etmaydi:

1-qadam: I := 1 bo‘lsin, u holda S := S + I = 0 + 1 = 1, P := P * I = 1 * 1 = 1;

2-qadam: I := I + 1 = 1 + 1 = 2, S := S + I = 1 + 2 = 3, P := P * I = 1 * 2 = 2;

3-qadam: I := I + 1 = 2 + 1 = 3, S := S + I = 3 + 3 = 6, P := P * I = 2 * 3 = 6;

4-qadam: I := I + 1 = 3 + 1 = 4, S := S + I = 6 + 4 = 10, P := P * I = 6 * 4 = 24.

3 –misol. 1 dan 1000 gacha bo‘lgan sonlar yig‘indisini, ya’ni S=1+2+3+…+1000 ni hisoblash algoritmini tuzing.

So‘zlar bilan ifodalangan algoritmda blok-sxema bilan mutanosiblikni ko’rsatish uchun qavslar ichida izohlar berib bordik. Odatda, takrorlanuvchi algoritmlarda “ I:=I+1 ” kabi ifoda sanagich deb yuritiladi. Bu misol yechimini chiziqli algoritm shaklida ham tashkil etish mumkin. Buning uchun har qanday natural N son uchun o’rinli bo’lgan 1+2+3+…+N  N·(N+1):2 ayniyatdan foydalanish kifoya (algoritmini mustaqil tuzing).

Quyidagi misollarda bu kabi ish anchagina qiyin.

4–misol. Ikki xonali sonlar ichidan raqamlari yig’indisi 7 ga teng sonlar yig‘indisini hisoblash algoritmini tuzing ([a] – a sonining butun qismi, / – bo‘lish amali).

5–misol. “Vatan sajdagoh kabi muqaddasdir” iborasini 20 marta yozdirish algoritmini tuzing. Bu misol algoritmini so’zlar orqali ifodalaymiz.

1) I ning qiymati 1 deb olinsin;

2) “Vatan sajdagoh kabi muqaddasdir” yozilsin;

3) I ga 1 ni qo‘shib I deb olinsin;

4) agar I  20 bo‘lsa 2-bandga o‘tilsin;

5) tugallansin.

Ko‘rib o‘tilgan algoritmlarga e’tibor qilsak, algoritmlar chiziqli, tarmoqlanuvchi yoki takrorlanuvchi qismlardan tashkil topganligini ko’rish mumkin. Demak, inson hayotida uchraydigan algoritmlar, asosan, shu uch turdagi algoritmlarning uzviy birligi sifatida namoyon bo‘ladi.

IV. Mustahkamlash uchun savol va topshiriqlar

1Qanday algoritmlar chiziqli algoritm deb ataladi? Misol keltiring.

2.Qanday algoritmlar tarmoqlanuvchi algoritm deb ataladi? Misol keltiring.

1. Qanday algoritmlar takrorlanuvchi algoritm deb ataladi? Misol keltiring.

2. Chiziqli, tarmoqlanuvchi va takrorlanuvchi algoritmlarning bir-biridan farqini tushuntiring.

3. Uchta sondan kattasini (UKT) aniqlab beruvchi algoritm tuzing.

Masqlar

1. Quyidagi algoritmlar qanday algoritm turiga misol bo‘lishini va natijasini aniqlang:

a) a:=3; x:=2*a+a*a. a=?, x=?

b) x:=1; x:=x+11, x:=x*x-4. x=?

d) a:=15; b:=a; a:=a-b. a=?, b=?

e) 1) a:=3;

2) agar a2 bo‘lsa, u holda x:=2*a+a*a va 4-bandga o‘tilsin, aks holda 3-bandga o‘tilsin;

3) x:=9-a*x;

4) natija x yozilsin;

5) tugallansin.

f) 1) x:=1;

2) agar x 2 bo‘lsa, u holda x:=x+11 va 4-bandga o‘tilsin, aks holda 3-bandga o‘tilsin;

3) x:=x*x-4;

4 ) natija x yozilsin;

5) tugallansin.

g) 1) a:=15;

2) b:= a;

3) agar a b bo‘lsa, u holda a:=a-b va 5-bandga o‘tilsin, aks holda 4-bandga o‘tilsin;

4) a:=a+b;

5) natija a, b yozilsin;

6) tugallansin.

1. Berilgan sonni ishorasini aniqlovchi algoritmni blok-sxema yordamida tuzing.

3. funksiyasini x ning [1; 10] oraliqdagi butun qiymatlarida hisoblash algoritmini blok-sxema shaklida tuzing.

IV. Uyga vazifa

3-mashq