10-dars: Ikki ko'rsatkich

2-darajaKumush — usullar9–16 darslar

HayotdaBozor

Narxlar o’sish tartibida yozilgan ro’yxat bor va sizda aniq 10 000 so’m. Ikkita narsa olmoqchisiz. Ro’yxatning ikki chetiga barmoq qo’yasiz: yig’indi kam bo’lsa chapdagini o’ngga suradingiz, ko’p bo’lsa o’ngdagini chapga. Ikki barmoq hech qachon orqaga qaytmaydi.

Bu darsdan keyin siz

• ikki ko’rsatkichning ikki shaklini — qarama-qarshi va sirpanuvchi oyna — ajratasiz
• ko’rsatkich qaysi yo’nalishda surilishini shartdan chiqarasiz
• usul qachon ishlamasligini ayta olasiz

Avval qo’lda

Avval qo‘lda

~5 daqiqa·juftlikda·Arqon va ikkita tugun (yoki chizg'ich)

Qog’ozga o’sish tartibida sakkizta son yozing va ikki chetiga barmoq qo’ying. Maqsad — yig’indisi aniq 20 bo’lgan juftlikni topish.

Har qadamda faqat bitta qoidaga amal qiling: yig’indi 20 dan kichik bo’lsa chap barmoqni o’ngga suring, katta bo’lsa o’ng barmoqni chapga. Nechta qadamda topdingiz?

Nimani sezishingiz kerak

Sakkizta son uchun ko’pi bilan yetti qadam ketdi, har juftni ko’rganda esa 28 ta bo’lardi. Sabab: har qadamda bitta variant emas, butun bir guruh chetlab o’tildi.

Kompyuter yopiq. Bu mashq tugamaguncha kod ochilmaydi.

Nega ishlaydi

ikki ko'rsatkichtwo pointers

Ikkita indeks bilan ishlash usuli: ular ma’lum tartibda suriladi va hech qachon orqaga qaytmaydi. Shu sababli jami ish n ga proporsional bo’ladi.

Chap barmoqni o’ngga surganda siz shunchaki bitta juftlikdan voz kechmaysiz. Siz «chapdagi shu son bilan hech qanday juftlik bo’lmaydi» degan xulosaga kelasiz, chunki eng katta sherik ham yetmadi. Bir qadamda butun bir qator o’chadi.

▲Bu yerda xato qilishadi

Usul saralangan ro’yxatda ishlaydi. Tartib bo’lmasa «bu tomonda kattaroq» degan xulosa chiqarib bo’lmaydi va butun mantiq quriydi.

Sekin yechim

Yig’indisi X ga teng juftlik bormi? To’liq izlash har juftni ko’radi.

sekin.pyNusxalash

1a = [2, 3, 5, 5, 7, 8]2X = 103def qidir():4  for i in range(len(a)):5      for j in range(i + 1, len(a)):6          if a[i] + a[j] == X:7              return (a[i], a[j])8  return None9print(qidir())

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

Bashorat qilingNusxalash

1a = [2, 3, 5, 5, 7, 8]2X = 103def qidir():4  for i in range(len(a)):5      for j in range(i + 1, len(a)):6          if a[i] + a[j] == X:7              return (a[i], a[j])8  return None9print(qidir())

Sizning bashoratingizTekshirish

Javobni ko'rish

(2, 8)

Yechim to'g'ri, lekin u ro'yxat saralanganini umuman ishlatmaydi. Diqqat: break faqat ICHKI sikldan chiqadi — shu sababli bu yerda return ishlatilgan, aks holda tashqi sikl davom etib javobni qayta yozardi.

Nega sekin

Har juftlik ko’riladi: n²/2. Ro’yxat esa saralangan — ya’ni bizda ishlatilmayotgan qimmatli ma’lumot bor.

Sig‘adimi?

Bir soniyada taxminan 10⁸ oddiy amal bajariladi.

Yechim	n = 1 000	n = 5 000	n = 200 000
Har juftni ko‘rishn^2	10⁶sig‘adi	10⁷sig‘adi	10¹⁰sig‘maydi
Ikki ko‘rsatkichn	1 000sig‘adi	5 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.

Tez yechim

Ikki chetdan boshlaymiz. Yig’indi kichik bo’lsa kattaroq son kerak — chap siljiydi. Katta bo’lsa kichikroq son kerak — o’ng siljiydi.

tez.pyNusxalash

1a = [2, 3, 5, 5, 7, 8]2X = 103chap, ong = 0, len(a) - 14javob = None5while chap < ong:6  yigindi = a[chap] + a[ong]7  if yigindi == X:8      javob = (a[chap], a[ong])9      break10  if yigindi < X:11      chap += 112  else:13      ong -= 114print(javob)

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

Bashorat qilingNusxalash

1a = [2, 3, 5, 5, 7, 8]2X = 103chap, ong = 0, len(a) - 14javob = None5while chap < ong:6  yigindi = a[chap] + a[ong]7  if yigindi == X:8      javob = (a[chap], a[ong])9      break10  if yigindi < X:11      chap += 112  else:13      ong -= 114print(javob)

Sizning bashoratingizTekshirish

Javobni ko'rish

(2, 8)

Birinchi urinishdayoq topildi. Har qadamda ko'rsatkichlardan bittasi albatta siljiydi, shuning uchun sikl ko'pi bilan n marta aylanadi.

Ikkinchi shakl: sirpanuvchi oyna

Ko’rsatkichlar qarama-qarshi emas, bir yo’nalishda ham yurishi mumkin. Bunda ular oraliq — «oyna» — chegaralarini bildiradi.

oyna.pyNusxalash

1a = [2, 1, 5, 1, 3, 2]2X = 83chap = 04yigindi = 05eng = 06for ong in range(len(a)):7  yigindi += a[ong]8  while yigindi > X:9      yigindi -= a[chap]10      chap += 111  if ong - chap + 1 > eng:12      eng = ong - chap + 113print(eng)

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

Bashorat qilingNusxalash

1a = [2, 1, 5, 1, 3, 2]2X = 83chap = 04yigindi = 05eng = 06for ong in range(len(a)):7  yigindi += a[ong]8  while yigindi > X:9      yigindi -= a[chap]10      chap += 111  if ong - chap + 1 > eng:12      eng = ong - chap + 113print(eng)

Sizning bashoratingizTekshirish

Javobni ko'rish

3

Yig'indisi 8 dan oshmaydigan eng uzun ketma-ket oraliq — uchta element. while ichkarida bo'lsa ham, chap faqat oldinga yuradi: jami ish n ga proporsional.

◆Asosiy g'oya

Ichkarida while bo’lgani yechimni O(n²) qilmaydi. Muhimi — chap hech qachon orqaga qaytmaydi, demak u butun ishlash davomida ko’pi bilan n qadam yuradi.

Sinab ko’r

Vizualda ikki ko’rsatkich o’rtaga yaqinlashadi. Har qadamda qaysi biri va nega surilganiga e’tibor bering.

Ikki ko'rsatkich — ikki chetdan o'rtaga

Yig'indi maqsaddan kichikmi yoki kattami — shu savol qaysi ko'rsatkich siljishini hal qiladi.

Chap va o'ng ko'rsatkichlar yig'indiga qarab bir-biriga yaqinlashadi va javobni bir yurishda topadi.

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

1. Yig'indisi 22 bo'lgan ikki son kerak. Ro'yxat saralangan — shuning uchun ikki chetdan boshlaymiz.
2. 1 + 24 = 25, katta. Kichikroq qilish kerak — O'NG chapga siljiydi.
3. 1 + 19 = 20, kichik. Kattaroq qilish kerak — CHAP o'ngga siljiydi.
4. 4 + 19 = 23, katta. Kichikroq qilish kerak — O'NG chapga siljiydi.
5. 4 + 15 = 19, kichik. Kattaroq qilish kerak — CHAP o'ngga siljiydi.
6. 6 + 15 = 21, kichik. Kattaroq qilish kerak — CHAP o'ngga siljiydi.
7. 8 + 15 = 23, katta. Kichikroq qilish kerak — O'NG chapga siljiydi.
8. 8 + 11 = 19, kichik. Kattaroq qilish kerak — CHAP o'ngga siljiydi.
9. Har juftni ko'rsak 28 ta taqqoslash bo'lardi. Ikki ko'rsatkich 7 tada tugatdi — chunki har qadamda bitta ko'rsatkich faqat OLDINGA yuradi.

saralangan

chap10416283114155196o'ng247

yig'indi

maqsad22

Yig'indisi 22 bo'lgan ikki son kerak. Ro'yxat saralangan — shuning uchun ikki chetdan boshlaymiz.

Qadam0

OrqagaO‘ynatishOldinga1/9Qayta boshlash

Xatoni toping

▲Tuzoq — xatoni toping

10 / 40

MasalaSaralangan ro'yxatda yig'indisi X bo'lgan juftlik bormi?

Taklif qilingan yechim

1. 1chap = 0, ong = n - 1 deb boshlaymiz.
2. 2Yig‘indi X ga teng bo‘lsa — topildi.
3. 3Yig‘indi X dan kichik bo‘lsa, ikkala ko‘rsatkichni ham o‘rtaga suramiz.
4. 4chap va ong uchrashganda sikl tugaydi.

Bu javobning 3-qismi noto'g'ri. Bir vaqtda ikkalasini surish variantlarni ATAYLAB o'tkazib yuboradi. Yig'indi kichik bo'lsa faqat CHAP siljishi kerak: kattaroq son kerak, o'ngdagini kichraytirish esa yig'indini yanada kamaytiradi.

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

Javobni ko'rsatish

O’zingizni sinang

1Ikki ko'rsatkich usuli qanday shartni talab qiladi?

Javobni ko'rish

Tartibni. Saralangan ro’yxatda «bu tomonda kattaroq» degan xulosa chiqarish mumkin — usulning butun mantiqi shunga suyanadi.

2Yig'indi X dan katta bo'lsa qaysi ko'rsatkich siljiydi va nega?

Javobni ko'rish

O’ng — chapga. Bizga kichikroq yig’indi kerak, uni esa faqat kattaroq sonni kichraytirish orqali olish mumkin.

3Sirpanuvchi oynada ichki while bo'lsa ham yechim nega O(n)?

Javobni ko'rish

Chunki chap faqat oldinga yuradi va butun ishlash davomida ko’pi bilan n qadam qiladi. Ichki sikl umumiy hisobda n martadan ko’p aylanmaydi.

4Ro'yxat saralanmagan bo'lsa nima qilasiz?

Javobni ko'rish

Yo saralaysiz (n log n), yo boshqa usul olasiz — masalan lug’at (9-dars). Tanlov shartga bog’liq: element o’rni kerak bo’lsa saralash indekslarni buzadi.

5«Oyna» shakli qanday masalalarda uchraydi?

Javobni ko'rish

Ketma-ket oraliq haqidagi savollarda: eng uzun oraliq, yig’indisi chegaradan oshmaydigan oraliq, takrorlanmaydigan belgilar oynasi. Belgisi — javob ketma-ket elementlardan iborat bo’lishi.

Masalalar

Masalalar

3 ta

• Sum of Two ValuesCSES 1640o'rta

  Saralashdan oldin indekslarni saqlab qoling — javobda asl o‘rinlar so‘raladi.

• Subarray Sums ICSES 1660o'rta

  Barcha sonlar musbat — demak oyna usuli ishlaydi.

• PlaylistCSES 1141o'rta

  Oyna ichida takror bo‘lmasin. Takror chiqqanda chap chegarani qayerga surish kerak?

Lokal mashq: mashqlar/10-ikki-korsatkich/ — 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

Qog’ozga o’sish tartibida o’nta son yozing va yig’indisi 25 bo’lgan juftlikni ikki barmoq usuli bilan toping. Har qadamda qaysi barmoq nega surilganini yozib boring.

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

10-ikki-korsatkich masalasini yeching — u juftliklarni sanaydi, takrorlangan sonlar bilan. Bir xil sonlar guruhi uchrasa nima qilish kerakligini alohida o’ylang.

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

Oyna shaklini murakkabroq shartda yozing: takrorlanmaydigan elementlardan iborat eng uzun ketma-ket oraliqni toping. Ichkarida to’plam yoki lug’at kerak bo’ladi — qaysi biri va nega?

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

Darsni tugatdim