|
2- ma`ruza. Saralash algoritmlari. Kvadratik, logarifmik va chiziqli qiyinchilikdagi saralash algoritmlari
|
| bet | 6/9 | | Sana | 16.02.2024 | | Hajmi | 5,7 Mb. | | #157511 |
Bog'liq 2- ma`ruza(2023)ALGORITM TURLARI VA ULARNING TAVSIFI
CHIZIQLI ALGORITMLAR
XX asrning 70-yillarida golland olimi Edsger Deykstra
(1930 – 2002) har qanday algoritm uning nima maqsadda tuzilganligi va murakkabligidan qat’iy nazar, uchta:
ketma-ketlik, tarmoqlanish va takrorlanish algoritmik konstruksiyalaridan foydalanilgan holda yozilishi mumkinligi haqidagi g‘oyani ilgari surdi va tо‘liq asoslab berdi.
Chiziqli algoritm
deb, barcha ko‘rsatmalari hech qanday shartsiz, faqat ketma-ket bajariladigan jarayonlarga aytiladi.
Har qanday algoritm mantiqiy tuzilishi,
ya’ni bajarilish tartibiga ko‘ra uchta asosiy
turga bo‘linadi: chiziqli, tarmoqlanuvchi
va takrorlanuvchi.
Edsger Deykstra
(1930 – 2002)
Choy damlash ketma-ketligi: Choy damlash ketma-ketligi:
choynak qopqog‘i ochilsin;
1
choynak qaynoq suv bilan chayilsin;
2
choynakka bir choy qoshiq miqdorida quruq choy solinsin;
3
choynak to‘lguncha qaynagan suv quyilsin;
4
choynakning qopqog‘i yopilsin;
5
choynak sochiq bilan yopilib, besh daqiqaga qoldirilsin.
6
Chiziqli algoritm blok-sxema ko‘rinishida
1-misol. Sayyoh qishloqdan chiqib, shahar tomon jo‘nadi. U a kilometr yayov yurganidan
keyin avtobusga o‘tirdi va avtobusda t soatda shaharga yetib keldi. Agar avtobus 60 km/soat tezlik bilan harakat qilgan bo‘lsa, a = 5 va t = 0,5 bo‘lganda, qishloq bilan shahar orasidagi S masofani hisoblash algoritmini tuzing.
Yechish: Masofani hisoblash formulasini esga olamiz:
S = v · t. Sayyoh avtobusda
t soatda S1 = 60t kilometr yo‘l yurgan. Shuning uchun qishloq bilan shahar orasidagi masofa
S = a + 60t formulasi
bilan ifodalanadi. a = 5 va
t = 0,5 bo‘lganda,
S = 5 + 60 · 0,5 = 35 km bo‘ladi.
Endi S masofani hisoblash algoritmini so‘zlar va
blok-sxema orqali ifodalaymiz:
boshlansin;
|
| |
