Asosiy mazmunga o'tish
STEAM AcademySTEAM Academy

13-dars: Javob bo'yicha ikkilik qidiruv

2-darajaKumush — usullar9–16 darslar

Bu darsdan keyin siz

  • «javobni qidirish» va «yechimni qidirish» farqini ayta olasiz
  • masalada monotonlik borligini tekshirasiz
  • yetadimi() funksiyasini yozib, uning ustidan ikkilik qidiruv yurgizasiz

Avval qo’lda

“Avval qo’lda” bo'limiga havola

Avval qo‘lda

~6 daqiqajuftlikdaQog'oz va qalam

Sinfdoshingiz 1 dan 100 gacha maxfiy son o’ylasin — bu «kerakli eng kam daqiqa». Siz undan faqat bitta shakldagi savol bera olasiz: «T daqiqa yetadimi?»

U «ha» yoki «yo’q» deb javob beradi. Sizga eng kichik yetadigan T kerak. Nechta savolda topdingiz?

Nimani sezishingiz kerak

Yetti savol yetdi. Muhimi son emas: siz javobni hisoblamadingiz, faqat tekshirdingiz. Ko’p masala aynan shunday — hisoblash qiyin, tekshirish oson.

Kompyuter yopiq. Bu mashq tugamaguncha kod ochilmaydi.

Fikr teskari

“Fikr teskari” bo'limiga havola

Odatda algoritm javobni quradi: qo’shadi, saralaydi, yig’adi. Bu darsda esa boshqacha ish tutamiz — javobni taxmin qilamiz va uni tekshiramiz.

monotonlikmonotonicity

«Bu javob bo’ladimi?» degan savolning bir marta «yo’q» dan «ha» ga o’tib, boshqa qaytmasligi. Ikkilik qidiruvga faqat shu xossa ruxsat beradi.

Buni tekshirish oson. Agar 8 soniyada yetarli detal chiqsa, 9 soniyada ham albatta chiqadi — vaqt ko’paysa natija kamaymaydi. Demak «yetadimi?» funksiyasi yo'q · yo'q · yo'q · ha · ha · ha ko’rinishida bo’ladi va bizga o’sha birinchi «ha» kerak.

Birinchi masala: mashinalar

“Birinchi masala: mashinalar” bo'limiga havola

Zavodda uchta mashina bor: ular bitta detalni 3, 2 va 5 soniyada yasaydi. Yetti detal uchun eng kam necha soniya kerak?

Javobni formula bilan chiqarish qiyin. Tekshirish esa bir qatorlik ish: T soniyada i-mashina T // t[i] ta detal yasaydi.

mashinalar.py
vaqtlar = [3, 2, 5]kerak = 7def yetadimi(T):  return sum(T // t for t in vaqtlar) >= kerakchap, ong = 1, min(vaqtlar) * kerakwhile chap < ong:  orta = (chap + ong) // 2  if yetadimi(orta):      ong = orta  else:      chap = orta + 1print(chap)

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

Bashorat qiling
vaqtlar = [3, 2, 5]kerak = 7def yetadimi(T):  return sum(T // t for t in vaqtlar) >= kerakchap, ong = 1, min(vaqtlar) * kerakwhile chap < ong:  orta = (chap + ong) // 2  if yetadimi(orta):      ong = orta  else:      chap = orta + 1print(chap)
Javobni ko'rish
8

Yuqori chegara — eng tez mashina yolg'iz o'zi ishlagandagi vaqt. U albatta yetarli, demak javob undan katta bo'la olmaydi.

Ikkinchi masala: arqonlar

“Ikkinchi masala: arqonlar” bo'limiga havola

Uchta arqon bor: 8, 5 va 13 metr. Ulardan bir xil uzunlikdagi beshta bo’lak kesish kerak. Bo’lak eng ko’pi bilan necha metr bo’lishi mumkin?

Bu safar biz eng katta yetadigan qiymatni qidiramiz — yo’nalish teskari, mantiq esa o’sha.

arqonlar.py
arqonlar = [8, 5, 13]kerak = 5def yetadimi(uzunlik):  return sum(a // uzunlik for a in arqonlar) >= kerakchap, ong = 1, max(arqonlar)javob = 0while chap <= ong:  orta = (chap + ong) // 2  if yetadimi(orta):      javob = orta      chap = orta + 1  else:      ong = orta - 1print(javob)

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

Bashorat qiling
arqonlar = [8, 5, 13]kerak = 5def yetadimi(uzunlik):  return sum(a // uzunlik for a in arqonlar) >= kerakchap, ong = 1, max(arqonlar)javob = 0while chap <= ong:  orta = (chap + ong) // 2  if yetadimi(orta):      javob = orta      chap = orta + 1  else:      ong = orta - 1print(javob)
Javobni ko'rish
4

4 metrda 2 + 1 + 3 = 6 ta bo'lak chiqadi, 5 metrda esa atigi 4 ta. Bu yerda monotonlik teskari yo'nalishda: uzunlik oshsa bo'laklar soni kamayadi.

Uchinchi masala: taqsimlash

“Uchinchi masala: taqsimlash” bo'limiga havola

Ro’yxatni k ta ketma-ket bo’lakka bo’lish kerak. Bo’laklarning eng katta yig’indisi imkon qadar kichik bo’lsin.

Bu yerda yetadimi() biroz uzunroq: berilgan chegara bilan ro’yxatni ochko’z tarzda bo’lib chiqamiz va nechta bo’lak kerak bo’lganini sanaymiz.

taqsimlash.py
a = [2, 4, 7, 3, 5]k = 3def yetadimi(chegara):  bolaklar = 1  joriy = 0  for x in a:      if joriy + x > chegara:          bolaklar += 1          joriy = x      else:          joriy += x  return bolaklar <= kchap, ong = max(a), sum(a)while chap < ong:  orta = (chap + ong) // 2  if yetadimi(orta):      ong = orta  else:      chap = orta + 1print(chap)

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

Bashorat qiling
a = [2, 4, 7, 3, 5]k = 3def yetadimi(chegara):  bolaklar = 1  joriy = 0  for x in a:      if joriy + x > chegara:          bolaklar += 1          joriy = x      else:          joriy += x  return bolaklar <= kchap, ong = max(a), sum(a)while chap < ong:  orta = (chap + ong) // 2  if yetadimi(orta):      ong = orta  else:      chap = orta + 1print(chap)
Javobni ko'rish
8

Bo'linish: 2+4, 7, 3+5 — eng katta yig'indi 8. Quyi chegara ro'yxatdagi eng katta son: bitta element hech qanday bo'lakka bo'linmaydi.

Uchtasida nima umumiy

“Uchtasida nima umumiy” bo'limiga havola

Uch masala uch xil sohadan, lekin ularning skeleti bir xil:

  1. Javobni to’g’ridan-to’g’ri hisoblash qiyin
  2. Berilgan javobni tekshirish esa oson va tez
  3. Javob kattalashsa shart buzilmaydi — monotonlik bor
  4. Demak yetadimi() ustidan ikkilik qidiruv yurgiziladi

Sig‘adimi?

Bir soniyada taxminan 10⁸ oddiy amal bajariladi.

Yechimn = 1 000n = 10⁶
Har javobni sinashn1 000sig‘adi10⁶sig‘adi
Javob bo‘yicha ikkilik qidiruvlog n10sig‘adi20sig‘adi

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

Jadval n — javob nomzodlari soni. Milliard nomzod bo’lganda ham yetadimi() atigi 30 marta chaqiriladi.

Sinab ko’r

“Sinab ko’r” bo'limiga havola

Vizualda javob nomzodlari qatori turibdi. Har «yetadimi?» savolidan keyin yarmi o’chishini kuzating — biz javobni qurmayapmiz, uni qisib boryapmiz.

Javob bo'yicha ikkilik qidiruv

Yuqori qatorda javob nomzodlari. Har savoldan keyin yarmi o'chadi.

Javob nomzodlari oralig'i har «yetadimi?» savolidan keyin ikki barobar kichrayadi.

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

  1. Uch mashina: 3, 2 va 5 soniyada bitta detal. 7 ta detal kerak. Javobni to'g'ridan-to'g'ri hisoblab bo'lmaydi — lekin tayyor javobni TEKSHIRISH oson.
  2. 5 soniyada atigi 4 ta chiqadi — yetmaydi. Demak javob 5 dan katta: chap yarmi kesildi.
  3. Qolgan oraliq: 6 dan 10 gacha.
  4. 8 soniyada 7 ta detal chiqadi — 7 ta yetarli. Demak javob 8 dan katta emas: o'ng yarmi kesildi.
  5. Qolgan oraliq: 6 dan 8 gacha.
  6. 7 soniyada atigi 6 ta chiqadi — yetmaydi. Demak javob 7 dan katta: chap yarmi kesildi.
  7. Qolgan oraliq: 8 dan 8 gacha.
  8. Javob — 8 soniya. Diqqat qiling: biz jadval tuzmadik va formula chiqarmadik. Faqat 3 marta «shu vaqt yetadimi?» deb so'radik.
T soniya
12345678910
chiqadi

Uch mashina: 3, 2 va 5 soniyada bitta detal. 7 ta detal kerak. Javobni to'g'ridan-to'g'ri hisoblab bo'lmaydi — lekin tayyor javobni TEKSHIRISH oson.

Savol0

1/8

Xatoni toping

“Xatoni toping” bo'limiga havola

Tuzoq — xatoni toping

13 / 40

MasalaEng kam vaqtni javob bo'yicha ikkilik qidiruv bilan toping.

Taklif qilingan yechim

Bu javobning 3-qismi noto'g'ri. Teskari qilingan. orta yetarli bo'lsa, javob undan KATTA emas — biz eng KAM yetadigan qiymatni qidiryapmiz, demak ong = orta. Yozilgani bilan qidiruv yetarli qiymatlarni tashlab, yetmaydiganlar tomonga ketadi va javob eng yuqori chegara bo'lib chiqadi.

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

O’zingizni sinang

“O’zingizni sinang” bo'limiga havola

1«Javobni qidirish» nima degani?

Javobni ko'rish

Yechimni qurish o’rniga javobni taxmin qilib, uni tekshirish. Masala «javobni hisobla» dan «bu javob bo’ladimi?» ga aylanadi.

2Ikkilik qidiruv ishlashi uchun qanday shart kerak?

Javobni ko'rish

Monotonlik: «yetadimi?» funksiyasi bir marta yolg’ondan rostga o’tib, boshqa qaytmasligi. Bu xossa bo’lmasa usul yaramaydi.

3Yuqori chegarani (ong) qanday tanlaysiz?

Javobni ko'rish

Albatta yetadigan har qanday qiymatni. U aniq bo’lishi shart emas — u faqat yetarli bo’lsa bas, chunki qidiruv uni tez qisqartiradi.

4Arqonlar masalasida yo'nalish nega teskari?

Javobni ko'rish

U yerda eng KATTA yetadigan qiymat kerak. Uzunlik oshsa bo’laklar soni kamayadi, ya’ni «ha» lar chap tomonda turadi va biz oxirgi «ha» ni qidiramiz.

5yetadimi() funksiyasining narxi umumiy vaqtga qanday ta'sir qiladi?

Javobni ko'rish

To’g’ridan-to’g’ri: jami vaqt yetadimi() narxini log (javob oralig’i) ga ko’paytirgan qiymat. Shuning uchun tekshiruv funksiyasi ham tez bo’lishi kerak.

Masalalar

“Masalalar” bo'limiga havola

Masalalar

3 ta

  • Factory MachinesCSES 1620o'rta

    Darsdagi birinchi masalaning haqiqiy o‘lchamdagi varianti. Yuqori chegarani ehtiyot bo‘lib tanlang.

  • Array DivisionCSES 1085o'rta

    Uchinchi masalaning o‘zi. Quyi chegara — ro‘yxatdagi eng katta son.

  • Reading BooksCSES 1631o'rta

    Bu masalani ikkilik qidiruvsiz ham yechish mumkin. Ikkala yo‘lni ham sinang va solishtiring.

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

Topshiriq

“Topshiriq” bo'limiga havola

Topshiriq — darajangizni tanlang

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

«Eng kichik yetadigan qiymat» o’yinini uch marta o’ynang, har safar berilgan savollarni qog’ozga yozib boring. Uchinchi o’yinda savollaringiz kamaydimi?

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

13-mashina masalasini yeching. sekin.py javobni birma-bir sinaydi — uni katta test bilan yurgizib ko’ring va nega tugamasligini tushuntiring.

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

Monotonligi yo’q masala o’ylab toping: javob kattalashganda shart gohida bajarilib, gohida buziladigan holat. Bunday masalada ikkilik qidiruv qanday xato javob berishini misolda ko’rsating.

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