Ðåôåðàò: Òðàíñïîðòíàÿ çàäà÷à
topnast1=top2;
else
top3->next=top2;
top3=top2;
top2->next=NULL;
top2->ick = ik;
top2->jck = jk;
ch++;
//************ PRODOLZHENIE 3 POISKA *************
top2->prnapr = 3;
pr("top2",top2);
napr = 4; jk = nst;
perlev = perpr = 0;
} // ******* IF *****
else{
fprintf(fil,"Point not found ! Change direction to RIGHT\n");
napr = 1;
perlev = 1;
}
break;
case 4:
printf("Search to the up --->");
fprintf(fil,"Search to the up --->");
if((nstr=verpoisk(ik,jk))>=0)
{
if((top2=(struct cik*)malloc(sizeof(struct cik)))==NULL)
abort();
printf("founded\n\r"); fprintf(fil,"founded\n");
if(!topnast1) topnast1=top2;
else top3->next=top2;
top3=top2;
top2->next=NULL;
top2->ick=ik;
top2->jck=jk;
ch++;
top2->prnapr = 4;
pr("top2",top2);
napr = 1;
ik = nstr;
perver = perniz = 0;
} // *****If **************
else
{
fprintf(fil,"Point not found ! Change direction to DOWN\n");
napr = 2;
perver = 1;
}
break;
} // ************ SWITCH ********************
// ************** PRODOLZHENIE 4 POISKA ********************
if(perlev == 1 && perpr == 1)
{
*(matr2+ik*n+jk) = 0;
ik = top3 ->ick;
jk = top3 ->jck;
napr = top3->prnapr;
top3 = topnast1;
printf("Zerro 1\n\r");
for(top2=topnast1;top2->next !=NULL;top2=top2->next)
top3 = top2;
top3 -> next=NULL;
perlev = perpr = 0; // if(ch == 1)
if(top2==top3)
{
fl3=1;
break;
}
else
{
top3->next=NULL;
free(top2);
ch--;
printf("Viynimaem tochky: (%d,%d)=%d\n",ik,jk,*(matr2+ik*n+jk));
fprintf(fil,"Viynimaem tochky: (%d,%d)=%d\n",ik,jk,*(matr2+ik*n+jk));
pr("top2",top2);
}
perpr = 0;
perlev = 0;
} // IF
if(perver == 1 && perniz == 1)
{
*(matr2+ik*n+jk)=0;
printf("Zerro 2\n\r");
ik=top3->ick;
jk = top3->jck;
napr = top3->prnapr;
top3 = topnast1;
for(top2 = topnast1;top2->next !=NULL;top2=top2->next)
top3 = top2; perver = perniz = 0;
if(top2==top3)
{
fl3=1;
break;
}
else
{
top3->next = NULL;
free(top2);
ch--;
// ******* PRODOLZHENIE 5 POISKA *********************
printf("Viynimaem tochky: (%d,%d) = %d\n",ik,jk,*(matr2+ik*n+jk));
fprintf(fil,"Viynimaem tochky: (%d,%d) = %d\n",ik,jk,*(matr2+ik*n+jk));
pr("top2",top2);
}
perver = 0;
perniz = 0;
} // IF
if(ch==0)
{
fl3=1;
break;
}
} //while
} //while
i=0;
if((zi = (int*)calloc(ch,sizeof(int))) == NULL ) abort();
if((zj = (int*)calloc(ch,sizeof(int))) == NULL ) abort();
printf("\n\r");
ch2 = ch;
for(top2 = topnast1;top2 !=NULL;top2 = top2->next)
{
*(zi+i) = top2 ->ick;
*(zj+i) = top2 ->jck;
i++;
}
return(0);
} // *********** cikl ****************************
int prpoisk(int i1, int j1)
{
int j;
for(j=j1+1;j<n;j++)
{
if((*(matr2+i1*n+j))!=0)
return(j);
}
return(-1);
}
int levpoisk(int i1,int j1)
{
int j;
for(j = j1-1;j>=0;j--)
{
if((*(matr2+i1*n+j))!=0)
return(j);
}
return(-1);
}
int verpoisk(int i1,int j1)
{
int i;
for(i=i1-1;i>=0;i--)
{
if((*(matr2+i*n+j1))!=0)
return(i);
}
return(-1);
}
int nizpoisk(int i1, int j1)
{
int i;
for(i = i1+1;i<m;i++)
{
if((*(matr2+i*n+j1))!=0)
return(i);
}
return(-1);
}
// ************* FUNCTION SEARCH ********************
void pr(char pr[],void *st)
{
struct cik { int prnapr;
int ick;
int jck;
struct cik *next;
} *ptr;
int i,j;
ptr = (struct cik *)st;
fprintf(fil,"Koordinatiy ytoplennoy tochki : %d and %d",ptr->ick,ptr->jck);
printf("Koordinatiy ytoplennoy tochki : %d and %d\n\r",ptr->ick,ptr->jck);
fprintf(fil,"and napravlenie");
printf("Napravlenie");
switch(ptr->prnapr)
{
case 1:
fprintf(fil,"Vpravo\n");
printf("Vpravo\n\r");
break;
case 2:
fprintf(fil,"Vniz\n");
printf("Vniz\n\r");
break;
case 3:
fprintf(fil,"Vlevo\n");
printf("Vlevo\n\r");
break;
case 4:
fprintf(fil,"Vverh\n");
printf("Vverh\n\r");
break;
default:
fprintf(fil,"Start\n");
printf("Start\n\r");
break;
}
fprintf(fil,"WORK MATRIX\n");
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
fprintf(fil,"%5d",*(matr2+i*n+j));
}
fprintf(fil,"\n");
}
fprintf(fil,"************************************\n");
return;
}
// **************** UPGRADE PLAN *********************************//
void plmi(void)
{
int i,j,k,min,i1,j1,flagok;
ch = ch2;
flagok = 0;
i1=*zi;
j1 = *zj;
for(k=1;k<ch;k+=2){
i=*(zi+k);
j = *(zj+k);
if(*(matr+i*n+j) == -2){
*(matr+i1*n+j1) = *(matr+i*n+j);
*(matr+i*n+j) = 0;
flagok = 1;
break;
}
} // for
if(!flagok){
for(k=2;k<ch;k+=2){
i = *(zi+k);
j = *(zj+k);
if(*(matr+i*n+j) == -2)
*(matr+i*n+j) = 0;
} // for
i = *(zi+1);
j = *(zj+1);
min = *(matr+i*n+j);
for(k=3;k<ch;k+=2){
i=*(zi+k);
j=*(zj+k);
if(*(matr+i*n+j)<min)
min = *(matr+i*n+j);
}
if(min == -2) min = 0;
for(k=0;k<ch;k+=2){
i = *(zi+k);
j = *(zj+k);
*(matr+i*n+j) += min;
}
for(k=1;k<ch;k+=2){
i=*(zi+k);
j=*(zj+k);
*(matr+i*n+j)-=min;
}
} //if
// ***************** PROVERKA **************************//
printf("PROVERKA\n");
for(i=0;i<m;i++){
for(j=0;j<n;j++){
printf("%5d",*(matr+i*n+j));
}
printf("\n");
}
free(matr2);free(zi);free(zj);free(pu);free(pv);
return;
}
void Bas(void)
{
int i,j;
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
if(*(matr+i*n+j)!=0) basper++;
}
}
return;
}
void sohran(void)
{
// Sravnenie
int i,j,k;
for(k=0;k<ch;k++)
{
i=zi[k];
j=zj[k];
if((*(matr+i*n+j) == 0) && (basper < m+n-1))
{
*(matr+i*n+j) = -2;
basper++;
}//if
}
return;
}
// ************ SOZDANIE OPORNOGO PLANA **************************
// ************ METODOM SEVERNO-ZAPADNOGO YGLA *******************
void opplan1(void)
{
int i,j, ch1 = n-1;
//**************** Viydelenie pamyty *************************
if((matr=(int*)calloc(m*n,sizeof(int))) == NULL) abort();
for(i=0;i<m;i++)
{
for(j=ch1;j>=0;j--)
{
if(*(po+i)<*(pn+j))
{
*(matr+i*n+j)=*(po+i);
*(pn+j)-=*(po+i);
*(po+i)=0;
break;
}
*(matr+i*n+j)=*(pn+j);
*(po+i)-=*(pn+j);
*(pn+j)=0;
ch1--;
}
}
//*************** Proverka *************************
printf("Proverka\n");
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
printf("%5d",*(matr+i*n+j));
}
printf("\n");
}
fprintf(fil,"matrix\n");
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
fprintf(fil,"%5d",*(matr+i*n+j));
}
fprintf(fil,"\n");
}
fprintf(fil,"*****************\n");
return;
}//******** opplan1
//************** SOZDANIE OPORNOGO PLANA ********************
//*************** METHOD NORD-WEST YGOL *********************
void opplan2(void)
{
int i,j,k_i,k_j=0, min = 32767, *kontr,fl;
if((matr=(int*)calloc(m*n,sizeof(int))) == NULL) abort();
if((kontr=(int*)calloc(m*n,sizeof(int))) == NULL) abort();
for(i=0;i<m;i++){
for(j=0;j<n;j++){
*(kontr+i*n+j) = 0;
}
}
for(i=0;i<m;i++){
fl = 0;
while(!fl){
for(j=0;j<n;j++){
if(*(st+i*n+j)<min){
if(*(kontr+i*n+j) == 0) {
min = *(st+i*n+j);
k_i = i; k_j = j;
}
}
}
*(kontr+k_i*n+k_j) = 1;
if(*(po+k_i)<*(pn+k_j)) {
min = 32767;
*(matr+k_i*n+k_j)=*(po+k_i);
*(pn+k_j)=*(po+k_i);
*(po+k_i)=0;
break;
}
else {
*(matr+k_i*n+k_j)=*(pn+k_j);
*(po+k_i)-=*(pn+k_j);
*(pn+k_j)=0;
min = 32767;
if(*(po+k_i) == 0) fl = 1;
}
}
}
printf("Proverka\n"); // proverka
for(i=0;i<m;i++){
for(j=0;j<n;j++){
printf("%5d",*(matr+i*n+j));
}
printf("\n");
}
fprintf(fil," matr\n");
for(i=0;i<m;i++){
for(j=0;j<n;j++){
fprintf(fil,"%5d",*(matr+i*n+j));
}
fprintf(fil,"\n");
}
fprintf(fil,"*********************************\n");
return;
}// opplan2
void main()
{
int i,j,met;
int flagok;
fil = fopen("otchet.txt","w");
clrscr();
gotoxy(1,3);
printf("WARNING USERS ---->\n\n\n");
printf("Ðåøåíèå çàêðûòîé òðàíñï.çàäà÷è\n\n");
printf("Áàçèñíûå ïåðåìåííûå,ðàâíûå íóëþ, ïîìå÷àþòñÿ -2;\n");
printf("Ãðàôîêëåòêà, îòíîñèòåëüíî êîòîðîé ñòðîèòñÿ öåïü\n");
printf("ïîìå÷àåòñÿ -1\n");
gotoxy(1,22);
printf("press anykey to contunio...\n");
getch();
clrscr();
data();
printf("press anykey to contunio...\n");
getch();
clrscr();
gotoxy(1,3);
printf("\n YOU selest method building first plan:\n");
printf("1-method NORD-WEST ygol\n");
printf("2-method NORD-EST ygol\n");
printf("3-method minimum element to string\n");
scanf("%d",&met);
gotoxy(1,22);
printf("press anykey, to contunie...\n");
getch();
//void opplan(void);
//void opplan1(void);
//void opplan2(void);
clrscr();
switch(met)
{
case 1: opplan();
break;
case 2: opplan1();
break;
case 3: opplan2();
break;
default: printf("íåâåðíî âûáðàí ÌÅÒÎÄ\n"); exit(-1);
}
basper = 0;
Bas();
flagok = 0;
if(basper<m+n-1)
{
//Åñëè â ïåðâîíà÷àëüíîì ïëàíå êîëè÷åñòâî áàçèñíûõ
//ïåðåìåííûõ, îòëè÷íûõ îò íóëÿ, ìåíüøå, ÷åì M+N-1
while(!flagok)
{
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
if(*(matr+i*n+j)==0)
{
*(matr+i*n+j) = -2;
flagok = 1;
basper++;
break;
} //if
}
if(flagok) break;
}
if(basper<m+n-1) flagok = 0;
}//while
}//if
for(;;)
{
fprintf(fil,"*********** Íà÷àëî ÄÎËÁÀÍÓÒÎÉ Èòåðàöèè**********\n");
basper = 0;
Bas();
//void sohran(void);
if(iter>0)
{
//Êîëè÷åñòâî áàçèñíûõ íåíóëåâûõ ïåðåìåííûõ <m+n-1
if(basper <m+n-1) sohran();
}
kost(); //****** Âûâîä îáùåé ñòîèìîñòè******
potenzial(); //*******Ïîäñ÷åò ïîòåíöèàëîâ********
ch2 = 0;
z = optim();
if(!z) break;
plmi();
iter++;
fprintf(fil,"%d ØÀÃ ÄÎÑÒÀÂØÅÉ ÄÎ ÑÚÅÕÀÂØÅÉ ÊÐÛØÈ ÈÒÅÐÀÖÈÈ",iter);
}
//************* ÏÐÎÂÅÐÊÀ************
printf("\n\nOPTIMAL PLAN :\n");
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
printf("%5d",*(matr+i*n+j));
}
printf("\n");
}
fprintf(fil,"optimal PLAN :\n");
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
fprintf(fil,"%5d",*(matr+i*n+j));
}
fprintf(fil,"\n");
}
kost(); //************ÂÛÂÎÄ îáùåé ñòîèìîñòè***********
fclose(fil);
clrscr();
printf("Îò÷åò î ïðîäåëàííîé ðàáîòå ÏÐÎÃÐÀÌÌÛ â ôàéëå otchet.txt");
getch();
return;
} // main
