Khử đệ quy bài toán tìm mọi đường đi từ thành phố D đến C

**Admin** Wed Jun 15, 2011 10:47 pm

Code:: #include <stdio.h> #include <conio.h> #define max 100 #define FileIn "Input.inp" int Dem = 0; /*Kiem tra xem co duong di tu C den D hay khong.*/ /*Doc file du lieu cua bai toan luu vao ma tran A.*/ void Doc_File(int A[max][max], int &n, int &D, int &C){ FILE*f = fopen(FileIn,"rb"); fscanf(f,"%d%d%d",&n,&D,&C); printf("%d %d\n",D,C); for(int i =1;i<=n;i++) { for(int j =1;j<=n;j++) { fscanf(f,"%d",&A[i][j]); printf("%3d",A[i][j]); } printf("\n"); } fclose(f); } /*Xuat ket qua tim duoc ra man hinh*/ void XuatDuongDi(int Stack2[max],int DemStack2) { printf("%d",Stack2[1]); for (int i = 2; i<= DemStack2; i++) printf(" -> %d",Stack2[i]); printf("\n"); Dem++; //tang so duong di len } /*Kiem tra dinh i co nam trong Stack2, neu co tra ve ket qua 0 va neu khong co tra ve ket qua 1*/ char KiemTraStack(int i, int Stack2[max],int Dem2){ for(int j=1;j<=Dem2; j++) if(i==Stack2[j]) return 0; return 1; } /*Xoa tat ca cac phan tu giong nhau o dau Stack1 va Stack2 khi co duong di hoac gap dinh treo khong the di duoc nua*/ void XoaStack(int Stack1[max],int &DemStack1,int Stack2[max],int &DemStack2) { while(Stack1[DemStack1]==Stack2[DemStack2]) { DemStack1--; DemStack2--; } DemStack2++; Stack2[DemStack2]=Stack1[DemStack1]; } /*Tim kiem tat ca cac duong di neu co, neu bien Dem>0 thi ton tai duong di va nguoc lai neu Dem=0 thi khong co duong di tu D den C*/ void TimKiem(int A[max][max], int n, int D, int C){ int Stack1[max],Stack2[max]; int DemStack1=1,DemStack2=1, DinhTreo; int i,ChiSo; //Khoi tao 2 stack Stack1[DemStack1]=D; Stack2[DemStack2]=D; while( DemStack1>0 && DemStack2>0 ){ ChiSo = Stack1[DemStack1]; DinhTreo = 1; //Gia su ton tai dinh treo for(i=1; i<=n; i++) if(A[ChiSo][i]==1 && KiemTraStack(i,Stack2,DemStack2)==1){ DemStack1++; Stack1[DemStack1] = i; DinhTreo = 0; } if(DinhTreo==1) XoaStack(Stack1,DemStack1,Stack2,DemStack2); else { DemStack2++; Stack2[DemStack2]=Stack1[DemStack1]; } if(Stack2[DemStack2]==C){ XuatDuongDi(Stack2,DemStack2); XoaStack(Stack1,DemStack1,Stack2,DemStack2); } } } void main() { clrscr(); int A[max][max],n,D,C; Doc_File(A,n,D,C); TimKiem(A,n,D,C); if(Dem==0) printf("Khong co duong di tu %d den %d.",D,C); getch(); }