Chegaraviy holatlar, brute force va invariant: yechimni mustahkam qilish

Qisqacha: Chegaraviy holat — yechimni buzishi mumkin bo'lgan chekka kirish: bo'sh ro'yxat, bitta element, aynan chegaradagi qiymat, manfiy son. Yaxshi yechim avval oddiy "hammasini sanab chiqish" (brute force) usulida yoziladi, keyin tezlashtiriladi. Invariant — takrorning har aylanishida rost qoladigan gap; u algoritm to'g'riligini tekshirishga yordam beradi.

Bu darsda

• Chegaraviy holatlarni ro'yxat bo'yicha topa olasiz.
• Chegara atrofidagi uchta qiymat bilan tekshirishni bilasiz.
• Brute force nima ekanini va nega birinchi yechim sifatida yaxshi ekanini tushunasiz.
• Invariant yordamida takror to'g'ri ishlashini tekshira olasiz.
• Mashhur FizzBuzz masalasini pseudokodda yecha olasiz.

Oldin bilishingiz kerak: Muammo yechish metodikasi, Pseudokod va uch g'isht.

1. Nega bu kerak?

Oldingi darsda o'rtacha baho masalasida bo'sh ro'yxatni tekshirgan edik. Bu tasodif emas edi. Dasturlar ko'pincha aynan shunday "chekka" joyda buziladi.

Yangi boshlovchi dasturini bitta oddiy misolda sinaydi: ishladi — tamom. Keyin dastur odamlar qo'liga tushadi. Kimdir maydonni bo'sh qoldiradi, kimdir yoshiga -5 yozadi, kimdir telefon raqamini bo'sh joylar bilan kiritadi. Oddiy misolda ishlagan dastur bunday kirishga tayyor emas.

Yaxshi dasturchini boshlovchidan ajratadigan narsa — buni oldindan ko'ra bilish. Bu dars sizga shuni o'rgatadi.

2. Chegaraviy holat nima?

2.1 Misol: yanvarning eng iliq kuni

Yanvar oyining besh kunlik harorati berilgan. Eng iliq kunni topamiz. Boshlovchi shunday yozdi:

haroratlar = [-3, -7, -1, -5, -2]
eng_issiq = 0
HAR BIR t UCHUN haroratlar ichida
    AGAR t > eng_issiq BO'LSA
        eng_issiq = t
CHIQAR eng_issiq

Natija: 0. Lekin ro'yxatda 0 umuman yo'q! To'g'ri javob — -1.

Nima bo'ldi? Hamma harorat manfiy. Birortasi ham 0 dan katta emas, shuning uchun shart hech qachon rost bo'lmadi. eng_issiq boshidagi 0 bilan qoldi.

Yozda bu algoritm yaxshi ishlardi: +25, +31, +28 — hammasi 0 dan katta. Xato faqat "hamma son manfiy" holatida chiqadi. Bunday holat chegaraviy holat (edge case) deyiladi — kam uchraydigan, lekin yechimni buzadigan chekka kirish.

Tuzatish pseudokod darsidan tanish: boshlang'ich qiymat sifatida ro'yxatning birinchi elementini olish. eng_issiq = haroratlar ichidagi birinchi harorat.

2.2 Chegaraviy holatlar ro'yxati

Har bir masalada shu ro'yxatni ko'zdan kechiring:

Professional dasturchi yechim yozishdan oldin o'zidan so'raydi: "Buni qanday buzish mumkin?" Keyin shu holatlar uchun alohida tekshiruv qo'yadi.

2.3 Chegarada uchta qiymat

"18 yoshdan ovoz berish mumkin" qoidasini tekshirmoqchisiz. Qaysi yoshlarni sinash kerak?

Faqat 30 ni sinash yetarli emas. Chegara atrofidagi uchta qiymatni oling:

• 17 — chegaradan bitta past: "Hali erta" chiqishi kerak.
• 18 — aynan chegara: "Ovoz bera olasiz" chiqishi kerak.
• 19 — chegaradan bitta yuqori: "Ovoz bera olasiz".

Nega aynan shular? Chunki eng ko'p xato > va >= ni adashtirishdan kelib chiqadi. yosh > 18 yozilgan bo'lsa, 18 yoshli odam rad etiladi — va buni faqat 18 bilan sinaganda ko'rasiz.

Bu xato turi shunchalik ko'p uchraydiki, uning alohida nomi bor: bittaga adashish (off-by-one). Mashhur misol: 10 metrli panjara quryapsiz va har metrga ustun qo'yasiz. Nechta ustun kerak? Ko'pchilik "10" deydi. To'g'ri javob — 11, chunki boshida ham, oxirida ham ustun turadi.

Tekshirib ko'ring: "Xarid 200 000 so'mdan oshsa chegirma" qoidasini tekshirish uchun qaysi uchta summani tanlaysiz?

3. Brute force: avval ishlasin, keyin tezlashsin

3.1 Brute force nima?

Uch xonali qulfli chamadoningiz bor va kodni unutdingiz. Nima qilasiz? 000 dan boshlab 001, 002, ... deb hammasini sinab chiqasiz. Eng ko'pi bilan 1000 ta urinish — va chamadon albatta ochiladi.

Bu brute force ("qo'pol kuch") — barcha variantlarni birma-bir sinab chiqish usuli. U aqlli emas, lekin ikki katta afzalligi bor: tushunish oson va natija albatta to'g'ri.

Diqqat: Xakerlar ham parolni brute force bilan buzishga urinadi: millionlab variantni avtomatik sinaydi. Shuning uchun parol uzun bo'lishi kerak va tizimlar urinishlar sonini cheklaydi. Blok-sxema darsidagi bankomat 3 urinishdan keyin kartani bloklagan edi — bu aynan brute force'ga qarshi himoya.

3.2 Nega birinchi yechim brute force bo'lishi kerak?

Ko'p boshlovchi masalani ko'rishi bilan eng tez, eng aqlli yechimni izlaydi. Natijada bir soat o'tiradi va hech narsa yozmaydi.

To'g'ri yo'l boshqacha:

flowchart TD
    A[Brute force yechim yozing] --> B[Misollar va chegaraviy holatlarda tekshiring]
    B --> C{Juda sekinmi?}
    C -- Yo'q --> D([Tayyor])
    C -- Ha --> E[Ortiqcha ishni toping va tezlashtiring]
    E --> B

Ishlaydigan sekin yechim ishlamaydigan tez yechimdan har doim yaxshi. Bundan tashqari, sekin yechim tezini tekshirish uchun ham kerak: ikkalasi bir xil javob bersa — tez yechim to'g'ri.

3.3 To'liq yechilgan misol: takrorlangan telefon raqam

Mijozlar ro'yxatida bitta raqam ikki marta yozilgan bo'lishi mumkin. Takror bormi-yo'qligini aniqlaymiz.

Brute force: har bir raqamni qolgan har biri bilan solishtiramiz.

raqamlar = [A, B, C, D, E]
takror = "yo'q"
HAR BIR birinchi UCHUN raqamlar ichida
    HAR BIR ikkinchi UCHUN birinchidan keyingi raqamlar ichida
        AGAR birinchi == ikkinchi BO'LSA
            takror = "bor"
CHIQAR takror

Bu yerda takror ichida yana takror bor. Beshta raqamda solishtirishlar soni: A ni 4 tasi bilan, B ni 3 tasi bilan, C ni 2 tasi bilan, D ni 1 tasi bilan. Jami 4 + 3 + 2 + 1 = 10.

Ishlaydi va to'g'ri. Endi ro'yxat kattalashsa nima bo'ladi?

100 ming mijozda deyarli 5 milliard solishtirish! Ro'yxat 100 barobar oshdi, ish esa deyarli 10 000 barobar.

Tezroq yechim: ortiqcha ish qayerda? Biz bir raqamni qayta-qayta ko'rib chiqyapmiz. O'rniga ko'rilgan raqamlarni "daftar"ga yozib boramiz:

korilganlar = bo'sh daftar
takror = "yo'q"
HAR BIR raqam UCHUN raqamlar ichida
    AGAR raqam korilganlar daftarida bor BO'LSA
        takror = "bor"
    AKS HOLDA
        raqamni korilganlar daftariga yozing
CHIQAR takror

Endi har bir raqam faqat bir marta ko'riladi: 100 ming mijoz — 100 ming qadam.

Bu yerda bitta shart bor: "daftarda bormi?" savoliga tez javob berish kerak. Dasturlash tillarida buning uchun maxsus to'plam bor — JavaScript'da u Set deyiladi. Hozir bilish shart emas, kursda alohida o'rganamiz. Tezlikni aniq o'lchashni esa Big-O darsida ko'rasiz.

4. Invariant: takrordagi buzilmas haqiqat

4.1 Hayotiy misol

Sinf rahbari eng baland o'quvchini topmoqchi. O'quvchilar birma-bir kiradi. Rahbar birinchisini "eng baland" deb eslab qoladi. Keyingisi undan baland bo'lsa — endi uni eslab qoladi.

Jarayonning istalgan paytida rahbardan so'rasangiz, shunday deydi: "Yodimdagi o'quvchi — hozirgacha kirganlar ichida eng balandi." Bu gap birinchi o'quvchidan keyin ham, beshinchidan keyin ham, oxirida ham rost.

Takrorning har aylanishida rost qoladigan bunday gap invariant deyiladi. "Invariant" — "o'zgarmas" degani: qiymatlar o'zgaradi, lekin bu gap rostligicha qoladi.

4.2 Invariantni uch joyda tekshirish

Invariant algoritm to'g'riligini tekshirishning kuchli usuli. Uni uch joyda tekshirasiz:

1. Boshida: takror boshlanishidan oldin gap rostmi?
2. Har aylanishda: bitta aylanish gapni buzmaydimi?
3. Oxirida: takror tugaganda gapdan kerakli javob kelib chiqadimi?

Eng iliq kun algoritmining to'g'ri variantiga qo'llaymiz. Invariant: "eng_issiq — hozirgacha ko'rilgan kunlar ichida eng iliq harorat."

1. Boshida: eng_issiq = birinchi kun harorati. Hozircha bitta kun ko'rilgan — u o'z-o'zidan eng iliq. Rost.
2. Har aylanishda: yangi kun iliqroq bo'lsa, eng_issiq yangilanadi. Bo'lmasa — eski qiymat baribir eng iliq. Ikki holatda ham rost.
3. Oxirida: "ko'rilgan kunlar" endi — butun oy. Demak eng_issiq — butun oyning eng iliq kuni. Aynan bizga kerak bo'lgan javob.

Uch tekshiruv ham "ha" bo'ldi — algoritm to'g'ri.

4.3 Invariant xatoni tushuntiradi

Endi xato variantni oling: eng_issiq = 0. Birinchi tekshiruv: 0 — "ko'rilgan kunlar ichidagi harorat"mi? Yo'q, ro'yxatda 0 yo'q. Invariant boshidanoq yolg'on — shuning uchun natija ham yolg'on chiqdi.

Ko'ryapsizmi? Invariant nafaqat "to'g'ri" deb aytadi, balki xato qayerdan kelayotganini ham ko'rsatadi. Murakkab algoritmlarni — saralash, qidirish — tushunish ham shu g'oyaga tayanadi.

Tekshirib ko'ring: Jasurning pul yig'ish algoritmida (har oy 500 000 so'm) qaysi gap har aylanishda rost qoladi: a) yigilgan = oylar × 500 000; b) yigilgan < 3 000 000?

5. FizzBuzz: klassik mashq

5.1 Masala

1 dan 15 gacha sonlarni chiqaring. Lekin:

• son 3 ga qoldiqsiz bo'linsa — son o'rniga "Fizz";
• 5 ga qoldiqsiz bo'linsa — "Buzz";
• ham 3 ga, ham 5 ga bo'linsa — "FizzBuzz".

"Qoldiqsiz bo'linadi" — bo'lganda qoldiq 0 chiqadi degani. 9 ÷ 3 = 3, qoldiq 0 — qoldiqsiz bo'linadi. 10 ÷ 3 = 3, qoldiq 1 — bo'linmaydi.

Bu masala dasturchilar intervyusida mashhur. U murakkab emas, lekin shartlar tartibiga oid tuzoq bor.

5.2 Yechim

Avval Polya bo'yicha misollar: 3 → Fizz, 5 → Buzz, 15 → FizzBuzz, 7 → 7. 15 — chegaraviy holat: u ikkala shartga ham tushadi.

i = 1
TOKI i <= 15 EKAN
    AGAR i 15 ga qoldiqsiz bo'linsa BO'LSA
        CHIQAR "FizzBuzz"
    AKS HOLDA AGAR i 3 ga qoldiqsiz bo'linsa BO'LSA
        CHIQAR "Fizz"
    AKS HOLDA AGAR i 5 ga qoldiqsiz bo'linsa BO'LSA
        CHIQAR "Buzz"
    AKS HOLDA
        CHIQAR i
    i = i + 1

Natija:

1
2
Fizz
4
Buzz
Fizz
7
8
Fizz
Buzz
11
Fizz
13
14
FizzBuzz

Nega 15 ga bo'linish tekshirildi? Son ham 3 ga, ham 5 ga bo'linsa, u 15 ga bo'linadi — ikki shartni bitta shart bilan yozdik.

5.3 Tartib nega muhim?

Shartlarni boshqa tartibda yozsangiz — avval 3, keyin 5, oxirida 15 — nima bo'ladi? 15 kelganda birinchi shart (3 ga bo'linadi) rost. "Fizz" chiqadi va qolgan shartlar tekshirilmaydi. "FizzBuzz" hech qachon chiqmaydi.

Qoida: eng tor, eng qat'iy shart birinchi tekshiriladi.

To'g'ri tartibdagi algoritmda 1 dan 30 gacha sanasak, 30 uchun nima chiqadi?

6. Ko'p uchraydigan xatolar

6.1 Faqat "baxtli yo'l"ni sinash

Hamma narsa to'g'ri kiritilgan oddiy holat "baxtli yo'l" (happy path) deyiladi. Faqat shuni sinasangiz, chegaraviy holatlardagi xato foydalanuvchida portlaydi. Har doim yuqoridagi chegaraviy holatlar jadvalidan kamida uchta holatni sinang.

6.2 Boshlang'ich qiymatga 0 qo'yish

Eng katta yoki eng kichikni qidirishda 0 dan boshlash — eng iliq kun misolidagi xato. Boshlang'ich qiymat — ro'yxatning birinchi elementi.

6.3 Chegarada adashish

> o'rniga >= yoki aksincha. Buni faqat chegara qiymatining o'zi bilan sinab topasiz: 18 yosh, 200 000 so'm.

6.4 Erta tezlashtirish

Yechim hali ishlamayapti-yu, siz uni qanday tezlashtirishni o'ylayapsiz. Dasturlash klassigi Donald Knut buni shunday baholagan: "Erta optimallashtirish — barcha yomonliklarning ildizi." Avval to'g'rilik, keyin tezlik.

7. Mashqlar

1-mashq (oson): Parol formasi

Saytda parol kiritish maydoni bor: parol kamida 8 belgidan iborat bo'lishi kerak. Tekshirish uchun kamida 4 ta chegaraviy holat yozing.

2-mashq (o'rta): Nolga bo'lish

Ikki son a va b ni bo'ladigan algoritmni pseudokodda yozing. b = 0 bo'lsa, "Nolga bo'lib bo'lmaydi" deb chiqarsin. So'ng uchta misol bilan tekshiring.

Ishora: pseudokod darsidagi taqqoslash belgilaridan == kerak bo'ladi.

KIRIT a
KIRIT b
AGAR b == 0 BO'LSA
    CHIQAR "Nolga bo'lib bo'lmaydi"
AKS HOLDA
    CHIQAR a / b

3-mashq (qiyin): Palindrom

Chapdan ham, o'ngdan ham bir xil o'qiladigan so'z palindrom deyiladi: "kiyik", "qoq", "non". So'z palindrom ekanini tekshiradigan algoritm yozing.

Ishora: ikki "barmoq" oling — biri birinchi harfda, ikkinchisi oxirgi harfda. Ular teng bo'lsa, ikkalasini o'rtaga bittadan suring. Barmoqlar uchrashganda to'xtang.

Yechimdan keyin shu holatlarni tekshiring: "kiyik", "salom", bitta harf "a", bo'sh so'z va "Kiyik" (katta harf bilan).

KIRIT soz
chap = 1
ong = soz dagi harflar soni
natija = "ha"
TOKI chap < ong EKAN
    AGAR chap-harf != ong-harf BO'LSA
        natija = "yo'q"
    chap = chap + 1
    ong = ong - 1
CHIQAR natija

8. Real ishda

• Test yozish. Dasturchilar kodni tekshiradigan maxsus kod — test yozadi. Yaxshi testlar aynan chegaraviy holatlarni qamraydi. Bu haqda test darsida gaplashamiz.
• Tester kasbi. QA muhandislar (dastur sifatini tekshiruvchilar) kuni bo'yi "buni qanday buzsam bo'ladi?" deb o'ylaydi. Ular uchun chegaraviy holatlar ro'yxati — asosiy qurol.
• Intervyu. FizzBuzz 2007-yildan beri intervyularda mashhur. Algoritmik masalalarda odatda "avval oddiy yechimni ayting, keyin tezlashtiring" deyishadi — brute force'dan boshlash aynan shu.
• Xavfsizlik. Hujumchilar ham chegaraviy holatlarni qidiradi: juda uzun matn, manfiy summa, bo'sh maydon. Himoya ham shu ro'yxatdan boshlanadi.

Xulosa

• Chegaraviy holat — bo'sh, bitta, manfiy, bir xil, aynan chegaradagi yoki juda katta kirish.
• Chegarani uchta qiymat bilan sinang: bitta past, aynan o'zi, bitta yuqori.
• Brute force — hamma variantni sinash. Avval u, keyin tezlashtirish.
• Invariant — takrorning har aylanishida rost qoladigan gap. Uni boshida, har aylanishda va oxirida tekshiring.
• FizzBuzz'da eng qat'iy shart birinchi tekshiriladi.

Keyingi dars: Muharrir va IDE; VS Code bilan tanishuv — endi fikrlash vositalaridan amaliy vositaga o'tamiz: kod yoziladigan asosiy dasturni o'rnatib, sozlaymiz.