1-dars: Algoritm nima

1-darajaBronza — algoritmik fikrlash1–8 darslar

HayotdaOshxona

Onangiz palov damlashni o’rgatmoqchi. «Yog’ni yaxshilab qizdir» deydi. Siz qanchagacha qizdirishni bilmaysiz va go’sht kuyib ketadi. Xato sizda ham, onangizda ham emas — ko’rsatmada: «yaxshilab» degan so’zni ikki kishi ikki xil tushunadi.

Bu darsdan keyin siz

• algoritmning uchta shartini ayta olasiz va har birini misolda ko’rsatasiz
• noaniq ko’rsatmani aniq ko’rsatmaga aylantirasiz
• bir masalaning bir necha yechimi borligini va ular teng emasligini bilasiz

Avval qo’lda

Bu mashq butun modulning kalitini beradi. Algoritm qiyin tuyulishining asosiy sababi shundaki, u odatda kod sifatida tanishtiriladi. Bir marta qo’lda bajargan odam esa keyin kodni o’rganmaydi — taniydi.

Avval qo‘lda

~5 daqiqa·juftlikda·Non, moy va bitta sinfdosh

Sinfdoshingiz — robot. U faqat aytilgan narsani, aytilgan tartibda, so’zma-so’z bajaradi va hech narsani o’zidan qo’shmaydi.

Unga sendvich yasatib ko’ring. «Nonni ol» desangiz, u butun bir non ushlaydi. «Moy surt» desangiz — qadoq bilan birga suradi. Har xatoda ko’rsatmangizni aniqroq qilib qayta yozing.

Nechta urinishdan keyin sendvich chiqdi? Yakuniy ko’rsatmangizni daftaringizga yozib qo’ying — u sizning birinchi algoritmingiz.

Nimani sezishingiz kerak

Ko’rsatma har safar uzayadi va aniqlashadi. Kompyuter aynan shu sinfdosh kabi: u sizni tushunmaydi, u sizga bo’ysunadi. Farqi shundaki, u «nima demoqchisiz?» deb so’ramaydi ham.

Kompyuter yopiq. Bu mashq tugamaguncha kod ochilmaydi.

Algoritmning uchta sharti

algoritmalgorithm

Masalani yechish uchun aniq belgilangan qadamlar ketma-ketligi. Nom IX asrda yashagan xorazmlik matematik al-Xorazmiy ismidan kelib chiqqan.

Har qadam aniq bo’lishi kerak: uni ikki xil tushunish mumkin bo’lmasin. «Yaxshilab qizdir» aniq emas, «160 gradusgacha qizdir» aniq. Kodda ham xuddi shunday — «katta son» emas, x > 100.

Algoritm tugashi kerak. Har qadamdan keyin oxirga bir qadam yaqinlashish shart, aks holda programma abadiy aylanadi. Va nihoyat, u takrorlanadigan bo’lsin: bir xil kirishda har doim bir xil natija bersin.

◆Asosiy g'oya

Uchta shartning bittasi buzilsa, sizda algoritm emas — maslahat qoladi. Maslahat foydali bo’lishi mumkin, lekin kompyuter uni bajara olmaydi.

Sekin yechim

Bir masalani olamiz va uni ikki xil yechamiz. Masala oddiy: sinf ballari ichidan ikkinchi eng katta ni topish — ya’ni kumush medal kimga tegadi.

Birinchi fikr odatda eng sodda bo’ladi: saralaymiz va oxiridan ikkinchisini olamiz. Bu yechim to’g’ri, ikki qatorga sig’adi va uni tushuntirish oson.

sekin.pyNusxalash

1ballar = [4, 9, 2, 9, 7]2ballar.sort()3print(ballar[-2])

?Avval o'ylang: bu kod nima chiqaradi? Ishga tushirishdan oldin yozing.

Bashorat qilingNusxalash

1ballar = [4, 9, 2, 9, 7]2ballar.sort()3print(ballar[-2])

Sizning bashoratingizTekshirish

Javobni ko'rish

9

Saralangandan keyin ro'yxat [2, 4, 7, 9, 9] bo'ladi. Oxiridan ikkinchisi — 9. Ikki o'quvchi ham 9 ball to'plagan, ikkalasi ham medalga da'vogar.

Nechta amal ketdi

Saralash ro’yxatni butunlay qayta joylashtiradi. Beshta son uchun bu sezilmaydi, lekin ikki yuz ming son uchun taxminan uch yarim million amal bo’ladi. Bizga esa bor-yo’g’i ikkita son kerak edi.

Yana bir narsa: sort() ro’yxatning o’zini o’zgartiradi. Original tartib kerak bo’lsa, u yo’qolgan bo’ladi va buni odatda ikki soatdan keyin sezasiz.

Tez yechim

Ikkita o’zgaruvchi yetadi. Ro’yxat bo’ylab bir marta yuramiz va yo’l-yo’lakay ikkita eng kattani yangilab boramiz. Ro’yxatga tegilmaydi, qo’shimcha xotira olinmaydi.

tez.pyNusxalash

1ballar = [4, 9, 2, 9, 7]2birinchi = ikkinchi = -13for b in ballar:4  if b > birinchi:5      ikkinchi = birinchi6      birinchi = b7  elif b > ikkinchi:8      ikkinchi = b9print(ikkinchi)

Diqqat qiling: birinchi yangilanganda eski qiymati yo’qolmaydi — u avval ikkinchi ga ko’chiriladi. Ikki qatorning tartibi almashsa, yechim jim buziladi va testda ham o’tib ketishi mumkin.

Sinab ko’r

Quyidagi vizualda eng katta sonni topish algoritmi ishlaydi. Har qadamda faqat bitta ish bajariladi — aynan shu narsa algoritmni algoritm qiladi.

Eng katta sonni topish — qadamma-qadam

Oldinga bosing: algoritm har qadamda faqat bitta ish qiladi.

Algoritm ro'yxat bo'ylab bir marta yuradi va yo'l-yo'lakay eng katta sonni eslab qoladi.

Algoritmning har qadami quyidagi ro‘yxatda matn sifatida ham berilgan — vizual faqat shu qadamlarni chizadi, yangi ma’lumot qo‘shmaydi.

1. Birinchi qadam: eng kattasi deb BIRINCHI sonni olamiz. Hali hech narsa taqqoslanmadi.
2. 9 > eski qiymat. Yangi eng katta: 9.
3. 4 kichik yoki teng — eng katta o'zgarmaydi (9).
4. 9 kichik yoki teng — eng katta o'zgarmaydi (9).
5. 2 kichik yoki teng — eng katta o'zgarmaydi (9).
6. 7 kichik yoki teng — eng katta o'zgarmaydi (9).
7. Ro'yxat tugadi — algoritm ham tugadi. Javob: 9. Jami 5 ta taqqoslash.

sonlar

qara309142932475

eng katta

3

Birinchi qadam: eng kattasi deb BIRINCHI sonni olamiz. Hali hech narsa taqqoslanmadi.

Taqqoslash0

OrqagaO‘ynatishOldinga1/7Qayta boshlash

Xatoni toping

▲Tuzoq — xatoni toping

1 / 40

MasalaRo'yxatdagi eng katta sonni toping. Ro'yxat: -5, -2, -9.

Taklif qilingan yechim

1. 1Boshlang‘ich qiymat: eng = 0.
2. 2Ro‘yxat bo‘ylab yuramiz va har sonni eng bilan solishtiramiz.
3. 3Son eng dan katta bo‘lsa, eng ni o‘sha songa yangilaymiz.
4. 4Sikl tugagach eng — javob.

Bu javobning 1-qismi noto'g'ri. Boshlang'ich qiymat ro'yxatdan olinishi kerak: eng = royxat[0]. Nol bilan boshlansa, barcha sonlar manfiy bo'lgan ro'yxatda algoritm 0 qaytaradi — ro'yxatda umuman yo'q sonni.

Javobning qaysi qismi noto'g'ri? Bosib belgilang.

Javobni ko'rsatish

O’zingizni sinang

1Algoritmning uchta sharti qanday?

Javobni ko'rish

Har qadam aniq (bir xil tushuniladi), algoritm tugaydi (cheksiz aylanmaydi), natija takrorlanadi (bir xil kirishda bir xil chiqish).

2«Ro'yxatni chiroyli tartibga sol» — bu algoritmning qaysi shartini buzadi?

Javobni ko'rish

Aniqlik shartini. «Chiroyli» — o’lchanmaydigan so’z: o’suvchi tartibdami, kamayuvchidami, uzunlik bo’yichami? Ko’rsatma o’rniga maslahat bo’lib qolgan.

3Ikkinchi eng kattani topishda nega saralash «ortiqcha ish» hisoblanadi?

Javobni ko'rish

Saralash barcha elementlarni o’z joyiga qo’yadi, bizga esa faqat ikkitasi kerak. Qolgan hamma joylashtirish natijaga ta’sir qilmaydi — ya’ni bajarilgan, lekin ishlatilmagan ish.

4Tez yechimda ikkinchi = birinchi qatorini olib tashlasak nima bo'ladi?

Javobni ko'rish

Eski maksimum yo’qoladi va ikkinchi hech qachon to’g’ri qiymat olmaydi. Masalan [4, 9] uchun javob 4 emas, -1 chiqadi. Kod xato bermaydi — shunchaki noto’g’ri javob qaytaradi.

5Bir masalaning ikki yechimi bo'lsa, qaysi biri «to'g'ri» yechim?

Javobni ko'rish

Ikkalasi ham to’g’ri, agar ikkalasi ham to’g’ri javob bersa. Tanlash boshqa mezonlar bo’yicha ketadi: tezlik, xotira, o’qilishi, ma’lumotni buzish-buzmasligi. Bu modul aynan shu tanlovni o’rgatadi.

Masalalar

Masalalar

3 ta

• Weird AlgorithmCSES 1068oson

  Shartda algoritm to‘liq yozilgan. Sizning ishingiz — uni so‘zma-so‘z bajarish.

• Missing NumberCSES 1083oson

  Ikki yechim bor: to‘plam bilan va yig‘indi bilan. Ikkalasini ham yozing.

• WatermelonCodeforces 4Aoson

  Javob bitta shartga sig‘adi. Chegara holati: w = 2.

Lokal mashq: mashqlar/01-eng-katta/ — masala matni, testlar va tekshir.py. Avval sekin.py ni o‘zingiz yozing, keyin tayyorini oching.

Topshiriq

Topshiriq — darajangizni tanlang

Asos5–7-sinfMustahkam8–9-sinfChuqur10–11-sinf

Asos · 5–7-sinf — Vizual va aniq ko'rsatmali

Tishni yuvish algoritmini qog’ozga yozing — kamida sakkiz qadam. Keyin uni sinfdoshingizga bering va u faqat yozilganini bajarsin. Qaysi qadamda to’xtab qoldi? O’sha qadamni aniqroq qilib qayta yozing va yana sinang.

Mustahkam · 8–9-sinf — Matnli masala, o'zingiz tuzasiz

01-eng-katta masalasini oching (mashqlar/01-eng-katta/masala.md). Avval sekin.py ni o’zingiz yozing, keyin tayyorini oching va solishtiring. So’ng tez.py ni yozing va python mashqlar/tekshir.py 01-eng-katta bilan ikkalasi bir xil javob berishini tekshiring.

Chuqur · 10–11-sinf — Algoritmik, chegara holatlari bilan

Ikkinchi eng kattani topuvchi yechimingizni buzadigan uchta kirish o’ylab toping va har birida nima bo’lishini oldindan yozing: bitta element, barcha elementlar bir xil, barcha elementlar manfiy. Keyin ishga tushirib tekshiring. Bashoratingiz bilan natija farq qilgan joy — siz bilmagan joy.

Darsni belgilash uchun JavaScript kerak. Bu progressni saqlash uchun ishlatiladi — darslikning o'zi JavaScript'siz ham to'liq o'qiladi.

Darsni tugatdim