Topish talab qilinadi

O`ZBEKISTON RESPUBLIKASI AXBOROT TEXNOLOGIYALARI VA KOMMUNIKATSIYALARINI RIVOJLANTIRISH VAZIRLIGI

MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI SAMARQAND FILIALI



"Kompyuter injiniring" fakulteti "Sonli usullar va chiziqli dasturlash” fanidan
Bajardi: Soliyev S
Qabul qildi: Bobanazarov A

2-masala. Sizga butun kvadrat matritsa (n×n) berilgan. Toshbaqa yuqori chap katakda va pastki o'ng katakga yurish kerak. Bir harakatda toshbaqa qo'shni o'ng

yoki qo'shni pastki katakchaga yurishi mumkin. toshbaqaning yo'lini topish talab qilinadi.
Maksimal yig'indi bilan

Kirish maʼlumotlari:
	2	1	3	5
	4	0	1	1
	1	1	0	1
	0	1	2	7

siljish uchun, qolgan uchtasi o'ngga o'tish uchun teriladi.

6
Oltitadan uchta harakatni tanlash usullari soni (С³) toshbaqa yo'llari sonini

𝑛+𝑚−2
aniqlaydi. Umuman olganda, С^𝑛−1 ..

Ushbu misol uchun toshbaqaning 20 ta yo'li bor:

_{С3 =} 6!

= 20

⁶ 3! ∙ 3!
Yo'lning yig'indisini (xarajatini) topishda, jami 100 ta operatsiya uchun beshta qo'shish operatsiyasi talab qilinadi.
Yechimning vaqt murakkabligi 0(n×m) ga teng. Har bir massiv B maksimal ikkita amalni (taqqoslash va qo'shish) talab qiladi.
300x300 massiv uchun operatsiyalarning umumiy soni 1000000 dan kam, ya'ni. million tezlikda ishlaydigan kompyuter vazifani bir soniyadan kamroq vaqt ichida bajarishi mumkin.