Assalomu alaykum, yordam.uz saytimizga xush kelibsiz.
Bu saytda o`zingizni qiziqtirgan savollarga javob olishingiz va o`z sohangiz bo`yicha savollarga javob berishingiz mumkin. Bizning Oilamizga a'zo bo`lganingiz uchun chuqur Minnatdorchilik bildiramiz !!!

Shaxmatda ot yurishi

+7 ovoz
661 marta ko‘rilgan
so‘radi 29 yanvar, 17 Bilmasvoy (904 bal)
tahrirlandi 29 yanvar, 17 Bilmasvoy

Assalomu alaykum, 

Shaxmatga va programmalashga qiziqadigan akalar uchun savol bor edi:

Shaxmat taxtasida biror joyiga OT qo`yilgan (xot; yot). Menga shu ot turgan joydan, boshqa bir katakka (x,y) eng kam necha qadamda borish mumkin ekanligini aniqlash kerak.

Men nima qilib ko`rdim. Rekursiya bilan keyingi kataklarni qidirishni boshladim. Lekin agar ot bilan katak juda uzoqda joylashgan bo`lsa, juda ko`p vaqt ketmoqda.

Nima qilsam tezroq yechim topsam bo`ladi? Fikrlar bormi?

X5
3
2     4
1
ot

izoh qoldirdi 01 fevral, 17 ulugbekrozimboyev (1 ball)
iloji bo'lsa yozgan kodingini tashang.

2 Javoblar

+3 ovoz
javob berdi 01 fevral, 17 Baxtiyorbek (156 bal)
tahrirlandi 08 mart, 17 Baxtiyorbek
 
Eng yaxshi javob
Bu tipdagi masalalar dinamik dasturlashga taaluqli bo'lib, rekursiya yo'li bilan yechilmaydi. Buning uchun ot turgan katakka nol yozasiz. Chunki, bu katakka kelish uchun yurish shart emas. Bu katakdan turib yurish mumkin bo'lgan kataklarga 1 qo'yasiz (nega 1 qo'yilishi menimcha tushunarli). Shu tarzda matritsani to'ldirib borasiz. Natijada aytilgan katakdan nechta yurishda borish mumkinligini olasiz.
izoh qoldirdi 03 fevral, 17 Bilmasvoy (904 bal)
Rahmat kattakon, rostanam, rekirsiya shart emas ekan. 8-10 ta qadamda chiqar ekan. Massivni -1 lar bilan to`ldirdim. Ot turgan joydan (0), borishi mumkin joylarga 1 qo`yib chiqdim. keyin 1 lar borishi mumkin bo`lgan joyga 2 qo`yib chiqdim va hokazo. Shunda eng uzun yo`l 8 talik bo`lib chiqdi. keyin, Natijadagi turgan joydan, (masalan 8) ot bilan borish mumkin bo`lgan bitta kichik sonni qidirdim, keyin yana bitta kichik, toki 0 ga yetib bormagunimcha. Menga bitta yo`l bo`lsa yetarli edi. Ishladi. Katta rahmat !!!
+2 ovoz
javob berdi 01 fevral, 17 muminoff (63 bal)
tahrirlandi 01 fevral, 17 muminoff

Shaxmatdagi bunday muammolar (boshqotirmalar) ni yechishda siz sinab ko'rgan yo'l Brute-force search algoritmi deb ataladi. Bu algoritm kichkina (5x5) dosklarda samara beradi, lekin nisbatan katta yoki cheksiz doskalarda maksimal tezlikda yechim topish imkonsiz.

Bunday muammoga grafik algoritmlarni har qaysisini ishlatib yechim topsa bo'ladi. Biz Deykstra algoritmini[1] ishlatib yechim topgan edik, albatta cheklangan shaxmat taxtasi uchun. Siz boshqa algoritmlar[2][3] bilan amalga oshirib ko'rsangiz ham bo'ladi.

[1] https://en.wikipedia.org/wiki/Dijkstra's_algorithm

[2] https://en.wikipedia.org/wiki/Knight's_tour

[3] https://en.wikipedia.org/wiki/Breadth-first_search

Tahrir: grammatik xatolar tuzatildi.

Assalomu alaykum, yordam.uz saytimizga xush kelibsiz.

Bu saytda o`zingizni qiziqtirgan savollarga javob olishingiz va o`z sohangiz bo`yicha savollarga javob berishingiz mumkin.

Bizning Oilamizga a'zo bo`lganingiz uchun chuqur Minnatdorchilik bildiramiz !!!

Telegram kanal YordamUzRss

...