8-dars: Ochko'zlik — kirish

1-darajaBronza — algoritmik fikrlash1–8 darslar

HayotdaKassa

Kassir 78 so’m qaytarishi kerak. U o’ylab o’tirmaydi: eng katta tangadan boshlaydi — 50, keyin 25, keyin uchta bir so’mlik. Beshta tanga. Bu usul shu qadar tabiiy ko’rinadiki, uning har doim ham to’g’ri emasligi hech kimning xayoliga kelmaydi.

Bu darsdan keyin siz

• ochko’z algoritmni yozasiz va uning nima qilayotganini bir gapda aytasiz
• ochko’zlik adashadigan misolni o’zingiz tuza olasiz
• «ishladi» bilan «to’g’ri» ni ajratasiz

Avval qo’lda

Avval qo‘lda

~5 daqiqa·juftlikda·Qog'oz va qalam

Ikkita tanga tizimini yozing: birinchisi 1, 5, 10, 25, ikkinchisi 1, 3, 4.

Har tizimda 6 so’mni eng kam tanga bilan qaytaring — avval «eng kattadan boshlash» qoidasi bilan, keyin barcha variantni qog’ozda ko’rib chiqib. Ikki javob ikkala tizimda ham bir xil chiqdimi?

Nimani sezishingiz kerak

Birinchi tizimda ikkala usul ham 5 + 1 beradi. Ikkinchisida esa eng kattadan boshlash 4 + 1 + 1 (uchta tanga) beradi, holbuki 3 + 3 (ikkita) mumkin edi. Usul o’zgarmadi — tizim o’zgardi.

Kompyuter yopiq. Bu mashq tugamaguncha kod ochilmaydi.

Ochko’zlik nima

ochko'z algoritmgreedy algorithm

Har qadamda o’sha ondagi eng yaxshi variantni tanlaydigan va hech qachon orqaga qaytmaydigan algoritm.

Ochko’zlikning ikkita xossasi bor. U juda tez — odatda bir marta yurish yetadi. Va u har doim ham to’g’ri emas, chunki bugungi eng yaxshi tanlov ertangi imkoniyatni yopib qo’yishi mumkin.

▲Bu yerda xato qilishadi

Ochko’z yechim yozilganda savol «ishladimi?» emas, «nega ishlaydi?» bo’ladi. Bir necha testda to’g’ri javob chiqishi hech narsani isbotlamaydi. Isbot usullari 16-darsda beriladi.

Sekin yechim

Ishonchli yo’l — barcha variantni ko’rib chiqish. Har summa uchun eng kam tanga sonini kichikroq summalar javobidan yig’amiz.

sekin.pyNusxalash

1TANGALAR = [1, 5, 10, 25, 50, 100]2summa = 783eng_kam = [0] + [10**18] * summa4for s in range(1, summa + 1):5  for t in TANGALAR:6      if t <= s and eng_kam[s - t] + 1 < eng_kam[s]:7          eng_kam[s] = eng_kam[s - t] + 18print(eng_kam[summa])

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

Bashorat qilingNusxalash

1TANGALAR = [1, 5, 10, 25, 50, 100]2summa = 783eng_kam = [0] + [10**18] * summa4for s in range(1, summa + 1):5  for t in TANGALAR:6      if t <= s and eng_kam[s - t] + 1 < eng_kam[s]:7          eng_kam[s] = eng_kam[s - t] + 18print(eng_kam[summa])

Sizning bashoratingizTekshirish

Javobni ko'rish

5

Bu yechim HAR QANDAY tanga tizimida to'g'ri ishlaydi, chunki u hech narsani taxmin qilmaydi. Uning usuli 25-darsda dinamik programmalash deb ataladi.

Nega sekin

E’tibor bering: bu yerda sekin yechim umumiyroq — u har tanga tizimida to’g’ri. Muammosi boshqa: u har summa uchun alohida javob hisoblaydi, summa esa 10¹⁸ gacha bo’lishi mumkin.

Sig‘adimi?

Bir soniyada taxminan 10⁸ oddiy amal bajariladi.

Yechim	n = 1 000	n = 10⁶
Har summani hisoblashn	1 000sig‘adi	10⁶sig‘adi
Ochko‘z: tangalar bo‘yicha yurish1	1sig‘adi	1sig‘adi

Yashil — yechim o‘tadi. Sariq — chegarada, konstanta va til muhim bo‘lib qoladi. Qizil — bu yechim bilan bormaydi, boshqasini qidiring.

Jadval n gacha bo’lgan summalar uchun. S = 10¹⁸ da bunday ro’yxat xotiraga umuman sig’maydi — million marta katta kompyuter ham yordam bermaydi.

Tez yechim

Ochko’zlik summani emas, tangalarni aylanib chiqadi. Oltita tanga turi bor, demak oltita qadam — summa qanchalik katta bo’lishidan qat’i nazar.

tez.pyNusxalash

1TANGALAR = [100, 50, 25, 10, 5, 1]2qoldiq = 783soni = 04for t in TANGALAR:5  soni += qoldiq // t6  qoldiq %= t7print(soni)

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

Bashorat qilingNusxalash

1TANGALAR = [100, 50, 25, 10, 5, 1]2qoldiq = 783soni = 04for t in TANGALAR:5  soni += qoldiq // t6  qoldiq %= t7print(soni)

Sizning bashoratingizTekshirish

Javobni ko'rish

5

Bo'lish va qoldiq: 78 // 50 = 1, qoldiq 28; 28 // 25 = 1, qoldiq 3; keyin uchta birlik. Sikl summaga emas, tanga turlariga bog'liq.

Va endi u adashadi

Xuddi shu kodni boshqa tanga tizimida yurgizamiz. Kod o’zgarmaydi, faqat ro’yxat boshqacha.

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

Bashorat qilingNusxalash

1TANGALAR = [4, 3, 1]2qoldiq = 63soni = 04for t in TANGALAR:5  soni += qoldiq // t6  qoldiq %= t7print(soni)

Sizning bashoratingizTekshirish

Javobni ko'rish

3

Ochko'zlik 4 + 1 + 1 — uchta tanga beradi. To'g'ri javob esa 3 + 3, ya'ni ikkita. Birinchi qadamda olingan to'rtlik qolgan ikkini ikkita birlikka bo'lishga majbur qildi.

◆Asosiy g'oya

Ochko’zlik bu yerda xato bermadi va sekinlashmadi ham — u shunchaki noto’g’ri javob qaytardi. Aynan shuning uchun har ochko’z yechim uchun nega to’g’ri ishlashini aytish talab qilinadi.

Sinab ko’r

Vizualda ochko’z qator optimal qator bilan yonma-yon ishlaydi. Ular qaysi qadamda ajralib ketishini kuzating.

Ochko'zlik qachon adashadi

Ochko'z qatorni optimal qator bilan solishtiring.

4, 3, 1 tanga tizimida ochko'zlik 6 ni uch tangaga yechadi (4+1+1), optimal yechim esa ikkita (3+3).

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

1. Tanga tizimi: 4, 3, 1. 6 so'mni eng kam tanga bilan qaytarish kerak.
2. Ochko'zlik: eng katta sig'adigan tanga — 4. Oldik, qoldiq 2.
3. Ochko'zlik: eng katta sig'adigan tanga — 1. Oldik, qoldiq 1.
4. Ochko'zlik: eng katta sig'adigan tanga — 1. Oldik, qoldiq 0.
5. Ochko'zlik tugadi: 3 ta tanga (4 + 1 + 1). Yaxshi ko'rinadi.
6. Lekin: 3 + 3 = 6. Ikkita tanga. Ochko'zlik birinchi qadamda 4 ni olib, o'zini tuzoqqa soldi.
7. Xulosa: ochko'zlik TEZ, lekin har doim to'g'ri emas. Uni ishlatishdan oldin nega to'g'ri ishlashini aytish kerak — bu 16-darsning mavzusi.

tangalar

403112

ochko'z

optimal

qoldiq

6

Tanga tizimi: 4, 3, 1. 6 so'mni eng kam tanga bilan qaytarish kerak.

Tanga olindi0

OrqagaO‘ynatishOldinga1/7Qayta boshlash

Xatoni toping

▲Tuzoq — xatoni toping

8 / 40

MasalaIstalgan tanga tizimida S so'mni eng kam tanga bilan qaytaring.

Taklif qilingan mulohaza

1. 1Tangalarni kamayuvchi tartibda saralaymiz.
2. 2Har qadamda qoldiqqa sig‘adigan eng katta tangadan imkon boricha ko‘p olamiz.
3. 3Har qadam qoldiqni kamaytiradi, demak algoritm albatta tugaydi.
4. 4Eng katta tangadan boshlanganligi uchun tanga soni eng kam bo‘ladi.

Bu javobning 4-qismi noto'g'ri. Uchinchi qadamgacha hammasi to'g'ri: algoritm haqiqatan tugaydi. Xato oxirgi xulosada — «eng kattadan boshlash» eng kam tanga sonini KAFOLATLAMAYDI. 1, 3, 4 tizimida 6 uchun bu qoida uchta tanga beradi, optimal javob esa ikkita.

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

Javobni ko'rsatish

O’zingizni sinang

1Ochko'z algoritmni bir gapda ta'riflang.

Javobni ko'rish

Har qadamda o’sha ondagi eng yaxshi variantni tanlaydi va tanlovini hech qachon qayta ko’rib chiqmaydi.

21, 3, 4 tizimida 6 uchun ochko'zlik nega adashadi?

Javobni ko'rish

Birinchi qadamda 4 olinadi va qoldiq 2 bo’lib qoladi — uni faqat ikkita birlik bilan yopish mumkin. To’rtlikdan voz kechilganda 3 + 3 ochiladi, lekin ochko’zlik orqaga qaytmaydi.

3Nega bu darsda sekin yechim aynan umumiyroq bo'lib chiqdi?

Javobni ko'rish

Chunki u hech narsani taxmin qilmaydi: har summani kichikroq summalar orqali to’liq hisoblaydi. Uning kamchiligi tezlikda, ochko’zlikniki esa to’g’rilikda.

4Ochko'z yechim uchta testda to'g'ri javob berdi. Bu yetarlimi?

Javobni ko'rish

Yetarli emas. Testlar xatoning borligini ko’rsatishi mumkin, yo’qligini esa hech qachon. Kerak bo’lgani — nega to’g’ri ishlashini ko’rsatuvchi mulohaza.

5Ochko'zlikning tezligi nimaga bog'liq — summagami yoki tanga turlarigami?

Javobni ko'rish

Tanga turlari soniga. Summa 10¹⁸ bo’lsa ham qadamlar soni o’zgarmaydi, chunki har tanga turi bir marta ko’riladi.

Masalalar

Masalalar

3 ta

• ApartmentsCSES 1084o'rta

  Ikkala ro‘yxatni saralang va eng kichikdan boshlab moslang. Nega bu optimal — o‘ylab ko‘ring.

• TaxiCodeforces 158Bo'rta

  Guruhlarni o‘lchami bo‘yicha sanang. To‘rtliklar alohida, uchliklar birliklar bilan.

• Ferris WheelCSES 1090o'rta

  Saralang, keyin eng yengil va eng og‘irni juftlashtirishga urinib ko‘ring.

Lokal mashq: mashqlar/08-tanga/ — 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

1, 6, 10 tanga tizimini oling. 12 so’mni ochko’zlik bilan va qo’lda eng yaxshi tarzda qaytaring. Ikki javob farq qildimi? Farqni bir gapda tushuntiring.

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

08-tanga masalasini yeching. Keyin tez.py ni 1, 3, 4 tizimida yurgizib, sekin.py bilan javoblari farq qiladigan eng kichik summani toping.

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

Ochko’zlik to’g’ri ishlaydigan tanga tizimlarining umumiy sharti bormi? Kichik tizimlarni kompyuterda sinab ko’ring: sekin.py va tez.py ni 1 dan 100 gacha barcha summada solishtiring va ochko’zlik buziladigan birinchi summani chiqaring. Bu — 15-darsdagi stress-testning birinchi ko’rinishi.

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

Darsni tugatdim