Bài Đầy đủ Thi Toán Rời Rạc,bao gồm tìm bậc của đỉnh bài thi của lớp 2

by **Nguyễn Phạm Anh Dũng** Mon Jul 16, 2012 10:32 pm

Nhấn chữ spoiler để xem

Spoiler:

Code:: #include <stdio.h> #include <conio.h> #include <string.h> #include <process.h> #include <iostream.h> #define MAX 100 //Buoi 1: Lam quen voi ma tran ke. struct GRAPH { int a[MAX][MAX]; int arrnLabel[MAX]; int nSoMienLienThong; int NhanDinh[MAX]; int sodinh; int dinhcha[MAX]; int chiphi[MAX]; int dinhdau,dinhcuoi; int temp[6][6]; }; typedef struct CK { int x,y; }; //TIM BAC CUA DINH CUA DO THI void timbac(GRAPH &g) { printf("\n"); int bac; int i; for(i=0;i<g.sodinh;i++) { bac=0; for(int j=0;j<g.sodinh;j++) { if(g.a[i][j]>0) bac++; printf(" %d",bac); } } } void DocMaTranKe(GRAPH &g) { int temp[6][6]={{0,1,1,0,0,0},{1,0,0,1,1,0},{1,0,0,0,1,0},{0,1,0,0,1,0},{0,1,1,1,0,1},{0,0,0,0,1,0}}; g.sodinh=6; int i,j; for(i=0;i<g.sodinh;i++) for(j=0;j<g.sodinh;j++) g.a[i][j]=temp[i][j]; } void XuatMaTranKe(GRAPH &g) { int i,j; printf("\n"); for(i=0;i<g.sodinh;i++) { printf("\n"); for(j=0;j<g.sodinh;j++) printf("%d ",g.a[i][j]); } } int KiemTraMaTranKeHopLe(GRAPH g) { int i; for(i=0;i<g.sodinh;i++) if(g.a[i][i]!=0) return 0; return 1; } int KiemTraDoThiVoHuong(GRAPH g) { int i,j; for(i=0;i<g.sodinh;i++) for(j=0;j<g.sodinh;j++) if(g.a[i][j]!=g.a[j][i]) return 0; return 1; } //Buoi 2: Lien thong - so thanh phan lien thong. void Visit(GRAPH &g,int dinh,int label) { int i; if(dinh==g.sodinh) return; g.NhanDinh[dinh]=label; for(i=0;i<g.sodinh;i++) { if(g.NhanDinh[i]==0) if(i!=dinh &&(g.a[dinh][i]==1||g.a[i][dinh]==1)) Visit(g,i,label); } } void XetLienThong(GRAPH &g) { int i; for(i=0;i<g.sodinh;i++) g.NhanDinh[i]=0; g.nSoMienLienThong=0; for(i=0;i<g.sodinh;i++) if(g.NhanDinh[i]==0) { g.nSoMienLienThong++; Visit(g,i,g.nSoMienLienThong); } } void InThanhPhanLienThong(GRAPH &g) { for(int i=1;i<=g.nSoMienLienThong;i++) { printf("\nMien lien thong la %d: ",i); for(int j=0;j<g.sodinh;j++) { if(i==g.NhanDinh[j]) printf("\t%d",j); } } } //buoi 3 void CayKhung(GRAPH &g,CK ck[],int &nck) { int i,j; nck=0; for(i=0;i<g.sodinh;i++) g.NhanDinh[i]=0; g.NhanDinh[0]=1; cout<<"sodinh"<<g.sodinh; while(nck<g.sodinh-1) { for(i=0;i<g.sodinh;i++) { if(g.NhanDinh[i]!=0) { for(j=0;j<g.sodinh;j++) { if(g.NhanDinh[j]==0 && (g.a[i][j]==1||g.a[j][i]==1)) { ck[nck].x=i;ck[nck].y=j; nck++; g.NhanDinh[j]=1; break; } } } } } } void incaykhung(CK ck[],int nck) { for(int i=0;i<nck;i++) { cout<<"\n"<<ck[i].x+1<<" "<<ck[i].y+1<<"\n"; } } //========Tim duong di void TraceVisit(GRAPH &g,int n) { printf("\n"); int j; if(n==g.dinhcuoi) return; //duyet cac dinh j chua vieng co canh noi truc tiep den dinh i for(j=0;j<g.sodinh;j++) { if(g.dinhcha[j]==-1 && g.a[n][j]!=0 && j!=n) { //luu dinh cha g.dinhcha[j]=n; printf("dinh cha cua %3d la %3d",j,n); //tich luy chi phi g.chiphi[j]=g.chiphi[n]+g.a[n][j]; TraceVisit(g,j); } } } //ham in duong di void Induongdi(GRAPH g) { if(g.dinhcha[g.dinhcuoi]< 0) { printf("khong co duong di"); return; } int i=g.dinhcuoi; printf("%3d",i); while(i!=g.dinhdau) { i=g.dinhcha[i]; printf(" <-- %3d",i); } } //ham tim duong di void Timduongdi(GRAPH &g) { printf("\n nhap dinh dau va dinh cuoi:"); scanf("%d %d",&g.dinhdau,&g.dinhcuoi); //khoi tao cac dinh cha =-1 for(int i=0;i<g.sodinh;i++) g.dinhcha[i]=-1; //khoi tao dinh xuat phat =1 g.dinhcha[g.dinhdau]=g.dinhdau ; //khoi tao chi phi tu dinh dau den dinh dau =0 g.chiphi[g.dinhdau]=0; TraceVisit(g,g.dinhdau); if(g.dinhcha[g.dinhcuoi]!=-1) { printf("\n co duong di tu dinh %d den dinh %d",g.dinhdau,g.dinhcuoi); printf("\n voi tong chi phi la: %d",g.chiphi[g.dinhcuoi]); printf("\n vay duong di la: \n"); Induongdi(g); } else printf("khong co duong di tu dinh %d den dinh %d",g.dinhdau,g.dinhcuoi); } void main() { GRAPH g; clrscr(); DocMaTranKe(g); XuatMaTranKe(g); timbac(g); // kiem tra ma tran ke hop le /* if(KiemTraMaTranKeHopLe(g)==0) printf("Ma tran ke khong hop le!"); */ //kiem tra do thi vo huong /* if(KiemTraDoThiVoHuong(g)==1) printf("\nDay la do thi vo huong"); else printf("\nDay la do thi co huong"); */ // xet do thi lien thong /* XetLienThong(g); int nck; CK ck[MAX]; if (g.nSoMienLienThong==1) { printf("\nDo thi lien thong."); CayKhung(g,ck,nck); incaykhung(ck,nck); // cout<<nck; } */ // else // InThanhPhanLienThong(g); // incaykhung(ck,nck); // Timduongdi(g); getch(); }