›
›

Giáo trình thực hành Lập trình nâng cao - Đào Anh Pha

pdf 73 trang Gia Huy 17/05/2022 2690
Download
Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình thực hành Lập trình nâng cao - Đào Anh Pha", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfgiao_trinh_thuc_hanh_lap_trinh_nang_cao_dao_anh_pha.pdf

Nội dung text: Giáo trình thực hành Lập trình nâng cao - Đào Anh Pha

  1. TRƯỜNG ĐẠI HỌC CỬU LONG KHOA TẠI CHỨC – LIÊN THÔNG BỘ MÔN TIN HỌC GIÁO TRÌNH THỰC HÀNH LẬP TRÌNH NÂNG CAO TÁC GIẢ Ths. Đào Anh Pha Ks. Đào Thị Kiều Diễm Ks. Cao Thị Trúc Linh LƯU HÀNH NỘI BỘ VĨNH LONG - 2010
  2. LỜI MỞ ĐẦU Giáo trình thực hành này được viết theo giáo trình Lập trình nâng cao nhằm mục đích làm tài liệu cho sinh viên năm thứ 2 thực hành môn học này. Nội dung của giáo trình gồm 4 chương thể hiện cơ bản các kỹ thuật lập trình thường gặp đối với sinh viên.  Chương 1. Kỹ thuật lập trình đệ quy.  Chương 2. Sắp xếp.  Chương 3. Đại số ma trận.  Chương 4. Một số thuật giải trên đồ thị. Chương 1 thể hiện một số kỹ thuật lập trình làm nền tảng cho các chương sau. Đối với đệ quy phi tuyến chủ yếu ta sử dụng kỹ thuật tìm kiếm theo chiều sâu. Kỹ thuật này được áp dụng trong chương 4 để tìm đường đi trên đồ thị. Tuy nhiên, ở đây ta chưa trình bài kỹ thuật duyệt theo chiều sâu bằng cách khử đệ quy. Kỹ thuật này sẽ được trình bài trong giáo trình Lý thuyết đồ thị và thuật giải. Chương 2 thể hiện một số thuật toán sắp xếp nhằm giúp sinh viên so sánh và đánh giá thuật toán sắp xếp nào sẽ tốt hơn. Chương 3 thể hiện phương pháp giải hệ phương trình tuyến tính bằng phương pháp phân rã ma trận bằng thuật toán Crout. Chương 4 thể hiện một số thuật giải tìm đường đi cơ bản trên đồ thị áp dụng kỹ thuật đánh dấu đỉnh, đánh dấu cạnh và kỹ thuật tham ăn. Vì thời gian phân bố giảng dạy theo chương trình khung và nội dung của môn học này nên giáo trình không tránh khỏi những khiếm khuyết. Rất mong nhận được sự góp ý của tất cả các bạn quan tâm đến giáo trình này. Ngày 24 tháng 04 năm 2010 Tác giả
  3. MỤC LỤC CHƯƠNG 1. KỸ THUẬT LẬP TRÌNH ĐỆ QUY 1 Bài tập 1. Tìm phần tử Fibonacci thứ n 1 Bài tập 2. Tính X lũy thừa n 1 Bài tập 3. Thuật toán Euclide tìm ước chung lớn nhất 2 Bài tập 4. Tìm ước chung lớn nhất của n số nguyên 3 Bài tập 5. Tính n giai thừa 4 Bài tập 6. Tổ hợp chập k của n phần tử 4 Bài tập 7. Tính tổng n phần tử trong danh sách 5 Bài tập 8. Đệ quy hỗ tương 6 Bài tập 9. Tích n phần tử trong danh sách 7 Bài tập 10. Đếm số lần xuất hiện của phần tử x trong danh sách 8 Bài tập 11. Tháp Hà Nội 9 Bài tập 12. Liệt kê tất cả dãy nhị phân độ dài k 10 Bài tập 13. Chỉnh hợp không lặp chập k của n phần tử 12 Bài tập 14. Hoán vị mảng số nguyên có n phần tử 14 Bài tập 15. Đặt n quân hậu trên bàn cờ vua 16 Bài tập 16. Mã đi tuần 18 CHƯƠNG 2. SẮP XẾP 20 Bài tập 1. Thuật toán Bubble Sort 20 Bài tập 2. Thuật toán Selection Sort 23 Bài tập 3. Thuật toán Insertion Sort 26 Bài tập 4. Thuật toán Quick Sort 28 Bài tập 5. Thuật toán Heap Sort 30 Bài tập 6. Thuật toán Merge Sort 34 CHƯƠNG 3. ĐẠI SỐ MA TRẬN 36 Bài tập 1. Nhập xuất ma trận 36 Bài tập 2. Một số phép toán trên ma trận 37 Bài tập 3. Hệ phương trình tuyến tính dạng tam giác trên 39 Bài tập 4. Hệ phương trình tuyến tính dạng tam giác dưới 41 Bài tập 5. Thuật toán phân rã ma trận A = LU 44 Bài tập 6. Giải hệ phương trình tuyến tính dựa vào phân rã LU 46 Bài tập 7. Định thức của ma trận 49 CHƯƠNG 4. MỘT SỐ THUẬT GIẢI TRÊN ĐỒ THỊ 51 Bài tập 1. Xét tính liên thông của đồ thị 51 Bài tập 2. Đếm số thành phần liên thông 53 Bài tập 3. Tìm mọi đường đi từ giữa hai đỉnh 56 Bài tập 4. Đường đi Hamilton 58 Bài tập 5. Đường đi Euler 61 Bài tập 6. Thuật toán Dijkstra tìm đường đi ngắn nhất 63 Bài tập 7. Thuật toán Prim tìm cây bao trùm tối tiểu 65 Bài tập 8. Thuật toán Kruskal tìm cây bao trùm tối tiểu 67 TÀI LIỆU THAM KHẢO 70
  4. CHƯƠNG 1. KỸ THUẬT LẬP TRÌNH ĐỆ QUY Bài tập 1. Tìm phần tử Fibonacci thứ n Viết chương trình tìm phần tử Fibonacci thứ n được định nghĩa đệ quy như sau: 1 ,n 0  n 1 F(n) F n 1 F n 2 , n 1 Cài đặt: #include #include /*Ham tra ve so nguyen tinh gia tri Fibonacci thu n*/ int F(int n) { if(n==0 || n==1) return 1; else return F(n-1) + F(n-2); } /*Chuong trinh chinh*/ void main() { clrscr(); int n; cout >n; cout #include /*Ham tra ve so thuc tinh gia tri X^n*/ float Power(float X, int n) { if(n==0) return 1; else Trang 1
  5. return X*Power(X,n-1); } /*Chuong trinh chinh*/ void main() { clrscr(); int n; float X; cout >n; cout >X; cout #include int UCLN(int a, int b) { if(a==b) return a; else if(a>b) return UCLN(a-b,b); else return UCLN(a,b-a); } void main() { clrscr(); int a,b; cout >a; cout >b; cout<<"Uoc chung lon nhat cua "<<a<<" va "<<b<<" la "<<UCLN(a,b); getch(); } Trang 2
  6. Bài tập 4. Tìm ước chung lớn nhất của n số nguyên Viết chương trình tìm ước chung lớn nhất của n số nguyên dương a0 , ,an 1 được định nghĩa đệ quy như sau: a0 ,n 1 UC a0 , ,an 1,n UCLN an 1,UC a0 , ,an 2,n 1 ,n 1 Cài đặt: #include #include /*Ham tra ve uoc chung lon nhat cua a va b*/ int UCLN(int a, int b) { if(a==b) return a; else if(a>b) return UCLN(a-b,b); else return UCLN(a,b-a); } /*Ham tra ve uoc chung lon nhat cua n phan tu duoc luu tru trong mang 1 chieu a*/ int UC(int a[], int n) { if(n==1) return a[0]; else return UCLN(a[n-1],UC(a,n-1)); } void main() { clrscr(); int *a,n; cout >n; a = new int[n]; cout >a[i]; } cout<<"UCLN cua "<<n<<" phan tu vua nhap la "<<UC(a,n); getch(); } Trang 3
  7. Bài tập 5. Tính n giai thừa Viết chương trình tính n! được định nghĩa đệ quy như sau: 1 ,n 0 n! n * n 1 ! ,n 1 Cài đặt: #include #include /*Ham tra ve so nguyen tinh n! (Factorial)*/ long int Fac(int n) { if(n==0) return 1; else return n*Fac(n-1); } /*Chuong trinh chinh*/ void main() { clrscr(); int n; cout >n; cout #include /*C(n,k)=C(n-1,k-1)+c(n-1,k) dk: 0<k<n; c(n,0)=c(n,n)=1*/ long int C(int n, int k) { if (n==k||k==0) return 1; else return C(n-1,k-1)+C(n-1,k); Trang 4
  8. } /*Chuong trinh chinh*/ void main() { clrscr(); int n,k; cout >n; cout >k; cout #include /*Ham tra ve so nguyen tinh tong n phan tu trong mang a*/ long int S(int a[], int n) { if(n==1) return a[0]; else return a[n-1]+S(a,n-1); } /*Chuong trinh chinh*/ void main() { clrscr(); int *a,n; cout >n; a = new int[n]; cout >a[i]; } cout<<"Tong "<<n<<" phan tu trong mang a la "<<S(a,n); getch(); } Trang 5
  9. Bài tập 8. Đệ quy hỗ tương Viết chương trình tính X n và Yn được xác định như sau: X 0 1 Y0 1 X n X n 1 Yn 1 Yn 2X n 1Yn 1 Cài đặt: #include #include long int Y(int n); long int X(int n) { if(n==0) return 1; else return X(n-1) + Y(n-1); } long int Y(int n) { if(n==0) return 1; else return 2*X(n-1)*Y(n-1); } /*Chuong trinh chinh*/ void main() { clrscr(); int n; cout >n; cout<<"X("<<n<<") = "<<X(n); cout<<"Y("<<n<<") = "<<Y(n); getch(); } Trang 6
  10. Bài tập 9. Tích n phần tử trong danh sách Viết chương trình tính tích n phần tử a0 , ,an 1 được định nghĩa đệ quy như sau: a0 , n 1 S a0 , ,an 1, n an 1S a0 , ,an 2 , n 1 , n 1 Cài đặt: #include #include /*Ham tra ve so nguyen tinh tich n phan tu trong mang a*/ long int S(int a[], int n) { if(n==1) return a[0]; else return a[n-1]*S(a,n-1); } /*Chuong trinh chinh*/ void main() { clrscr(); int *a,n; cout >n; a = new int[n]; cout >a[i]; } cout<<"Tong "<<n<<" phan tu trong mang A la "<<S(a,n); getch(); } Trang 7
  11. Bài tập 10. Đếm số lần xuất hiện của phần tử x trong danh sách Viết chương trình đếm số lần xuất hiện của số nguyên x trong danh sách A a0 , ,an 1 với n phần tử. Thuật toán đệ quy được thể hiện như sau: 0 , n 0 Find A,n, x 1 Find A, n 1, x , n 0  an x Find A,n 1, x , n 0  an x Cài đặt: #include #include /*Ham tra ve so lan xuat hien cua x trong danh sach A*/ int Find(int a[], int n, int x) { if(n==0) return 0; else if(a[n-1]==x) return 1+Find(a,n-1,x); else return Find(a,n-1,x); } /*Chuong trinh chinh*/ void main() { clrscr(); int *a,n,x; cout >n; a = new int[n]; cout >a[i]; } cout >x; cout<<"So lan xuat hien cua "<<x<<"trong danh sach la "<<Find(a,n,x); getch(); } Trang 8
  12. Bài tập 11. Tháp Hà Nội Mô tả bài toán: chuyển n đĩa từ cột 1 sang cột 2 lấy cột 3 làm trung gian. Thứ tự các đĩa được sắp xếp từ nhỏ đến lớn (đĩa lớn nắm phía dưới). Ví dụ: n = 3 ta có các bước chuyển 1 2, 1 3, 2 3, 1 2, 3 1, 3 2, 1 2. Cài đặt: #include "conio.h" #include "iostream.h" /*Thap Ha Noi*/ void Move(int n, int a, int b) { if (n==1) cout " >n; Move(n,1,2); //chuyen n dia tu cot 1 sang cot 2 lay cot 3 lam trung gian getch(); } Trang 9
  13. Bài tập 12. Liệt kê tất cả dãy nhị phân độ dài k Chỉnh hợp lặp chập k của n phần tử là một nhóm có thứ tự gồm k phần tử lấy từ n phần tử đã cho, trong đó mỗi phần tử có thể có mặt 1, 2, , k lần trong nhóm tạo thành. Phương pháp: ta liệt kê tất cả chỉnh hợp có lặp chập k của hai phần tử 0 và 1. Khi đó ta sẽ có tất cả dãy nhị phân có độ dài k. Ví dụ: minh họa dạng cây với k = 3. Cài đặt: #include "conio.h" #include "iostream.h" #define max 20 int Luu[max]; int k; /*Xuat ket qua ra man hinh*/ void Out() { cout<<endl; for(int i = 0; i<k; i++) cout<<Luu[i]; } /*Day nhi phan do dai n*/ void Try(int i) { if(i==k) Out(); else { for(int j = 0; j<=1; j++) { Luu[i] = j; Try(i+1); Luu[i]=0; } Trang 10
  14. } } /*Chuong trinh chinh*/ void main() { clrscr(); cout >k; cout<<"Day nhi phan do dai k.\n"; Try(0); getch(); } Hàm Try(int i) có thể viết lại theo cách như sau: void Try(int i) { for(int j = 0; j<=1; j++) { Luu[i] = j; if(i==k-1) Out(); else Try(i+1); } } Trang 11
  15. Bài tập 13. Chỉnh hợp không lặp chập k của n phần tử Chỉnh hợp chập k của n phần tử ( k n ) là một nhóm có thứ tự gồm k phần tử khác nhau được chọn từ n phần tử đã cho. Phương pháp: liệt kê dãy có độ dài k và các phần tử trong dãy được lấy từ tập hợp {0, 1, , n-1} các phần tử được đưa vào dãy không được phép trùng nhau. Ví dụ: n = 3 và k = 2 ta sẽ có các dãy con {0,1}, {0,2}, {1,0}, {1,2}, {2,0} và {2,1}. Cài đặt: #include "conio.h" #include "iostream.h" #define max 20 char DanhDau[max]; int Luu[max]; int n,k; /*Khoi tao cac bien*/ void Init() { cout >n; cout >k; //khoi tao tat ca cac dinh chua duoc chon for(int i = 0; i<k; i++) DanhDau[i] = 0; } /*Xuat ket qua ra man hinh*/ void Out() { cout<<endl; for(int i = 0; i<k; i++) cout<<Luu[i]<<" "; } /*Chinh hop khong lap chap k*/ void Try(int i) { if(i==k) Out(); else { for(int j = 0; j<n; j++) if(DanhDau[j] == 0) { //neu dinh j chua duoc chon DanhDau[j] = 1; //chon dinh j Luu[i] = j; //luu lai gia tri j Try(i+1); //tim phan tu tiep theo DanhDau[j] = 0; //phuc hoi dinh j Trang 12
  16. } } } /*Chuong trinh chinh*/ void main() { clrscr(); cout<<"Chinh hop khong lap n chap k"; Init(); Try(0); getch(); } Hàm Try(int i) có thể viết lại theo cách như sau: void Try(int i) { for(int j = 0; j<n; j++) if(DanhDau[j]==0) { Luu[i] = j; if(i==n-1) Out(); else { DanhDau[j] = 1; Try(i+1); DanhDau[j] = 0; } } } Trang 13
  17. Bài tập 14. Hoán vị mảng số nguyên có n phần tử Phương pháp: tương tự phương pháp làm bài tập 13 nhưng ở đây ta thay tập hợp {0, 1, , n-1} là tập hợp giá trị n phần tử của mảng và độ dài của dãy là n. Ví dụ: n = 3 và A = {-1,0,1} ta sẽ có các dãy con tương ứng là {-1,0}, {-1,1}, {0,-1}, {0,1}, {1,-1} và {1,0}. Cài đặt: #include "conio.h" #include "iostream.h" #define max 20 char DanhDau[max]; //mang danh dau dinh duoc chon int Luu[max], A[max], n; /*Khoi tao cac bien*/ void Init() { cout >n; for(int i = 0; i >A[i]; } } /*Xuat ket qua ra man hinh*/ void Out() { cout<<endl; for(int i = 0; i<n; i++) cout<<Luu[i]<<" "; } /*Hoan vi mang n phan tu*/ void Try(int i) { if(i==n) Out(); else { for(int j = 0; j<n; j++) if(DanhDau[j] == 0) { //neu dinh j chua duoc chon DanhDau[j] = 1; //chon dinh j Luu[i] = A[j]; //luu lai gia tri dinh duoc chon Try(i+1); //tim dinh tiep theo DanhDau[j] = 0; //phuc hoi dinh j } } Trang 14
  18. } /*Chuong trinh chinh*/ void main() { clrscr(); Init(); cout<<"Hoan vi cac phan tu trong mang A"; Try(0); getch(); } Hàm Try(int i) có thể viết lại theo cách như sau: void Try(int i) { for(int j = 0; j<n; j++) if(DanhDau[j]==0) { Luu[i] = A[j]; if(i==n-1) Out(); else { DanhDau[j] = 1; Try(i+1); DanhDau[j] = 0; } } } Trang 15
  19. Bài tập 15. Đặt n quân hậu trên bàn cờ vua Mô tả bài toán: liệt kê tất cả phương án đặt n quân hậu trên bàn cờ vua cấp n n sao cho n quân hậu không được phép ăn nhau. Ví dụ: cho bàn cờ vua cấp 8 8 . Dưới đây là 1 phương án đặt quân hậu: Cài đặt: #include "conio.h" #include "iostream.h" #define max 20 char a[max]; //danh dau cot char b[2*max-1]; //danh dau huong Dong-Bac char c[2*max-1]; //danh dau huong Tay-Bac int Luu[max]; //luu ket qua tim duoc int n; /*Khoi tao cac bien*/ void Init() { cout >n; //tat ca cac cot chua duoc chon for(int i = 0; i<n; i++) a[i] = 0; //tat ca cac huong chua duoc chon for( i = 0; i<2*n-1; i++) { b[i] = 0; c[i] = 0; } } /*Xuat ket qua ra man hinh*/ void Out() { Trang 16
  20. cout<<endl; for(int i = 0; i<n; i++) cout<<"("<<i+1<<","<<Luu[i]+1<<") "; } /*Chinh hop khong lap chap k*/ void Try(int i) { if(i==n) Out(); else { for(int j = 0; j<n; j++) if(a[j] == 0 && b[i+j] == 0 && c[i-j+n] == 0) { a[j] = 1; //danh dau cot j b[i+j] = 1; //danh dau huong Dong-Bac thu i+j c[i-j+n] = 1; //danh dau huong tay-Bac thu j-i+n Luu[i] = j; //luu vi tri dat hau (i,j) Try(i+1); //tim vi tri dat hau tiep theo a[j] = 0; //phuc hoi cot j b[i+j] = 0; //phuc hoi huong Dong-Bac thu i+j c[i-j+n] = 0; //phuc hoi huong tay-Bac thu j-i+n } } } /*Chuong trinh chinh*/ void main() { clrscr(); Init(); cout<<"Dat Hau"; Try(0); getch(); } Trang 17
  21. Bài tập 16. Mã đi tuần Mô tả bài toán: đặt quân mã tại ô có vị trí (x,y) trên bàn cờ vua cấp n n. Hãy liệt kê tất cả các phương án quân mã xuất phát tại vị trí (x,y) có thể nhảy đến tất cả các ô khác trên bàn cờ với điều kiện mỗi ô quân mã chỉ được phép đi qua đúng 1 lần. Ví dụ: cho bàn cờ vua cấp 8 8 . Ta có 2 phương án đặt quân mã như sau: Cài đặt: #include "iostream.h" #include "conio.h" #define max 10 int A[max][max]; //Mang danh dau int B[max][max]; //Mang luu duong di int X[8]={-1,-2,-2,-1,1,2,2,1}; int Y[8]={-2,-1,1,2,2,1,-1,-2}; int n, x, y, Dem=0; //Khoi tao void Init() { cout >n; cout >x; cout >y; for(int i = 0; i<n; i++) for(int j = 0; j<n; j++) A[i][j] = 0; //tat ca cac o chua duoc danh dau B[x][y] = 1; //duong di dau tien A[x][y] = 1; //danh dau o duoc chon } //Xuat ket qua ra man hinh Trang 18
  22. void Out() { Dem++; for(int i = 0; i n*n) Out(); else { for(int j = 0; j =0 && x1 =0 && y1<n && A[x1][y1]==0){ A[x1][y1] = 1; //danh dau o (i,j) B[x1][y1] = i; //luu lai duong di x = x1; //lay toa do x moi y = y1; //lay toa do y moi Try(i+1); //tim duong di tiep theo A[x1][y1] = 0; //phuc hoi o (i,j) B[x1][y1] = 0; //xem nhu o chua di qua x = x1 - X[j]; //phuc hoi dinh x y = y1 - Y[j]; //phuc hoi dinh y } } } } //chuong trinh chinh void main() { clrscr(); Init(); Try(2); if (Dem==0) cout<<"Khong co duong di"; else cout<<"So phuong an tim duoc"<<Dem; getch(); } Trang 19
  23. CHƯƠNG 2. SẮP XẾP Bài tập 1. Thuật toán Bubble Sort Ý tưởng thuật toán: xuất phát từ phần tử cuối danh sách ta tiến hành so sánh với phần tử bên trái của nó. Nếu phần tử đang xét có khóa nhỏ hơn phần tử bên trái của nó ta tiến đưa nó về bên trái của dãy bằng cách hoán vị với phần tử bên trái của nó. Tiếp tục thực hiện như thế đối với bài toán có n phần tử thì sau n – 1 bước ta thu được danh sách tăng dần. Ví dụ: sử dụng thuật toán Bubble Sort sắp xếp dãy số {3, 10, 4, 6, 2, 6, 15, 3, 9,7} theo thứ tự tăng dần. Sau 9 bước lặp ta thu được dãy đã được sắp xếp: {2, 3, 3, 4, 6, 6, 7, 9, 10, 15}. Cài đặt: #include #include #define max 100 //nhap mang void NhapMang(int A[],int n) { for(int i=0; i >A[i]; } } //xuat mang void XuatMang(int A[],int n) { cout<<endl; for(int i=0; i<n; i++) cout<<A[i]<<"\t"; } Trang 20
  24. //hoan vi 2 phan tu void Swap(int &a,int &b) { int temp = a; a = b; b = temp; } //sap xep cac phan tu void BubbleSort(int A[],int n) { for(int i = 0; i i; j ) if(A[j] >n; NhapMang(A,n); cout #include #define max 100 void NhapMang(int A[],int n) { for(int i=0; i >A[i]; } } void XuatMang(int A[],int n, int k) { cout<<endl; for(int i=0; i<n; i++) if(i<k) Trang 21
  25. cout i; j ) if(A[j] >n; NhapMang(A,n); cout<<"\nThuat toan Bubble Sort"; XuatMang(A,n,0); BubbleSort(A,n); XuatMang(A,n,0); getch(); } Trang 22
  26. Bài tập 2. Thuật toán Selection Sort Ý tưởng thuật toán: xét dãy n phần tử a0 ,a1, ,an 1. Chọn trong dãy a0 ,a1, ,an 1 ra phần tử có khỏa nhỏ nhất và hoán vị nó với a0. Chọn trong dãy a1,a2 , ,an 1 ra phần tử có khỏa nhỏ nhất và hoán vị nó với a1. Cứ tiếp tục như thế sau n – 1 bước ta thu được danh sách có thứ tự. Ví dụ: Sau 9 bước lặp ta thu được dãy đã được sắp xếp: {2, 3, 4, 5, 6, 6, 7, 7, 8, 9}. Cài đặt: #include #include #define max 100 //nhap mang void NhapMang(int A[],int n) { for(int i=0; i >A[i]; } } //xuat mang void XuatMang(int A[],int n) { cout<<endl; for(int i=0; i<n; i++) cout<<A[i]<<"\t"; } //hoan vi 2 phan tu void Swap(int &a,int &b) { int temp = a; a = b; b = temp; Trang 23
  27. } //thuat toan Selection Sort void SelectionSort(int A[],int n) { int min; // chi so phan tu nho nhat trong day hien hanh for(int i=0; i A[j]) min = j; //ghi nhan vi tri phan tu nho nhat if(min != i) Swap(A[i],A[min]); } } //chuong trinh chinh void main() { int A[max],n; clrscr(); cout >n; NhapMang(A,n); cout #include #define max 100 void NhapMang(int A[],int n) { for(int i=0; i >A[i]; } } void XuatMang(int A[],int n, int k) { cout<<endl; for(int i=0; i<n; i++) if(i<k) Trang 24
  28. cout A[j]) min = j; if(min!=i) Swap(A[i],A[min]); XuatMang(A,n,i); } } void main() { int A[max],n; clrscr(); cout >n; NhapMang(A,n); cout<<"\nThuat toan Selection Sort"; XuatMang(A,n,0); SelectionSort(A,n); XuatMang(A,n,0); getch(); } Trang 25
  29. Bài tập 3. Thuật toán Insertion Sort Ý tưởng thuật toán: xét dãy n phần tử a0 ,a1, ,an 1. Xem dãy gồm 1 phần tử a0 là dãy có thứ tự. Thêm a1 vào dãy có thứ tự a0 sao cho dãy mới a0, a1 là dãy có thứ tự. Nếu a1 #include #define max 100 //nhap mang void NhapMang(int A[],int n) { for(int i=0; i >A[i]; } } //xuat mang void XuatMang(int A[],int n) { cout<<endl; for(int i=0; i<n; i++) cout<<A[i]<<"\t"; } //hoan vi 2 phan tu void Swap(int &a,int &b) { int temp = a; a = b; b = temp; Trang 26
  30. } //thu tuc Insertion Sort void InsertionSort(int A[],int n) { for(int i=1; i 0; j ) if(A[j] >n; NhapMang(A,n); cout 0; j ) if(A[j]<A[j-1]) Swap(A[j],A[j-1]); XuatMang(A,i+1); } } Trang 27
  31. Bài tập 4. Thuật toán Quick Sort Ý tưởng thuật toán: xét dãy n phần tử a0 ,a1, ,an 1. Bước 1: chọn khóa pivot a Left Right / 2 . Bước 2: Phân vùng. Những phần tử nhỏ hơn khóa thì nằm bên trái của khóa, những phần tử lớn hơn khóa thì nằm bên phải của khóa và những phần tử bằng khóa có thể nằm bất cứ chỗ nào trên dãy. Bước 3: sắp xếp cho cả hai phân vùng mới bên trái và bên phải. Mô tả hoạt động của thuật toán Quick Sort: Cài đặt: #include #include #define max 100 void NhapMang(int A[],int n) { for(int i=0; i >A[i]; } } void XuatMang(int A[],int n) { cout<<endl; Trang 28
  32. for(int i=0; i pivot) j ; if (i >n; NhapMang(A,n); cout<<"\nMang vua nhap la:"; XuatMang(A,n); cout<<"\nSap xep theo Quick Sort:"; QuickSort(A,0,n-1); XuatMang(A,n); getch(); } Trang 29
  33. Bài tập 5. Thuật toán Heap Sort Ta xem danh sách n phần tử a0 ,a1, ,an 1 là cây nhị phân. Cây nhị phân này được xác định như sau: tại nút thứ i tương ứng với chỉ số thứ i của mảng có con trái là nút 2*(i+1)-1 và con phải 2*(i+1) nếu 2*(i+1)-1 và 2*(i+1) nhỏ hơn n. Thuật toán được mô tả như sau: - Xây dựng Heap sao cho với mọi nút cha đều có giá trị lớn hơn nút con. Khi đó nút gốc là nút có giá trị lớn nhất. - Hoán vị nút gốc với nút thứ n – 1 và xây dựng lại Heap mới với n – 2 nút và tiếp tục hoán vị nút gốc với nút lá cuối của cây mới sau n – 2 bước ta sẽ thu được danh sách được sắp xếp theo thứ tự. Ví dụ: xét danh sách trước khi sắp xếp 0 1 2 3 4 5 6 7 11 3 5 4 9 15 19 7 Danh sách trên được thể hiện bằng cây theo thuật toán Heap Sort như sau: Trang 30
  34. Trang 31
  35. Sau 7 bước ta thu được danh sách đã được sắp xếp 0 1 2 3 4 5 6 7 3 4 5 7 9 11 15 19 Cài đặt: #include #include #define max 100 void NhapMang(int A[],int n) { for(int i=0; i >A[i]; } } void XuatMang(int A[],int n) { cout A[i]) Largest = Left; else Largest = i; if(Right A[Largest]) Trang 32
  36. Largest = Right; if(i!=Largest) { Swap(A[i],A[Largest]); Heapify(A,n,Largest); } } //xay dung Heap sao cho moi nut cha luon lon hon nut con tren cay void BuildHeap(int A[], int n) { for(int i = n/2-1; i>=0; i ) Heapify(A,n,i); } void HeapSort(int A[], int n) { BuildHeap(A,n); for(int i = n-1; i>0; i ){ Swap(A[0],A[i]); Heapify(A,i,0); } } void main() { int A[max], n; clrscr(); cout >n; NhapMang(A,n); cout<<"\nMang vua nhap la:"; XuatMang(A,n); cout<<"\nSap xep theo Heap Sort:"; HeapSort(A,n); XuatMang(A,n); getch(); } Trang 33
  37. Bài tập 6. Thuật toán Merge Sort Mô tả bài toán: cho 2 danh sách A và B lần lượt có m và n phần tử đã sắp xếp theo thứ tự. Bài toán đặt ra trộn 2 danh sách A và B với nhau thành danh sách C cũng là một danh sách có thứ tự. Thuật toán: Bước 1: khởi tạo ba chỉ số chạy trong vòng lặp i = 0, j = 0, k = 0 tương ứng cho ba mảng A, B và C. Bước 2: tại mỗi bước nếu cả hai chỉ số (i #include #define max 100 void NhapMang(int A[],int n) { for(int i=0; i >A[i]; } } void XuatMang(int A[],int n) { cout<<endl; for(int i=0; i<n; i++) cout<<A[i]<<"\t"; } void MergeSort(int m, int n, int &k, int A[], int B[], int C[]) { int i = 0, j = 0; k = 0; while (i < m && j < n) { if (A[i] <= B[j]) { C[k] = A[i]; i++; } else { C[k] = B[j]; j++; } Trang 34
  38. k++; } if (i >n; cout >m; cout<<"Nhap danh sach co thu tu A:\n"; NhapMang(A,m); cout<<"Nhap danh sach co thu tu B:\n"; NhapMang(B,n); cout<<"\nSap xep tron 2 mang A, B\n"; MergeSort(m,n,k,A,B,C); XuatMang(C,k); getch(); } Trang 35
  39. CHƯƠNG 3. ĐẠI SỐ MA TRẬN Bài tập 1. Nhập xuất ma trận Phương pháp: ta tổ chức mảng hai chiều lưu trữ các phần tử trong ma trận. Cài đặt: #include "conio.h" #include "iostream.h" #define max 100 /*Nhap ma tran he so*/ void NhapMaTran(float A[max][max], int m, int n) { for(int i = 0; i >A[i][j]; } } /*Xuat ma tran*/ void XuatMaTran(float A[max][max], int m, int n) { for(int i=0 ; i >m; cout >n; cout<<"\nNhap ma tran A cap "<<m<<"x"<<n<<endl; NhapMaTran(A,m,n); cout<<"\nXuat ma tran A"; XuatMaTran(A,m,n); getch(); } Trang 36
  40. Bài tập 2. Một số phép toán trên ma trận  Cộng ma hai ma trận Cho A aij và B bij là hai ma trận cùng cấp m n . Khi đó C A B cũng là ma trận cấp m n và được xác định bởi cij aij bij ,1 i m,1 j n .  Nhân hai ma trận Cho A aij là ma trận cấp m n và B b jk là ma trận cấp n p . Khi đó n C A.B cik là ma trận cấp m p và được xác định như bởi cik aijb jk với j 1 i 1, ,m và k 1, , p . Cài đặt: #include "conio.h" #include "iostream.h" #define max 100 /*Nhap ma tran he so*/ void NhapMaTran(float A[max][max], int m, int n, char ch) { for(int i = 0; i >A[i][j]; } } /*Xuat ma tran*/ void XuatMaTran(float A[max][max], int m, int n) { for(int i=0 ; i<m; i++){ cout<<endl; for(int j=0 ; j<n; j++) cout<<A[i][j]<<"\t"; } } /*C = A+B*/ void CongMaTran(float A[max][max], float B[max][max], float C[max][max], int m, int n) { for(int i = 0; i<m; i++) for(int j = 0; j<n; j++) C[i][j] = A[i][j]+B[i][j]; } /*A cap mxn * B cap nxp = C cap mxp*/ void NhanMaTran(float A[max][max],float B[max][max] float C[max][max],int m,int n,int p) { Trang 37
  41. for(int i = 0; i >m; cout >n; cout >p; cout<<"Nhap ma tran A cap "<<m<<"x"<<n<<endl; NhapMaTran(A,m,n,'A'); cout<<"Nhap ma tran B cap "<<m<<"x"<<n<<endl; NhapMaTran(B,m,n,'B'); cout<<"Nhap ma tran C cap "<<n<<"x"<<p<<endl; NhapMaTran(C,n,p,'C'); clrscr(); cout<<"Ma tran A"; XuatMaTran(A,m,n); getch(); cout<<"\n\nMa tran B"; XuatMaTran(B,m,n); getch(); cout<<"\n\nMa tran C"; XuatMaTran(C,n,p); getch(); cout<<"\n\nMa tran D = A+B"; CongMaTran(A,B,D,m,n); XuatMaTran(D,m,n); getch(); cout<<"\n\nMa tran D = A.C"; NhanMaTran(A,C,D,m,n,p); XuatMaTran(D,n,p); getch(); } Trang 38
  42. Bài tập 3. Hệ phương trình tuyến tính dạng tam giác trên Cho hệ phương trình tuyến tính dạng tam giác trên: a a a x b 11 12 1n 1 1 0 a22 a2n x2 b2 0 0 a x b nn n n A X B det A a11a22 ann 0 aii 0, i 1,2, ,n . Nghiệm của hệ trên được xác định như sau: AX B n  aij x j bi , i 1,2, ,n j i bn xn ann 1 n x b a x , i n 1, n 2, ,1 i i  ij j aii j i 1 Cài đặt: #include "conio.h" #include "iostream.h" #define max 100 //Nhap ma tran tam giac tren void Nhap(float A[max][max],int n) { for(int i = 0; i >A[i][j]; } } /*Nhap ma tran he so tu do*/ void Nhap(float B[max],int n) { for(int i = 0; i >B[i]; } } /*Xuat ma tran he so tu do*/ void Xuat(float B[max],int n) { cout<<"("; for(int i = 0; i<n-1; i++) cout<<B[i]<<","; Trang 39
  43. cout j) cout =0; i ) { if (A[i][i]!=0) { if (i==n-1) X[i] = B[i]/A[i][i]; else { X[i] = B[i]; for(int j=i+1; j<n; j++) X[i]=X[i]-A[i][j]*X[j]; X[i] = X[i]/A[i][i]; } } else return 0; } return 1; } /*Chuong trinh chinh*/ void main() { int n; float A[max][max],B[max],X[max]; clrscr(); Trang 40
  44. cout >n; cout<<"Nhap vao ma tran tam giac tren A\n"; Nhap(A,n); cout<<"\nNhap vao ma tran he so B\n"; Nhap(B,n); clrscr(); cout<<"Ma tran A"; Xuat(A,n); cout<<"\nMa tran B\n"; Xuat(B,n); if(HeTamGiacTren(A,X,B,n)) XuatNghiem(X,n,"x"); else cout<<"\nHe phuong trinh tuyen tinh vo nghiem"; getch(); } Bài tập 4. Hệ phương trình tuyến tính dạng tam giác dưới Cho hệ phương trình tuyến tính dạng tam giác dưới: a 0 0 x b 11 1 1 a a 0 x b 21 22 2 2 a a a x b n1 n2nn n n A X B det A a11a22 ann 0 aii 0, i 1,2, ,n . Nghiệm của hệ trên được xác định như sau: AX B i aij x j bi , i 1,2, ,n j 1 b1 x1 a11 1 i 1 x b a x , 2 i n i i  ij j aii j 1 Cài đặt: #include "conio.h" #include "iostream.h" #define max 100 //Nhap ma tran tam giac duoi void Nhap(float A[max][max],int n) { for(int i = 0; i<n; i++) Trang 41
  45. for(int j = 0; j >A[i][j]; } } /*Nhap ma tran he so tu do*/ void Nhap(float B[max],int n) { for(int i = 0; i >B[i]; } } /*Xuat ma tran he so tu do*/ void Xuat(float B[max],int n) { cout<<"("; for(int i = 0; i<n-1; i++) cout<<B[i]<<","; cout<<B[n-1]<<")"; } /*Xuat ma tran*/ void Xuat(float A[max][max], int n) { cout<<"\n"; for(int i=0 ; i<n; i++){ cout<<endl; for(int j=0 ; j<n; j++) if(i<j) cout<<"0\t"; else cout<<A[i][j]<<"\t"; } } /*Xuat nghiem*/ void XuatNghiem(float X[], int n, char * s){ cout<<"\nNghiem cua he A.X = B\n"; for(int i=0; i<n; i++) cout<<s<<i+1<<" = "<<X[i]<<endl; } /*He tam giac duoi*/ char HeTamGiacDuoi (float A[max][max], float X[max], float B[max], int n ) { for(int i = 0; i<n; i++) { if (A[i][i]!=0) { if (i==0) X[i] = B[i]/A[i][i]; Trang 42
  46. else { X[i] = B[i]; for(int j=0; j >n; cout<<"Nhap vao ma tran tam giac duoi A\n"; Nhap(A,n); cout<<"\nNhap vao ma tran he so B\n"; Nhap(B,n); clrscr(); cout<<"Ma tran A"; Xuat(A,n); cout<<"\nMa tran B\n"; Xuat(B,n); if(HeTamGiacDuoi(A,X,B,n)) XuatNghiem(X,n,"x"); else cout<<"\nHe phuong trinh tuyen tinh vo nghiem"; getch(); } Trang 43
  47. Bài tập 5. Thuật toán phân rã ma trận A = LU Quá trình chuyển hoá ma trận A ban đầu thành tích hai ma trận tam giác L.U dựa vào phép khử Gauss được thực hiện bằng các phép nhân ma trận. Thuật toán này được gọi là thuật toán Crout. Quá trình Crout bao gồm nhiều bước hồi quy. Nếu ma trận A có cấp n n ta cần n 1 bước. Thuật toán được thể hiện cụ thể như sau: a w T a w T 1 0 11 11 Crout T L U 0 H vw a11 n n v H 1 v a11 I n 1  An 1 1 0 0 u u u 11 12 1n T l21 1 0 0 a22 a2n 1 0 u u 11 1 l I 0 A 1 n 1 n 1 ln1 0 1 0 an2 ann 1 0 u uT 1 0 u uT 11 1 11 1 Crout 2 l1 I n 1 0 L n 1U n 1 l1 L n 1 0 U n 1 1 0 0 0 u u u 11 12 1n l 21 1 0 0 0 u 22 u 2n l l 0 0 Crout 31 32 I A n 2 n 2 0 0 l n1 l n2 1 0 0 u u u 11 12 1n l21 1 0 0 u u Crout 22 2n L.U n 1 ln1 ln2 1 0 0 unn Thông qua n 1 bước hồi quy ta được A L.U với L là ma trận tam giác dưới và U là ma trận tam giác trên. Cài đặt: #include "conio.h" #include "iostream.h" #define max 100 void Nhap(float A[max][max],int n) { for(int i = 0; i >A[i][j]; Trang 44
  48. } } void XuatMaTran(float A[max][max], int n) { cout >n; cout<<"Nhap ma tran A\n"; Nhap(A,n); cout<<"Ma tran A vua nhap"; XuatMaTran(A,n); PhanRaLU(A,L,U,n); cout<<"\nMa tran L"; XuatMaTran(L,n); cout<<"\nMa tran U"; XuatMaTran(U,n); getch(); } Trang 45
  49. Bài tập 6. Giải hệ phương trình tuyến tính dựa vào phân rã LU Ý tưởng thuật toán: cho hệ phương trình tuyến tính tổng quát A.X B . Ta tiến hành phân rã A L.U . Trong đó, L là ma trận tam giác dưới và U là ma trận tam giác trên. Khi đó, L.Y B A.X B L.U.X B U.X Y Cài đặt: #include "conio.h" #include "iostream.h" #define max 100 /*Nhap ma tran he so*/ void Nhap(float A[max][max],int n) { for(int i = 0; i >A[i][j]; } } /*Nhap ma tran he so tu do*/ void Nhap(float B[max],int n) { for(int i = 0; i >B[i]; } } /*Xuat ma tran he so tu do*/ void Xuat(float B[max],int n) { cout<<"("; for(int i = 0; i<n-1; i++) cout<<B[i]<<","; cout<<B[n-1]<<")"; } /*Xuat ma tran*/ void Xuat(float A[max][max], int n) { cout<<"\n"; for(int i=0 ; i<n; i++){ cout<<endl; for(int j=0 ; j<n; j++) cout<<A[i][j]<<"\t"; } } Trang 46
  50. /*Xuat nghiem*/ void XuatNghiem(float X[], int n, char * s) { cout =0; i ) { if (A[i][i]!=0) { if (i==n-1) X[i] = B[i]/A[i][i]; else { X[i] = B[i]; for(int j=i+1; j<n; j++) X[i]=X[i]-A[i][j]*X[j]; X[i] = X[i]/A[i][i]; } } else return 0; } return 1; } void PhanRaLU(float A[max][max], float L[max][max], float U[max][max], int n) { for(int k =0; k<n; k++) { U[k][k] = A[k][k]; L[k][k] = 1; for(int i=k+1; i<n; i++) { Trang 47
  51. L[i][k] = A[i][k]/U[k][k]; U[k][i] = A[k][i]; U[i][k] = 0; L[k][i] = 0; } for(i = k+1; i >n; cout<<"Nhap ma tran he so A\n"; Nhap(A,n); cout<<"Nhap ma tran he so tu do B\n"; Nhap(B,n); GiaiHePTTT(A,X,B,n); getch(); } Trang 48
  52. Bài tập 7. Định thức của ma trận Ý tưởng thuật toán: ta tiến hành phân rã ma trận A L.U . Ta có: Det(A)=Det(L)*Det(U) mà Det(L) = 1 nên Det(A) = Det(U). Cài đặt: #include "conio.h" #include "iostream.h" #define max 100 /*Nhap ma tran*/ void Nhap(float A[max][max],int n) { for(int i = 0; i >A[i][j]; } } /*Xuat ma tran*/ void XuatMaTran(float A[max][max], int n) { cout<<"\n"; for(int i=0 ; i<n; i++){ cout<<endl; for(int j=0 ; j<n; j++) cout<<A[i][j]<<"\t"; } } /*Phan ra A = LU*/ void PhanRaLU(float A[max][max], float L[max][max], float U[max][max], int n) { for(int k = 0; k<n; k++) { U[k][k] = A[k][k]; L[k][k] = 1; for(int i=k+1; i<n; i++) { L[i][k] = A[i][k]/U[k][k]; U[k][i] = A[k][i]; U[i][k] = 0; L[k][i] = 0; } for(i = k+1; i<n; i++) for(int j = k+1; j<n; j++) A[i][j] = A[i][j]-L[i][k]*U[k][j]; } } //dinh thuc ma tran tam giac double DinhThucMaTranTamGiac(float A[max][max], int n) { Trang 49
  53. double temp = 1; for(int i = 0; i >n; cout<<"Nhap ma tran A\n"; Nhap(A,n); cout<<"Ma tran A vua nhap"; XuatMaTran(A,n); PhanRaLU(A,L,U,n); cout<<"\nMa tran L"; XuatMaTran(L,n); cout<<"\nMa tran U"; XuatMaTran(U,n); cout<<"\nDet(A) = Det(L)*Det(U) = "<<DinhThucMaTranTamGiac(U,n); getch(); } Trang 50
  54. CHƯƠNG 4. MỘT SỐ THUẬT GIẢI TRÊN ĐỒ THỊ Bài tập 1. Xét tính liên thông của đồ thị Mô tả bài toán: cho đồ thị vô hướng G=(V,E) hãy kiểm tra tính liên thông của đồ thị G. Ý tưởng thuật toán: Bước 1: xuất phát từ một đỉnh bất kỳ của đồ thị. Ta đánh dấu đỉnh xuất phát và chuyển sang Bước 2. Bước 2: từ một đỉnh i đã đánh dấu, ta đánh dấu đỉnh j nếu A[i,j] = 1 và j chưa được đánh dấu và chuyển sang Bước 3. Bước 3: thực hiện Bước 2 cho đến khi không còn thực hiện được nữa chuyển sang Bước 4. Bước 4: kiểm tra nếu số đỉnh đánh dấu nhỏ hơn n (hay tồn tại ít nhất một đỉnh chưa được đánh dấu) đồ thị sẽ không liên thông và ngược lại đồ thị liên thông. Mô tả dữ liệu đầu vào và đầu ra của bài toán: Dữ liệu vào: cho trong tập tin Bai1.inp - Dòng đầu ghi số n là số đỉnh của một đồ thị (0<n<100). - Dòng i+1 (1 i n ) 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: thông báo kết quả ra màn hình ”DO THI LIEN THONG” hay “ DO THI KHONG LIEN THONG”. Ví dụ: Bai1.inp OUTPUT 8 0 1 0 0 0 1 0 0 1 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 DO THI LIEN 0 0 1 0 1 0 0 0 THONG 0 0 0 1 0 1 0 0 1 0 0 0 1 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 Bai1.inp OUTPUT 6 0 1 1 0 0 0 1 0 1 0 0 0 DO THI KHONG 1 1 0 0 0 0 LIEN THONG 0 0 0 0 1 1 0 0 0 1 0 1 0 0 0 1 1 0 Trang 51
  55. Cài đặt: #include #include #include #define TenFile "Bai1.inp" //doc du lieu tu tap tin void Doc_File(int A,int &n) { FILE*f = fopen(TenFile,"rb"); fscanf(f,"%d",&n); *A = new int [n]; cout 0) { DanhDau[j] = 1; ThanhCong = 0; //con kha nang loang Dem++; if(Dem == n) return 1; Trang 52
  56. } } }while (ThanhCong == 0); //lap lai cho den khi khong con kha nang loan return 0; } //chuong trinh chinh void main() { clrscr(); int A,n; Doc_File(A,n); if (Lien_Thong(A,n)==1) cout<<"\nDO THI LIEN THONG"; else cout<<"\nDO THI KHONG LIEN THONG"; delete *A; getch(); } Bài tập 2. Đếm số thành phần liên thông Mô tả bài toán: cho đồ thị vô hướng G=(V,E) hãy đếm số thành phần liên thông của đồ thị G. Ý tưởng thuật toán: Bước 0: khởi tạo số thành phần liên thông bằng 0. Bước 1: xuất phát từ một đỉnh chưa được đánh dấu của đồ thị. Ta đánh dấu đỉnh xuất phát, tăng số thành phần liên thông lên 1 và chuyển sang bước 2. Bước 2: từ một đỉnh i đã đánh dấu, ta đánh dấu đỉnh j nếu A[i,j] = 1 và j chưa được đánh dấu và chuyển sang Bước 3. Bước 3: thực hiện Bước 2 cho đến khi không còn thực hiện được nữa chuyển sang Bước 4. Bước 4: nếu số số đỉnh đánh dấu bằng n kết thúc thuật toán, ngược lại quay về Bước 1. Mô tả dữ liệu đầu vào và đầu ra của bài toán: Dữ liệu vào: cho trong tập tin Bai1.inp - Dòng đầu ghi số n là số đỉnh của một đồ thị (0<n<100). - Dòng i+1 (1 i n ) 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: xuất ra màn hình số thành phần liên thông của đồ thị. Ví dụ: Trang 53
  57. Bai2.inp OUTPUT 6 0 1 1 0 0 0 1 0 1 0 0 0 THANH PHAN 1 1 0 0 0 0 LIEN THONG: 2 0 0 0 0 1 1 0 0 0 1 0 1 0 0 0 1 1 0 Bai2.inp OUTPUT 8 0 1 0 0 0 1 0 0 1 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 THANH PHAN 0 0 1 0 1 0 0 0 LIEN THONG: 1 0 0 0 1 0 1 0 0 1 0 0 0 1 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 Cài đặt: #include #include #include #define TenFile "Bai2.inp" //doc du lieu tu tap tin void Doc_File(int A,int &n) { FILE*f = fopen(TenFile,"rb"); fscanf(f,"%d",&n); *A = new int [n]; cout<<"Ma Tran Lien Ket Cua Do Thi"; for(int i =0;i<n;i++) { A[i] = new int [n]; cout<<endl; for(int j =0;j<n;j++) { fscanf(f,"%d",&A[i][j]); cout<<" "<<A[i][j]; } } fclose(f); } //ham tra ve so thanh phan lien thong cua do thi int TPLien_Thong(int A, int n) { char*DanhDau = new char [n]; char ThanhCong; Trang 54
  58. int Dem=0, i,j, MLT=0; for( i = 0; i 0) { DanhDau[j] = 1; ThanhCong =1; Dem++; if(Dem == n) return MLT; } }while (ThanhCong == 1); } while(Dem<n); //lap lai khi con dinh chua duoc danh dau return MLT; } //chuong trinh chinh void main() { clrscr(); int A,n; Doc_File(A,n); cout<<"\nTHANH PHAN LIEN THONG: "<<TPLien_Thong(A,n); delete *A; getch(); } Trang 55
  59. Bài tập 3. Tìm mọi đường đi từ giữa hai đỉnh Mô tả bài toán: cho đồ thị vô hướng G=(V,E) hãy xác định mọi đường đi từ đỉnh D tới đỉnh C của đồ thị G. Ý tưởng thuật toán: sử dụng kỹ thuật tìm kiếm theo chiều sâu. Mô tả dữ liệu đầu vào và đầu ra của bài toán: Dữ liệu vào: đồ thị liên thông và cho trong tập tin Bai3.inp - Dòng đầu ghi số n là số đỉnh của một đồ thị (0 #include #include #define FileIn "Bai3.inp" int Dem = 0; //dem so duong di int *L; //luu duong di char *DanhDau; //danh dau dinh da di int A,n,D,C; //doc du lieu tu tap tin void Doc_File() { Trang 56
  60. FILE*f = fopen(FileIn,"rb"); fscanf(f,"%d%d%d",&n,&D,&C); cout " 0 && DanhDau[i] == 0 ){ L[SoCanh] = i; //luu dinh da di qua DanhDau[i] = 1; //danh dau dinh da di qua Try(SoCanh+1); //tim kiem dinh tiep theo Trang 57
  61. L[SoCanh] = 0; DanhDau[i] = 0; //phuc hoi dinh da di qua } } } //chuong trinh chinh void main() { Doc_File(); KhoiTao(); cout<<"Duong di tu "<<D+1<<" den "<<C+1; Try(1); if(Dem==0) cout<<" khong co duong di"; delete*A,DanhDau,L; getch(); } Bài tập 4. Đường đi Hamilton Mô tả bài toán: cho đồ thị vô hướng G=(V,E) hãy xác định mọi đường đi từ đỉnh xuất phát đi qua tất cả các đỉnh mỗi đỉnh chỉ qua duy nhất 1 lần. Ý tưởng thuật toán: sử dụng kỹ thuật tìm kiếm theo chiều sâu bằng cách đánh dấu đỉnh đã đi qua trong quá trình tìm kiếm. Mô tả dữ liệu đầu vào và đầu ra của bài toán: Dữ liệu vào: cho trong tập tin Bai4.inp - Dòng đầu ghi số n là số đỉnh của một đồ thị (0<n<100) - Dòng 2 ghi đỉnh xuất phát. - Dòng i+2 (1 i n ) 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 qua tất cả các đỉnh (nếu có). Ví dụ: Bai4.inp OUTPUT 6 1 0 1 1 0 0 0 1 0 1 0 1 0 KHONG TON TAI 1 1 0 0 0 1 DUONG DI 0 0 0 0 1 0 0 1 0 1 0 0 0 0 1 0 0 0 Trang 58
  62. Bai4.inp OUTPUT 5 1 0 1 0 0 0 1 0 1 1 1 1 2 3 4 5 0 1 0 1 0 0 1 1 0 1 0 1 0 1 0 Cài đặt: #include #include #include #define FileIn "Bai4.inp" int Dem = 0; //dem so duong di int *L; //luu duong di char *DanhDau; //danh dau dinh da di int A,n,D; //doc du lieu tu tap tin theo yeu cau cua bai toan void Doc_File() { FILE*f = fopen(FileIn,"rb"); fscanf(f,"%d%d",&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 ; } //khoi tao du lieu ban dau cho bai toan void KhoiTao() { DanhDau = new char [n]; L = new int [n]; for (int i = 0; i<n; i++) { DanhDau[i] = 0; //tat ca cac dinh dieu danh dau L[i] = 0; } DanhDau[D] = 1; //danh dau dinh xuat phat Trang 59
  63. L[0] = D; } //xuat duong di ra man hinh void InDuongDi(int Dinh) { Dem++; cout " 0 && DanhDau[i] == 0){ L[Dinh] = i; DanhDau[i] = 1; //danh dau dinh da di qua Try(Dinh+1); //tim kiem dinh tiep theo L[Dinh] = 0; DanhDau[i] = 0; //phuc hoi dinh da danh dau } } } void main() { clrscr(); Doc_File(); KhoiTao(); cout<<"Duong di"; Try(1); if(Dem==0) cout<<" khong co."; delete*A,DanhDau,L; getch(); } Trang 60
  64. Bài tập 5. Đường đi Euler Mô tả bài toán: cho đồ thị vô hướng G=(V,E) hãy xác định mọi đường đi qua tất cả các cạnh mỗi cạnh chỉ qua duy nhất 1 lần. Ý tưởng thuật toán: sử dụng kỹ thuật tìm kiếm theo chiều sâu bằng cách xóa cạnh đã đi qua trong quá trình tìm kiếm đường đi. Mô tả dữ liệu đầu vào và đầu ra của bài toán: Dữ liệu vào: cho trong tập tin Bai5.inp - Dòng đầu ghi số n là số đỉnh của một đồ thị (0 2->3->4->5->2->1 0 1 1 0 1 0 1 0 1 0 Cài đặt: #include #include #include #define Filename "Bai5.inp" int Dem = 0, SoCanh=0; //dem so duong di va luu so canh cua do thi int *L; //luu dinh da di qua int A,n; int XuatPhat=0; //dinh xuat phat la dinh bac le neu do thi co dinh bac le void Doc_File() { int BacDinh; FILE*f = fopen(Filename,"rb"); fscanf(f,"%d",&n); cout<<"Ma Tran Lien Ket Tuong Ung.\n"<<n<<endl; *A = new int [n]; for(int i =0;i<n;i++) { A[i] = new int [n]; BacDinh = 0; for(int j =0;j<n;j++) { fscanf(f,"%d",&A[i][j]); cout<<A[i][j]<<" "; Trang 61
  65. if(A[i][j] == 1) BacDinh++; } if(BacDinh%2==1) XuatPhat = i; //xuat phat tu dinh bac le SoCanh+=BacDinh; cout " SoCanh) //tim du so canh thi xuat duong di InDuongDi(); else { for(int i = 0; i 0){ L[Canh] = i; A[L[Canh-1]][i]=A[i][L[Canh-1]]=0; //xoa canh Try(Canh+1); //tim canh tiep theo A[L[Canh-1]][i]=A[i][L[Canh-1]]=1; //phuc hoi canh L[Canh] = 0; } } } void main() { Doc_File(); cout<<"\nDUONG DI"; Try(1); if(Dem==0) cout<<" KHONG CO"; delete*A,L; getch(); } Trang 62
  66. Bài tập 6. Thuật toán Dijkstra tìm đường đi ngắn nhất Mô tả bài toán: cho đồ thị vô hướng G=(V,E) hãy xác định đường đi ngắn nhất từ đỉnh D tới đỉnh C của đồ thị G. Ý tưởng thuật toán: sử dụng thuật toán Dijkstra. Mô tả dữ liệu đầu vào và đầu ra của bài toán: Dữ liệu vào: đồ thị đã liên thông và cho trong tập tin Bai6.inp. - Dòng đầu ghi số n là số đỉnh của một đồ thị (0 #include #include #include #define max 100 #define FileIn "Bai6.inp" 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); cout<<"Ma Tran Lien Ket Tuong Ung.\n"; cout<<D<<" "<<C<<endl; for(int i =0;i<n;i++) { for(int j =0;j<n;j++) { fscanf(f,"%d",&A[i][j]); cout<<A[i][j]<<" "; } cout<<endl; Trang 63
  67. } fclose(f); D ; C ; } void Dijkstra(int A[max][max], int n, int D, int C) { char DanhDau[max]; int Nhan[max], Truoc[max], XP, min; for(int i=0; i 0 && Nhan[j]>A[XP][j]+Nhan[XP] && DanhDau[j]==0) { Nhan[j] = A[XP][j]+Nhan[XP]; Truoc[j] = XP; } min = MAXINT; for(j = 0; j Nhan[j]&& DanhDau[j]==0){ min = Nhan[j]; XP = j; } DanhDau[XP] = 1; } cout<<"Duong Di Ngan Nhat La:"<<Nhan[C]<<endl; cout<<C+1<<" <- "<<Truoc[C]+1; i = Truoc[C]; while(i!=D){ i = Truoc[i]; cout<<" <- "<<i+1; } } void main() { int A[max][max],n,Dau,Cuoi; Doc_File(A,n,Dau,Cuoi); Dijkstra(A,n,Dau,Cuoi); getch(); } Trang 64
  68. Bài tập 7. Thuật toán Prim tìm cây bao trùm tối tiểu Mô tả bài toán: cho đồ thị vô hướng có trọng số G=(V,E) hãy tìm đường đi sao cho tất cả các đỉnh điều có đường đi với nhau và tổng trọng số của đường đi là nhỏ nhất. Tức là tìm đồ thị con liên thông G' G sao cho tổng trọng số của G’ là nhỏ nhất. Ý tưởng thuật toán: Bước 1: xuất phát từ đỉnh k bất kỳ (thông thường chọn đỉnh đầu tiên) chọn một cạnh có trọng số nhỏ nhất liền kề với đỉnh k (min{A[k][j]}j=1 n) ta đánh dấu 2 đỉnh đi qua cạnh đó và số cạnh tìm được là 1. Chuyển sang Bước 2. Bước 2: tìm cạnh nhỏ nhất của đồ thị với điều kiện cạnh tìm được phải có 1 đỉnh chưa đánh dấu và 1 đỉnh đã đánh dấu. Nghĩa là, ta tìm min{A[i][j]}j=1 n, i=1 n sao cho i đánh đấu và j chưa đánh dấu để tránh trường hợp tạo thành chu trình con. Ta tăng số cạnh tìm được lên 1 và chuyển sang Bước 3. Bước 3: nếu số cạnh tìm được bằng n-1 kết thúc thuật toán, ngược lại quay về Bước 2. Mô tả dữ liệu đầu vào và đầu ra của bài toán: Dữ liệu vào: lưu trong tập tin Bai7.inp - Dòng đầu ghi số n là số đỉnh của một đồ thị (0 #include #define max 100 #define FileInt "Bai7.inp" #define FileOut "Bai7.out" typedef struct Egde { int x,y; }; Trang 65
  69. //doc du lieu tu tap tin void Doc_File(int A[max][max],int &n) { FILE*f = fopen(FileInt,”rb”); fscanf(f,”%d”,&n); for(int i =0;i A[0][j] && A[0][j]!=0){ min = A[0][j]; L[0].y = j; } L[0].x = 0; D[0] = 1; D[L[0].y] = 1; Sum+=min; Dem++; do { min = MAXINT; for( i=0; i 0 && min>A[i][j] && D[j]==0){ min = A[i][j]; Trang 66
  70. L[Dem].x = i; L[Dem].y = j; } Sum+=min; D[L[Dem].y] = 1; Dem++; } while(Dem<n-1); Ghi_File(L,n,Sum); } //chuong trinh chinh void main() { int A[max][max],n; Doc_File(A,n); Prim(A,n); } Bài tập 8. Thuật toán Kruskal tìm cây bao trùm tối tiểu Mô tả bài toán: cho đồ thị vô hướng có trọng số G=(V,E) hãy tìm đường đi sao cho tất cả các đỉnh điều có đường đi với nhau và tổng trọng số của đường đi là nhỏ nhất. Tức là tìm đồ thị con liên thông G' G sao cho tổng trọng số của G’ là nhỏ nhất. Ý tưởng thuật toán: Bước 0: khởi tạo tập cạnh tìm được là rỗng và chuyển sang Bước 1. Bước 1: chọn một cạnh có trọng số nhỏ nhất sao cho khi đưa cạnh này vào tập cạnh tìm được không tạo thành chu trình. Tăng số cạnh tìm được lên 1 và chuyển sang Bước 2. Bước 2: nếu số cạnh tìm được bằng n-1 thuật toán kết thúc, ngược lại quay về Bước 1. Mô tả dữ liệu đầu vào và đầu ra của bài toán: Dữ liệu vào: lưu trong tập tin Bai8.inp - Dòng đầu ghi số n là số đỉnh của một đồ thị (0<n<100) - Dòng i+1 (1 i n ) lưu ma trận kề của đồ thị với 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: lưu trong file Kruskal.out - Dòng đầu ghi trọng số nhỏ nhất của cây bao trùm. - Các dòng còn lại lưu đường đi giữa đỉnh i nối với đỉnh j. Trang 67
  71. Ví dụ: Bai8.inp Bai8.out 8 20 0 2 3 4 0 0 0 0 6 - 7 2 0 3 0 4 0 0 0 1 - 2 3 3 0 7 6 5 2 0 3 - 7 4 0 7 0 0 0 3 0 1 - 3 0 4 6 0 0 4 0 8 4 - 7 0 0 5 0 4 0 1 6 2 - 5 0 0 2 3 0 1 0 5 7 - 8 0 0 0 0 8 6 5 0 Cài đặt: #include #include #define FileInt "Bai8.inp" #define FileOut "Bai8.out" typedef struct Egde { int x,y; }; //doc du lieu tu tap tin void Doc_File(int A,int &n) { FILE*f = fopen(FileInt,"rb"); fscanf(f,"%d",&n); *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]); } } fclose(f); } //ghi du lieu ra tap tin void Ghi_File(Egde*L,int n,int Sum) { FILE*f = fopen(FileOut,"wb"); fprintf(f,"%d\n",Sum); for(int i =0; i<n-1; i++) fprintf(f,"%d - %d\n",L[i].x+1,L[i].y+1); fclose(f); } void Kruskal(int A, int n) { int *D = new int[n]; Egde *L = new Egde[n-1]; Trang 68
  72. int min = MAXINT, Dem = 0, Sum = 0, T = 0, Temp; for(int i=0; i 0 && min>A[i][j]&& !(D[i]!=0 && D[i]==D[j])) { min = A[i][j]; L[Dem].x = i; L[Dem].y = j; } if(D[L[Dem].x] ==0 && D[L[Dem].y] == 0){ T++; D[L[Dem].x] = D[L[Dem].y] = T; } if(D[L[Dem].x] == 0 && D[L[Dem].y] != 0){ D[L[Dem].x] = D[L[Dem].y]; } if(D[L[Dem].x] != 0 && D[L[Dem].y] == 0){ D[L[Dem].y] = D[L[Dem].x]; } if(D[L[Dem].x] != D[L[Dem].y] && D[L[Dem].y]!=0) { Temp = D[L[Dem].x]; for( i=0; i<n; i++) if(Temp==D[i]) D[i]=D[L[Dem].y]; } Sum+=min; Dem++; } while(Dem<n-1); Ghi_File(L,n,Sum); } //chuong trinh chinh void main() { int A,n; Doc_File(A,n); Kruskal(A,n); delete *A; } Trang 69
  73. TÀI LIỆU THAM KHẢO [1] Chu Đức Khánh, Nguyễn Cam, Lý thuyết đồ thị, NXB Đại học Quốc gia TPHCM. [2] Dương Thủy Vỹ, Giáo trình Phương pháp tính, NXB KHKT. [3] Ngọc Anh Thư, Giáo trình thuật toán, NXB Thống kê. [4] Ngô Đắc Tân, Lý thuyết tổ hợp và đồ thị, NXB ĐH Quốc gia Hà Nội. [5] Dương Vũ Diệu Trà, Nguyễn Tiến Huy, Trần Đan Thư, Vũ Mạnh Trường, Cẩm nang thuật toán, NXB KHKT. [6] Đỗ Xuân Lôi, Cấu trúc dữ liệu & Giải thuật, 1995. [7] Nguyễn Đức Nghĩa, Tô Văn Thành, Toán rời rạc, 1997. [8] A.V. Aho, J.E. Hopcroft, J.D. Ullman, Data Structures and Algorithms, Addison – Wesley, 1983. [9] Jeffrey H Kingston, Algorithms and Data Structures, Addison-Wesley, 1998.