Algoritmlar, 0-dars

Rasm manbasi: linkedin.com/pulse

Assalomu alaykum dasturlashga qiziquvchilar. Bugungi darsimiz shunchaki algoritm tushunchasi, uning dasturlashda qanchalik muhimligi haqida bo’ladi va nima ekanligini his qilib ko’rishingiz uchun 1–2 ta oddiy misollar keltiraman. Boshlashdan avval umumiy qoidalarni aytib o’tmoqchiman:

  1. Bu dars davomida Java dasturlash tilidan foydalanaman. Lekin bu unchalik muhimmas, istaganlar boshqa tildan foydalanishi mumkin.
  2. Algoritmni chuqur o’rganishning yo’li uni qog’ozda yozib, miyada xuddi kompyuterdek fikrlab amalga oshirish. Daftar va ruchkada mashq qilishdan to’xtamang.
  3. Darslarni yaxshi tushunishingiz uchun elementar matematikani yaxshi bilishingiz talab etiladi.
  4. Maqolalarimni yozishda o’qishimizning “Algorithms and complexity (COMP90038)” darsida o’tilgan ma’lumotlardan va quyidagi kitoblardan foydalanaman:

Nega algoritmlarni o’rganishim kerak?

Yaxshi savol. Javobini qisqa beraman: algoritmlar dasturlashning o’zagi. Uni yaxshi o’rgansangiz har qanday qiyinchilikdagi dasturni yarata olasiz. Google, Amazon, Microsoft yoki Apple’ga ishga kirmoqchi bo’lsangiz, albatta, algoritmlar bo’yicha suhbatdan o’tasiz va bu eng muhim sinov deb bemalol ayta olaman.

Bilamizki, dasturchining ishi kompyuterga biror vazifani bajarishni buyurishdan iborat. Masalan, kichkina ukangizga yoki singlingizga: “Kelgunimcha barcha darslaringi qilib qo’y” deysiz. U sizni tushunadi va bajaradi. Kompyuter bilan ham shunga o’xshash. Farqi kompyuterning ukangizdek “tushunishi” yoki “farosati” yuqori emas. Uning o’z tili bor (alifbosi faqat 0 va 1 dan iborat: nega?). U bizni tushunishi uchun dasturlash tillari mavjud lekin shunda ham u biz gaplashadigan tildan ancha cheklangan va qat’iy qoidalarga asoslanadi. Unga eng yosh bolaga tushuntirganday tushuntirish kerak. Masalan, 3 yashar bolayam 1 dan 5 gacha sana desangiz, sanab beroladi. Lekin kompyuterda bu quyidagicha bosqichda buyurilishi kerak:

  1. x nomli butun sonli o’zgaruvchi yarat va unga 0 ni o’zlashtir (x=0).
  2. x 5 dan kichik bo’lganda:
  3. unga 1 ni qo’shib ekranda yangi qatorda ko’rsat.

Yuqorida 5 gacha sanaydigan algoritm yaratdik. Lekin bu hammasimas — yozganimizni kompyuter tushunmaydi, bu shunchaki sizu-bizga tushunarli bo’lgan psevdokod, xolos. Kutganingizdek, endi uni dasturlash tilida yozamiz:

int x=0;
while (x < 5)
{
x = x + 1;
System.out.println(x);
}

Buni umumlashtirib, 1 dan n gacha sanash algoritmini yaratish ham mumkin (n ni foydalanuvchi kiritadi).

Demak algoritm (odatda, kompyuterda) biror ishni amalga oshirish uchun yaratilgan qoidalar ketma-ketligi ekan. Qolaversa, algoritm 3 ta asosiy talabga javob berishi kerak:

  1. Noaniqlik bo’lmasligi. Har bir qadam kompyuter tushunadigan aniq qilib ko’rsatilishi shart.
  2. Foydalanuvchi tomonidan kiritiladigan barcha ma’lumotlar uchun to’g’ri ishlashi kerak.
  3. Algoritm doim ma’lum vaqtdan keyin ishni tugallashi kerak, cheksiz davom etmasligi kerak (yuqoridagi misolimizda takrorlanish shartini 5*5 25 bo’lsa deb kiritsangiz cheksiz sanayveradi).

Endi sal qiyinroq masalaga o’taman:

Berilgan 2 ta natural sonning eng katta umumiy bo’luvchisini (EKUB) topish algoritmini yarating.

Bu masalaning bir necha xil usulda yaratish mumkin. Men Yevklid algoritmi bilan masalani yechmoqchiman. Matematik ko’rinishi:

EKUB(m, n)=EKUB(n, m mod n)=..=EKUB(k, 0)=k

(bu yerda m mod n — “m ni n ga bo’lgandagi qoldiq”)

Ya’ni 1-sonni 2-songa bo’lgandagi qoldiq 0 chiqmaguncha jarayon davom etaveradi.

EKUB(m, n) ni topish algoritmi quyidagicha bo’ladi:

  1. Agar n=0 bo’lsa, m ning qiymatini chiqar va jarayonni tugat, aks holda 2-bosqichga o’t
  2. m ni n ga bo’lib, qoldiqni r o’zgaruvchiga o’zlashtir.
  3. n ning qiymatini m ga, r nikini n ga o’zlashtir. 1-qadamga qayt.

Algoritmning Java’dagi ko’rinishi:

// m va n o'zgaruvchilarini e'lon qilib, foydalanuvchidan ularning qiymatini qabul qilish
Scanner in = new Scanner(System.in);
int m = in.nextInt(),
n = in.nextInt();
// qoldiq uchun r o'zgaruvchi e'lon qilindi
int r;

// n o ga teng bo'lmaguncha davom ettir
while(n != 0)
{
// % operatori m ni n ga bo'lgandagi qoldiqni hisoblaydi
r = m % n;
m = n;
n = r;
}
// natijani ekranga chiqar
System.out.println("EKUB = " + m);

Java’ni umuman bilmaganlar uchun bugungi darsimiz qiyinchilik tug’dirmasligi uchun kommentda (// dan keyin) har bir qatorning vazifasini keltirdim. Savollaringiz bo’lsa, pastda fikr bildirishda berishingiz mumkin. Bu 1-darsim bo’lganligi uchun pedagogik jihatdan xatolarim bo’lishi mumkin. Fikringizniyam jon deb qabul qilaman.

Vazifa: 2 ta natural sonning EKUBini topishning boshqa algoritmini yarating.