15-dars: Chegara holatlari va stress-test

2-darajaKumush — usullar9–16 darslar

HayotdaMusobaqa

Yechimingiz o’zingiz o’ylab topgan beshta testda to’g’ri ishladi va siz topshirdingiz. Javob keldi: noto’g’ri, 7-test. Test ko’rsatilmaydi, vaqt esa ketmoqda. Siz o’zingizga o’xshab o’ylaysiz, shuning uchun sizni sindiradigan testni o’ylab topa olmaysiz — buni mashina qiladi.

Bu darsdan keyin siz

• har masalada chegara holatlari ro’yxatini yozib chiqasiz
• ikki yechimni tasodifiy testlarda avtomatik solishtirasiz
• farq topilgan eng kichik testni ajratib olasiz

Avval qo’lda

Avval qo‘lda

~6 daqiqa·juftlikda·Sinfdoshning yozilgan yechimi

Sinfdoshingiz bilan yechimlaringizni almashing. Vazifa — bir-biringizni sindirish: shunday kirish o’ylab topingki, uning yechimi noto’g’ri javob bersin.

Kodni o’qishga urinmang. O’rniga chekkalarni sinang: bitta element, bo’sh kirish, hamma sonlar bir xil, hamma sonlar manfiy, eng katta chegara.

Nimani sezishingiz kerak

Sindirgan test deyarli har doim kichik bo’ladi. Bu tasodif emas: xato mantiqda bo’ladi, mantiq esa uchta sonda ham buziladi.

Kompyuter yopiq. Bu mashq tugamaguncha kod ochilmaydi.

Chegara holatlari ro’yxati

Har masalada bir xil joylar qoqiladi. Ro’yxatni yodlash shart emas — uni yechim yozib bo’lgach ochib chiqish kifoya.

Holat	Nima buziladi
n = 1	Qo’shnilar bo’yicha yuradigan sikllar bo’sh qoladi
Barcha elementlar bir xil	Qat’iy taqqoslash (>) hech qachon rost bo’lmaydi
Barcha sonlar manfiy	Nol bilan boshlangan hisoblagichlar noto’g’ri javob beradi
Javob nolga teng	«Topilmadi» belgisi bilan chalkashadi
Eng katta chegara	Vaqt yoki xotira chegarasidan chiqadi
Kirish saralangan yoki teskari saralangan	Eng yomon holat aynan shu yerda

Sekin va tez yechim

Masala: ketma-ket kunlardan iborat bo’sh bo’lmagan oraliqning eng katta yig’indisi. To’liq izlash barcha oraliqlarni ko’radi.

sekin.pyNusxalash

1def sekin(a):2  eng = a[0]3  for i in range(len(a)):4      y = 05      for j in range(i, len(a)):6          y += a[j]7          if y > eng:8              eng = y9  return eng10print(sekin([-1, 3, -2, 5, 3, -5, 2, 2]))

Tez yechim bitta yurishda ishlaydi: har kunda «oldingi oraliqni davom ettiraymi yoki shu kundan yangisini boshlaymi?» degan qaror qabul qilinadi.

tez.pyNusxalash

1def tez(a):2  eng = joriy = a[0]3  for x in a[1:]:4      joriy = max(x, joriy + x)5      eng = max(eng, joriy)6  return eng7print(tez([-1, 3, -2, 5, 3, -5, 2, 2]))

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

Bashorat qilingNusxalash

1def tez(a):2  eng = joriy = a[0]3  for x in a[1:]:4      joriy = max(x, joriy + x)5      eng = max(eng, joriy)6  return eng7print(tez([-1, 3, -2, 5, 3, -5, 2, 2]))

Sizning bashoratingizTekshirish

Javobni ko'rish

9

Eng yaxshi oraliq — 3, -2, 5, 3 va u 9 beradi. Ikkala yechim ham shu javobni qaytaradi.

Va endi buzuq variant

Ko’p manbada bu yechim boshqacha yoziladi: joriy yig’indi manfiy bo’lsa nolga tashlanadi. Farq bitta belgida va u musbat sonli testlarda umuman ko’rinmaydi.

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

Bashorat qilingNusxalash

1def buzuq(a):2  eng = joriy = 03  for x in a:4      joriy = max(0, joriy + x)5      eng = max(eng, joriy)6  return eng7def togri(a):8  eng = joriy = a[0]9  for x in a[1:]:10      joriy = max(x, joriy + x)11      eng = max(eng, joriy)12  return eng13sinov = [-4, -2, -7]14print(buzuq(sinov), togri(sinov))

Sizning bashoratingizTekshirish

Javobni ko'rish

0 -2

Buzuq variant nol qaytaradi — ya'ni «hech narsa tanlamayman» degan javob. Shart esa bo'sh bo'lmagan oraliqni talab qiladi, demak to'g'ri javob -2.

▲Bu yerda xato qilishadi

Bu xato o’nlab tasodifiy testda ko’rinmaydi, chunki tasodifiy ro’yxatda deyarli har doim musbat son bo’ladi. Uni topish uchun generator ham to’g’ri yozilgan bo’lishi kerak: kichik rejimda sonlar ko’pincha manfiy bo’lsin.

Stress-test

stress-teststress testing

Tasodifiy kichik testlar yasab, ikki yechimni yonma-yon yurgizish va javoblari farq qilgan birinchi testni ajratib olish.

Loyihada tayyor shablon bor va uni o’zgartirish kerak emas — u faqat mashq papkasining nomini biladi.

terminalNusxalash

1# terminalda:2# python mashqlar/stress.py 15-eng-katta-yigindi3# python mashqlar/stress.py 15-eng-katta-yigindi 500

Skript uch narsani takrorlaydi: generator.py dan kichik test oladi, sekin.py va tez.py ni yurgizadi, javoblarni solishtiradi. Farq chiqsa — to’xtaydi va testni ekranga chiqaradi.

Sig‘adimi?

Bir soniyada taxminan 10⁸ oddiy amal bajariladi.

Yechim	n = 1 000	n = 200 000
Barcha oraliqni ko‘rishn^2	10⁶sig‘adi	10¹⁰sig‘maydi
Bir yurishdan	1 000sig‘adi	200 000sig‘adi

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

Sinab ko’r

Vizualda stress-test ishlayapti. Uchta testda farq yo’q, to’rtinchisida esa chiqadi — va u atigi uchta sondan iborat.

Stress-test — xatoni mashina topadi

Har qadamda bitta tasodifiy test. Javoblar farq qilgan joyda to'xtaymiz.

Tasodifiy kichik testlarda ikki yechim solishtiriladi; farq chiqqan birinchi test ekranga chiqariladi.

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

1. Generator kichik tasodifiy testlar yasaydi. Har testda ikkala yechim ishga tushadi va javoblar solishtiriladi.
2. 1-test: ikkala javob ham 6. Farq yo'q, davom etamiz.
3. 2-test: ikkala javob ham 6. Farq yo'q, davom etamiz.
4. 3-test: ikkala javob ham 6. Farq yo'q, davom etamiz.
5. FARQ TOPILDI. Sekin yechim -2 dedi, tez yechim 0. Test atigi uchta sondan iborat — xatoni qo'lda ko'rish mumkin.
6. Sabab: tez yechim joriy yig'indini nolga tashlaydi, ya'ni «hech narsa tanlamaslik» variantini ham hisobga oladi. Shart esa bo'sh bo'lmagan oraliqni talab qiladi.

tasodifiy test

0123

javoblar

sekintez

Generator kichik tasodifiy testlar yasaydi. Har testda ikkala yechim ishga tushadi va javoblar solishtiriladi.

Test0

OrqagaO‘ynatishOldinga1/6Qayta boshlash

Xatoni toping

▲Tuzoq — xatoni toping

15 / 40

MasalaStress-test 500 ta tasodifiy testda farq topmadi. Xulosa?

Taklif qilingan mulohaza

1. 1Sekin yechim to‘liq izlash, ya‘ni u aniq to‘g‘ri.
2. 2500 ta tasodifiy testda ikki yechim bir xil javob berdi.
3. 3Demak tez yechim ham to‘g‘ri.
4. 4Endi uni topshirish mumkin.

Bu javobning 3-qismi noto'g'ri. Test xatoning BORLIGINI ko'rsatadi, yo'qligini emas. Generator faqat o'zi yasay oladigan testlarni beradi: barcha sonlar manfiy bo'lgan holat chiqmasa, o'sha holatdagi xato ham chiqmaydi. To'g'ri xulosa: «ishonch ortdi, isbot yo'q».

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

Javobni ko'rsatish

O’zingizni sinang

1Nega stress-test uchun testlar kichik bo'lishi kerak?

Javobni ko'rish

n = 5 dagi xato n = 100000 dagi xato bilan bir xil, lekin kichik testni o’qib, qo’lda tekshirib bo’ladi. Katta test faqat «xato bor» deydi, «qayerda» demaydi.

2Stress-test uchun nechta programma kerak?

Javobni ko'rish

Uchta: sekin yechim (etalon), tez yechim va generator. Uchtasidan bittasi yo’q bo’lsa usul ishlamaydi.

3Generator yomon yozilgan bo'lsa nima bo'ladi?

Javobni ko'rish

Stress-test hech qanday farq topmaydi va sizga soxta ishonch beradi. Generator masalaning xavfli joylarini qamrab olishi kerak: manfiy sonlar, takrorlar, chegaraviy o’lchamlar.

4«Barcha sonlar manfiy» holati qaysi turdagi xatoni ochadi?

Javobni ko'rish

Nol bilan boshlangan hisoblagichlarni. eng = 0 yoki joriy = 0 yozilgan har qanday yechim shu testda jimgina noto’g’ri javob beradi.

5500 ta testdan o'tgan yechim to'g'rimi?

Javobni ko'rish

Noma’lum. Ishonch ortdi, lekin isbot yo’q. Testlar xatoning borligini ko’rsatadi, yo’qligini esa faqat mulohaza ko’rsatishi mumkin — 16-darsning mavzusi.

Masalalar

Masalalar

3 ta

• Maximum Subarray SumCSES 1643oson

  Darsdagi masalaning o‘zi. Barcha sonlar manfiy bo‘lgan testni albatta sinang.

• Missing NumberCSES 1083oson

  Chegara holatlari: yo‘qolgan son birinchi yoki oxirgi bo‘lsa ham ishlaydimi?

• Increasing ArrayCSES 1094oson

  Javob 10^9 · 2·10^5 gacha chiqishi mumkin. Bu son qayerga sig‘adi?

Lokal mashq: mashqlar/15-eng-katta-yigindi/ — 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

Chegara holatlari jadvalini daftaringizga ko’chiring. Keyin oldingi uch darsda yozgan yechimlaringizdan bittasini oling va jadvalning har qatorini unda sinab chiqing. Nechtasida qoqildingiz?

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

15-eng-katta-yigindi mashqini oching va tez.py ni ATAYLAB buzing — joriy ni nolga tashlaydigan variantga o’zgartiring. Keyin python mashqlar/stress.py 15-eng-katta-yigindi ni ishga tushiring. Nechanchi urinishda farq topildi?

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

Sinfdoshingiz bilan sindirish musobaqasi o’tkazing. Har biringiz bitta masalani yeching, keyin yechimlarni almashing va bir-biringiz uchun generator yozing. Sindirgan test topilsa — uni saqlab qo’ying: bunday testlar to’plami eng qimmatli o’quv materiali.

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

Darsni tugatdim