Algoritm tahlilining asoslari. Algoritmlar va uning xususiyatlari. Rekursiv algoritmlar, Rekurrent munosabatlari. Iterativ algoritmlar. Asosiy algoritmlar. Qidiruv va saralash algoritmlari

Download 2,45 Mb.
bet	3/6
Sana	29.05.2024
Hajmi	2,45 Mb.
	#256522

1 2 3 4 5 6

Bog'liq
Algoritm tahlili asoslariga kirish

Masalaning qo‘yilishiga qarab siklik jarayonlar takrorlanish soni ma’lum bo’lgan va takrorlanish soni noma’lum bo‘lgan sikllarga bo‘linadi.

5. Algoritmning algoritmik tilda tasvirlanishi, ya‘ni algoritm bir xil va aniq ifodalash, bajarish uchun qoʻllanadigan belgilash va qoidalar majmui algoritmik til orqali ifodalashdir. Ulardan oʻquv oʻrganish tili sifatida foydalanilmoqda. Bulardan E-praktikum yoki E-tili algoritm ijrochisi algoritmik tili ham mavjud.

6. Algoritmlarning grafik shaklda tasvirlanishi. Masalan, grafiklar, sxemalar ya‘ni blok - sxema bunga misol boʻla oladi. Blok sxemaning asosiy elementlari quyidagilar: oval (ellips shakli)-algoritm boshlanishi va tugallanishi, toʻgʻri burchakli toʻrtburchak-qiymat berish yoki tegishli koʻrsatmalarni bajarish. Romb - shart tekshirishni belgilaydi. Uning yoʻnaltiruvchilari tarmoqlar boʻyicha biri ha ikkinchisi yoʻq yoʻnalishlarni beradi, parallelogramm- ma‘lumotlarni kiritish yoki chiqarish, yordamchi algoritmga murojaat - parallelogramm ikki tomoni chiziq, yoʻnaltiruvchi chiziq - blok-sxemadagi harakat boshqaruvi, nuqta-toʻgʻri chiziq (ikkita parallel) - qiymat berish.

Algoritmda bajarilishi tugallangan amallar ketma-ketligi algoritm qadami deb yuritiladi. Har bir alohida qadamni ijro etish uchun bajarilishi kerak boʻlgan amallar haqidagi koʻrsatma buyruq deb aytiladi.
Algoritmlarni koʻrgazmaliroq qilib tasvirlash uchun bloksxema, ya‘ni geometrik usul koʻproq qoʻllaniladi. Algoritmning bloksxemasi algoritmning asosiy tuzilishining yaqqol geometrik tasviri: algoritm bloklari, ya‘ni geometrik shakllar koʻrinishida, bloklar orasidagi aloqa esa yoʻnaltirilgan chiziqlar bilan koʻrsatiladi. Chiziqlarning yoʻnalishi bir blokdan soʻng qaysi blok bajarilishini bildiradi. Algoritmlarni ushbu usulda ifodalashda vazifasi, tutgan oʻrniga qarab quyidagi geometrik shakl(blok) lardan foydalaniladi.
Algoritmlar berilishi va ifodalanishiga qarab:

chiziqli;
tarmoqlanuvchi;
takrorlanuvchi turlarga boʻlinadi.

Hech qanday shart tekshirilmaydigan va tartib bilan faqat ketma-ket bajariladigan jarayonlarni ifodalaydigan chiziqli algoritmlar deb ataladi.
Chiziqli algoritmlar algoritmlarning eng sodda va oddiy ko‘rinishi hisoblanadi. Unida bajariladigan amallar ham buyruqlar ham buyruqlar ham qanday tartibda berilgan bo‘lsa shunday tartibda ketma- ket bajariladi. Chiziqli tuzilishga ega bo'lgan algoritmlarda ko'rsatmalar yozilish tartibida bajariladi. Ularning blok-sxemalari ishga tushirish, to'xtatish, kiritish-chiqarish jarayoni bloki hamda avvaldan ma'lum jarayon bloklari yordamida tuzilib, bir chiziq bo'ylab ketma-ket joylashgan bo'ladi.
Chiziqli tuzilishdagi algoritmni tuzish masalani yechish uchun kerak bo'ladigan boshlang'ich ma'lumotlarni tashkil qiluvchi o'zgaruvchilar nomi, ularning turi va o'zgarish ko'lamini aniqlashdan boshlanadi. Keyin oraliq va yakuniy natijalar o'zgaruvchilarining nomlari, turlari va mumkin bo'lsa o'zgarish ko'lamini aniqlash kerak. Endi algoritm mana shu boshlang'ich ma'lumotlarni qanday qayta ishlab oraliq va yakuniy natijalarni olish kerakligini aniqlashdan iborat bo'ladi.
1- misol.
funksiyani x ning ixtiyoriy qiymatlarida xisoblash algoritmini tuzing.
2-misol. Geron formulasidan foydalanib uchburchak yuzini hisoblash algoritmini tuzing.
Shunday hisoblash jarayonlari mavjud bo‘ladiki, bunda qo‘yilgan ayrim mantiqiy shartlarning bajarilishiga qarab, bu jarayonlar bir nechta tarmoqqa bo‘linadi. Hisoblash jarayonlarining shundayiga tarmoqlangan deb ataladiki, unda u birlamchi yoki oraliq ma‘lumotlar xususiyatidan kelib chiqqan holda bir yoki bir necha yo‘nalish bo‘yicha bajarilishi mumkin bo‘ladi. Bunda har bir yo‘nalish hisoblash jarayonining tarmog‘i hisoblanadi. U yoki bu tarmoqning tanlanishi mantiqiy shartlarning bajarilishini tekshirish asosida ta‘minlanadi. Aniq bir holda jarayon faqat tarmoqlarning bittasi bo‘yicha bajariladi. Boshqa tarmoqlanishlarning bajarilishi mumkin emas. 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 va shu tarmoqlardan hech bo‘lmaganda bittasi bajariladi.
Shunday hisoblash jarayonlari mavjud bo‘ladiki, bunda uning ayrim bo‘laklarini bir necha marta takroran hisoblashga to‘g‘ri keladi. Bunday jarayonlar takrorlanuvchi yoki siklik jarayonlar deyiladi va ular uchun algoritmlar tuzishda takrorlanuvchi algoritmlardan foydalaniladi. Siklik jarayonlar sikl parametri va sikl tanasidan iborat bo‘ladi.
Hisoblash jarayonining ko‘p marta takrorlanadigan qismi ichki sikl tanasi deb yuritiladi. Sikl tanasi bir necha marta takroran bajariluvchi amallar ketmaketligidan iborat bo‘ladi. Siklli jarayonlarni algoritmlashda bitta yoki bir nechta parametrlar qatnashadi. Ularning qiymatlarini bir vaqtda o‘zgarishida sikl tanasi ichidagi amallar ketma-ketligi ko‘p marotaba takrorlanadi. Masalaning qo‘yilishiga qarab siklik jarayonlar takrorlanish soni ma’lum bo’lgan va takrorlanish soni noma’lum bo‘lgan sikllarga bo‘linadi.
Takrorlanuvchi algoritmlar 2 xil ko‘rinishda ifodalanishi mumkin.
Repeat…until… takrorlanuvchi algoritm quyidagi ko‘rinishga ega:
Bu ko‘rinishdagi algoritmda avval sikl tanasi bajarilib, so‘ngra parametrning qiymati, ya‘ni sikldan chiqish sharti tekshiriladi Bu yerda sikl tanasi qo‘yilgan shart bajarilib turguncha takrorlanaveradi.
While… Do.. takrorlanuvchi algoritm quyidagi ko‘rinishga ega:
Bu ko‘rinishdagi algoritmlarda avval shart tekshiriladi, so‘ngra agar shart qanoatlantirsa, sikl tanasi bajariladi, aks holda hisoblash to‘xtatiladi. Aniq berilgan son asosida sikllarni tashkil qilishda sikl parametrining boshlang‘ich va oxirigi qiymatlari, uning har bir takrorlanishidagi sikl parametrining o‘zgarish qonunlari, siklrning takrorlanish sonlari ko‘rsatilishi kerak bo‘ladi. Sikl tanasidagi birlamchi ma‘lumotlar doimiy kattalik, oddiy o‘zgaruvchan, indeksli o‘zgaruvchan ko‘rinishlarida bo‘lishi mumkin.

Download 2,45 Mb.

1 2 3 4 5 6

Download 2,45 Mb.