1.1-ilova
Mavzuni jonlantirish uchun savollar
1. Intuitiv algoritm tushunsnasining moiyati nimada?
2. Algoritmning intuitiv ta’riflaridan birini keltiring?
3. Formal algoritm deganda nimani tushunamiz?
4. Algoritm ob’ekti deganda nimani tushunamiz?
5. Algoritm ob’ektining tasviri deganda nimani tushunamiz?
1.4-ilova
3.B/B/B jadvali 1.5-ilova
Bilaman
|
Bilmoqchiman
|
Bilib oldim
|
|
|
|
Ma’ruza matni
Hisoblash jarayonida ba’zi bir algoritmlarning o’ziga qayta murojaat qilishga to’g’ri keladi. O’ziga–o’zi murojaat qiladigan algoritmlarga rekkurent algoritmlar yoki rekursiya deb ataladi.
Bunday algoritmga misol sifatida Fibonachchi sonlarini keltirish mumkin. Ma’lumki, Fibonachchi sonlari quyidagicha aniqlangan.
1-misol. a0qa1q1, aiqai-1Qai-2 iq 2,3,4,
Bu rekkurent ifoda algoritmiga mos keluvchi blok-sxema quyida keltirilgan.
Eslatib, o’tamiz formuladagi i-indeksga hojat yo’q, agar Fibonachchi sonining nomerini ham aniqlash zarur bo’lsa, birorta parametr-kalit kiritish kerak bo’ladi.
2-misol.
Bu ifoda i ning har bir qiymatida faktorialni va yig’indini hisoblashni taqozo etadi. Shuning uchun avval faktorialni hisoblashni alohida ko’rib chiqamiz. Quyidagi rekkurent ifoda faktorialni kam amal sarflab qulay usulda hisoblash imkonini beradi.
R=1
R=R*2i*(2i+1)
Haqiqatan ham, iq1 da 3! ni, iq2 da Rq3!*4*5q5! ni va hakozo tarzda (2i1)! ni yuqoridagi rekkurent formula yordamida hisoblash mumkin bo’ladi. Bu misolga mos keluvchi blok-sxema quyida keltirilgan.
Amalda shunday bir masalalar uchraydiki, ularda takrorlanishlar soni oldindan berilmagan-noma’lum bo’ladi. Ammo, bu jarayonni tugatish uchun biror bir shart berilgan bo’ladi.
Masalan, quyidagi qatorda nechta had bilan chegaralanish berilmagan. Lekin qatorni aniqlikda hisoblash zarur bo’ladi. Buning uchun shartni olish mumkin.
Yuqori tartibli algebraik va transtsendent tenglamalarni echish ususllari yoki algoritmlari ketma-ket yaqinlashuvchi – interatsion algoritmlarga misollar bo’la oladi. Ma’lumki, transtsendent tenglamalarni echishning quyidagi asosiy usullari mavjud:
- Urinmalar usuli (Nyuton usuli),
- Ketma-ket yaqinlashishi usuli,
- Vatarlar usuli,
- Teng ikkiga bo’lish usuli.
Bizga f(x)0 (1) transtsendent tenglama berilgan bo’lsin. Faraz qilaylik, bu tenglama [a,b] oraliqda uzluksiz va f(a) f(b)<0 shartni qanoatlantirsin. Ma’lumki, bu holda berilgan tenglama [a,b] oraliqda kamida bitta ildizga ega bo’ladi va u quyidagi formula orqali topiladi.
Boshlang’ich X0 qiymat shart asosida tanlab olinsa, (2) iteratsion albatta yaqinlashadi. Ketma-ketlik
shart bajarilgunga davom ettiriladi.
1-Misol. Berilgan musbat a xaqiqiy sondan kvadrat ildiz chiqarish algoritmi tuzilsin.
Bu masalani echish uchun kvadrat ildizni x deb belgilab olib, ifodalash yozib olamiz. U holda (1) tenglamaga asosan
ekanligini topish mumkin (4) ifodani (2) ga qo’yib, quyidagi rekurrent formulani topish mumkin.
Bu formulaga mos blok-sxema quyida keltirilgan. - kvadrat ildizni topishning berilgan aniqligi. Eslatib o’tamiz, algoritmda indeksli o’zgaruvchilarga zarurat yo’q.
Kompyuter uchun tuzilgan algoritm ijrochisi-bu kompyuterdir. Biror programmalash tilida yozilgan algoritm kodlashtirilgan oddiy ko’rsatmalar ketma-ketliliga o’tadi va mashina tomonidan avtomatik ravishda bajariladi. Metodik nuqtai–nazardan qaraganda algoritmning birinchi ijrochisi sifatida o’quvchining o’zini olish muhim ahamiyatga ega. O’quvchi tomonidan biror masalani echish algoritmi tuzilganda bu algoritmni to’g’ri natija berishini tekshirish juda muhimdir. Buning yagona usuli o’quvchi tomonidan algoritmni turli boshlang’ich berilganlarda qadamma - qadam bajarib (ijro etib) ko’rishdir. Algoritmni bajarish natijasida xatolar aniqlanadi va to’g’rilanadi. Ikkinchi tomonidan, masalani echishga qiynalayotgan o’quvchi uchun tayyor algoritmni bajarish – masalani echish yo’llarini tushunishga xizmat qiladi.
Algoritm ijrosini quyidagi misolda ko’raylik.
Berilgan sonlarning eng kattasini topish algoritmini tuzaylik. Buning uchun, berilgan sonlardan birinchisi ni eng katta qiymat deb faraz qilaylik va uni max nomli yangi o’zgaruvchiga uzataylik: maxa1. Parametr i ning qiymatini bittaga oshirib, ya’ni ii1 a1 ni a2 bilan taqqoslaymiz va qaysi biri katta bo’lsa uni max o’zgaruvchisiga uzatamiz va jarayon shu tarzda to in bo’lguncha davom ettiramiz. Bu fiklar quydagi blok-sxemada o’z aksini topgan.
Endi bu blok-sxema yoki algoritmning ijrosini
Aniq sonlarda qadamma–qadam ko’rib o’taylik:
i1 da max3 bo’ladi.
ii12 ni topamiz,
a2>max, ya’ni 5>3 ni tekshiramiz, shart bajarilsa, max5 bo’ladi.
i
a3 max, ya’ni 1>5, ni tekshiramiz. Shart bajarilmadi, demak, keyingi
i
|
