🔗 https://telegra.ph/Ot-masalasi---javobi-05-06
Masala: Shaxmat taxtasida ot va piyoda bor. Ot eng kam yurish bilan piyodani urishi kerak.
Ot eng kam necha qadamda piyodani uradi?
~ ~ ~ ~ ~ ~ ~ ~ ~
Masalani ko‘pchilik rekursiya yordamida yechib ko‘rsatishdi. Men esa 9 sinf bolasi qanday yechganini yozib bermoqchiman.
Massiv (array) yasab olamiz. taxta[8][8]
Ot turgan joyni 0 deb belgilaymiz. Endi massivning har bir katagidan yurib chiqamiz. Agar biror son ko‘rsak, shu sondan borish mumkin bo‘lgan joylarni +1 qilib belgilab chiqamiz.
Demak, agar ot 0-raqamda turgan bo‘lsa, undan borish mumkin bo‘lgan joylar 1 ga aylanadi.
Bitta o‘tishda butun taxtani to‘ldirib bo‘lmaydi. Shu sababli bajargan ishimizni bir necha marta takrorlaymiz. Necha marta takrorlash kerak? Aniq bilmaganim uchun o‘sha payt 10 marta takrorlaganman. keyinchalik esa maksimum qadamlar sonini aniqlab, 8 martaga tushirganman.
2-o‘tishda taxtamizda (massivda) 0, 1, va 2 sonlari paydo bo‘ladi. Shu zaylda davom etamiz va 3 lar va 4 lar hosil bo‘lishini kuzatamiz.
Endi, Ot turgan joydan boshlab, keyingi raqamga qarab yurishni boshlasak har doim ham manzilga yeta olmaymiz. Chunki 0->1->2 dan keyin 3 ga o‘ta olmasligimiz mumkin.
Mana shu yerda men o‘rgangan bitta zo‘r falsafa bor:
- Natija olish uchun har doim ham boshlang‘ich nuqtadan tugash nuqtasiga harakat qilinmaydi. Ba’zida shunday holatlar bo‘ladi, tugash nuqtasidan boshlanish nuqtasiga borish kerak.
Man hayron qolganman (shok bo‘lganman). Rostdan ham shunday ekan.
Agar ot turgan joydan biror keyingi songa o‘tsam va yana ixtiyoriy keyingi onga o‘tsam, men tugash nuqtasiga bora olmas ekanman.
Lekin, agar tugash nuqtasidan orqaga qaytishni boshlasam, ixtiyoriy kichik sonni tanlasam ham doim boshlang‘ich nuqtaga yetib kelar ekanman.
Shunday qilib, piyoda turgan joy 3 ga teng. U yerdan ixtiyoriy 2 ga o‘taman, keyin yana ixtiyoriy 1 ga va 0. Bu eng qisqa yo‘l bo‘ladi. Ishonmasangiz tekshirib ko‘ring. Va agar yo‘llar ko‘p bo‘lsa, shu usulda barchasini ko‘rib chiqa olasiz.
Ana shunaqa gaplar.
🏠 Endi esa, uyga vazifa.
1. Ot turgan katak (manzil) va piyoda turgan katak (manzili) beriladi. Siz borish mumkin bo‘lgan barcha eng qisqa yo‘llarni yozib bering.
2. Ot va piyodani shunday joylashtiring-ki. Ular orasidagi yo‘l eng uzun bo‘lsin. Eng uzun masofa necha qadamli?
07.05.2025 London
@DrAlgorithm