Muhammad al-xorazmiy nomidagi toshkent axborot texnologiyalari universiteti dasturiy injiniring kafedrasi

Танланган тугунлар тўплами	(u,v) қирра	V/U танланмаган тугунлар тўплами
Изоҳ
	{ }		{A,B,C,D,E,F,G}	Бошланғич граф
	{D}	(D,A)=5 V (D,B) = 9 (D,E)= 15 (D,F) = 6	{A,B,C,E,F,G}	D тугундан бошлаймиз A, B, E и F лар D билан боқланган. A тугун — D га энг яқин бўлганлиги учун шу тугун олинади.
	{A,D}	(D,B) = 9 (D,E)= 15 (D,F) = 6  (A,B) = 7 V	{B,C,E,F,G}	D ёки A га энг яқин бўлган тугунни топамиз.  B - D  9,  A —D 7. E гача масофа 15, F —гача 6. F энг яқин тугун.
	{A,B,D,F}	(B,C) = 8 (B,E)=7 V  (D,B) = 9 цикл (D,E)= 15 (F,E) = 8 (F,G)= 11	{C,E,G}
	{A,B,D,E,F}	(B,C) = 8 (D,B) = 9 цикл (D,E) = 15 цикл (E,C) = 5 V (E,G) = 9 (F,E) = 8 цикл (F,G) = 11	{C,G}
	{A,B,C,D,E,F}	(B,C) = 8 цикл (D,B) = 9 цикл (D,E) = 15 цикл (E,G) = 9 V (F,E) = 8 цикл (F,G) = 11	{G}
	{A,B,C,D,E,F,G}	(B,C) = 8 цикл (D,B) = 9 цикл (D,E) = 15 цикл (F,E) = 8 цикл (F,G) = 11 цикл	{ }	Минимал нархли дарахтлар склети қурилди. Бунда оғирлиги 39 бўлди.

Masalaning dasturi:

#include

using namespace std;

int main()

{int a,b,u,v,n,i,j,ne=1;

int mas[10]={0}, min, mincost=0,cost[10][10];

int path[100]={0}; //ushbu massivda yulni tashkil qiladigan tugunlar yoziladi

int path_index=0;

cout<<"Tugunlar sonini kiriting "; cin>>n;

cout<<"Qushnilik matritsasini kiriting\n";

for(i=0;i

for(j=0;j

{cin>>cost[i][j];

if(cost[i][j]==0)

cost[i][j]=999;

}mas[0]=1;

cout<<"\n";

while(ne < n)

{for(i=0, min=999; i

for(j=0;j

if(cost[i][j]< min)

if(mas[i]!=0)

{min=cost[i][j];

a=u=i;

b=v=j;}

if(mas[u]==0 || mas[v]==0)

{path[path_index]=b;

path_index++;

ne++;

mincost+=min;

mas[b]=1;}

cost[a][b]=cost[b][a]=999; }

cout<<"\n";

cout<<1<<" --> ";

for (int i=0;i

{ cout<

if (i "; }

cout<<"\n Minimal narx "<

return 0;

}

2-masala: Jamshid – internet magazine ochgan. Turkiya tovarlarini sotish bo’yicha agent, unga 5 ta shahardan buyurtmalar tushdi. U yo’l harajatlarini tejamoqchi. Jamshid unga buyurtmalar tushgan har ikki shahar orasida yo’l harajatini hisoblab chiqqan. Masala yo’l harajatlarini kamaytirishdan iborat.

Dastlabki ma’lumotlar Jamshid Tovar tarqatishi kerak bo’lgan shaharlar ruyhati va yo’l harajatlari matrisasi ko’rinishida berilgan. Bu yerda matrisa i shahardan j shaharga borish narxiga teng bo’lgan c(i,j) elementlardan tashkil topgan ikki o’lchamli massiv. Shaharlar soni 20 ta bo’lsa, matrisa - bo’ladi.

	P1	P2	P3	P4	P5
P1	-	12	15	11	13
P2	12	-	10	13	12
P3	15	10	-	14	10
P4	11	13	14	-	16
P5	13	12	10	16	-

Masala dasturi:

#include

using namespace std;

int main()

{ int cost, u,w, kk=100000, v,t, c[100][100],n;

cout<<"matritsa o'lchamini kiriting "<

cin>>n;

cout<<"c[i][j] "<for(int i=0; i

for(int j=0; j

cin>>c[i][j];

t=0; cost=0; v=0;

cout<<"1 ->";

for(int k=0; k

{ for(int i=0; i

if(c[v][i]

cout<";

cost+=c[v][t];

for(int i=0; i

c[i][t]=0;

if(k!=(n-2)) c[t][0]=0;

v=t;

kk=10000000;

}

cout<<"1"<

cost+=c[v][0];

return 0;}

Laboratoriya mashg’uloti 12.1