Giáo trình thực hành Lập trình nâng cao - Trường ĐH Cửu Long

Chia sẻ: Hương Hoa Cỏ Mới | Ngày: | Loại File: PDF | Số trang:73

Thêm vào BST

Báo xấu

34
lượt xem 2
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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. Mời các bạn cùng tham khảo!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Giáo trình thực hành Lập trình nâng cao - Trường ĐH Cửu Long

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
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ả
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
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; coutn; cout
return X*Power(X,n-1); } /*Chuong trinh chinh*/ void main() { clrscr(); int n; float X; coutn; coutX; cout
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 a 0 ,..., a n1 , n    UCLN a n1 ,UC a0 ,..., a n 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; coutn; a = new int[n]; cout
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; coutn; cout
} /*Chuong trinh chinh*/ void main() { clrscr(); int n,k; coutn; coutk; cout
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 Y  1  0   X n  X n1  Yn1 Yn  2 X 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; coutn; cout
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 ,..., a n 1 được định nghĩa đệ quy như sau: a 0 ,n 1 S a 0 ,..., a n1 , n    a n1 S a 0 ,..., a n 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; coutn; a = new int[n]; cout
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  a 0 ,..., a n 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  a n  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; coutn; a = new int[n]; cout
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
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
} } /*Chuong trinh chinh*/ void main() { clrscr(); coutk; cout
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() { coutn; coutk; //khoi tao tat ca cac dinh chua duoc chon for(int i = 0; i
} } } /*Chuong trinh chinh*/ void main() { clrscr(); cout
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() { coutn; for(int i = 0; i
} /*Chuong trinh chinh*/ void main() { clrscr(); Init(); cout
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() { coutn; //tat ca cac cot chua duoc chon for(int i = 0; i
cout