Chiziqli algoritmlar
Faqat ketma-ket bajariladigan jarayonlardan tashkil topgan algoritmlarga chiziqli algoritmlar deb ataladi. Bunday algoritmni ifodalash uchun ketma-ketlik strukturasi ishlatiladi. Strukturada bajariladigan amal mos keluvchi shakl bilan ko‘rsatiladi. Chiziqli algoritmlar blok-sxemasining umumiy strukturasi quyidagi ko‘rinishda bo‘lishi mumkin:
Chiziqli algoritmlar blok-sxemasining strukturasi
-
Tarmoqlanuvchi algoritmlar
Agar algoritm jarayoni berilgan shartning natijasiga qarab turli tarmoqlar bo‘yicha davom ettirilsa va hisoblash jarayonida har bir tarmoq faqat bir marta bajarilsa, bunday hisoblash jarayonlariga tarmoqlanuvchi algoritmlar deb ataladi. Tarmoqlanuvchi algoritmlar uchun ayri strukturasi ishlatiladi. Tarmoqlanuvchi strukturasi berilgan shartning bajarilishiga qarab ko‘rsatilgan tarmoqdan faqat bittasining bajarilishini ta’minlaydi. Tarmoqlanuvchi algoritmning shart bajaradigan jarayon blok-sxemada romb figurasi bilan ifodalanadi. Quyidagi suratda shart bajarilishi blok-sxemasi keltirilgan.
Tarmoqlanish algortimining strukturasi
Berilgan shart romb geometrik figura orqali ifodalanadi, a > b - berilgan shart. Agar shart to‘g‘ri bo‘lsa, "ha" tarmoq bo‘yicha a-jarayon bajariladi, shart noto‘g‘ri bo‘lsa "yo‘q" tarmoq bo‘yicha b-jarayon bajariladi.
Tarmoqlanuvchi algoritmga misol sifatida quyidagi sodda misolni ko‘raylik.
1- Misol: Berilgan a ning qiytmatiga bog‘liq holda, agar a qiymati 100 dan katta bo‘lsa «ha» tarmoq bo‘yicha ‘100 dan katta son’ xabarini chop etsin, agar shart noto‘g‘ri bo‘lsa ‘100 dan kichik son’ xabarini chop etsin.
Ko‘pgina masalalarni yechishda, shart asosida tarmoqlanuvchi algoritmlarning ikkita tarmog‘idan bittasini, ya’ni “ha” yoki “yo‘q” tarmoqlarining bajarilishi yetarli bo‘ladi.
-
Takrorlanuvchi yoki Sikllik algoritmlar
Agar tarmoqlanuvchi algoritm holatiga qarab takrorlansa tarmoqlanuvchi algoritmning xususiy holi sifatida aylanish strukturasi deb ham atash mumkin. Aylanish strukturasi quyidagi ko‘rinishga ega:
Aylanish strukturasining ko‘rinishi
Agar masalani yechish uchun tuzilgan buyruqlar ketma-ketligi takrorlansa bunday algoritm takrorlanuvchi algoritm yoki sikllik algoritmlar ham deb ataladi. Takrorlanuvchi algoritmlarga misol sifatida 1 dan 100 gacha bo‘lgan sonlarni chop etish yoki ‘Dasturlash’ xabarini n-marta chop etishlarni keltirish mumkin. Quyidagi misolda ‘C++ ga xush kelibsiz!’ xabari 100 marta ekranga chop etiladi.
Bu masalani bajarish uchun i=0 da maks=100 qiymatda deb olamiz va i 100 ga teng bo‘lmaguncha xabarni ekranga chop etamiz. Buni matnli algoritm sifatida quyidagidek yozish mumkin:
-
Boshlash
-
i=0 berilsin,
-
maks=100 berilsin,
-
i=i+1 hisoblansin,
-
i tekshirilsin va bu shart to‘g‘ri bo‘lsa, “C++ ga xush kelibsiz” xabari chop etilsin va 4-qatorga qaytilsin, aks holda keying qatorga o‘tilsin.
-
Tugatish
‘C++ ga xush kelibsiz!’ xabarini 100 marta ekranga chop etuvchi algoritm
Yuqorida keltirilgan algoritm va blok-sxemadan ko‘rinib turibdiki buyqurlarlar ketma-ketligining ma’lum qismi parametr i ga nisbatan maks marta takrorlanayapti.
‘C++ ga xush kelibsiz!’ xabarini 100 marta chop etuvchi algoritm
-
Amaliy mashgulotlar
-
Choy damlash algoritmini tuzish
-
Matnli algoritm
-
Boshlash
-
Idishga suvni quying
-
Gazni yoqing
-
Suv idishini gazga qo‘ying
-
Suv qaynagandan so‘ng, choyni damlang
-
Tugatish
-
Blok-sxemasi
-
Farangeyt darajani selsius darajasiga o‘tkazish algoritmi
-
Matnli algoritm
-
Boshlash
-
Farangeyt darajasini kiriting
-
Farangeyt darajani selsius darajasiga o‘tkazing (hisoblang)
-
Selsius darajani ekranga chop eting
-
Tugatish
-
Blok-sxemasi
-
Mashina svetoforga kelganda harakatlanish algoritmi
-
Matnli algoritm
-
Boshlash
-
Mashinani yurgizing
-
Agar svetofor qizil chirogi yoniq bo`lsa to`xtang, aks holda mashinani yurgizing
-
Tugatish
-
Blok-sxemasi
-
2 ta sonni o‘rtacha qiymatini aniqlash algoritmini yozing.
-
Matnli algoritm
-
Boshlash
-
A sonini kiriting
-
B sonini kiriting
-
Hisoblang – ikkala sonlarni o‘rtachasini aniqlang
-
Natija ekranga chop eting
-
Tugatish
-
Blok-sxemasi
-
C++ ga xush kelibsiz xabarini 5 marta ekran chop etish algoritmi
-
Matnli algoritm
-
Boshlash
-
Sanoqni 0 ga teng qilib belgilang
-
Agar ssnoq 5 dan kichik bo‘lsa “C++ ga xush kelibsiz” xabarini chop eting, aks holda keying jarayonga o‘ting
-
Tugatish
Algoritmlarni ishlab chiqish va taqdim etish usullari
3-mavzu
-
Matnli algoritm
-
Sxematik(grafik) algoritmlar
-
Algoritmni tahlil qilish
-
Algoritmni dasturlashga bog‘lash
-
Algoritmning afzalliklari va dasturlashdagi ahamiyati
-
Amaliy mashg‘ulotlar
Algoritmlarni ishlab chiqish va tahlil qilish. Algoritmlarni taqdim etish usullari. Algoritmni dasturlashga bog‘lash usullari.
Algoritmlarning ishlab chiqishning amaliyotda ikkita asosiy usullari mavjud:
-
matnli algoritmlar
-
sxematik(grafik) algoritmlar
-
Matnli algoritm
Matnli algoritm bu muammoni qadam va qadam yechimi va har qadam oddiy inson tushunadigan matn bilan ifodalanadi. Matnli algoritmning asosiy yutug‘i bu uning soddaligi hisoblanadi. Ya’ni dasrtuchi yoki informatik bo‘lmagan inson ham matnli algoritmni o‘qib masala yechimini tushunishi mumkin. Matnli algortimlar odatda sodda masalalar uchun qo‘llaniladi. Matnli algoritmning har bir qadami raqamlab boriladi. Esda saqlash kerak bo‘lgan qoida bu algoritmning birinchi qadami doim ‘boshlash’ va oxirgi qadami ‘tugatish, yaakunlash’ bo‘lishi kerak. Agar algoritm qadamlarini oxiri ‘tugash’ bilan yakunlamasa bunday algoritm, algoritm deb tan olinmaydi. Mantli algoritmni dasturchi kodga o‘zgartishi juda oson hisoblanadi. Matnli algoritmga misol qilib kundalik hayotimizdagi vazifalarni keltirish ham mumkin. Masalan piyodalar o‘tish joyidan yo‘lni narigi tomoniga o‘tish algoritmi mana bunday ifodalanishi mumkin:
Matnli algoritm piyodalar o‘tish joyidan yo‘lini kesib o‘tish:
-
boshlash
-
chapga qarang
-
agar mashina yo‘q bo‘lsa, yo‘lni o‘rtasigacha yuring va to‘xtang
-
o‘ngga qarang
-
agar mashina yo‘q bo‘lsa, yuring
-
tugatish
-
Sxematik(grafik) algoritmlar
Aytib o‘tilganimizdek matnli algoritmlar murakkab masalalarni yechishda tushunmovchiliklar keltirib chiqaradi. Murakkab masalalarni yechish uchun grafik algoritmlar qo‘llaniladi. Bunday algoritmlar blok-sxemali algoritmlar deb ham ataladi. Blok-sxemali algoritmlar geometrik figuralar orqali ifodalanadi (2-mavzuda keltirilgan). Blok-sxemali algoritmlarda har bir geometrik figuraning o‘z vazifasi bor. Bu vazifalarni dasturchi bilishi shart hisoblanadi aks holda katta hajmdagi dastur tuzilishida uzulishlar va bu dastur muddatidan kechga qolib tayyorlanishiga olib keladi. Blok-sxemali algoritmlar masalani aniq yechimini taqdim etadi va bu dasturchiga ancha vaqt tejalishini ta’limlaydi. Matnli algoritmda aytib o‘tkanimizdek har bir algoritmning boshlash va tugash qadamlari shart bo‘lgan qadamlar hisoblanadi. Blok-sxemali algoritmda boshlash va tugatish buyruqlarini qovunsimon dumolaq figura ifodalaydi. Oddiy misol sifatida grafik algoritmga 2 ta butun sonni ko‘paytmasini topishni keltirishimiz mumkin.
1-qadam. Boshlash. Algoritmning boshlanishini ifodalaydi.
2-qadam. Kiritish ma’lumoti, bu yerda son kiritilyapti.
3-qadam. Kiritish ma’lumoti, bu yerda son kiritilyapti.
4-qadam.Hisoblash. a va b sonlarini ko‘paytmasini hisoblayapti.
5-qadam. Chop etish. Natijani ya’ni a va b sonlarni ko‘paytmasi natijasini ekranga chop etadi.
6-qadam. Tugash. Algoritmni yakuniga yetganini ifodalaydi.
Algoritm tahlili aniq hisoblash muammosini hal qilish uchun algoritmning zarur resurslarini nazariy baholashni ta’minlaydi. Ko‘pgina algoritmlar ixtiyoriy uzunlikdagi kirishlar bilan ishlash uchun mo‘ljallangan. Algoritmlarni tahlil qilish - uni bajarish uchun zarur bo‘lgan vaqt va xotiradigi joy resurslari miqdorini aniqlash jarayoni hisoblanadi.
Odatda, algoritmning samaradorligi ishlash vaqti, kirish ma’lumotlari ko‘pligi bilan baholanadi.
Algoritmlar ko‘pincha bir-biridan juda farq qiladi, ammo bir nechta algoritm bir xil natija taqdim etish uchun yaratilgan bo‘lishi ham mumkin. Masalan, raqamlar to‘plamini turli xil algoritmlar yordamida tartiblash mumkin. 2 ta algoritm bir xil natija berganda, dasturchi sifatida bulardan qaysi biri samaraliroq ekanligini aniqlab o‘sha algoritmdan foydalanish maqsadga muvofiq hisoblanadi. Algortimning samaradorligi uning qancha vaqt sarflashi va qancha xotiradan joy talab etishi bilan baholanadi. Agar algoritm tez va xotirada oz joy talab etsa shu algortim samarador deb hisoblanadi.
Algoritm tahlil turlari quyidagilardan iborat:
-
Eng yomon holat - har qanday misolda bajarilgan qadamlarning soni maksimal darajada bo‘lishi
-
Eng yaxshi holat - har qanday misolda bajarilgan qadamlarning soni minimal darajada bo‘lishi
-
O‘rtacha holat - Har qanday misolda bajarilgan qadamlarning soni o‘rtacha darajada bo‘lishi
-
Algoritmni dasturlashga bog‘lash
Har bir yaratilgan algoritm dasturlashda ifodalanishi mumkin. Eng muhimi algoritm dasturlash tili tanlamaydi. Ya’ni algoritm yaratilganidan keyin uni xoxlasangiz C++ dasturlash tilida, xoxlasangiz Piton (Python) dasturlash tilida dastur sifatida ifodalashingiz mumkin bo‘ladi. Algortim qadamlarini ifodalash uchun har bir dasturlash tilida maxsus jarayonlar mavjud. Masalan yuqoridagi misolda a va b sonlarini kiritish degan qadam bor. Ma’lumot kiritishni C++ dasturlash tilida cin>> orqali amalga oshirish mumkin. Yoki 5-qadamda natijani ekranga chop etish jarayoni mavjud, buni C++dasturlash tilida cout<< funksiyasi orqali amalga oshirish mumkin. Demak, yaratilayotgan algoritmlarni dasturiy ifodasini sizga ma’qul bo‘lgan dasturlash tilida amalga oshirish mumkin. Ushbu kitobda biz dasturlash tili sifatida C++ tilini o‘rganamiz. Dasturlashda nima uchun algoritmlardan foydalanishimiz kerakligi haqida gapirganda, kompyuter dasturlari protsessor va xotiraga ega kompyuter uskunasida ishlaydigan turli xil algoritmlarni qabul qiladi va bu komponentlar cheklovlarga ega hisoblanadi. Protsessor cheklangan resurslar iborat. Ulardan oqilona foydalanish kerak va vaqt nuqtai nazaridan samarali bo‘lgan yaxshi algoritm buni amalga oshirishga yordam beradi. Dasturlashda masalani yechishning turli usullari mavjud. Biroq, mavjud usullar samaradorligi bilan farq qiladi. Ba’zi usullar boshqalarga qaraganda aniqroq javob berish uchun juda mos keladi. Algoritmlar muammoni hal qilishning eng yaxshi usulini topish uchun ishlatiladi. Algortimlar dastur samaradorligini ham oshiradi.
Dastur samaradorligi turlicha talqin qilinishi mumkin. Ulardan biri dasturiy ta’minotning aniqligi hisoblanadi. Eng yaxshi algoritm bilan kompyuter dasturi juda aniq natijalarni berishi mumkin bo‘ladi.
Dasturiy ta’minot samaradorligini ko‘rishning yana bir usuli - bu dasturning tezligi hisoblanadi. Dasturning masalani bajarish tezligini oshirish uchun algoritmdan foydalanish mumkin. Yaxshi algoritm muammoni hal qilish uchun dastur vaqtini qisqartirish imkoniyatiga ega hisoblanadi.
-
Algoritmning afzalliklari va dasturlashdagi ahamiyati
Algoritmlar dasturchiga berilgan muammoni hal qilish mumkinmi yoki yo‘qligini aniqlashga yordam beradi. Agar muammoni hal qilish mumkin bo‘lsa, qanday qilib, qanchalik tez va qanchalik aniq hal qilish mumkinligi haqida to‘liq ma’lumot beradi. Agar muammoni hal qilish mumkin bo‘lmasa, algoritm muammoni bir qismini hal qila oladimi yoki yo‘q degan savolga javob topishga yordam beradi.
-
Foydalanuvchi manzilini kiritsin va kiritilgan ma’lumotni ekranga chop etsin.
-
Matnli algoritm
1-qadam. Boshlash
2-qadam. Foydalanuvchidan manzilini kiritishni so‘rang
3-qadam. Foydalanuvchi kiritgan ma’lumotni ekranga chop eting
4-qadam. Tugatish
-
Foydalanuvchi ism va familyasini kiritsin va foydalanuvchi kiritgan ma’lumotlarni ekranga chop eting.
-
Matnli algoritm
1-qadam. Boshlash
2-qadam. Foydalanuvchidan ismini kiritishni so‘rang
3-qadam. Foydalanuvchidan familyasini kiritishni so‘rang
4-qadam. Foydalanuvchi kiritgan ma’lumotlarni ekranga chop eting
5-qadam. Tugatish
-
Foydalnuvchi 3 ta butun sonlarni kiritsin va kiritilgan sonlarni yig‘indisini hisoblab ekranga chop etsin.
-
Matnli algoritm
1-qadam. Boshlash
2-qadam. Foydalanuvchidan birinchi butun sonni kiritishni so‘rang
3-qadam. Foydalanuvchidan ikkinchi butun sonni kiritishni so‘rang
4-qadam. Foydalanuvchidan uchinschi butun sonni kiritishni so‘rang
5-qadam. Foydalanuvchi kiritgan sonlarni yig‘indisini hisoblang
6-qadam. Yig‘indini ekranga chop eting
7-qadam. Tugatish
-
Foydalanuvchi tug‘ilgan yilini kiritsin va hozirgi yildan tug‘ilgan yilni ayirib foydalanuvchini yoshini toping, foydalanuvchi yoshini ekranga chop eting.
-
Matnli algoritm
1-qadam. Boshlash
2-qadam. Foydalanuvchidan yoshini kiritishni so‘rang
3-qadam. Hozirgi yildan foydalanuvchi kiritgan yilni ayirib hisoblang
4-qadam. Foydalanuvchi yoshini ekranga chop eting
5-qadam. Tugatish
-
Soatbay ishlaydigan insonni kunlik ish haqini hisoblab ekranga chop eting.
-
Matnli algoritm
1-qadam. Boshlash
2-qadam. Foydalanuvchidan necha soat ishlaganini so‘rang
3-qadam. Foydalanuvchidan soatiga qancha maosh olishini so‘rang
4-qadam. Foydalanuvchi necha soat ishlaganini, foydalanuvchi soatiga oladigan maoshga ko‘paytirib ish haqini hisoblang
5-qadam. Foydalanuvchi ish haqisini ekranga chop eting
6-qadam. Tugatish
Ushbu mavzuda bajargan barcha grafik algoritmlarimiz chiziqli algoritm hisoblanadi. Keyingi mavzuda tarmoqlanuvchi algoritmlarni o‘rganamiz.
Tarmoqlanuvchi va takrorlanuvchi algoritmlar
4-mavzu
-
Tarmoqlanuvchi algoritm
-
Takrorlanuvchi (sikl) algoritm
-
Amaliy mashg‘ulotlar
Elementar asosiy boshqaruv tuzilmalari: ketma-ketlik, tarmoqlanish, turli halqalar (old shartli, keyingi shartli, parametrik). Tuzilgan dasturlashning asosiy dasturlash tuzilmalari: chiziqli, tarmoqli, siklik.
Yuqoridagi mavzularda grafik algoritmning faqat chiziqli turini ko‘rib chiqdik. Bu mavzuda grafik algoritmning tarmoqlanuvchi va takrorlanuvchi turlarini o‘rganamiz.
Tarmoqlanuvchi algoritm - algoritm qaror qabul qilish funksiya mavjud bo‘lsa shu algoritm tarmoqlanuvchi algoritm deb ataladi. Masalan, kundalik hayotimizda uchraydigan qarorlarni misol keltrishimiz mumkin: agar qornim ochsa ovqatlanaman, agar yomg‘ir yog‘sa sayobon ishlataman, agar kasal bo‘lsam doktorga boraman. Qaror qabul qilish jarayoni tarmoqlanuvchi algoritmning asosiy xususiyati hisoblanadi. Blok-sxema yaratishda qaror qabul qilish romb geometrik figurasi orqali ifodalanadi.
Qaror qabul qilish jaroyoni dasturchilar tili bilan ta’riflasak, agar nimadur bo‘lsa bunday ishni amalga oshiraman, aks holda bunday ishni amalga oshiraman jarayoni hisoblanadi.
Tarmoqlanuvchi algoritmning qaror qabul qilish jarayonidan faqat ikkita natija chiqishi mumkin: (True/False) To‘g‘ri yoki Noto‘g‘ri.
Ushbu natijalarga bog‘liq holda algoritm keyingi jarayonni hal qiladi. Masalan, agar telefonim zaryadi 10% dan oz qolgan bo‘lsa zaryadkaga ulayman, aks holda zaryadkaga ulashim shart emas. Blok-sxema ko‘rinishi quyidagidek ifodalanadi.
Demak tarmoqlanuvchi algoritm qaror qabul qilish orqali keyingi jarayonni belgilaydi. Yuqoridagi misolda agar telefon zaryadi 10% foizdan oz qolgan bo‘lsa 1-holatdagi jarayon amalga oshiriladi, aks holda (agar telefon zaryadi 10%dan yuqori bo‘lsa) 2-holatdagi jarayon amalga oshiriladi.
|