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


Ứng dụng đường đi Hamilton

View previous topic View next topic Go down

Ứng dụng đường đi Hamilton

Post  Admin on Wed Jun 15, 2011 9:11 pm

Một người khách du lịch muốn đi thăm n thành phố được đánh số từ 1 đến n, mỗi thành phố người khách chỉ muốn đi qua chúng một lần. Mạng lưới giao thông giữa n thành phố là hai chiều và được cho bởi ma trận A[i,j] trong đó A[i,j] =1 nếu có đường đi giữa thành phố i và thành phố j, A[i,j] = 0 trong trường hợp ngược lại.
Hãy viết chương trình thiết lập cho người khách một lộ trình (có thể tồn tại nhiều lộ trình) hay thông báo không tồn tại lộ trình theo yêu cầu của khách.
Dữ liệu vào: cho trong file Bai6.inp
- Dòng đầu ghi số n là số đỉnh của một đồ thị (0- Dòng 2 ghi đỉnh mà người khách du lịch xuất phát.
- Dòng i+2 (0 < i<=100) chứa n số A[i,1],A[i,2]…A[i,n] mỗi số cách nhau bởi một khoảng trắng.
Dữ liệu ra: In ra màn hình đường đi của người khách (nếu có).

Ví dụ:
Bai6.inp
5
1
0 1 0 0 0
1 0 1 1 1
0 1 0 1 0
0 1 1 0 1
0 1 0 1 0
Kết quả:1->2->3->4->5

Bai6.inp
6
1
0 1 1 0 0 0
1 0 1 0 1 0
1 1 0 0 0 1
0 0 0 0 1 0
0 1 0 1 0 0
0 0 1 0 0 0
Kết quả: KHONG TON TAI DUONG DI

Bai6.inp
5
2
0 1 0 1 1
1 0 1 0 1
0 1 0 1 0
1 0 1 0 1
1 1 0 1 0
Kết quả: 2->1->5->4->3

Code:
#include <stdio.h>
#include <conio.h>
#include <iostream.h>
#define FileIn "Bai6.inp"
int Dem = 0;      //Dếm số đường đi
int*L;        //Lưu lại đường đi
char*DanhDau;  //Dánh dấu đỉnh đã đi
int **A,n,D;
/*Dọc file dữ liệu bài toán*/
void Doc_File() {
  FILE*f = fopen(FileIn,"rb");
  fscanf(f,"%d%d",&n,&D);      //Đọc n và đỉnh xuất phát lưu trong biến D
  cout<<"Ma Tran Lien Ket Tuong Ung.\n"<<D<<endl;
  *A = new int [n];
  for(int i =0;i<n;i++) {
      A[i] = new int [n];
      for(int j =0;j<n;j++) {
        fscanf(f,"%d",&A[i][j]);
        cout<<A[i][j]<<" ";
      }
      cout<<endl;
  }
  fclose(f);
  D--;
}
/*Khởi tạo dữ liệu ban đầu cho bài toán*/
void KhoiTao() {
  DanhDau = new char [n];
  L = new int [n];
  for (int i = 0; i<n; i++) { 
      DanhDau[i] = 0;  //Khởi tạo mọi đỉnh chưa được đánh dấu
      L[i] = 0;
  }
  DanhDau[D] = 1;      //Đánh dấu đỉnh xuất phát
  L[0] = D;
}
/*In đường đi của bài toán ra màn hình*/
void InDuongDi(int Dinh) {
  Dem++;
  cout<<endl<<D+1;
  for (int i = 1; i<Dinh; i++)
      cout<<" -> "<<L[i]+1;
}
/*Tìm kiếm đường đi*/
void TimKiem(int Dinh) {
  if(Dinh == n && Dem == 0) InDuongDi(Dinh);
  else {
      for(int i = 0; i<n; i++)
      if( A[L[Dinh-1]][i]>0 && DanhDau[i] == 0 && Dem==0){
        L[Dinh] = i;
        DanhDau[i] = 1;  //Đánh dấu đỉnh tìm được
        TimKiem(Dinh+1);  //Tiếm kiếm đỉnh kế tiếp
        L[Dinh] = 0;
        DanhDau[i] = 0;  //Phục hồi đỉnh đánh dấu
      }
  }
}
/*Chương trình chính*/
void main() {
  clrscr();
  Doc_File();
  KhoiTao();
  cout<<"Duong Di Nguoi Khach";
  TimKiem(1);      //Tìm kiếm từ đỉnh thứ 2 của đồ thị
  if(Dem==0)
      cout<<" Khong Co";
  delete*A,DanhDau,L;
  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