Takrorlanuvchi (siklik) algoritmlar

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 takrorlanuvchi 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
Qanday algoritmlar chiziqli algoritm deb ataladi? Misol keltiring.
Qanday algoritmlar tarmoqlanuvchi algoritm deb ataladi? Misol keltiring.
Qanday algoritmlar takrorlanuvchi algoritm deb ataladi? Misol keltiring.
Chiziqli, tarmoqlanuvchi va takrorlanuvchi algoritmlarning bir-biridan farqini tushuntiring.
Uchta sondan kattasini (UKT) aniqlab beruvchi algoritm tuzing.
Masqlar
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 a>2 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.
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
SANA___________________ Tasdiqlayman O’IBDO’
Informatika-9. 10 –dars.
Mavzu: Algoritmning asosiy tuzilmalarimavzusini takrorlashga doir topshiriqlar
Maqsad:
1) ta’limiy: o`quvchilarga chiziqli, tarmoqlanuvchi va takrorlanuvchi algoritmlar tuzishni o`rgatish;
2) tarbiyaviy: o`quvchilarni vatanga muhabbat ruhida tarbiyash;
3) rivojlantiruvchi: O`quvchilarning algoritm tuzish ko`nikmalarini rivojlantirish.
DTS: chiziqli, tarmoqlanuvchi va takrorlanuvchi sodda algoritmlar tuza olish
Kompetensiya:
TK3 - doimiy ravishda o’z-o’zini intelektual va kreativ rivojlantirish, hayot davomida mustaqil kognitivlik ko’nikmalarini mustaqil ravishda rivojlantirib boradi;
FK1 - axborotlarni izlash va elektron vositalarda yig‘ish ko’nikmasiga ega bo’ladi
Tashkiliy qisim:
1) salomlashish;
2) davomatni aniqlash
II. Takrorlash
Qanday algoritmlar chiziqli algoritm deb ataladi? Misol keltiring.
Qanday algoritmlar tarmoqlanuvchi algoritm deb ataladi? Misol keltiring.
Qanday algoritmlar takrorlanuvchi algoritm deb ataladi? Misol keltiring.
Chiziqli, tarmoqlanuvchi va takrorlanuvchi algoritmlarning bir-biridan farqini tushuntiring.
III. Yangi mavzuni o`rganish
Aytib o’tilganidek, har qanday algoritmni chiziqli, tarmoqlanuvchi va takrorlanuvchi algoritmlarning o’zaro uyg’un birikmasi ko’rinishida tasvirlash mumkin. Shuning uchun quyida keltiriladigan tuzilmalarni o’zlashtirib olish maqsadga muvofiq bo’ladi. Bu tuzilmalarning ahamiyatga molik tomoni shundan iboratki, ularda bitta kirish va bitta chiqish bor.
1. Chiziqli tuzilma. Ketma-ket keladigan oddiy harakatni, ya’ni qiymat berish yoki tegishli ko‘rsatmalar berishdangina iborat bo’ladi.
So’zlar orqali
|
Blok-sxema ko’rinishida
|
oddiy harakat 1
oddiy harakat 2
…
oddiy harakat N
|
|
1-masala. Uchta a, b, c sonlar berilgan. a va b sonlar yig’indisi yarminini, a va c sonlar ayirmasini modulini, b va c sonlar ko’paytmasini kvadratini hisoblash algoritmini tuzing.
2-masala. Radiusi R ga teng aylana uzunligi, doira yuzi va shar hajmini hisoblash algoritmini tuzing (yo’llanma: L=2R; S=R2; V=R3).
2. Tarmoqlanish tuzilmalari. Bu tuzilmalar shart tekshirish natijasiga (ha yoki yo’q) ko’ra ikki yo’ldan birini tanlash imkoniyatini beradi. Bu tuzilmalar, asosan, 2 xil ko’rinishda bo’ladi.
a) agar – u holda:
So’zlar orqali
|
Blok-sxema ko’rinishida
|
agar shart
u holda
ko’rsatmalar guruhi
oxiri
|
|
3-masala. Berilgan a son musbat bo’lsa, u holda uning kvadratini va kvadrat ildizini hisoblash algoritmini tuzing.
4-masala. Uchta a, b, c sonlar berilgan. Ular ichida manfiy bo’lmagan sonlar kvadrat ildizini hisoblash algoritmini tuzing.
b) agar – u holda – aks holda:
So’zlar orqali
|
Blok-sxema ko’rinishida
|
agar shart
u holda
ko’rsatmalar guruhi 1
aks holda
ko’rsatmalar guruhi 2
oxiri
|
|
5-masala. Uchta a, b, c sonlar berilgan. a < b–c shart bajarilsa “Ha”, aks holda “Yo‘q” deb javob chiqaruvchi algoritm tuzing.
6-masala. a va b sonlar berilgan. Agar ularning ko‘paytmasi musbat bo‘lsa, ularning har birini kvadratini, aks holda ularning har biriga 100 ni qo‘shib chiqaruvchi algoritm tuzing.
3. Takrorlanish tuzilmalari. Bu tuzilmalar bir nechta ko’rsatmalar guruhini ko’p marta bajarilishini ta’minlaydi. Bu tuzilmalar ham, asosan, 2 xil ko’rinishda bo’ladi.
a) toki:
So’zlar orqali
|
Blok-sxema ko’rinishida
|
toki shart
ko’rsatmalar guruhi
oxiri
|
|
7–masala. x ning qiymati berilgan a sonidan kichik bo’lganda y=ax2+20 funksiyaning qiymatlarini hisoblash algoritmini tuzing.
8–masala. Berilgan A va B musbat sonlarning qiymatlari teng bo’lguncha bu sonlarni kattasidan kichigini ayirib kattasi bilan almashtirib boruvchi algoritm tuzing.
b) parametr – dan – gacha:
So’zlar orqali
|
Blok-sxema ko’rinishida
|
parametr B dan O gacha
ko’rsatmalar guruhi
oxiri
|
|
|