Nazorat savollari: Algoritm nima?

Nazorat savollari:

1. 
   Algoritm nima?
   

Algoritm bu ma’lum bir vazifani bajarishga qaratilgan kichik dastur. Algoritm tushunchasini kengroq qilib tushintirganda, berilgan masalani yechish uchun ketma-ketliklar majmuasidir.

Algoritmni hayotimizda juda ko’p sohalarda ishlatiladi: chorraxada svetafor, binolarda lift. Hattoki o’zimiz oddiy hayotiy ishlarda ham algoritm ishlatamiz: choynakga choy damlash. Algoritmlarning komputer sohasida ham muhim ro’l o’ynaydi. Chunki, dasturchi yozgan dasturlar hammasi ma’lum bir ketma-ketlik bilan ishlaydi.

2. 
   Eng dastlabki algoritmlarga misol keltiring.
   

Bizga maʼlum boʻlgan eng qadimiy algoritm bu Yevklid algoritmidir
Yevklid algoritmi ikkita qoidaga asoslanadi:

Ikkita sondan kattasidan kichigi ayrilganda ularning EKUBi o’zgarmaydi

Yuqoridagi misoldagi 76 va 16 ning shu tarzda EKUBini topib ko'raylik. Bunda 76 dan 16 ayirma 16 dan kichik bo'lib qolguncha ayrib boriladi. Ayirma 16 dan kichik bo'lib qolgan payt ularning o'rni almashtiriladi

76 - 16 = 60

60 - 16 = 44

44 - 16 = 28

28-16 = 12

16 - 12 = 4

Shu tarzda yakunda biz EKUBga ega bo'lamiz.

Muammo: Agar sonlar 1 000 000 va 2 bo’lsachi? Unda algoritm 500 000 dan ortiq amal bajarishiga to'g'ri keladi. Ikki son orasidagi farq oshgani sari algoritm bajaradigan ish ham keskin ortib ketadi.

2. Qadamlar sonini kamaytirish uchun ayrish o’rniga qoldiqli bo’lishdan foydalanish mumkin. Bunda 1 000 000 va 2 sonlarining EKUBi atiga bir-ikkita amal bilan topiladi.

Yevklid algoritmi qadamlari:

Ikkita sondan kattasini kichigiga bo’lib qoldiq olamiz.
Ularni o’rnini almashtiramiz
1- va 2-qadamlarni sonlardan biri nol bo’lib qolguncha davom ettiramiz
Qolgan son shu ikki son uchun EKUB bo’ladi.

3. 
   Input va Output nima?Algoritmning Input va Outputga bog’liqligi?
   

Masalaning tavsifi kerakli input/output bog’lanishini umumiy terminlarda tavsiflaydi
Algoritm esa bu input/output bog’lanishiga erishish uchun aniq hisoblash protseduralarini tavsiflaydi
Masalan: Bir o’lchamli sonli massiv elementlarini saralash masalasi.
Input: A[1], A[2], … A[n] massiv elementlari
Output: input ketma-ketlikning A‘[1]≤A‘[2]≤ … ≤A‘[n] shartni qanoatlantiruvchi A‘[1], A‘[2], … A‘[n] o’rin almashishi.
Input
(31, 41, 59, 26, 41, 58)
Output
(26, 31, 41, 41, 58, 59)
Bu misol deb ataladi.
Ma’lum har bir input misol uchun to‘g'ri output bilan o’z ishini tugatishi lozim.
Xato algoritm umuman tugamasligi yoki xato output bilan tugashi mumkin.

4.