5 laboratoriya ishi mavzu: Dinamik dasturlash masalasini yechish Ishning maqsadi


Download 90.01 Kb.
bet2/7
Sana30.05.2020
Hajmi90.01 Kb.
#112130
1   2   3   4   5   6   7
Bog'liq
Laboratoriya ishi №5

Dastur kodi


#include

#include

#include

const int nm=5;

int a[nm][nm];

int n;


void makebase(int ik, int jk)

{

int i,j;



for (i=0;i=0) a[i][jk]=-1;

for (j=0;j=0) a[ik][j]=-1;

a[ik][jk]=-2;

if (a[jk][ik]>=0) a[jk][ik]=-1;

}

void main()



{

int i,j,c,i2,j2,i3,j3;

int cnt;

int minv, miniv, minjv, maxv;

int flag;

ifstream f("mx.txt");

f >> n;

for (i=0;i> a[i][j];



f.close();

for (i=0;i

for (c=0;c

{

// looking for one-in-row or one-in-col element



flag=0;

for (i=0;(i

{

cnt=0;


for (j=0;j=0)

{

i2=i;



j2=j;

cnt++;


}

if (cnt==1) flag=1;

}

for (j=0;(j

{

cnt=0;


for (i=0;i=0)

{

i2=i;



j2=j;

cnt++;


}

if (cnt==1) flag=1;

}

if (flag==1)



{

makebase(i2,j2);

continue;

}

// minus mins



for (i=0;i

{

minv=30000;



for (j=0;j

if ((a[i][j]>=0)&&(a[i][j]

for (j=0;j=0) a[i][j]-=minv;

}

for (j=0;j

{

minv=30000;

for (i=0;i

if ((a[i][j]>=0)&&(a[i][j]

for (i=0;i=0) a[i][j]-=minv;

}

// checking nulls and looking for base values



maxv=-1;

for (i=0;i

{

miniv=30000;



minjv=30000;

for (i2=0;i2=0)&&(i2!=i)&&(a[i2][j]

for (j2=0;j2=0)&&(j2!=j)&&(a[i][j2]

if (miniv+minjv>maxv)

{

maxv=miniv+minjv;



i3=i;

j3=j;


}

}

makebase(i3,j3);



}

// output

clrscr();

i2=0;


cout << i2+1;

for (c=0;c

{

for (j=0;j

{

cout << "->" << j+1;

i2=j;

break;


}

}

getch();



}

Dasturni ishga tushirishdan oldin, siz shaharlarning soni va harakatlanuvchi matritsani o'z ichiga olgan matn faylini yaratishingiz kerak, masalan:



Dasturni ishga tushirgandan so'ng, u tarmoqlar va chegaralar usulini amalga oshiradi va eng qisqa yo'lni ko'rsatadi



Har qanday tugmachani bosgandan so'ng, dastur o'z ishini tugatadi.



TOPSHIRIQ:

Topshiriq variantlari. Kommivoyajer masalasini yechishning algoritmi va dasturini tuzing. Quyidagi ma’lumotlar asosida dasturni bajaring va hisobot yozing. Variant raqami talabaning jurnaldagi tartib raqamiga mos bo’lishi kerak.


1)



6

9

2

4




6



2

6

2




6

3



3

3




5

7

3



6




3

2

2

5





2)



9

12

7

10




9



7

2

4




2

4



3

5




8

7

1



5




3

4

3

5



Download 90.01 Kb.

Do'stlaringiz bilan baham:
1   2   3   4   5   6   7




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling