Muhammad al-xorazmiy nomidagi toshkent axborot texnologiyalari universiteti samarqand filiali

O`ZBEKISTON RESPUBLIKASI AXBOROT TEXNOLOGIYALARI VA KOMMUNIKATSIYALARINI RIVOJLANTIRISH VAZIRLIGI

MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI

SAMARQAND FILIALI

"Kompyuter injiniring" fakulteti

"Dasturiy injiniring" kafedrasi

"Algoritmlarni loyihalash" fanidan

Mavzu: Dinamik dasturlash asosida masalalar uchun dastur tuzish

Bajardi: Ro’zimurodov D

Qabul qildi:Axmedov F

1-Masala. Butun sonlardan iborat kvadrat matritsa (n × n) berilgan. Toshbaqa yuqori chap yacheykada va u pastki o'ng yacheykagaga tushishi kerak. Bir harakatda toshbaqa qo'shni o'ngga yoki qo'shni pastki qafasga harakatlanishi mumkin. Toshbaqaga maksimal miqdordagi yo'lni topish talab qilinadi.

Kiruvchi ma’lumotlar:

2	1	3	5
4	0	1	1
1	1	0	1
0	1	2	7

Variantlarni to’liq tekshirib chiqish bu - masalani yechishning universal usulidir. Qidiruvni amalga oshirish tamoyillari va uning potentsial imkoniyatlarini ko'rib chiqing. 4×4 o’lchamli bo’sh jadval berilgan. Har qanday yo'l pastga uchta harakatdan iborat. Boshqacha qilib aytganda, 6 ta qadam berilgan, ulardan uchtasi pastga tushish uchun, qolgan uchtasi o'ng tomonga o'tish uchun berilgan.

Oltitadan pastga qarab uchta harakatni tanlash usullari soni () toshbaqaga yo'llarining sonini aniqlaydi. Umumiy holda, .

Ushbu misol uchun, toshbaqa 20 xil usulga ega:

Yo'lning miqdorini (narxini) topishda beshta qo'shimcha operatsiya talab qilinadi, jami 100 ta operatsiya.

Keling, millionta operatsiyali masalani sekundiga million marta amal bajaradigan kompyuterda yechish uchun vaqtni hisoblaylik:

Jadval o’lchami	Yo’l uzunligi	Operatsiyalar soni	Jami operatsiyalar soni	Masalani yechish uchun ketgan vaqt
	6	20	100	0,00001 s
	14	3432	44616	0,045s
	60			200 000 yil

Bu barcha variantlarni ko’rib chiqqanda ketgan vaqt.
Dastur kodi:

#include

using namespace std;

int max(int a1, int b1)

{

if (a1>b1) return a1; else return b1;

}
int main()

{

setlocale(0,"");

int n=4;

const

int a[4][4]={

{ 2, 1, 3, 5 },

{ 4, 0, 1, 1 },

{ 1, 1, 0, 1 },

{ 0, 1, 2, 7 }

};
cout<<"Berilgan matritsa="<
for(int i=0; ifor(int j=0; j

cout<

cout<

int b[5][5];

for(int i=0; i

{

b[i][0]=0; b[0][i]=0;

}

for(int i=1; i

for(int j=1; j

b[i][j]=max(b[i-1][j], b[i][j-1])+a[i-1][j-1];

cout<

for(int i=0; i

for(int j=0; j

cout<

cout<

}
Natija:

2-Masala. Butun sonlardan iborat kvadrat matritsa (n × n) berilgan. Toshbaqa pastki chap yacheykada va u yuqori o'ng yacheykagaga tushishi kerak. Bir harakatda toshbaqa qo'shni o'ngga yoki qo'shni pastki qafasga harakatlanishi mumkin. Toshbaqaga maksimal miqdordagi yo'lni topish talab qilinadi.

Kiruvchi ma’lumotlar:

2	1	3	5
4	0	1	1
1	1	0	1
0	1	2	7

Dastur kodi:

#include

using namespace std;

int max(int a1, int b1)

{

if (a1>b1) return a1; else return b1;

}

int main()

{

setlocale(0,"");

int n=4;

const

int a[4][4]={

{ 2, 1, 3, 5 },

{ 4, 0, 1, 1 },

{ 1, 1, 0, 1 },

{ 0, 1, 2, 7 }

};

cout<<"Berilgan matritsa="<

for(int i=0; i

for(int j=0; j

cout<

cout<

int b[5][5];

for(int i=0; i

{

b[i][0]=0; b[n][i]=0;

}

for(int i=1; i

for(int j=1; j

b[i][j]=max(b[i-1][n+1], b[i][n-1])+a[i-1][j-1];

cout<

for(int i=0; i

for(int j=0; j

cout<

cout<

}

Natija:

Xulosa

Mavzu bilan to’liq tanishib chiqdim. Dinamik dasturlash va uni dasturlashdagi ahamiyati haqida bilim va ko’nikmalarga ega bo’ldim.