25-dars: DP — memoizatsiya

4-darajaPlatina — dinamik programmalash25–32 darslar

HayotdaUy vazifasi

Sinfdoshingiz sizdan bitta masalaning javobini so’radi, siz aytdingiz. Besh daqiqadan keyin yana o’sha masalani so’radi. Keyin yana. Uchinchi safar «yozib ol-da» deysiz — va bu gap dinamik programmalashning butun mazmuni.

Bu darsdan keyin siz

• takroriy hisoblashni ko’rasiz va uni raqam bilan o’lchaysiz
• rekursiv yechimga memoizatsiya qo’shasiz — bitta lug’at bilan
• DP nima ekanini formuladan emas, ish jarayonidan tushunasiz

Avval qo’lda

Avval qo‘lda

~7 daqiqa·juftlikda·Katta qog'oz va qalam

f(5) = f(4) + f(3) + f(2) qoidasini oling, f(0) = 1 va manfiy argument uchun f = 0.

Endi f(5) ni daraxt qilib chizing: har tugundan uchta shox chiqsin. Chizib bo’lgach, f(2) yozilgan tugunlarni sanang. f(1) ni ham sanang.

Nimani sezishingiz kerak

Bitta f(2) bir necha marta chizildi, f(1) esa undan ham ko’p. Ularning javobi har safar bir xil. Savol o’z-o’zidan chiqadi: nega qayta hisoblaymiz?

Kompyuter yopiq. Bu mashq tugamaguncha kod ochilmaydi.

Takroriy chaqiruvlar

Masala: zinapoyada n pog’ona bor, bir qadamda 1, 2 yoki 3 pog’ona ko’tarilish mumkin. Nechta usul bor?

Rekursiv yechim to’g’ridan-to’g’ri shartdan chiqadi: oxirgi qadam 1, 2 yoki 3 pog’ona bo’lgan.

sekin.pyNusxalash

1def f(n):2  if n < 0:3      return 04  if n == 0:5      return 16  return f(n - 1) + f(n - 2) + f(n - 3)7print(f(4), f(10))

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

Bashorat qilingNusxalash

1def f(n):2  if n < 0:3      return 04  if n == 0:5      return 16  return f(n - 1) + f(n - 2) + f(n - 3)7print(f(4), f(10))

Sizning bashoratingizTekshirish

Javobni ko'rish

7 274

Yechim to'g'ri va u shartning so'zma-so'z tarjimasi. Hech qanday hiyla yo'q — shuning uchun uni yozish oson va unda xato qilish qiyin.

Nega sekin

Endi chaqiruvlarni sanaymiz. Bu darsning eng muhim raqami.

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

Bashorat qilingNusxalash

1sanoq = [0]2def f(n):3  sanoq[0] += 14  if n < 0:5      return 06  if n == 0:7      return 18  return f(n - 1) + f(n - 2) + f(n - 3)9f(20)10print(sanoq[0])

Sizning bashoratingizTekshirish

Javobni ko'rish

433993

Yigirma pog'onali zinapoya uchun deyarli yarim million chaqiruv. n = 40 da bu son taxminan 100 milliardga chiqadi va yechim umuman tugamaydi.

Sig‘adimi?

Bir soniyada taxminan 10⁸ oddiy amal bajariladi.

Yechim	n = 20	n = 40	n = 60
Naif rekursiya2^n	10⁶sig‘adi	10¹²sig‘maydi	10¹⁸sig‘maydi
Memoizatsiyan	20sig‘adi	40sig‘adi	60sig‘adi

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

Sabab bitta: bir xil argument qayta-qayta hisoblanadi. f(20) hisoblanayotganda f(0) 44 marta chaqiriladi va har safar bir xil javob qaytaradi.

Tez yechim

Hech narsa o’zgarmaydi — algoritm ham, formula ham, tartib ham. Faqat bitta lug’at qo’shiladi.

tez.pyNusxalash

1xotira = {}2def f(n):3  if n < 0:4      return 05  if n == 0:6      return 17  if n in xotira:8      return xotira[n]9  xotira[n] = f(n - 1) + f(n - 2) + f(n - 3)10  return xotira[n]11print(f(4), f(10))

memoizatsiyamemoization

Funksiya javobini birinchi hisoblashda saqlab qo’yish va keyingi chaqiruvlarda qaytadan hisoblamaslik.

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

Bashorat qilingNusxalash

1from functools import lru_cache2sanoq = [0]3@lru_cache(maxsize=None)4def f(n):5  sanoq[0] += 16  if n < 0:7      return 08  if n == 0:9      return 110  return f(n - 1) + f(n - 2) + f(n - 3)11f(20)12print(sanoq[0])

Sizning bashoratingizTekshirish

Javobni ko'rish

23

433 993 o'rniga 23 ta chaqiruv. lru_cache — Python'ning tayyor memoizatsiyasi: u qo'lda yozilgan lug'at bilan aynan bir xil ish qiladi.

◆Asosiy g'oya

DP nima ekanini shu yerda aytish mumkin: takroriy qism masalalarni bir marta yechib, javobini saqlab qo’yish. Jadval, formula va «holat» degan so’zlar keyin keladi — ular shu bitta g’oyaning turli ko’rinishlari.

Ikki shart

Memoizatsiya har rekursiyaga yordam bermaydi. Ikkita shart kerak.

Birinchisi — takroriy qism masalalar: bir xil argument bir necha marta uchrashi kerak. Ikkinchisi — optimal qism tuzilma: katta masalaning javobi kichiklarining javobidan yig’ilishi kerak.

Ikkalasi bo’lmasa memoizatsiya faqat xotira sarflaydi va hech narsa tejamaydi.

Sinab ko’r

Vizualda f(7) uchun har argument necha marta hisoblanganini ko’rasiz. Kichik argumentlarga alohida e’tibor bering — eng ko’p azob chekadigan aynan ular.

Memoizatsiya — takroriy chaqiruvlar

Ikki qatorni solishtiring: naif yechim bir xil ishni necha marta qaytaradi.

Naif rekursiyada bir xil argument o'nlab marta qayta hisoblanadi; memoizatsiya har birini bir marta hisoblaydi.

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

1. f(7) ni hisoblaymiz: f(k) = f(k-1) + f(k-2) + f(k-3). Javob 44. Savol boshqa: har argument NECHA MARTA hisoblandi?
2. f(7) naif yechimda 1 marta hisoblandi, memo bilan esa 1 marta. Katta argumentlar kam takrorlanadi.
3. f(6) naif yechimda 1 marta hisoblandi, memo bilan esa 1 marta. Katta argumentlar kam takrorlanadi.
4. f(5) naif yechimda 2 marta hisoblandi, memo bilan esa 1 marta. Katta argumentlar kam takrorlanadi.
5. f(4) naif yechimda 4 marta hisoblandi, memo bilan esa 1 marta. Katta argumentlar kam takrorlanadi.
6. f(3) naif yechimda 7 marta hisoblandi, memo bilan esa 1 marta. Katta argumentlar kam takrorlanadi.
7. f(2) naif yechimda 13 marta hisoblandi, memo bilan esa 1 marta. Kichik argumentlar eng ko'p azob chekadi — ular har shoxda qayta-qayta kerak bo'ladi.
8. f(1) naif yechimda 24 marta hisoblandi, memo bilan esa 1 marta. Kichik argumentlar eng ko'p azob chekadi — ular har shoxda qayta-qayta kerak bo'ladi.
9. f(0) naif yechimda 44 marta hisoblandi, memo bilan esa 1 marta. Kichik argumentlar eng ko'p azob chekadi — ular har shoxda qayta-qayta kerak bo'ladi.
10. Jami 96 ta chaqiruv o'rniga 8 tasi yetardi. DP shu yerdan tug'iladi: formula emas, «hisoblanganini saqlab qo'yaylik» degan savoldan.

argument

0011223344556677

naif

memo

f(7) ni hisoblaymiz: f(k) = f(k-1) + f(k-2) + f(k-3). Javob 44. Savol boshqa: har argument NECHA MARTA hisoblandi?

Naif chaqiruv0

OrqagaO‘ynatishOldinga1/10Qayta boshlash

Xatoni toping

▲Tuzoq — xatoni toping

25 / 40

MasalaRekursiv yechimga memoizatsiya qo'shing.

Taklif qilingan yechim

1. 1Bo‘sh xotira lug‘ati ochamiz.
2. 2Funksiya boshida bazaviy holatlarni tekshiramiz.
3. 3Javobni hisoblaymiz va xotiraga yozamiz.
4. 4Xotirada bor bo‘lsa saqlangan javobni qaytaramiz.

Bu javobning 4-qismi noto'g'ri. Tartib teskari. Xotira tekshiruvi HISOBLASHDAN OLDIN turishi kerak, aks holda javob avval qaytadan hisoblanadi, keyingina xotiradan qaraladi — ya'ni memoizatsiya hech narsa tejamaydi. Kod to'g'ri javob beradi, tezligi esa naif yechimniki bo'lib qoladi.

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

Javobni ko'rsatish

O’zingizni sinang

1Memoizatsiya nima qiladi?

Javobni ko'rish

Funksiya javobini birinchi hisoblashda saqlab qo’yadi va keyingi chaqiruvlarda qayta hisoblamaydi.

2Memoizatsiya ishlashi uchun qanday ikki shart kerak?

Javobni ko'rish

Takroriy qism masalalar (bir xil argument bir necha marta uchrashi) va optimal qism tuzilma (katta javob kichiklaridan yig’ilishi).

3Xotira tekshiruvi funksiyaning qayerida turishi kerak?

Javobni ko'rish

Bazaviy holatlardan keyin, lekin hisoblashdan oldin. Keyin qo’yilsa memoizatsiya hech narsa tejamaydi.

4f(20) naif yechimda nechta chaqiruv qildi?

Javobni ko'rish

433 993 ta. Memoizatsiya bilan esa 23 ta — argumentlar soniga teng.

5Memoizatsiyalangan rekursiyaning qanday cheklovi qoladi?

Javobni ko'rish

Rekursiya chuqurligi. n katta bo’lganda RecursionError chiqadi, shuning uchun keyingi qadam — jadval ko’rinishiga o’tish (26-dars).

Masalalar

Masalalar

3 ta

• Dice CombinationsCSES 1633oson

  Darsdagi masala, olti xil qadam bilan va n ≤ 10⁶. Rekursiya bu chegarada yiqiladi.

• Minimizing CoinsCSES 1634o'rta

  Avval rekursiv yozing, keyin memoizatsiya qo‘shing. «Yechib bo‘lmaydi» holatini alohida ishlang.

• Coin Combinations ICSES 1635o'rta

  Tartib muhimmi yoki yo‘qmi — shartni diqqat bilan o‘qing. Javob shunga bog‘liq.

Lokal mashq: mashqlar/25-zinapoya/ — 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

f(5) chaqiruv daraxtini qog’ozda to’liq chizing va har argument necha marta uchraganini sanang. Keyin xuddi shu daraxtni memoizatsiya bilan chizing — nechta tugun qoldi?

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

25-zinapoya masalasini yeching. Ikkala yechimga ham chaqiruv hisoblagichi qo’shing va n = 22 uchun ikki raqamni yozib qo’ying.

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

Memoizatsiyani n = 100000 da sinang. Qanday xato chiqdi? Keyin xuddi shu masalani rekursiyasiz, oddiy sikl bilan yozing — bu 26-darsning mavzusi, lekin uni o’zingiz topishga urinib ko’ring.

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

Darsni tugatdim