Search
 
 

Display results as :
 


Rechercher Advanced Search

Latest topics
» NewBlueFx TotalFX Windows-FL | 1.11 GB
Tue Dec 17, 2013 12:42 pm by titquarra

» NewBlueFx TotalFX Windows-FL | 1.11 GB
Tue Dec 17, 2013 12:42 pm by titquarra

» Celebrity.Sex.Tape.UNCUT.&.UNRATED.2012.720p.BRrip.x264.YIFY.mp4
Tue Dec 17, 2013 8:32 am by titquarra

» Maya Autodesk Personal Learning Edition 8.5
Tue Dec 17, 2013 7:47 am by titquarra

» Tuyệt Kỹ Đong Giai Chân Kinh (tuyệt Kỹ cua trai)
Thu Aug 23, 2012 5:38 am by Admin

» Tuyệt kỹ cua giai
Thu Aug 23, 2012 5:36 am by Admin

» NETCAT.........
Mon Aug 13, 2012 6:35 am by Admin

» Bảo mật CSDL bằng phương pháp mã hóa.
Tue Apr 17, 2012 10:04 pm by Admin

» Hàm mã hóa MD5 bằng JavaScript
Tue Apr 17, 2012 10:03 pm by Admin

Shopmotion


Affiliates
free forum


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

View previous topic View next topic Go down

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

Post  Admin on 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();
}

Admin
Admin

Tổng số bài gửi : 782
Join date : 2009-08-15

View user profile http://hackis.forumotion.com

Back to top Go down

View previous topic View next topic Back to top


 
Permissions in this forum:
You cannot reply to topics in this forum