3-dars: Modellashtirish

1-darajaBronza — algoritmik fikrlash1–8 darslar

HayotdaOmbor

Omborda yuk tashuvchi robot ishlaydi. Unga «o’ngga, o’ngga, pastga» deyiladi va u shunday yuradi — devorga tiralsa esa xato bermaydi, shunchaki joyida qoladi. Operator ertalab bitta savolga javob izlaydi: robot tunda nechta xonani aylanib chiqdi?

Bu darsdan keyin siz

• uzun shartni qadamlarga ajratib, har qadamni alohida kodga o’girasiz
• chekka va to’siq holatlarini shartda yozilganidek bajarasiz
• «avval bo’lganmidim?» savoliga javob berish usulini tanlaysiz

Avval qo’lda

Avval qo‘lda

~5 daqiqa·juftlikda·Katakli qog'oz va tanga

Katakli qog’ozga 3 × 4 panjara chizing. Ikkita katakni qora bo’yang — bular devor. Tangani chap yuqori katakka qo’ying.

Sinfdoshingiz DDRRU kabi 6–8 harfli buyruq satrini o’qib bersin, siz tangani suring. Devorga yoki chekkaga urilsangiz tanga qimirlamaydi, lekin buyruq sarflanadi. Oxirida tanga nechta har xil katakda bo’lganini sanang.

Nimani sezishingiz kerak

Ikki narsani sezgan bo’lasiz. Birinchisi: «qimirlamaydi» degan qoidani unutish oson. Ikkinchisi: «nechta har xil katak» degan savolga javob berish uchun qayerda bo’lganingizni eslab turish kerak edi.

Kompyuter yopiq. Bu mashq tugamaguncha kod ochilmaydi.

Modellashtirish nima

modellashtirishsimulation

Shartda tasvirlangan jarayonni kodda qadamma-qadam takrorlash. Yashirin formula ham, hiyla ham izlanmaydi.

Bunday masalalarning qiyinligi algoritmda emas. Shart uzun bo’ladi va ichida bir nechta alohida qoida yashiringan: chekka nima bo’ladi, to’siqda nima bo’ladi, boshlang’ich holat hisobga olinadimi.

◆Asosiy g'oya

Modellashtirish masalasida xatoning to’qson foizi kodda emas, shartni o’qishda bo’ladi. Shuning uchun kod yozishdan oldin har qoidani daftarga alohida qator qilib ko’chirib oling.

Sekin yechim

Robot yurgan kataklarni ro’yxatga yig’amiz va har safar «bu katak ro’yxatda bormi?» deb tekshiramiz.

sekin.pyNusxalash

1panjara = ["S..#", ".##.", "...."]2yonalish = {"U": (-1, 0), "D": (1, 0), "L": (0, -1), "R": (0, 1)}3y, x = 0, 04korilgan = [(y, x)]5for b in "DDRRU":6  dy, dx = yonalish[b]7  ny, nx = y + dy, x + dx8  if 0 <= ny < 3 and 0 <= nx < 4 and panjara[ny][nx] != "#":9      y, x = ny, nx10      if (y, x) not in korilgan:11          korilgan.append((y, x))12print(len(korilgan))

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

Bashorat qilingNusxalash

1panjara = ["S..#", ".##.", "...."]2yonalish = {"U": (-1, 0), "D": (1, 0), "L": (0, -1), "R": (0, 1)}3y, x = 0, 04korilgan = [(y, x)]5for b in "DDRRU":6  dy, dx = yonalish[b]7  ny, nx = y + dy, x + dx8  if 0 <= ny < 3 and 0 <= nx < 4 and panjara[ny][nx] != "#":9      y, x = ny, nx10      if (y, x) not in korilgan:11          korilgan.append((y, x))12print(len(korilgan))

Sizning bashoratingizTekshirish

Javobni ko'rish

5

Robot pastga ikki marta tushdi, o'ngga ikki marta yurdi, so'ng yuqoriga urindi — u yerda devor bor, shuning uchun joyida qoldi. Boshlang'ich katak bilan birga beshta katak.

Nega sekin

(y, x) not in korilgan qatori ro’yxatni boshidan oxirigacha ko’rib chiqadi. Ro’yxat uzayib borgani sari har tekshiruv qimmatlashadi: oxirgi qadamlarda deyarli butun tarix qayta o’qiladi.

Sig‘adimi?

Bir soniyada taxminan 10⁸ oddiy amal bajariladi.

Yechim	n = 1 000	n = 200 000
Ro‘yxatda qidirishn^2	10⁶sig‘adi	10¹⁰sig‘maydi
To‘plamda qidirishn	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.

Buyruqlar soni 200000 gacha bo’lishi mumkin. Ro’yxat bilan yozilgan yechim shu testda tugamaydi, garchi u mutlaqo to’g’ri bo’lsa ham.

Tez yechim

Bitta so’z o’zgaradi: ro’yxat o’rniga to’plam. To’plam elementni saqlaganda uning o’rnini oldindan hisoblab qo’yadi, shuning uchun «bormi?» savoliga qidirmasdan javob beradi.

tez.pyNusxalash

1panjara = ["S..#", ".##.", "...."]2yonalish = {"U": (-1, 0), "D": (1, 0), "L": (0, -1), "R": (0, 1)}3y, x = 0, 04korilgan = {(y, x)}5for b in "DDRRU":6  dy, dx = yonalish[b]7  ny, nx = y + dy, x + dx8  if 0 <= ny < 3 and 0 <= nx < 4 and panjara[ny][nx] != "#":9      y, x = ny, nx10      korilgan.add((y, x))11print(len(korilgan))

Endi if ham kerak emas: to’plam takrorni o’zi qabul qilmaydi. Kod qisqardi va tezlashdi — bunday holat kam uchraydi, shuning uchun eslab qoling.

Sinab ko’r

Vizualda robot buyruqlarni birma-bir bajaradi. Devorga tiralgan qadamlarga alohida e’tibor bering: buyruq sarflanadi, robot esa qimirlamaydi.

Robot panjarada — aytilganini bajaradi

Har buyruqni bosib o'tkazing: devor va chekka qanday ishlashini kuzating.

Robot to'qqizta buyruqni ketma-ket bajaradi. Devor yoki chekka uchrasa buyruq shunchaki bajarilmaydi.

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

1. Robot chap yuqori burchakda. # — devor, robot u yerga o'ta olmaydi.
2. o'ngga — robot bir katak siljidi.
3. o'ngga — robot bir katak siljidi.
4. pastga — robot bir katak siljidi.
5. o'ngga — robot bir katak siljidi.
6. o'ngga — robot bir katak siljidi.
7. o'ngga — robot bir katak siljidi.
8. yuqoriga — robot bir katak siljidi.
9. o'ngga — panjaradan chiqib ketardi, buyruq bajarilmadi.
10. o'ngga — panjaradan chiqib ketardi, buyruq bajarilmadi.
11. Buyruqlar tugadi. Robot (5, 0) katagida. Kod aynan shu — aytilganini bajarish.

R··#··

······

·###··

······

buyruqlar

oopoooyoo

Robot chap yuqori burchakda. # — devor, robot u yerga o'ta olmaydi.

Buyruq0

OrqagaO‘ynatishOldinga1/11Qayta boshlash

Xatoni toping

▲Tuzoq — xatoni toping

3 / 40

MasalaRobot bosib o'tgan har xil kataklar sonini toping.

Taklif qilingan yechim

1. 1korilgan — bo‘sh to‘plam bilan boshlanadi.
2. 2Har buyruqda yangi katak hisoblanadi; devor yoki chekka bo‘lsa robot joyida qoladi.
3. 3Robot ko‘chgan bo‘lsa, yangi katak to‘plamga qo‘shiladi.
4. 4Javob — to‘plam o‘lchami.

Bu javobning 1-qismi noto'g'ri. Boshlang'ich katak hech qachon to'plamga tushmaydi, chunki u hech qanday ko'chishning natijasi emas. Javob har doim bittaga kam chiqadi, robot umuman qimirlamasa esa 0 bo'ladi. To'g'risi: korilgan to'plami boshlang'ich katak bilan boshlanadi.

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

Javobni ko'rsatish

O’zingizni sinang

1Robot devorga urilganda buyruq nima bo'ladi?

Javobni ko'rish

Bajarilgan hisoblanadi va yo’qoladi. Robot joyida qoladi, lekin buyruq qaytadan urinilmaydi. Bu qoida shartda yozilgan — o’zimizdan o’ylab topilmaydi.

2Nega U yo'nalishi uchun (-1, 0) yozilgan?

Javobni ko'rish

Panjarada qatorlar yuqoridan pastga sanaladi, ya’ni yuqoriga chiqish qator raqamini kamaytiradi. Ustun o’zgarmaydi, shuning uchun ikkinchi son nol.

3Ro'yxat o'rniga to'plam ishlatilganda javob o'zgaradimi?

Javobni ko'rish

O’zgarmaydi. Ikkala yechim ham bir xil kataklarni yig’adi, farqi faqat «bu katak bormi?» savoliga qancha vaqtda javob berishida.

40 <= nx < 4 tekshiruvini olib tashlasak nima bo'ladi?

Javobni ko'rish

Python manfiy indeksni oxiridan sanaydi, shuning uchun robot chap chekkadan chiqib ketib panjaraning o’ng chekkasida paydo bo’ladi. Kod ishlaydi, javob esa noto’g’ri — eng yomon turdagi xato.

5Shartni o'qiyotganda birinchi navbatda nimani yozib olish kerak?

Javobni ko'rish

Chegara va istisno qoidalarini: panjara o’lchami, buyruqlar soni, devorda nima bo’ladi, chekkada nima bo’ladi, boshlang’ich holat sanaladimi. Algoritm keyin keladi.

Masalalar

Masalalar

3 ta

• Queue at the SchoolCodeforces 266Boson

  Har soniyani alohida modellashtiring. Almashishlar bir vaqtda bo‘lishiga e‘tibor bering.

• Night at the MuseumCodeforces 731Aoson

  G‘ildirak aylanma: ikki yo‘nalishdan qisqasini tanlang.

• RepetitionsCSES 1069oson

  Bir marta yurish yetadi: joriy seriya uzunligi va eng uzun seriya.

Lokal mashq: mashqlar/03-robot/ — 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

Katakli qog’ozda 4 × 4 panjara chizing, uchta devor qo’ying va 10 harfli buyruq satri o’ylab toping. Robot yo’lini qo’lda chizib chiqing va nechta har xil katakda bo’lganini yozing.

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

03-robot masalasini yeching. Kod yozishdan oldin shartdagi har qoidani daftaringizga alohida qator qilib ko’chiring — keyin har qoidaning kodda qayerda bajarilganini ko’rsating.

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

Yechimingizni sindiradigan uchta kirish o’ylab toping: 1 × 1 panjara, robot atrofi butunlay devor, va barcha buyruqlar bir yo’nalishda. Har biriga javobni oldindan yozing, keyin yurgizib tekshiring.

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

Darsni tugatdim