Giáo trình Kỹ thuật lập trình 2

122 trang vanle 1900

Download

Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình Kỹ thuật lập trình 2", để 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:

giao_trinh_ky_thuat_lap_trinh_2.pdf

Nội dung text: Giáo trình Kỹ thuật lập trình 2

Giáo trình Kỹ thuật lập trình 2 
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN MỤC LỤC Mục lục 1 Lời nĩi đầu 3 Chương 1 Một số kỹ thuật – phong cách lập trình tốt 4 1.1 Cách đặt tên cho biến hàm 4 1.2 Phong cách viết mã nguồn 6 1.3 Tối ưu sự thực thi mã nguồn 8 Chương 2 Kỹ thuật đệ quy 16 2.1 Kỹ thuật đệ quy 16 2.2 Xây dựng một chương trình đệ quy 20 2.3 Các ví dụ đệ quy 21 2.4 Khử đệ quy 27 2.4.1 Tìm hiểu cơ chế thực hiện hàm đệ quy 27 2.4.2 Các trường hợp khử đệ quy đơn giản 29 2.4.3 Khử đệ quy dùng stack 31 Chương 3 Bài tốn liên quan tổ hợp 37 3.1 Phương pháp sinh (kế tiếp) 37 3.1.1 Bài tốn sinh dãy nhị phân độ dài n 37 3.1.2 Bài tốn liệt kê tập con k phần tử 39 3.1.3 Bài tốn liệt kê các hốn vị 42 3.2 Thuật tốn quay lui (Back Tracking) 45 3.2.1 Thuật tốn quay lui liệt kê dãy nhị phân n 47 3.2.2 Thuật tốn quay lui liệt kê tập con k phần tử 48 3.2.3 Thuật tốn quay lui liệt kê hốn vị n phần tử 50 3.2.4 Bài tốn sắp xếp quân Hậu 51 3.2.5 Bài tốn mã đi tuần 57 Chương 4 Tìm kiếm và Sắp xếp 63 4.1 Tìm kiếm 63 4.1.1 Mơ tả bài tốn tìm kiếm trong tin học 63 4.1.2 Tìm kiếm tuyến tính 64 4.1.3 Tìm kiếm nhị phân 65 4.1.4 Kết luận 67 4.2 Bài tốn sắp xếp 67 4.3 Một số phương pháp sắp xếp cơ bản 67 4.3.1 Phương pháp chọn 67 4.3.2 Phương pháp sắp xếp nổi bọt 68 4.3.3 Phương pháp sắp xếp chèn 68 4.3.4 Phương pháp đổi chỗ trực tiếp 69 4.3.5 Phương pháp ShellSort 73 4.3.6 Phương pháp phân đoạn QuickSort 76 4.3.7 Phương pháp cơ số RadixSort 80 Chương 5 Stack - Queue 84 5.1 Giới thiệu Stack – ngăn xếp 84 5.1.1 Cài đặt Stack dùng CTDL mảng 85 5.1.2 Các ứng dụng stack 87 1
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN 5.1.3 Các ví dụ minh họa 88 5.2 Giới thiệu Queue – hàng đợi 103 5.2.1 Cài đặt Queue dùng CTDL mảng 105 5.2.2 Các ứng dụng Queue 106 BÀI TẬP 114 TÀI LIỆU THAM KHẢO 121 \[ 2
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN Lời nĩi đầu Học phần kỹ thuật lập trình 2 được thiết kế dành cho sinh viên khoa cơng nghệ thơng tin ĐH Kỹ Thuật Cơng Nghệ, là phần tiếp nối với mơn kỹ thuật lập trình 1. Mục đích của mơn học là bổ sung những kỹ thuật lập trình đệ quy, khử đệ quy, các bài tốn trên tập hợp, phương pháp sinh, kỹ thuật quay lui, tìm kiếm và sắp xếp trên mảng, ngăn xếp và hàng đợi Song song với phần lý thuyết là các ví dụ minh họa cụ thể, cho phép sinh viên hiểu rõ vấn đề hơn. Ngồi những kỹ thuật lập trình, giáo trình cịn đề cập tới phương diện phong cách lập trình trong chương 1. Việc sớm làm quen với phong cách lập trình sẽ hỗ trợ sinh viên hồn thiện kỹ năng viết chương trình. Bài giảng được viết lần đầu tiên nên sẽ khơng tránh khỏi những sai sĩt. Kính mong sự đĩng gĩp của các giảng viên và sinh viên nhằm hồn thiện phần bài giảng này trong lần tái bản sau. Tất cả những ý kiến đĩng gĩp điều được trân trọng. Xin chân thành cảm ơn! Tác giả 3
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN Chương 1 Một số kỹ thuật – phong cách lập trình tốt \[ Một chương trình nguồn được xem là tốt khơng chỉ được đánh giá thơng qua thuật giải đúng và cấu trúc dữ liệu thích hợp. Mà cịn phụ thuộc vào phong cách và kỹ thuật mã hố (coding) của người viết chương trình. Nếu một người lập trình viết một chương trình tuy thực hiện đúng yêu cầu đặt ra nhưng mã nguồn quá lộn xộn và phong cách lập trình cẩu thả, thì mã nguồn này sẽ gây khĩ khăn cho chính người lập trình! Đơi khi người mới lập trình khơng quan tâm đến vấn đề này do ban đầu chỉ làm việc với chương trình nhỏ. Tuy nhiên, vấn đề phát sinh khi họ phải làm việc với dự án lớn và chương trình lúc này khơng cịn đơn giản vài chục dịng lệnh nữa. Nếu khơng rèn luyện một phong cách và trang bị một số kỹ thuật lập trình tốt thì người lập trình đối mặt với nhiều khĩ khăn Trong chương đầu tiên xin giới thiệu một số kỹ thuật và phong cách lập trình cơ bản, ít nhiều giúp cho người học viết chương trình được tốt hơn. 1.1 Cách đặt tên cho biến hàm Thơng thường tùy theo ngơn ngữ và mơi trường lập trình, người viết chương trình thường chọn cho mình một phong cách nhất quán trong việc đặt tên các định danh. Một số quy tắc cần quan tâm khi đặt tên như sau: 1. Tên của định danh phải thể hiện được ý nghĩa: thơng thường các biến nguyên như i, j, k dùng làm biến lặp; x, y dùng làm biến lưu tọa độ Cịn những biến lưu trữ dữ liệu khác thì nên đặt gợi nhớ: biến đếm số lần dùng “count” hay So_Luong, biến lưu trọng lượng “weight”, chiều cao “height” Nếu đặt quá ngắn gọn như c cho biến đếm, hay w cho khối lượng thì sau này khi nhìn vào chương trình sẽ rất khĩ hiểu! 2. Tên phải xác định được kiểu dữ liệu lưu trữ: phong cách lập trình tốt là khi người đọc nhìn vào một biến nào đĩ thì xác định ngay được kiểu dữ liệu mà 4
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN biến đĩ lưu trữ. Giả sử cĩ biến đếm số lần thì ta cĩ thể đặt iCount, trong đĩ i là kiểu của dữ liệu, strContent là kiểu chuỗi Cĩ nhiều cú pháp quy ước đặt tên biến, người lập trình cĩ thể chọn cho mình một quy ước thích hợp. Cĩ thể tham khảo một số quy ước trong phần 3 bên dưới. 3. Theo một quy ước cụ thể: a. Cú pháp Hungary: hình thức chung của cú pháp này là thêm tiền tố chứa kiểu dữ liệu vào tên biến. Bảng 1.1 bên dưới là một số tiền tố quy ước được nhiều lập trình viên sử dụng. Các cơng ty phần mềm thường cĩ các quy ước về cách đặt tên biến cho đội ngũ lập trình viên. Tuy nhiên đa số các quy ước này đều dựa trên cú pháp Hungary. Tiền tố Kiểu dữ liệu Minh họa b boolean bool bStop c char char cLetterGenre str/s C++ string string strFirstName si short integer short siTables i/n integer int iCars int nCars li long integer long liStars f floating point float fPercent d Double precision floating point double dMiles ld long double precision floating long double ldPI point sz Null terminated string char szName[NAME_LEN] if Input file stream ifstream ifNameFile is Input stream istream isInput of Output file stream ofstream ofNameFile os Output stream ostream osOut S Struct struct sPoint { } C Class class CStudent { } w Word word wChar 5
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN u Unsigned m_ biến thành viên của hàm class CStudent { private: string m_strName; } g_ biến tồn cục string g_strBuff lp long pointer LPCTSTR lpszClassName h handle trong windows HINSTANCE hInstance Bảng 1.1: Minh họa tiền tố của cú pháp Hungary. Đối với những hằng thì tất cả các ký tự đều viết hoa #define MAXSIZE 100 const int MAXLENGTH 200 Cách đặt tên cho hàm: hàm bắt đầu với ký tự đầu tiên là ký tự hoa và khơng cĩ tiền tố. Tuy nhiên, điều này cũng khơng bắt buộc tuỳ theo ngơn ngữ lập trình. Nĩi chung là hàm cĩ chức năng thực hiện một chức năng nào đĩ, cho nên chúng thường bắt đầu bằng động từ: get, set, do CString GetName(); // Microsoft VC++ standard String setName(); // Sun Java standard 1.2 Phong cách viết mã nguồn Sử dụng tab để canh lề chương trình: khi soạn thảo mã nguồn nên dùng tab với kích thước là 4 hay 8 để canh lề. Thĩi quen này giúp cho chương trình được rõ ràng và dễ quản lý. for (i = 0;i < N; i++) for (i = 0; i < N; i++) { { if (Check(i)) if (Check(i)) { { Action1(); Action1(); Action2(); Action2(); } } else else Action3(); Action3(); ActionMain(); ActionMain(); } } 6
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN Sử dụng khoảng trắng: chương trình sẽ dễ nhìn hơn. int count; int count; for(count=0;count 5){b=a;a++;} if (a > 5) { b=a; a++; } Định nghĩa các hằng số: một thĩi quen là người lập trình khơng định nghĩa những hằng số thường xuyên sử dụng. Dẫn đến những con số khĩ hiểu xuất hiện trong chương trình, một số tài liệu lập trình gọi những con số này là “magic mumber”. #define MAX_LEN 100 for(int i=0; i < 100; i ++) #define MAX_NUM 100 A[i] = Rand(100); for(int i=0; i < MAX_LEN; i++) k = InputNum(); A[i] = Rand(MAX_NUM); j=0; while (A[j] != k && j < 100) k = InputNum(); j++; j=0; while (A[j] != k && j < MAX_LEN) j++; Trong đoạn chương trình bên trái rất khĩ phân biệt giá trị 100 ở ba vị trí cĩ mối quan hệ gì với nhau. Tuy nhiên, trong đoạn bên phải ta dễ dàng thấy được ý nghĩa của từng giá trị khi thay bằng định danh. Ngồi ra khi cần thay đổi giá trị của MAX_LEN, MAX_NUM thì chỉ cần thay một lần trong phần định nghĩa. Do đĩ đoạn chương trình B dễ nhìn hơn và dễ thay đổi hơn! Viết chú thích cho chương trình: biến, hàm khi định nghĩa nên viết chú thích ý nghĩa và chức năng rõ ràng. Đơi khi các lệnh thực thi cũng cần cĩ giải thích nếu chúng quá phức tạp. int CheckFactor(int n) { 7
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN /* Ý nghĩa: kiểm tra xem 1 số cĩ phải là nguyên tố hay khơng Tham số vào: n số cần kiểm tra Tham số ra: giá trị trả về 0: khơng phải số nguyên tố 1: là số nguyên tố */ .// phần thực hiện của hàm } Ví dụ chú thích cho biến byte Image; // buffer ảnh int Rows, Cols; // số dịng, số cột int r, c; // dịng cột hiện hành int PixelCount; // tổng số pixel Tuy nhiên khơng phải bất cứ lệnh nào cũng chú thích, việc chú thích tràn lan ngay cả với câu lệnh đơn giản cũng khơng cĩ ý nghĩa gì. Đơi khi cịn làm cho chương trình khĩ nhìn hơn! Nên viết biểu thức điều kiện mang tính tự nhiên: biểu thức nên viết dưới dạng khẳng định, việc viết biểu thức dạng phủ định sẽ làm khĩ hiểu! if ( !(iBlock = Block2)) Mỗi biểu thức trong điều kiện được viết dưới dạng phủ định, ta nên viết lại dưới dạng khẳng định cho dễ hiểu hơn: if ( (iBlock >= Block1 ) || (iBlock < Block2)) Dùng chính ngơn ngữ đĩ để tính kích thước của đối tượng: khơng nên dùng giá trị tường minh cho kích thước của dữ liệu. Khi cần lấy kích thước của biến int, ta cĩ thể dùng sizeof(int) thay cho các giá trị 2 hay 4. Tương tự như vậy khi lấy kích thước của phần tử trong một mảng int ta dùng sizeof(array[0]) thay cho sizeof(int). Sau này khi mảng array cĩ thay đổi kiểu dữ liệu thì cách viết sizeof(array[0]) cũng khơng ảnh hưởng. 1.3 Tối ưu sự thực thi mã nguồn Mã nguồn nếu được viết tốt sẽ làm cho tốc độ chương trình cải thiện đáng kể. Cĩ thể ngày nay năng lực xử lý của máy tính khá mạnh, do đĩ người lập trình khơng quan tâm đến việc tối ưu mã nguồn. Nhưng cũng khơng vì thế mà bỏ qua kỹ thuật 8
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN này. Vậy thế nào là tối ưu mã nguồn? ở đây khơng đề cập đến giải thuật, vì chắc chắn giải thuật tốt thì sẽ cho chương trình tối ưu. Tuy nhiên, việc cài đặt cũng cần phải cĩ kỹ thuật, nếu khơng thì chính khả năng cài đặt của lập trình viên làm hạn chế sự thực thi của thuật giải hay chương trình. Mục đích của việc tối ưu mã nguồn là nâng cao tốc độ xử lý và hạn chế khơng gian bộ nhớ mà chương trình chiếm dụng. Thơng thường cĩ thể mâu thuẫn giữa tốc độ và khơng gian lưu trữ, do đĩ tuỳ theo điều kiện cụ thể mà người lập trình cĩ thể lựa chọn thích hợp. Trong phần dưới xin trình bày một số thủ thuật chọn lọc cĩ thể giúp ích để hình thành nên phong cách lập trình tốt cho người đọc. Thu gọn những biểu thức dùng nhiều lần: nếu một biểu thức tính tốn được dùng nhiều lần thì chúng ta nên tính kết quả một lần rồi lưu vào một biến và dùng lại. Ví dụ: F = sqrt(dx*dx+dy*dy) + (sqrt(dx*dx + dy*dy)*sqrt(dx*dx)-sqrt(dy*dy)) Trong dãy biểu thức trên cĩ sqrt(dx*dx+dy*dy), dx*dx, dy*dy được dùng nhiều chỗ, ta cĩ thể tính trước bên ngồi và lưu vào biến tạm để dùng lại sau này. Hạn chế việc tính tốn với cùng một biểu thức nhiều lần! Đưa những biểu thức khơng phụ thuộc vịng lặp ra ngồi: trong một số vịng lặp ta cĩ sử dụng biểu thức tính tốn nhưng giá trị của biểu thức khơng phụ thuộc vào sự thay đổi của vịng lặp thì cĩ thể đưa biểu thức này ra ngồi. Ví dụ: for(i =0; i < strlen(str); i++) . chuyển thành: int n = strlen(str) for(i =0; i < n; i++) . Thay thế một biểu thức bằng một biểu thức tương đương nhưng lợi về thực thi: một số chương trình xử lý ảnh địi hỏi tốc độ cao, thì người lập trình cĩ thể thay thế các phép nhân chia bằng phép dịch chuyển bit. Thay thế sử dụng chỉ mục trong mảng C/C++ bằng con trỏ 9
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN Ví dụ: khi so sánh khoảng cách của hai điểm ta thường làm như sau if (sqrt(dx1*dx1+dy1*dy1) < sqrt(dx2*dx2+dy2*dy2)) Thay bằng if ((dx1*dx1+dy1*dy1) < (dx2*dx2+dy2*dy2)) Dùng số nguyên thay cho số thực: do việc xử lý số thực chậm hơn xử lý số nguyên nên ta cĩ thể dùng số nguyên thay cho số thực cĩ phần lẻ nhỏ. Ví dụ: điểm trung bình của sinh viên là số thực ta cĩ thể thay bằng số nguyên: DTB là 8.72 thì lưu theo số nguyên 872, khi xuất ra thì chia cho 100. Loại bỏ vịng lặp: nếu thân vịng lặp đơn giản và số lần lặp cũng khơng nhiều, ta cĩ thể làm cho đoạn chương trình hiệu quả hơn bằng cách bỏ vịng lặp. Ví dụ: for(i =0; i < 3; i++) A[i] = B[i] + C[i]; Thay bằng A[1] = B[1] + C[1]; A[2] = B[2] + C[2]; A[3] = B[3] + C[3]; Đoạn chương trình thay thế loại bỏ vịng lặp, tức là lệnh rẽ nhánh, lệnh rẽ nhánh làm chậm chương trình do ngắt luồng thực thi. Nếu vịng lặp dài và cùng dạng biểu thức ta cĩ thể cải tiến như ví dụ sau for(i=0; i < 3*n; i++) A[i] = B[i] + C[i]; Thay bằng for(i=0; i < 3*n; i+=3) { A[i] = B[i] + C[i]; A[i+1] = B[i+1] + C[i+1]; A[i+2] = B[i+2] + C[i+2]; } Ví dụ trên chỉ áp dụng khi chiều dài vịng lặp là bội số của bước nhảy! Loại bỏ câu lệnh rẽ nhánh trong vịng lặp: xem ví dụ sau 10
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN Chương trình A Chương trình B for i to 1000 do if (w) then { for i to 1000 do x[i] = x[i] + y[i]; { if (w) then y[i] = 0; x[i] = x[i] + y[i]; } y[i] = 0; } else for i to 1000 do x[i] = x[i] + y[i]; Trong chương trình A, mỗi lần lặp thì phải kiểm tra thêm điều kiện của w. Trong khi chương trình B thì ta kiểm tra giá trị của w trước khi vào vịng lặp. Do đĩ B cĩ hai vịng lặp nhưng chỉ thực hiện một trong hai và chỉ kiểm tra giá trị w duy nhất 1 lần! Thốt khỏi vịng lặp sớm nhất: một số trường hợp khơng cần phải lặp hết tồn bộ vịng lặp mà đã đạt được mục đích thì cĩ thể thốt ra khỏi vịng lặp. Ví dụ: chỉ cần xác định giá trị -99 cĩ xuất hiện trong danh sách hay khơng ta cĩ hai chương trình A và B minh họa như sau: Chương trình A Chương trình B found = FALSE; found = FALSE; for(i=0;i<10000;i++) for(i=0; i<10000; i++) { { if( list[i] == -99 ) if( list[i] == -99 ) { { found = TRUE; found = TRUE; } break; } } if( found ) printf("Yes, there is a -99."); } if( found ) printf("Yes, there is a -99."); Chương trình A khi tìm thấy thì vẫn cứ lặp cho đến hết, trong khi B thì sẽ thốt ngay. Rõ ràng khi đã tìm thấy thì khơng cần phải lặp tiếp, khi đĩ B sẽ tối ưu hơn! Gom các vịng lặp: các vịng lặp cùng số lần lặp thì nên gom lại Ví dụ: for( int i=0; i<n; i++) a[i]= 0; 11
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN for(i=0; i >3 a = 2*(b+c) ⇒ a = (b+c) y) flag =1; else flag =0; Cải tiến thành: flag = x>y; 12
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN Lưu tạm giá trị thường sử dụng: trong chương trình đơi khi một giá trị được tính tốn một lần nhưng lại thường được sử dụng mà ít cĩ thay đổi giá trị. Khi đĩ ta cĩ thể dùng biến lưu trữ giá trị của biểu thức này, khi nào cần thì cĩ thể sử dụng biến đĩ thay vì phải tính tốn lại. Ví dụ: đoạn chương trình giải phương trình bậc hai. if ((b*b)-4*a*c < 0) printf(“Phuong trinh vo nghiem!”); else if ((b*b)-4*a*c == 0) printf(“Phuong trinh co nghiem kep”); else { x1= (-b + sqrt((b*b)-4*a*c))/(2*a); x2= (-b - sqrt((b*b)-4*a*c))/(2*a); } Trong đoạn chương trình trên delta được tính lại 4 lần, ta cĩ thể cải tiến chỉ tính duy nhất một lần! delta = (b*b)-4*a*c; if ( delta < 0) printf(“Phuong trinh vo nghiem!”); else if (delta == 0) printf(“Phuong trinh co nghiem kep”); 13
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN else { x1= (-b + sqrt(delta))/(2*a); x2= (-b - sqrt(delta))/(2*a); } Tránh lãng phí bộ nhớ: bằng cách sử dụng kiểu dữ liệu nhỏ nhất cĩ thể được để lưu trữ: khơng gian bộ nhớ hiện tại cĩ thể khơng cịn eo hẹp như trước, nhưng khơng vì thế mà người lập trình cĩ thể tự do phung phí cấp cho chương trình. Việc sử dụng quá nhiều tài nguyên hơn mức địi hỏi của chương trình là thĩi quen xấu mà người lập trình hay mắc phải. Hơn nữa tốc độ chương trình sẽ nhanh hơn khi sử dụng kiểu dữ liệu nhỏ hơn. Khai báo biến cục bộ trong phạm vi gần nhất: đúng như tên gọi là biến cục bộ do đĩ khi sử dụng nên khai báo gần với điểm sử dụng nhất. Việc khai báo ở phạm vị rộng hơn chỉ làm lãng phí và khĩ kiểm sốt. Sử dụng macro: một số hàm đơn giản và thường sử dụng cĩ thể chuyển thành macro để tăng tốc độ thực thi của chương trình. Do mỗi lần gọi hàm sẽ tốn chi phí cho việc gọi và trả về từ hàm. Ví dụ: int max(int a, int b) { return a>b? a: b; } Chuyển thành macro: #define max(a, b) ((a)>(b)) ? (a) : (b) Hàm hốn chuyển giá trị 2 số nguyên void swap(int &a, int &b) { int t; 14
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN t = a; a = b; b = t; } Chuyển thành macro swap #define swap(a, b) {int t = a; a = b; b = t;} Giảm số lượng tham số truyền vào hàm: việc sử dụng hàm cĩ quá nhiều tham số được truyền vào cĩ thể làm ảnh hưởng đến ngăn xếp dành cho việc gọi hàm. Nhất là trường hợp tham số là kiểu dữ liệu cấu trúc. Sử dụng con trỏ hay tham chiếu trong trường hợp này để đơn giản hố. Ví dụ : void Print(struct Student s) { printf(“%d”, s.StudentCode); } Thay bằng: void Print(const struct Student *s) { printf(“%d”, s->StudentCode); } \[ 15
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN Chương 2 Kỹ thuật đệ quy \[ 2.1 Kỹ thuật đệ quy Đệ quy là một thuật tốn dùng để đơn giản hĩa những bài tốn phức tạp bằng cách phân nhỏ phép tốn đĩ thành nhiều phần đồng dạng. Qua việc giải những bài tốn được phân nhỏ này, những lời giải sẽ được kết hợp lại để giải quyết bài tốn lớn hơn. Một số các ví dụ đệ quy Định nghĩa số tự nhiên o 0 là số tự nhiên o N là số tự nhiên n-1 là số tự nhiên Định nghĩa giai thừa của n o 0! là 1 o Nếu n>0, n! = n *(n-1)! Hàm đệ quy : Hàm đệ quy là một hàm trong đĩ cĩ dùng lời gọi hàm đến chính bản thân nĩ. Ví dụ ta cĩ hàm đệ quy như sau: int Sum(int n) { if (n==0) return 0; else return (n+Sum(n-1)); // gọi đệ quy đến chính bản thân hàm sum } Khi một hàm đệ quy gọi đến chính nĩ thì mỗi lần gọi máy sẽ tạo ra tập các biến cục bộ mới hồn tồn độc lập với biến cục bộ đã tạo ra trong lần gọi trước. Bao nhiêu lần gọi hàm đệ quy thì tương ứng với bấy nhiêu lần thốt ra khỏi hàm, mỗi lần ra khỏi hàm thì tập biến cục bộ bị xĩa. Cĩ một sự tương ứng giữa các lời gọi hàm và lần thốt khỏi hàm theo thứ tự ngược lại: lần ra khỏi hàm đầu tiên tương ứng với lần gọi hàm cuối cùng. 16
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN Ví dụ minh họa hàm đệ quy: tính giai thừa của n (tích của các số từ 1 đến n). Ta cĩ định nghĩa của giai thừa n như sau: n! = 1.2.3 (n-1).n hoặc định nghĩa: ⎧ 1 n = 0 n! = ⎨ ⎩(n −1)!.n n ≥1 Phương pháp thứ nhất là dùng vịng lặp: long GT(int n) { long result = 1; for(int i=1; i <= n; i++) result *= i; return result; } Phương pháp thứ hai là dùng hàm đệ quy: long Giaithua(int n) { if (n == 0) return 1; else return (n*Giaithua(n-1)); } Phân tích chương trình thực hiện đệ quy: Giả sử chương trình cĩ lời gọi hàm như sau long l = Giaithua(5); 17
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN long l = Giaithua(5) 120 Giaithua(5) n = 5 return 5* Giaithua(4) 24 Giaithua(4) n = 4 return 4* Giaithua(3) 6 Giaithua(3) n = 3 return 3* Giaithua(2) 2 Giaithua(2) n = 2 return 2* Giaithua(1) 1 Giaithua(1) n = 1 return 1* Giaithua(0) 1 Giaithua(0) n = 0 return 1 Hình 2.1: Gọi đệ quy của hàm giai thừa. Lưu ý: Hàm đệ quy dùng nhiều vùng nhớ trên ngăn xếp do đĩ cĩ thể dẫn đến tràn ngăn xếp. Do đĩ nếu một bài tốn cĩ thể dùng phương pháp lặp (khơng đệ quy) để giải quyết thì nên sử dụng cách này. Phân loại hàm đệ quy: Đệ quy trực tiếp: trong một hàm cĩ lời gọi hàm đến chính bản thân hàm đĩ. 18
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN - Đệ quy tuyến tính: thân hàm gọi một lần đến chính nĩ: Un a, n =1 r + Un-1, n>1 double U(int n, double a, double r) { if (n == 1) return a ; return r + U(n-1, a, r) ; } - Đệ quy nhị phân: thân hàm cĩ hai lần gọi chính nĩ Un 1, n =1, 2 Un-2 + Un-1, n>2 long Fibo(int n) { if (n =6 long U( int n) { if (n 0; i ) S+= U(n-i); return S; } - Đệ quy hỗ tương: hai hàm đệ quy gọi nhau Un n, n =5 Gn n-3, n =8 19
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN long G(int n); long U( int n) { if (n<5) return n; return U(n-1) + G(n-2); } long G(int n) { if (n<8) return n-3; return U(n-1) + G(n-2); } Đệ quy gián tiếp: trong một hàm cĩ lời gọi hàm đến một hàm khác và bên trong hàm này lại cĩ lời gọi hàm đến hàm ban đầu. Ví dụ như hàm F1 gọi hàm F2 và bên trong hàm F2 lại cĩ lời gọi hàm đến F1. Đây được gọi là sự đệ quy gián tiếp. Thơng thường những dạng chương trình đệ quy gián tiếp thì khĩ theo dõi và gỡ rối, nên khi xây dựng chương trình loại này phải hết sức cẩn thận. 2.2 Xây dựng một chương trình đệ quy Phương pháp đệ quy thường được áp dụng cho những bài tốn phụ thuộc tham số và cĩ các đặc điểm sau: 1. Bài tốn dễ dàng giải quyết trong một số trường hợp riêng ứng với các giá trị đặc biệt nào đĩ của tham số. Trường hợp này gọi là suy biến. Ví dụ như khi tính giai thừa thì giai thừa của 0 là 1. 2. Trong trường hợp tổng quát, bài tốn quy về cùng một dạng nhưng giá trị tham số được thay đổi. Sau một số lần hữu hạn các bước biến đổi đệ quy thì bài tốn trở về trường hợp suy biến. Ví dụ như n! = (n-1)!. n, khi đĩ n giảm về 0 thì xảy ra trường hợp suy biến. Các hàm đệ quy thường cĩ dạng tổng quát như sau: if (Trường hợp đặc biệt, suy biến) { // giải theo cách suy biến, trường hợp này đã cĩ lời giải 20
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN } else // trường hợp tổng quát. { // gọi đệ quy với giá trị tham số khác (thay đổi tham số) } Ví dụ 1: Tính tổng các số nguyên từ 1 đến N. N N −1 N −2 ∑i = N + ∑i = N + (N −1) + ∑i i=1 i i−1 Ta phân tích như sau: + Trường hợp đặc biệt N=1 thì kết quả là 1 + Trường hợp khác ta thực hiện đệ quy: N + Tong(N-1). Ví dụ 2: tìm USCLN của hai số nguyên dương a, b. + Trường hợp đặc biệt khi a = b khi đĩ USCLN(a, b) = a + Trường hợp chung a và b khác nhau ta cĩ thể thực hiện đệ quy như sau: - USCLN(a, b) = USCLN(a-b, b) nếu a>b - USCLN(a, b) = USCLN(a, b-a) nếu a b) return USCLN(a-b, b); else return USCLN(a, b-a); } Ví dụ 3: Tính an. + Trường hợp đặc biệt n = 0, kết quả là 1 + Trường hợp khác, kết quả là a * a(n-1). 2.3 Các ví dụ đệ quy Trong phần này chúng ta sẽ tìm hiểu một số chương trình đệ quy như sau: Tháp Hanoi (Tower of Hanoi): Cho 3 cột tháp được đặt tên là C1, C2, và C3. Cĩ N đĩa cĩ đường kính giảm dần và được sắp như hình vẽ. Hãy dịch chuyển N đĩa đĩ sang cột C2, theo nguyên tắc sau: 21
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN mỗi lần chỉ dịch được một đĩa, khơng được để một đĩa cĩ đường kính lớn nằm trên đĩa cĩ đường kính nhỏ. Ta phân tích cách thực hiện như sau: Với N = 2: ta cĩ cách làm như sau: chuyển đĩa bé nhất sang C3, chuyển đĩa lớn sang C2, chuyển đĩa nhỏ từ C3 sang C2. 1 2 3 1 2 3 1 2 3 1 2 3 Hình 2.2: Minh họa tháp Hanoi với n =2. Với N = 3: ta thực hiện với giả thiết đã biết cách làm với N-1 đĩa (2 đĩa trong ví dụ N=3): chuyển đĩa 1 và 2 sang cọc 3, chuyển đĩa 3 sang cọc 2, chuyển hai đĩa 1, 2 từ cọc 3 sang cọc 2. 22
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN C1 C2 C3 B1 B2 B3 1, 2 qua cọc 3 1, 2 qua cọc 2 3 qua cọc 2 C1 C2 C3 C1 C2 C3 C1 C2 C3 B1.1 B3.3 C1 C2 C3 C1 C2 C3 B1.2 B3.2 C1 C2 C3 C1 C2 C3 B1.3 B3.1 C C C1 C2 C3 C1 2 3 Hình 2.3: Minh họa trường hợp N = 3. Trong trường hợp N = 3 như hình 2.3, thực hiện ba bước để đưa 3 đĩa về cọc 2: gồm B1, B2 và B3. Với B2 thì đơn giản do chuyển 1 đĩa, cịn bước B1 và B3 phải di chuyển nhiều hơn 1 đĩa nên chúng sẽ bao gồm nhiều bước nhỏ trong đĩ. B1 gồm {B1.1, B1.2, B1.3} và 23
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN B2 gồm {B2.1, B2.2, B2.3}. Cuối cùng cách thực hiện theo các bước: B1.1 ⇒ B1.2 ⇒ B1.3 ⇒ B2 ⇒ B3.1 ⇒ B3.1⇒ B3.3. C1 C2 C3 Hình 2.4: Tháp Hanoi với n = 4. Chúng ta định nghĩa hàm DichChuyen chuyển N đĩa từ cọc nguồn, sang cọc đích thơng qua một cọc trung gian (cọc thứ 3 cịn lại). Hàm này định nghĩa như sau: DichChuyen(N, Nguon, Dich, Trung gian); Với N = 2 ta diễn tả lại như sau: DichChuyen(1, C1, C3, C2) DichChuyen(1, C1, C2, C3) DichChuyen(1,C3, C2, C1) Với N = 3 ta diễn tả như sau: thơng qua dịch chuyển 2 đĩa DichChuyen(2, C1, C3, C2) DichChuyen(1, C1, C2, C3) DichChuyen(2,C3, C2, C1) Với N tổng quát ta cĩ DichChuyen(N-1, C1, C3, C2) DichChuyen(1, C1, C2, C3) DichChuyen(N-1,C3, C2, C1) Trường hợp N =1 ta chỉ cần dịch từ cọc nguồn tới cọc đích khơng cần cọc trung gian. Đoạn chương trình C/C++ minh họa như sau: #include void DichChuyen(int N, int C1, int C2, int C3); int main() { int N; 24
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN printf(“Nhap so dia: “); scanf(“%d”, &N); DichChuyen(N, 1, 2, 3); return 0; } void DichChuyen(int N, int C1, int C2, int C3) { if (N == 1) printf(“%d - > %d”, C1, C2); else { DichChuyen(N-1, C1, C3, C2); DichChuyen(1, C1, C2, C3); DichChuyen(N-1, C3, C2, C1); } } Tìm phần tử lớn nhất trong mảng dùng đệ quy: cho mảng a[n], n > 1, hãy tìm phần tử lớn nhất trong mảng a[n]. Ta thử phân tích như sau: ý tưởng là đi từ phần đuơi và so sánh với phần tử cuối cùng của mảng với biến tạm m, chọn ra phần tử lớn nhất ⇒ lưu lại vào m. Bước tiếp theo thực hiện tương tự nhưng lúc này mảng rút ngắn lại cịn n-1 phần tử. a1 a2 a3 an-1 an m = Max(m, a ) n = n-1 n a1 a2 a3 an m = Max(m, an) n =1 an m = Max(m, an) Hình 2.5 : Tìm phần tử lớn trong mảng dùng đệ quy Hàm đệ quy tìm phần tử lớn nhất mơ tả như sau: giả sử chỉ số mảng tính từ 1. 25
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN DeQuyMax(int a[N], int n, int &max)// Gỉa sử n > 0 if ( n ==1) {max = a[1] ; return;} if (max < a[n]) max = a[n]; DeQuyMax(a, n-1, max); Tính tổng các phần tử trong mảng dùng đệ quy: cho dãy a[1:n], gọi hàm Sum là hàm đệ quy tính tổng, khi đĩ tổng của dãy a[1:n] là Sum(a[1:n]) Sum(a[1:n]) = Sum(a[1:n-1]) + a[n] Và Sum(a[m:m]) = a[m], trường hợp m=1 thì Sum(a[1:1]) = a[1] a1 a2 a3 an-1 an Sum(n) = an + Sum(n-1) n = n-1 a1 a2 a3 an Sum(n) = an + Sum(n-1) n = 1 an Trả về Sum(n) = an = a1 Hình 2.6: Tổng các phần tử trong mảng. Hàm đệ quy mơ tả bằng mã giả như sau: Sum(int a[], int n) - if ( n == 1) Sum = a[1]; - else Sum = Sum(a, n-1) + a[n]; 26
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN 2.4 Khử đệ quy 2.4.1 Tìm hiểu cơ chế thực hiện hàm đệ quy Tại mỗi thời điểm của hàm đệ quy được đặc trưng bởi: nội dung các biến và các lệnh cần thực hiện tiếp theo. Do đĩ tại mỗi thời điểm trong tiến trình xử lý của hàm đệ quy cần phải lưu trữ cả các trạng thái xử lý dang dở. Ví dụ trong hàm đệ quy tính giai thừa n, GT(n): if (n == 0) return 1; else return (n* GT(n-1)); Trong trường hợp n = 3 GT(3) = 3 * GT(2) GT(2) = 2 * GT(1) GT(1) = 1 * GT(0) GT(0) = 1 Hình 2.7: Gọi đệ quy hàm GT. Khi thực hiện lời gọi GT(3) thì sẽ phát sinh lời gọi hàm đến GT(2) và đồng thời phải lưu giữ thơng tin trạng thái xử lý cịn dang dở GT(3) = 3 * GT(2). Đến lượt hàm GT(2) sẽ phát sinh lời gọi hàm đến GT(1) và lưu giữ thơng tin trạng thái cịn dang dở GT(2) = 2 * GT(1) Quá trình cứ thực hiện tương tự cho tới khi gặp trường hợp suy biến GT(0) = 1. Kết thúc quá trình gọi đệ quy là quá trình xử lý ngược được thực hiện: Giá trị của GT(0) được dùng để tính GT(1) theo quá trình lưu trữ Dùng giá trị GT(1) để tính GT(2) theo quá trình tương tự 27
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN Dùng giá trị GT(2) để tính GT(3) để ra kết quả cuối cùng Song song với quá trình xử lý ngược là xĩa bỏ thơng tin lưu trữ trong những lần gọi hàm tương ứng. Ví dụ hàm đệ quy tính giá trị dãy Fibonacci Fibo(n) if (n ==0) || (n == 1) return 1; else return (Fibo(n-1) + Fibo(n-2)); Fibo(4) = Fibo(2) + Fibo(3) Fibo(2) = Fibo(1) + Fibo(0) Fibo(3) = Fibo(2) + Fibo(1) Fibo(1) = 1 Fibo(0) = 1 Fibo(2) = Fibo(1) + Fibo(0) Fibo(1) = 1 Fibo(1) = 1 Fibo(0) = 1 Hình 2.8: Hàm đệ quy tính dãy Fibonacci. Do đặc điểm của quá trình xử lý một hàm đệ quy: việc thực thi lời gọi đệ quy sinh ra lời gọi đệ quy mới cho đến khi gặp trường hợp suy biến, do đĩ cần phải cĩ cơ chế lưu trữ thơng tin thoả yêu cầu: o Ở mỗi lần gọi phải lưu trữ thơng tin trạng thái con cịn đang xử lý dang dở, số trạng thái này bằng với số lần gọi chưa hồn tất. o Sau khi thực hiện xong một lần gọi thứ k, cần khơi phục lại tồn bộ thơng tin trạng thái của lần gọi trước đĩ là lần gọi k-1. o Lệnh gọi cuối cùng (trường hợp suy biến) sẽ được hồn tất trước tiên. Các lệnh gọi sau sẽ hồn thành trước, do đĩ dãy thơng tin trạng thái được hồi phục theo thứ tự ngược với thứ tự lưu trữ. 28
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN Cấu trúc dữ liệu ngăn xếp lưu trữ theo kiểu Last In First Out thoả các yêu cầu trên nên được sử dụng để lưu trữ thơng tin trạng thái của quá trình xử lý đệ quy. Thơng thường đệ quy là phương pháp giúp chúng ta tìm giải thuật cho những bài tốn khĩ. Kết quả của giải thuật đệ quy thường rất gọn gàng, dễ hiểu và dễ chuyển thành các chương trình trên các ngơn ngữ lập trình. Tuy nhiên, việc xử lý giải thuật đệ quy cũng gây khĩ khăn cho máy về khơng gian lưu trữ và thời gian xử lý. Vì vậy việc thay thế một chương trình đệ quy bằng một chương trình khơng đệ quy cũng được quan tâm rất nhiều. Thơng thường khi gặp một bài tốn khĩ giải quyết theo hướng khơng đệ quy thì người ta thực hiện quá trình như sau: o Dùng quan niệm đệ quy để tìm giải thuật cho bài tốn o Mã hố giải thuật đệ quy o Khử đệ quy để cĩ một chương trình khơng đệ quy. Quá trình trên gọi là khử đệ quy, đơi khi việc khử đệ quy cũng khơng dễ dàng gì, nên nhiều khi cũng phải chấp nhận chương trình đệ quy! 2.4.2 Các trường hợp khử đệ quy đơn giản o Hàm tính giá trị của dãy dữ liệu mơ tả bằng hồi quy: Ví dụ 1: hàm tính giai thừa khơng đệ quy long int GiaiThua( int n) { long int F =1; for (int k = 1; k <= n; k++) F = k*F; return (F); } Ví dụ 2: hàm tính Sn khơng đệ quy int Sn(int n) { int k = 1; int tg = 1; while ( k < n ) { k++; if ( k % 2 ) tg += 2*k -1; else tg -= 2*k + 1; } 29
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN } o Dạng đệ quy đuơi Một hàm đệ quy đuơi P cĩ dạng như sau: P(X) { if B(X) D(X) else { A(X) P(f(X)) } } Trong đĩ: X: là biến (một hay nhiều biến) P(X): là hàm đệ quy phụ thuộc X A(X) và D(X): là các nhĩm lệnh khơng đệ quy f(X): là hàm biến đổi x trong lần gọi thứ Pi nếu B(fi(X)) khơng đúng thì thực hiện lệnh X và gọi Pi+1, ngược lại B(fi(X)) đúng thì thực hiện D(X) và kết thúc quá trình gọi (Pi ko gọi thêm hàm đệ quy khác). Ví dụ: Tìm USCLN của hai số dựa vào thuật tốn Euclide Giải thuật đệ quy USCLN(m ,n) bằng Euclide như sau : void USCLN( int m, int n, int & kq) { if ( n ==0) kq = m ; else USCLN(n, m %n, kq) ; } Trong trường hợp này: X là m, n và kq P(X) : USCLN(m, n, kq) B(X) : n ==0 30
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN D(X) : kq = m ; A(X) : khơng cĩ f(x): USCLN(n, m %n, kq) Hàm USCLN khơng đệ quy được thể hiện như sau: void USCLN(int m, int n, int & kq) { int temp; while (n !=0) { temp = m %n; m = n; n = temp; } kq = m; } 2.4.3 Khử đệ quy dùng stack Để thực hiện một chương trình con đệ quy thì hệ thống phải tổ chức vùng nhớ lưu trữ theo quy tắc LIFO. Các ngơn ngữ lập trình cấp cao đều cĩ khả năng tạo vùng nhớ stack mới cho phép tổ chức các chương trình đệ quy. Thực hiện một chương trình con đệ quy theo cách mặc định thường tốn bộ nhớ. Do cách tổ chức stack mặc định thích hợp cho mọi trường hợp nên sẽ khơng tối ưu trong từng trường hợp cụ thể. Do đĩ sẽ tốt khi người lập trình chủ động tạo cấu trúc dữ liệu stack đặc dụng cho từng chương trình đệ quy cụ thể. Giả sử thủ tục đệ quy trực tiếp cĩ cấu trúc như sau : P(X) { if C(X) D(X) ; else A(X) ; P(f(X)) ; B(X) ; } Trong đĩ X : là một hay nhiều biến 31
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN C(X) : biểu thức điều kiện theo X A(X), B(X) và D(X) : nhĩm lệnh khơng đệ quy f(X) : là hàm của X Quá trình thực hiện thủ tục P(X) như sau: Nếu C(X) đúng thì thực hiện D(X) Ngược lại thực hiện A(X), gọi P(f(X)), thực hiện B(X) sau khi hồn thành P(f(X)). Mỗi lần P(Y) được gọi thì thơng tin của B(Y) lại được sinh ra nhưng chưa thực hiện. Giả sử quá trình đệ quy kết thúc sau k lần gọi đệ quy thì chương trình phải thực hiện dãy k thao tác B theo thứ tự: B(fk-1(X)), B(fk-2(X)), , B(f(f(X))), B(f(X), B(X) Để thực hiện dãy thao tác B trên ta cần xây dựng stack để lưu trữ tạm. Giải thuật thực hiện P(X) với việc sử dụng stack cĩ dạng: P(X) { CreateStack(S) ; while ( ! C(X)) { A(X) ; Push(S, X) ; X = f(X) ; } D(X) ; while ( !Empty(S)) { Pop(S, X) ; B(X) ; } } Ví dụ: thủ tục đệ quy biểu diễn số thập phân sang nhị phân cĩ dạng: 32
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN void Binary(int m) { if (m >0) { Binary( m / 2); printf("%d", m % 2); } } Trong đĩ: X là m P(X) là Binary(X) A(X) và D(X) khơng cĩ B(X) là lệnh printf("%d", m % 2) ; C(X) là m ≤ 0 f(X) = f(m) = m / 2 ; Giải thuật khơng đệ quy như sau: void Binary( int m) { int temp; CreateStack(S); while (m > 0) { temp = m % 2; Push(S, temp); m = m / 2; } while (! Empty(S)) { Pop(S, temp); printf(“%d”, temp); } } Lệnh gọi đệ quy với hai lần gọi trực tiếp: Thủ tục đệ quy cĩ dạng như sau: 33
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN P(X) { if C(X) D(X) else { A(X); P(f(X)); B(X); P(g(X)); } } Quá trình thực hiện thủ tục đệ quy P(X) như sau: Nếu C(X) đúng thì thực hiện D(X). Nếu C(X) sai thì thực hiện A(X), gọi P(f(X)), thực hiện B(X) và gọi P(g(X)); khi đĩ ngồi việc lưu giá trị fi(X) tương ứng chương trình cịn phải lưu thêm các giá trị gi(X) phát sinh tương ứng Do đĩ ngồi dữ liệu X, chương trình cịn phải lưu vào ngăn xếp thêm thứ tự lần gọi. Thủ tục khử đệ quy dùng stack trong trường hợp này cĩ dạng như sau: P(X) { CreateStack(S); Push(S, (X, 1)); do { while ( !C(X)) { A(X); Push(S, (X, 2)); X = f(X); 34
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN }// end while D(X); Pop(S, (X, k)); if ( k != 1) { B(X); X = g(X); }// end if } while (k > 1); } Ví dụ: khử đệ quy của thủ tục tháp Hanoi Dạng thủ tục đệ quy của tháp Hanoi như sau: Hanoi(n, a, b, c) { if (n>0) { Hanoi(n-1, a, c, b); Move(a, c); Hanoi(n-1, b, a, c); } } Trong đĩ n là số đĩa, a là cột đầu tiên, b là cột trung gian, và c là cột cuối cùng, Move(x, y) là thao tác chuyển 1 đĩa từ cột x sang y. Trong trường hợp này: X là bộ (n, a, b, c); C(X) là (n ≤ 0) A(X) và D(X) là rỗng B(X) là B(n,a, b, c) = Move(a, c) f(X) là f(n, a, b, c) = Hanoi(n-1, a, c, b) g(X) là g(n, a, b, c) = Hanoi(n-1, b, a, c) Giải thuật khơng đệ quy tương ứng như sau: Create_Stack(S) ; 35
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN Push(S, (n, a, b, c, 1)); do { while (n > 0) { Push(S, (n, a, b, c, 2)); n = n-1; Swap(b, c); } Pop(S, (n, a, b, c, k)); if ( k != 1) { Move(a, c); n = n-1; Swap(a, b); } } while (k>1); \[ 36
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN Chương 3 Bài tốn liên quan tổ hợp \[ 3.1 Phương pháp sinh Phương pháp sinh được áp dụng để giải quyết bài tốn liệt kê của lý thuyết tổ hợp. Để áp dụng được phương pháp này thì bài tốn phải thoả mãn hai điều kiện sau: o Cĩ thể xác định được thứ tự trên tập các cấu hình tổ hợp cần liệt kê. Từ đĩ cĩ thể xác định được cấu hình đầu tiên và cấu hình cuối cùng trong thứ tự đĩ. o Xây dựng được một thuật tốn cho phép từ một cấu hình chưa phải cấu hình cuối, sinh ra được cấu hình kế tiếp của nĩ. Phương pháp sinh cĩ thể được mơ tả tổng quát như sau: Do While 3.1.1 Bài tốn sinh dãy nhị phân độ dài n Bài tốn: một tập hợp hữu hạn cĩ n phần tử cĩ thể được biểu diễn tương đương với tập các số tự nhiên 1, 2, , n. Bài tốn đặt ra là: cho một tập hợp gồm n phần tử X = {X1, X2, , Xn} hãy liệt kê tất cả các tập con của tập này. Để biểu diễn tập con Y của X ta dùng xâu nhị phân Bn = {B1, B2, , Bn}, sao cho nếu Bi = 0 thì Xi∉ Y, ngược lại Bi = 1 thì Xi ∈ Y. Ví dụ như dãy 0011 của tập hợp gồm n thể hiện cho tập Y = {X3, X4} do phần tử B3 và B4 cĩ giá trị là 1. Khi đĩ ta quy về bài tốn liệt kê tất cả xâu nhị phân cĩ kích thước n. Số các xâu nhị phân là 2n. 37
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN Một dãy nhị phân x độ dài n là biểu diễn một số nguyên p(x) nào đĩ trong đoạn [0, 2n-1]. Do đĩ số các dãy nhị phân độ dài n = số các số nguyên ∈ [0, 2n-1] = 2n. Mục tiêu là lập một chương trình liệt kê các dãy nhị phân n phần tử theo thứ tự từ điển, cĩ nghĩa là liệt kê dãy nhị phân biểu diễn các số nguyên theo thứ tự 0, 1, , 2n-1. Khi n =3, các độ dài 3 được liệt kê như sau: p(x) 0 1 2 3 4 5 6 7 x 000 001 010 011 100 101 110 111 Khi đĩ dãy đầu tiên là: 000 và dãy cuối cùng là 111. Nhận thấy rằng nếu x là dãy đang cĩ và phải là dãy cuối cùng thì dãy tiếp theo cần liệt kê chính là x cộng thêm 1 đơn vị trong hệ nhị phân! Ví dụ n = 6: Dãy đang cĩ: 010000 Dãy đang cĩ: 010111 Cộng thêm 1: +1 Cộng thêm 1: +1 ___ ___ Dãy mới: 010001 Dãy mới: 011000 Kỹ thuật sinh kế tiếp từ cấu hình hiện tại cĩ thể mơ tả như sau: xét từ cuối dãy lên từ hàng đơn vị tìm số 0 đầu tiên. Nếu tìm thấy thì thay số 0 bằng số 1 và đặt tất cả phần tử phía sau vị trí đĩ bằng 0. Nếu khơng tìm thấy thì tồn là dãy chứa 1, đây là cấu hình cuối cùng. Chương trình minh họa 1: chương trình C/C++ liệt kê chuỗi nhị phân n bit. int Stop; // biến tồn cục void Next_BS(int B[MAX], int n) // Hàm phát sinh chuỗi kế tiếp { int i = n; // duyệt từ cuối while (i>0 && B[i]) // lặp khi chưa tìm thấy B[i] ==0 { B[i] = 0; // gán các bit sau là 0 i ; // giảm về trước } if (i==0 ) Stop = 1; // cấu hình cuối nên khơng tìm được B[i] = 0 -> dừng else B[i] = 1; // gán 1 cho B[i] 38
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN } void Generate(int B[MAX], int n) // Hàm sinh chuỗi nhị phân { Stop = 0; while (! Stop) { Result(B,n); // xuất chuỗi nhị phân hiện tại Next_BS(B,n); // chuỗi nhị phân tiếp theo. } } void Result(int B[MAX], int n) { static int count=0; printf(“\n Xau nhi phan thu %d”, ++count); for(int i=0; i < n;i++) printf(“%3d”, B[i]); } int main() { int i, B[MAX], n; printf(“Nhap n: ”); scanf(“%d”,&n); for(i=0; i< n; i++) B[i] =0; Generate(b, n); getch(); return 0; } 3.1.2 Bài tốn liệt kê tập con k phần tử Phát biểu: Cho tập hợp X = {1, 2, , n}. Hãy liệt kê tất cả tập con k phần tử của X. Mỗi tập con k phần tử của X cho thể biểu diễn như bộ thứ tự: a = (a1, a2, , ak) thỏa mãn 1 ≤ a1 ≤ a2 ≤ ≤ ak ≤ n. Trên tập con k phần tử của X, ta định nghĩa thứ tự của các tập con như sau: Ta nĩi tập a = (a1, a2, , ak) cĩ thứ tự trước tập a’ = (a’1, a’2, , a’k) theo thứ tự từ điển và ký hiệu là a < a’ nếu tìm được j sao cho: a1 = a’1, a2 = a’2 , aj-1 = a’j-1 và aj < a’j. Ví dụ với n = 5, k = 3, ta liệt kê 10 tập con của nĩ như sau: {{1,2,3},{1,2,4}{1,2,5}{1,3,4}{1,3,5}{1,4,5}{2,3,4}{2,3,5}{2,4,5}{3,4,5}} + Ta thấy cấu hình đầu tiên là {1, 2 , k} 39
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN + Cấu hình kết thúc là {n-k+1, n-k+2, , n}. Nhận xét: chúng ta sẽ in ra tập con với các phần tử của nĩ theo thứ tự tăng dần. Biểu diễn tập con là một dãy a{a1, a2, , ak} trong đĩ a1 , các phần tử a3 ⇒ a6 đã đạt đến giới hạn nên ta khơng thể tăng các phần tử này được, ta phải tăng a2 từ 2 lên thành 3. Được cấu hình mới là cấu hình này thoả mãn lớn hơn cấu hình cũ, nhưng chưa thoả mãn tính chất vừa đủ lớn do đĩ ta phải thay a3, a4, a5, a6 bằng giới hạn dưới của nĩ như sau: a3 = a(3-1= 2) + 1 = 3 + 1 = 4 a4 = a(4-1= 3) + 1 = 4 + 1 = 5 a5 = a(5-1= 4) + 1 = 5 + 1 = 6 a6 = a(6-1= 5) + 1 = 6 + 1 = 7 Vậy cấu hình tiếp theo là cấu hình cần tìm. Do đĩ muốn xác định cấu hình tiếp ta thấy a6 = 7 chưa đạt đến giới hạn ta chỉ cần tăng a6 lên một là được cấu hình tiếp theo: . Vậy kỹ thuật sinh tập con kế tiếp từ tập x đã cĩ cĩ thể xây dựng như sau: Tìm từ cuối lên đầu dãy cho tới khi gặp phần tử ai chưa đạt đến giới hạn n-k+i. Nếu tìm thấy: o Tăng ai đĩ lên 1. o Đặt tất cả phần tử phía sau ai bằng giới hạn dưới. Nếu khơng tìm thấy tức là phần tử đã đạt giới hạn trên, đây là cấu hình cuối cùng. Kết thúc thuật tốn. Chương trình minh họa 2: liệt kê tập con k phần tử của n. int A[MAX], Stop, n ,k; 40
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN void Next_SubSet() { int i,j; i = k; // duyệt từ cuối dãy // lặp khi chưa tìm được phần tử chưa tới giới hạn while (i >0 && A[i] == n-k+i) i ; // duyệt về đầu if ( i > 0) { A[i] = A[i] +1; // tăng một đơn vị // cho các phần tử cịn lại qua giới hạn dưới for(j = i+1; j <= k; j++) A[j] = A[j-1]+ 1 } else Stop = 1; // kết thúc phát sinh cấu hình } void GenerateSet() { Stop = 0; while (!Stop) { Result(); // xuất cấu hình hiện tại Next_SubSet(); // qua cấu hình khác } } void Result() { static int count=0; printf(“Tap con thu %d”, ++count); for(i=1; i <=k; i++) printf(“%3d”, A[i]); } int main() { printf(“Nhap n: ”); scanf(“%d”, &n); printf(“Nhap k: ”); scanf(“%d”, &k); for(int i=1; i <= n;i++) A[i] = i; GenerateSet(); getch(); return 0; } 41
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN 3.1.3 Bài tốn liệt kê các hốn vị Bài tốn: Cho tập hợp X = {1, 2, , n}, hãy liệt kê tất cả hốn vị của X. Mỗi hốn vị n phần tử của tập X cĩ thể biểu diễn bởi bộ cĩ thứ tự gồm n thành phần a = {a1, a2, , an} thoả ai ∈ X; i = 1, 2, , n; ap ≠ aq nếu p ≠ q. Trên các tập hốn vị của X ta định nghĩa thứ tự của các hốn vị như sau: a = (a1, a2, , an) được gọi là cĩ thứ tự trước hốn vị a’=(a’1,a’2, ,a’n). Cĩ ký hiệu a , ta xét 4 phần tử cuối cùng, do chúng được sắp theo thứ tự giảm dần. Khi đĩ ta hốn vị 4 giá trị này thì cũng chỉ được hốn vị nhỏ hơn hốn vị hiện tại. Như vậy ta phải xét đến a2 = 2, ta phải thay giá trị này, nhưng thay giá trị nào? ta khơng thể thay bằng 1 vì nếu như vậy sẽ được hốn vị nhỏ hơn, khơng thể thay bằng 3 vì giá trị này đã cĩ rồi a1 = 3 (phần tử sau khơng được chọn vào những giá trị xuất hiện ở phần tử trước). Chỉ cịn lại giá trị 4, 5, 6. Vì cần một hốn vị đủ lớn nên ta chọn a2 = 4. Cịn các giá trị a3, a4, a5, a6 sẽ lấy trong tập {2, 6, 5, 1}. Cũng do tính chất vừa đủ lớn nên ta sẽ tìm biểu diễn nhỏ nhất của 4 số này để gán cho a3, a4, a5, a6, là vậy ta được hốn vị mới là Nhận xét: đoạn cuối của hốn vị hiện tại được sắp giảm dần. số a5 là 4 là số nhỏ nhất trong đoạn cuối lớn hơn a2 = 2. Nếu đổi chỗ a5 cho a2 thì ta được a2 = 4 và đoạn cuối vẫn được xếp giảm dần là khi đĩ muốn biểu diễn nhỏ nhất cho các giá trị trong đoạn cuối thì ta chỉ cần đảo ngược đoạn cuối. 42
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN Ví dụ trong hốn vị hiện tại cĩ hốn vị kế tiếp là . Ta cĩ thể xem cĩ đoạn cuối giảm dần là một phần tử . Vậy kỹ thuật sinh hốn vị kế tiếp từ hốn vị hiện tại cĩ thể xây dựng như sau: Xác định đoạn cuối giảm dần dài nhất, tìm phần tử ai đứng trước đoạn cuối đĩ. Điều này đồng nghĩa với việc tìm từ vị trí sát cuối dãy lên đầu, gặp chỉ số i đầu tiên thoả mãn ai ai. Do đoạn cuối giảm dần nên thực hiện bằng cách từ cuối dãy lên đầu gặp chỉ số k đầu tiên thoả ak > ai. o Đảo giá trị ak và ai. o Lật ngược thứ tự đoạn cuối giảm dần (ai+1 đến ak) trở thành tăng dần Nếu khơng tìm thấy tức là dãy giảm dần, đây là cấu hình cuối cùng. Chương trình minh họa 3: Liệt kê hốn vị n phần tử. int n, P[MAX], Stop; void Next_Permutation() { int j, k; j = n -1; while (j>0 && P[j]> P[j+1]) j ; if (j == 0) Stop = 1; else { k = n; while (P[j] > P[k]) k ; Swap(P[j], P[k]); l = j+1; r = n; while (l < r) { Swap(P[l], P[r]); l++; r ; } }// end else } void Permutation() { 43
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN Stop = 0; while (! Stop) { Result(); Next_Permutation(); } } void Result() { static int count=0; printf(“\n Hoan vi thu %d”, ++count); for(int i=1; i <= n; i++) printf(”%3d”, P[i]); } int main() { printf(“Nhap n: ”); scanf(“%d”, &n); for(int i=1; i <= n; i++) P[i] = i; return 0; } 44
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN 3.2 Thuật tốn quay lui (Back Tracking) Thuật tốn quay lui dùng để giải quyết các bài tốn liệt kê các cấu hình. Phương pháp sinh trong phần trước cũng được giải quyết cho các bài tốn liệt kê khi nhận biết được cấu hình đầu tiên của bài tốn. Tuy nhiên, khơng phải bất cứ cấu hình sinh kế tiếp nào cũng cĩ thể sinh một cách đơn giản từ cấu hình hiện tại. Do đĩ thuật tốn sinh kế tiếp chỉ giải quyết được cái bài tốn liệt kê đơn giản. Để giải quyết những bài tốn tổ hợp phức tạp, người ta dùng thuật tốn quay lui. Nội dung chính của thuật tốn quay lui: Xây dựng dần dần các thành phần của cấu hình bằng cách thử tất cả các khả năng cĩ thể xảy ra. Giả sử cấu hình cần liệt kê cĩ dạng x = (x1, x2, ,xn) khi đĩ thuật tốn quay lui thực hiện qua các bước: 1. Xét tất cả những giá trị cĩ thể cĩ của x1, thử cho x1 nhận lần lượt các giá trị đĩ. Với mỗi giá trị thử gán cho x1 ta sẽ làm tiếp như sau: 2. Xét tất cả giá trị x2 cĩ thể nhận, lại thử cho x2 nhận lần lượt các giá trị đĩ. Với mỗi giá trị x2 ta lại xét lần lượt những giá trị của x3 cứ tiếp tục như vậy cho đến bước n. 3. Xét giá trị cĩ thể nhận cho xn, thử cho xn lần lượt nhận những giá trị đĩ, thơng báo những cấu hình tìm được như (x1, x2, , xn). Tĩm lại thuật tốn quay lui liệt kê các cấu hình n phần tử dạng x = (x1, x2, , xn) bằng cách thử cho x1 nhận lần lượt các giá trị cĩ thể được. Với mỗi giá trị thử gán cho x1 thì bài tốn trở thành liệt kê tiếp cấu hình n-1 phần tử x = (x2, x3, , xn). 45
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN Gốc Khả năng chọn x1 Khả năng chọn x2 với x1 đã chọn Khả năng chọn x3 với x1 và x2 đã chọn Hình 3.1: Liệt kê các lời giải theo thuật tốn quay lui. Mơ hình chung của thuật tốn quay lui xác định thành phần thứ i được mơ tả tổng quát như sau: (thuật tốn này thử cho xi nhận lần lượt những giá trị mà nĩ cĩ thể nhận). void Try(int i) { for do { if then else { Try(i+1); // gọi đệ quy cho tiếp chi x[i+1]. } } } Thuật tốn quay lui sẽ bắt đầu bằng lời gọi Try(1). 46
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN 3.2.1 Thuật tốn quay lui liệt kê dãy nhị phân n Biểu diễn dãy nhị phân độ dài n dưới dạng x = (x1, x2, , xn) trong đĩ xi nhận các giá trị là {0, 1}. Với mỗi giá trị gán cho xi ta lại thử gán các giá trị cĩ thể cĩ cho xi+1. Thuật tốn quay lui được viết như sau: void Try(int i, int B[MAX], int n) { int j; for(j=0; j <= 1; j++) { B[i] = j; if (i == n) Result(B, n); else Try(i+1, B, n); } } void Result(int B[MAX], int n) { int i; printf(“\n”); for(i=1; i <= n; i++) printf(“%3d”, B[i]); } int main() { int n, B[MAX]; printf(“Nhap n: ”); scanf(“%d”, &n); for(int i=1; i <= n; i++) // khởi tạo cho mảng B B[i] = 0; Try(1, B, n); // gọi thuật tốn quay lui return 0; } Khi n = 3, cây tìm kiếm quay lui như sau: 47
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN Try(1) x1 = 0 x1 = 1 Try(2) Try(2) x2 = 0 x2 = 1 x2 = 0 x2 = 1 Try(3) Try(3) Try(3) Try(3) x3 = 0 x3 = 1 x3 = 0 x3 = 1 x3 = 0 x3 = 1 x3 = 0 x3 = 1 000 001 010 011 100 101 110 111 Hình 3.2: Cây tìm kiếm quay lui trong bài tốn liệt kê dãy nhị phân. 3.2.2 Thuật tốn quay lui liệt kê tập con k phần tử Để liệt kê tập con k phần tử của tập S = {1, 2, , n} ta cĩ thể đưa về liệt kê các cấu hình x = (x1, x2, , xn) ở đây xi ∈ S và x1 < x2 < < xn. Từ đĩ giá trị được chọn cho xi là xi-1 + 1 cho đến n –k+i (1 ≤ i ≤ k ), giả thiết cĩ thêm số x0 = 0 khi xét i =1. Như vậy xét tất cả cách chọn x1 từ 1 (x0 +1) đến n-k+1, với mỗi giá trị đĩ, xét tiếp tất cả cách chọn x2 từ x1+1 đến n-k+2 cứ như vậy khi chọn được xk thì ta cĩ cấu hình cần liệt kê. Với trường hợp n = 5 {1, 2, 3, 4, 5} và k = 3 thuật tốn quay lui liệt kê tập con k phần tử được minh họa như sau: 48
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN N = 5; k = 3 1 2 3 2 3 4 3 4 4 3 4 5 4 5 5 4 5 5 5 Hình 3.3: Cây liệt kê tập con 3 phần tử với n = 5. Chương trình quay lui liệt kê tập k phần tử: void Try(int i, int B[MAX], int k, int n) { int j; for(j = B[i-1] + 1; j <= (n-k+i); j++) { B[i] = j; if (i == k) Result(B, k); else Try(i+1, B, k, n); } } void Result(int B[MAX], int k) { static int count=0; printf(“Tap con thu %d: ”, ++count); for(i=1; i <= k; i++) printf(“%3d”, B[i]); } int main() { int n, k, B[MAX]; printf(“Nhap n: ”); scanf(“%d”,&n); printf(“Nhap k: ”); scanf(“%d”, &k); B[0] = 0; 49
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN Try(1, B, k, n); return 0; } 3.2.3 Thuật tốn quay lui liệt kê hốn vị n phần tử Biểu diễn hốn vị dưới dạng p1, p2, , pn, trong đĩ pi nhận giá trị từ 1 đến n và pi ≠ pj với i ≠ j. Các giá trị từ 1 đến n được đề cử cho pi, trong đĩ giá trị j được chấp nhận nếu nĩ chưa được dùng trước đĩ. Do đĩ cần phải ghi nhớ xem giá trị j đã được dùng chưa. Ta thực hiện điều này bằng một mảng B, trong đĩ Bj = true nếu j chưa được dùng và ngược lại. Đầu tiên các giá trị trong B này phải được khởi tạo là true, sau khi gán j cho xi thì ghi nhận Bj = false, sau khi gọi xong thủ tục Try(i+1) thì thiết lập lại Bj = true, để đánh dấu nĩ chưa được dùng để cho bước thử tiếp theo. n = 3 1 2 3 2 3 1 3 1 2 3 2 3 1 2 1 Hình 3.4: Cây liệt kê hốn vị 3 phần tử Chương trình quay lui liệt kê hốn vị m phần tử: void Try(int i, int P[MAX], int B[MAX], int n) { int j; for(j = 1; j <= n; j++) if (B[j] == 1) 50
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN { P[i] = j; B[j] = 0; // đánh dấu đã sử dụng j if (i == n) result(P, n); // xuất kết quả else Try(i+1, P, B, n); // thử cho bước tiếp theo B[j] = 1; // bỏ đánh dấu phần đã sử dụng j } } void Result(int P[MAX], int n) { static int count=0; printf(“Hoan vi thu %d”, ++count); for(int i=1; i<= n; i++) printf(”%3d”, P[i]); } int main() { int P[MAX], B[MAX], n; printf(“Nhap n: ”); scanf(“%d”, &n); for(int i=1; i <=n; i++) B[i] = 1; Try(1, P, B, n); return 0; } 3.2.4 Bài tốn sắp xếp quân Hậu Yêu cầu: cho một bàn cờ vua nxn, hãy liệt kê cách sắp xếp n quân hậu sao cho các quân hậu khơng ăn được nhau! Quân hậu trên bàn cờ cĩ thể ăn quân khác trên cùng hàng, cùng cột hoặc cùng đường chéo. Phân tích: các quân hậu sẽ được sắp trên các dịng khác nhau do chúng cĩ thể ăn theo hàng ngang. Để dễ phân tích ta mơ tả quân hậu theo dịng; quân hậu 1 ở dịng 1, quân hậu i ở dịng i Do mỗi quân hậu chắc chắn nằm trên các dịng khác nhau nên ta chỉ cần xác định vị trí cột của mỗi quân hậu là xong. Tiếp theo ta xét những ràng buộc theo đường chéo, cĩ hai đường chéo: o Chéo “\”: theo hướng Trên Trái - Dưới Phải o Chéo “/”: theo hướng Trên Phải - Dưới Trái 51
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN Hình 3.5: Các nước đi của quân hậu cĩ thể cĩ. Hình 3.6: Một cách sắp xếp 8 hậu trên bàn cờ 8x8 Các đường chéo Trên Trái - Dưới Phải như hình vẽ dưới, mỗi đường chéo này sẽ đi qua các ơ, các ơ này cĩ tính chất: dịng - cột = C (hằng số). Do đĩ với mỗi đường chéo ta cĩ 1 hằng số C và 1-n ≤ C ≤ n-1 xác định duy nhất đường chéo đĩ. 52
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN 1 2 3 4 5 6 7 8 1 -7 2 3 4 4 5 6 7 -1 7 8 0 Hình 3.7: Các đường chéo Trên Trái - Dưới Phải Các đường chéo Trên Phải - Dưới Trái: mỗi đường chéo này sẽ đi qua các ơ cĩ tính chất sau: dịng + cột = C (hằng số). Do đĩ với mỗi đường chéo ta cĩ một hằng số C và 2 ≤ C ≤ 2n. 1 2 3 4 5 6 7 8 2 1 9 2 3 4 5 6 14 7 8 16 Hình 3.8: Các đường chéo Trên Phải - Dưới Trái. 53
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN 1 2 3 4 5 6 7 8 1 Đừng chéo TT- 2 DP cĩ chỉ số 0 3 4 5 Ơ ( 5, 5) 6 Đừng chéo TP- 7 DT cĩ chỉ số 10 8 Hình 3.9: Vị trí của quân hậu ảnh hưởng đến 2 đường chéo. Cài đặt: o Cấu trúc dữ liệu: o Mảng R[N]: lưu theo cột, R[i] = true ⇒ cột i cịn tự do, ngược lại cột i đã bị quân hậu khống chế. o Mảng C1[2*N-1]: lưu đường chéo TT-DP, do các dường chéo này cĩ chỉ số từ 1-n ⇒ n-1 nên ánh xạ chỉ số này vào mảng C1 bằng cách cộng thêm (n-1). Khi đĩ đường chéo 1-n sẽ cĩ chỉ số là 0 trong mảng C1 o Mảng C2[2*N+1]: lưu đường chéo TP-DT, các đường chéo này cĩ chỉ số từ 2- 2n nên ta đánh chỉ số C2 từ 2- 2n luơn cho tiện (hai phần tử C2[0] và C2[1] ta khơng dùng đến). o Các phần tử của 3 mảng R, C1 và C2 được gán giá trị True khi bắt đầu! o Thuật tốn quay lui: o Ý tưởng chính như sau: xét tất cả các cột, thử đặt quân hậu 1 vào 1 cột, với mỗi cách đặt quân hậu 1, xét tất cả các đặt quân hậu 2 sao cho quân hậu 1 khơng ăn được nĩ, thử đặt quân hậu 2 vào ơ cĩ thể rồi xét tiếp đến quân hậu 3 đến quân hậu n. Với mỗi cách đặt quân hậu n sẽ cho ta một kết quả! Khi xét hết tất cả các giá trị cĩ thể cĩ gán cho quân hậu thứ i thì thuật tốn sẽ quay lên xét những giá trị cịn lại của quân hậu thứ i-1. 54
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN o Khi chọn vị trí j cho quân hậu thứ i, thì ơ (i, j) khơng bị quân hậu đặt trước đĩ ăn. Do vậy ơ (i, j) phải thoả điều kiện: Cột j cịn tự do. Đường chéo TT-DP cĩ chỉ số (i-j) khơng bị bất kỳ quân hậu nào khống chế. Đường chéo TP-DT cĩ chỉ số (i+j) cũng khơng bị các quân hậu trước đĩ khống chế. o Sau khi đặt quân hậu thứ i vào cột j, nếu i = n tức là đặt xong quân hậu cuối cùng ⇒ được một bộ kết quả. Ngược lại Đánh dấu 2 đường chéo TT-DP (i-j) và đường TP-DT(i+j) và cột j đã bị khống chế. Tiếp tục gọi đệ quy cho quân thứ i+1. Sau khi gọi đệ quy cho quân hậu i+1, ta phải thử vị trí khác cho quân hậu thứ i trong số những giá trị j cĩ thể nhận được. Do đĩ ta phải bỏ việc đánh dấu cột j và 2 đường chéo, lúc này cột j và 2 đường chéo đĩ sẽ tự do. Thao tác này cho phép quân hậu khác cĩ thể đặt ở vị trí đĩ ở những bước tiếp sau. Chương trình C/C++ minh họa bài tốn n-Hậu: #define MAX 12 void ShowResult(int b[MAX], int n) { /*Xuat ket qua theo dong*/ for(int i=0; i < n; i++) printf("(%d, %d)\t", i+1, b[i]+1); printf("\n"); } void Try(int *r,int *b, int n, int i, int *c1, int *c2) { for(int j=0; j < n; j++) //tìm vị trí cột { if (r[j] && c1[(i-j)+n-1] && c2[i+j]) //kiểm tra cột và 2 chéo { b[i] = j; // chọn cột j if (i==n-1) ShowResult(b,n); // xuất 1 bộ kết quả else { 55
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN r[j] = false; // đánh dấu chọn cột j c1[(i-j)+n-1] = false; //chéo bị hậu khống chế c2[i+j] = false; //chéo bị hậu khống chế Try(r, b, n, i+1, c1, c2); // đặt hậu tiếp theo r[j] = true; // bỏ chọn cột j c1[(i-j)+n-1] = true; // chéo tự do c2[i+j] = true; // chéo tự do } } } } int main(int argc, char* argv[]) { int b[MAX], r[MAX]; int c1[2*MAX-1], c2[2*MAX-1]; int n; printf("doc n (<12): "); scanf("%d",&n); for(int i=0; i < n;i++) r[i] = true; for(i=0; i < 2*MAX-1; i++) { c1[i] = c2[i] = true; } Try(r, b, n, 0, c1, c2); return 0; } Kết quả khi n = 5 (1, 1) (2, 3) (3, 5) (4, 2) (5, 4) (1, 1) (2, 4) (3, 2) (4, 5) (5, 3) (1, 2) (2, 4) (3, 1) (4, 3) (5, 5) (1, 2) (2, 5) (3, 3) (4, 1) (5, 4) (1, 3) (2, 1) (3, 4) (4, 2) (5, 5) (1, 3) (2, 5) (3, 2) (4, 4) (5, 1) (1, 4) (2, 1) (3, 3) (4, 5) (5, 2) (1, 4) (2, 2) (3, 5) (4, 3) (5, 1) 56
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN (1, 5) (2, 2) (3, 4) (4, 1) (5, 3) (1, 5) (2, 3) (3, 1) (4, 4) (5, 2) 3.2.5 Bài tốn mã đi tuần Yêu cầu: Cho một bàn cờ tổng quát dạng nxn, hãy chỉ ra một hành trình của một quân Mã, xuất phát từ một vị trí bắt đầu đi qua tất cả các ơ cịn lại của bàn cờ, mỗi ơ đi đúng một lần. Ý tưởng cơ bản: dùng thuật tốn quay lui; xuất phát từ 1 ơ, gọi số nước đi là t=1, ta cho quân mã thử đi tiếp 1 ơ (cĩ 8 nước đi cĩ thể), nếu ơ đi tiếp này chưa đi qua thì chọn làm bước đi tiếp theo. Tại mỗi nước đi kiểm tra xem tổng số nước đi bằng n*n chưa, nếu bằng thì mã đã đi qua tất cả các ơ ⇒ dừng (do chỉ cần tìm một giải pháp). Trường hợp ngược lại, gọi đệ quy để chọn nước đi tiếp theo. Ngồi ra, nếu tại một bước tìm đường đi, nếu khơng tìm được đường đi tiếp thì thuật tốn sẽ quay lui lại nước đi trước và tìm đường đi khác Hình 3.10: Minh họa tám nước đi tiếp của quân mã. 57
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN Hình 3.11: Đường đi của quân mã trong bàn cờ 5x5 Cài đặt: o Cấu trúc dữ liệu: o Mảng board[MAX][MAX]: lưu bàn cờ, trong đĩ board[i][j] là ơ (i, j); giá trị của board[i][j] là 0 khi quân mã chưa đi qua, và >0 khi quân mã đã đi qua, giá trị board[i][j] lúc này chính là thứ tự nước đi trên hành trình. Thật sự cài đặt mảng board như vậy là đủ, nhưng nếu bổ sung thêm một tí thì sẽ tăng tốc độ thực hiện. Vấn đề bổ sung liên quan đến đường biên, do mỗi lần di chuyển quân mã ta phải kiểm tra xem nước đi cĩ ra ngồi biên hay khơng. Ta cĩ thể mở rộng mảng board để khơng cần phải kiểm tra bằng cách mở rộng hai ơ về bốn hướng trên dưới trái phải. Khi đĩ chỉ cần gán giá trị cho các ơ ngồi biên là -1. 58
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN Hình 3.12 : Mảng board cho bàn cờ 8x8 ⇒ 12x12. o Mảng dr[8], dc[8]: lưu các độ dời của bước đi kế tiếp, cĩ tám nước đi cĩ thể cho vị trí quân mã hiện tại. Do đĩ để đi nước thứ i ta chỉ cần cộng thêm dr[i] cho dịng và dc[i] cho cột! (-2, -1) (-2, 1) (-1, -2) (-1, 2) (1, -2) (1, 2) (2, -1) (2, 1) Hình 3.13: Thứ tự tám nước đi theo chiều kim đồng hồ. Mảng dr[] = {-2, -1, 1, 2, 2, 1, -1, -2} dc[] = {1, 2, 2, 1, -1, -2, -2, 1} o Thuật giải đệ quy: Tại mỗi bước lần lượt cho quân mã thử tất cả các nước đi kế tiếp (tám nước đi kế tiếp). Với mỗi bước đi, kiểm tra xem nếu nước đi hợp lệ (chưa đi qua và ở trong 59
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN bàn cờ) thì thử đi nước này. Nếu quân mã đã đi qua hết bàn cờ thì xuất kết quả. Ngược lại thì gọi đệ quy tiếp cho vị trí mới thử trên. Lưu ý là mỗi khi vị trí đã đi qua được đánh dấu chính bằng chính thứ tự nước đi trên bàn cờ. Sau khi khơng thử vị trí này thì phải bỏ đánh dấu để chọn giải pháp khác (trường hợp quay lui). Minh họa hàm Try với step là thứ tự của nước đi, i và j là vị trí của quân mã hiện tại. Try( int step, int i, j) { + Với mỗi nước đi kế tiếp (ii, jj) từ (i, j) + Nếu (ii,jj) hợp lệ chọn (ii, jj) làm nước đi kế tiếp + nếu đi hết bàn cờ Ư xuất 1 kết quả + ngược lại Gọi đệ quy Try(step +1, ii, jj) Khơng chọn (ii, jj) là nước đi kế tiếp } Chương trình C/C++ minh họa cho trường hợp bàn cờ 8x8. #include "stdafx.h" #include "conio.h" #include "stdlib.h" #define MAX 12 // trường hợp bàn cờ 8x8 void Show(int board[MAX][MAX]); void Init(int board[MAX][MAX]) { for(int i=0;i =2 && i =2 && j<=MAX-3) board[i][j]=0; // đánh dấu chưa đi qua else board[i][j]=-1; // đánh dấu biên } void Try(int step, int i, int j, int board[MAX][MAX], int *dr, int *dc) { 60
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN for(int k=0; k de tiep tuc tim loi \ giai ke. Nhan de thoat"); char c; if(c = getch() == 27) exit(1); } else // gọi đệ quy cho nước kế tiếp Try(step+1, i+dr[k], j+ dc[k], board, dr, dc); Board[i+dr[k]][j+dc[k]]= 0;// trả tự do cho vị trí vừa chọn }// end if }//end for } void Show(int board[MAX][MAX]) { for(int i=0;i<MAX;i++) { for(int j=0;j<MAX;j++) printf("%4d",board[i][j]); printf("\n\n"); } } void main() { int board[MAX][MAX]; int dr[8]={-2,-1,1, 2, 2, 1,-1,-2}; int dc[8]={1, 2, 2, 1,-1,-2,-2,-1}; Init(board); board[2][2]=1; // chọn vị trí đầu tiên Show(board); Try(1, 2, 2, board, dr, dc); } Một kết quả của chương trình như sau: 61
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN 1 38 43 34 3 36 19 22 44 59 2 37 20 23 4 17 39 42 33 60 35 18 21 10 58 45 40 53 24 11 16 5 41 32 57 46 61 26 9 12 50 47 52 25 54 15 6 27 31 56 49 62 29 8 13 64 48 51 30 55 14 63 28 7 Hình 3.14: Một giải pháp cho bàn cờ 8x8. \[ 62
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN Chương 4 Tìm kiếm và Sắp xếp \[ 4.1 Tìm kiếm Tìm kiếm là thao tác cơ bản, thường xuyên và quan trọng trong tin học. Ví dụ như tìm kiếm nhân viên trong danh sách nhân viên, tìm kiếm một sinh viên trong danh sách lớp học Các hệ thống thơng tin thường lưu trữ khối lượng dữ liệu lớn, nên thuật tốn tìm kiếm tốt sẽ cĩ nhiều lợi ích. Tuy nhiên, thao tác tìm kiếm cịn phụ thuộc rất nhiều đến dữ liệu được tổ chức như thế nào; nếu dữ liệu được tổ chức tốt thì việc tìm kiếm sẽ tiến hành nhanh chĩng và hiệu quả hơn. Giả sử sách được sắp theo chủ đề, thể loại thì dễ tìm kiếm hơn là khơng được sắp. Hoặc danh sách tên người được sắp theo thứ tự alphabet cũng dễ cho việc tìm kiếm 4.1.1 Mơ tả bài tốn tìm kiếm trong tin học Tìm kiếm là quá trình xác định một đối tượng nào đĩ trong một tập các đối tượng. Kết quả trả về là đối tượng tìm được hoặc một chỉ số (nếu cĩ) xác định vị trí của đối tượng trong tập đĩ. Việc tìm kiếm dựa theo một trường nào đĩ của đối tượng, trường này là khĩa (key) của việc tìm kiếm. Ví dụ: đối tượng sinh viên cĩ các dữ liệu {MaSV, HoTen, DiaChi, }. Khi đĩ tìm kiếm trên danh sách sinh viên thì khĩa thường chọn là MaSV hoặc HoTen. Thơng thường người ta phân làm hai loại tìm kiếm: tìm kiếm tuyến tính hay cịn gọi là tuần tự cho tập dữ liệu bất kỳ; tìm kiếm nhị phân cho tập dữ liệu đã được sắp xếp. Bài tốn tìm kiếm được mơ tả như sau: Tập dữ liệu được lưu trữ là dãy a1, a2, ,an. Giả sử chọn cấu trúc dữ liệu mảng để lưu trữ dãy số này trong bộ nhớ chính, cĩ khai báo: int a[n]; 63
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN Khố cần tìm là x cĩ kiểu nguyên : int x. Tìm kiếm Tìm kiếm tuyến tính Tìm kiếm nhị phân Tập DL Tập DL bất kỳ được sắp Hình 4.1: Phân loại phương pháp tìm kiếm 4.1.2 Tìm kiếm tuyến tính x ? a1 a2 a3 an-1 an Ý tưởng chính: duyệt tuần tự từ phần tử đầu tiên, lần lượt so sánh khĩa tìm kiếm với khố tương ứng của các phần tử trong danh sách (trong trường hợp mơ tả trên là so sánh x và a[i]). Cho đến khi gặp phần tử cần tìm hoặc đến khi duyệt hết danh sách. Các bước tiến hành như sau : Bước 1: i = 1 ; Bước 2: so sánh a[i] với x, cĩ hai khả năng i. a[i] = x: tìm thấy ⇒ dừng ii. a[i] n: hết mảng, khơng tìm thấy ⇒ dừng ii. ngược lại: quay lại bước 2 Hàm tìm kiếm tuyến tính đơn giản minh họa bằng ngơn ngữ C/C++. 64
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN int Search(int a[], int n, int key) { int i =0; while (i = n) return -1; // tìm khơng thấy else return i; // tìm thấy tại vị trí i } 4.1.3 Tìm kiếm nhị phân Phương pháp tìm kiếm nhị phân được áp dụng cho dãy khố đã cĩ thứ tự: k[1] ≤ k[2] ≤ ≤ k[n]. Ý tưởng của phương pháp này như sau: Giả sử ta cần tìm trong đoạn a[left right] với khố tìm kiếm là x, trước hết ta xét phần tử giữa a[mid], với mid = (left + right)/2. Nếu a[mid] x thì cĩ nghĩa là đoạn a[m] đến a[right] chỉ chứa khố > x, ta tiến hành tìm kiếm từ a[left] đến a[mid-1]. Nếu a[mid] = x thì việc tìm kiếm thành cơng. Quá trình tìm kiếm thất bại nếu left > right. Các bước tiến hành như sau: Bước 1: left =1, right = n // tìm kiếm trên tất cả phần tử. Bước 2: mid = (left + right)/2 // lấy mốc so sánh So sánh a[mid] với x cĩ 3 khả năng: - a[mid] = x, tìm thấy ⇒ dừng - a[mid]> x, tìm tiếp trong dãy a[left] a[mid-1] right = mid -1; - a[mid] < x, tìm tiếp trong dãy a[mid+1] a[right] left = mid +1; Bước 3: Nếu left ≤ right; cịn phần tử ⇒ tìm tiếp ⇒ bước 2 65
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN Ngược lại: dừng, đã xét hết phần tử ⇒ khơng tìm thấy. Ví dụ: cho dãy số gồm 8 phần tử {1, 2, 4, 5, 6, 8, 12, 15} và x = 8 X = 8 1 2 4 5 6 8 12 15 Left = 1 Mid = 4 Right = 8 Đoạn tìm kiếm X = 8 = 1 2 4 5 6 8 12 15 Left = 5 Mid = 6 Right = 8 Đoạn tìm kiếm Hình 4.2: Tìm kiếm nhị phân. Hàm C minh họa cài đặt thuật tốn tìm kiếm nhị phân int BinarySearch(int key) { int left = 0, right = n-1, mid; while (left <= right) { mid = (left + right)/ 2; // lấy điểm giữa if (a[mid] == key) // nếu tìm được return mid; if (a[mid] < x) // tìm đoạn bên phải mid left = mid+1; else right = mid-1; // tìm đoạn bên trái mid } return -1; // khơng tìm được } 66
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN 4.1.4 Kết luận Giải thuật tìm kiếm tuyến tính khơng phụ thuộc vào thứ tự của các phần tử trong mảng, do vậy đây là phương pháp tổng quát nhất để tìm kiếm trên một dãy bất kỳ. Thuật giải nhị phân dựa vào quan hệ giá trị của các phần tử trong mảng để định hướng trong quá trình tìm kiếm, do vậy chỉ áp dụng được với dãy đã cĩ thứ tự. Thuật giải nhị phân tìm kiếm nhanh hơn tìm kiếm tuyến tính. Tuy nhiên khi áp dụng thuật giải nhị phân thì cần phải quan tâm đến chi phí cho việc sắp xếp mảng. Vì khi mảng được sắp thứ tự rồi thì mới tìm kiếm nhị phân. 4.2 Bài tốn sắp xếp Sắp xếp là quá trình bố trí lại các phần tử của một tập đối tượng nào đĩ theo một thứ tự nhất định. Ví dụ như: tăng dần, giảm dần với một dãy số, thứ tự từ điển với các từ Việc sắp xếp là một bài tốn thường thấy trong tin học, do các yêu cầu tìm kiếm thuận lợi, sắp xếp kết quả các bảng biểu Dữ liệu thường được tổ chức thành mảng các mẫu tin dữ liệu, mỗi mẫu tin thường cĩ một số các trường dữ liệu khác nhau. Khơng phải tồn bộ các trường đều tham gia quá trình sắp xếp mà chỉ cĩ một trường nào đĩ (hoặc một vài trường) được quan tâm. Người ta gọi trường này là khố, việc sắp xếp sẽ được tiến hành dựa vào giá trị khố này. Ví dụ: sắp xếp một mảng các số nguyên tăng dần, sắp xếp một danh sách học sinh với điểm thi giảm dần 4.3 Một số phương pháp sắp xếp cơ bản Trong phần này giới thiệu một số phương pháp sắp xếp cơ bản thường được dùng để sắp xếp một danh sách, mảng dữ liệu. 4.3.1 Phương pháp chọn Đây là một trong những thuật tốn sắp xếp đơn giản nhất. Ý tưởng cơ bản của phương pháp này được thể hiện như sau: 67
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN 1. Ở lượt thứ nhất, ta chọn trong dãy khố k[1 n] ra khố nhỏ nhất và đổi giá trị nĩ với k[1], khi đĩ k[1] sẽ trở thành khố nhỏ nhất. 2. Ở lượt thứ hai, ta chọn trong dãy khố k[2 n] ra khĩa nhỏ nhất và đổi giá trị nĩ cho k[2]. 3. 4. Ở lượt thứ i, ta chọn trong dãy khĩa k[i n] ra khĩa nhỏ nhất và đổi giá trị nĩ cho k[i]. 5. Tới lượt k-1, ta chọn giá trị nhỏ nhất trong k[n-1] và k[n] ra khố nhỏ nhất và đổi cho giá trị cho k[n-1]. Thuật giải SelectionSort: (mã giả, chỉ số 1 là đầu mảng) begin for i:= 1 to n-1 do begin jmin := i; for j:=i+1 to n do if a[j] i) Swap(a[i], a[jmin]) end. end. 4.3.2 Phương pháp sắp xếp nổi bọt Trong thuật tốn sắp xếp nổi bọt, dãy khĩa sẽ được duyệt từ cuối lên đầu dãy, nếu gặp hai khĩa kế cận ngược thứ tự thì đổi chỗ cho nhau. Sau lần duyệt như vậy, khĩa nhỏ nhất trong dãy khĩa sẽ được chuyển về vị trí đầu tiên và vấn đề trở thành sắp xếp dãy khố từ k[n] đến k[2]. Thuật giải bubblesort: (mả giả, chỉ số 1 là đầu mảng) begin for i:=2 to n do for j:= n downto i do if (a[j] < a[j-1]) Swap(a[j],a[j-1]) end. 4.3.3 Phương pháp sắp xếp chèn Xét dãy khĩa k[1 n], ta thấy dãy con chỉ gồm mỗi một khố là k[1] cĩ thể coi là đã sắp xếp rồi. Xét thêm k[2], ta so sánh nĩ với k[1], nếu thấy k[2] < k[1] thì chèn nĩ vào trước k[1]. Đối với k[3], ta chỉ xét dãy chỉ gồm hai khố k[1] và k[2] đã sắp xếp 68
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN và tìm cách chèn k[3] vào dãy khĩa đĩ để được thứ tự sắp xếp. Một cách tổng quát, ta sẽ sắp xếp dãy k[1 i] trong điều kiện dãy k[1 i-1] đã sắp xếp rồi bằng cách chèn k[i] vào dãy đĩ tại vị trí đúng khi sắp xếp. Thuật giải InsertionSort: (mả giả, chỉ số 1 là đầu mảng) begin for i:= 2 to n do begin tmp = a[i]; j = i-1; while (j>0) and (tmp tạo khoảng trống j := j-1; end k[j+1] = tmp; // chèn vào khoảng trống. end end. 4.3.4 Phương pháp đổi chỗ trực tiếp Ý tưởng chính: xuất phát từ đầu dãy, tìm những phần tử cịn lại khơng thoả thứ tự sắp xếp với phần tử đang xét, hốn vị các phần tử tương ứng để thỏa thứ tự. Lặp lại tương tự với các phần tử tiếp theo của dãy. Các bước tiến hành như sau: Bước 1: i = 1; // xuất phát từ đầu dãy Bước 2: j = i+1; // tìm các phần tử phía sau i Bước 3: o While j ≤ n do Nếu a[j]< a[i] ⇒ Swap(a[i], a[j]); j = j+1; Bước 4: i = i+1; o Nếu i < n: ⇒ Bước 2 o Ngược lại ⇒ Kết thúc Ví dụ: cho dãy số a: 10 3 7 6 2 5 4 16 69
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN 70
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN 71
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN 72
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN Hình 4.3: Minh họa đổi chỗ trực tiếp. 4.3.5 Phương pháp ShellSort Trong phương pháp sắp xếp kiểu chèn nếu ta luơn phải chèn một khĩa vào vị trí đầu dãy thì dẫn đến hạn chế của thuật tốn này. Để khắc phục trong trường hợp này thì người ta đưa ra một phương pháp sắp xếp là ShellSort. Ý tưởng chính: xét một dãy a[1] a[n], cho một số nguyên h (1 ≤ h ≤ n), ta cĩ thể chia dãy đĩ thành h dãy con như sau: Dãy con 1: a[1], a[1+ h], a[1+2h] Dãy con 2: a[2], a[2+h], a[2+2h] Dãy con 3: a[3], a[3+h], a[3+2h] Dãy con h: a[h], a[2h], a[3h] Ví dụ cho dãy: 10 3 7 6 2 5 4 16 n = 8, h = 3. Ta cĩ dãy con sau: Dãy chính 10 3 7 6 2 5 4 16 73
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN Dãy con 1 10 6 4 Dãy con 2 3 2 16 Dãy con 3 7 5 Những dãy này được coi là những dãy con xếp theo độ dài bước h. Tư tưởng chính của thuật tốn ShellSort là: với mỗi bước h, áp dụng thuật tốn sắp xếp kiểu chèn từng dãy con độc lập để làm mịn dần các phần tử trong dãy chính. Tiếp tục làm tương tự đối với bước (h div 2) cho đến khi h = 1 thì ta được dãy phần tử được sắp. Xét trong ví dụ trên, nếu chúng ta dùng phương pháp chèn thì với phần tử a[5] = 2 là phần tử nhỏ nhất trong dãy, do đĩ nĩ phải chèn vào vị trí thứ 1, tức là phải chèn trước 4 phần tử trước nĩ. Nhưng nếu chúng ta xem 2 là phần tử của dãy 2 thì ta chỉ cần chèn trước một phần tử là 3. Đây chính là nguyên nhân thuật tốn ShellSort thực hiện hiệu quả hơn sắp xếp chèn. Khi đĩ khĩa nhỏ nhanh chĩng đưa về gần vị trí đúng của nĩ. Các bước thực hiện chính như sau: Bước 1: chọn k khoảng cách h[1], h[2], , h[k], và i = 1. Bước 2: Chia dãy ban đầu thành các dãy con cĩ bước nhảy là h[i]. Thực hiện sắp xếp từng dãy con bằng phương pháp chèn trực tiếp. Bước 3: i = i+1 o Nếu i > k: ⇒ Dừng o Ngược lại: ⇒ Bước 2. Ví dụ: cho dãy bên dưới với n = 8, h = {5, 3, 1}. 10 3 7 6 2 5 4 16 Ta cĩ minh họa như sau: 74
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN Hình 4.4: Minh hoạ ShellSort. 75
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN Cài đặt ShellSort: sắp xếp dãy a[] tăng, với h[] là mảng chứa các độ dài (bước nhảy) đã chọn sẵn: void ShellSort(int a[], int n, int h[], int k) { int step, i, j; int x, len; for(step = 0; step = 0)) // sắp xếp dãy con chứa x dùng pp chèn { a[j+len] = a[j]; // dời về sau theo dãy con j = j – len; // qua phần tử trước trong dãy con } a[j+len] = x;// đưa x vào vị trí thích hợp trong dãy con } } } 4.3.6 Phương pháp phân đoạn QuickSort Đây là một phương pháp sắp xếp tốt do C.A.R Hoare đề xuất. Thuật tốn này cĩ tốc độ trung bình nhanh hơn các thuật tốn sắp xếp tổng quát khác. Do đĩ Hoare dùng chữ “Quick” để đặt tên cho thuật tốn này. Ý tưởng chính: Để sắp dãy a[1] a[n], ta thực hiện sắp xếp dãy a từ chỉ số 1 đến chỉ số n. QuickSort dựa trên phân hoạch dãy ban đầu thành hai phần dựa vào giá trị x, x là giá trị của một phần tử tùy ý trong dãy ban đầu: Dãy thứ 1: gồm các phần tử a[1] a[i] cĩ giá trị khơng lớn hơn x. Dãy thứ 2: gồm các phần tử a[i] a[n] cĩ giá trị khơng nhỏ hơn x. Sau khi phân hoạch thì dãy ban đầu được phân thành ba phần: 1. a[k] < x, với k = 1 i 2. a[k] = x, với k = i j 76
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN 3. a[k] > x, với k = j n Ta cĩ nhận xét khi đĩ dãy con thứ 2 đã cĩ thứ tự, nếu dãy con 1 và dãy con 3 cĩ một phần tử thì chúng cũng đã cĩ thứ tự, khi đĩ dãy ban đầu đã được sắp. Ngược lại, nếu dãy con 1 và 3 cĩ nhiều hơn một phần tử thì dãy ban đầu cĩ thứ tự khi dãy con 1 và 3 được sắp. Để sắp xếp dãy con 1 và 3, ta lần lượt tiến hành việc phân hoạch từng dãy con theo cùng phương pháp vừa trình bày. Giải thuật phân hoạch dãy a[left], a[left+1], , a[right] thành hai dãy con: Bước 1: Chọn tùy ý một phần tử a[k] trong dãy là giá trị mốc, left ≤ k ≤ right, o Cho x = a[k], i = left, j = right. Bước 2: Tìm và hốn vị cặp phần tử a[i] và a[j] khơng đúng thứ tự đang sắp. o Bước 2-1: Trong khi a[i] x ⇒ j ; o Bước 2-3: Nếu i x Bước 2: o Nếu (left < j) // dãy con 1 cĩ nhiều hơn 1 phần tử Phân hoạch dãy a[left] a[j] o Nếu (i < right) // dãy con 3 cĩ nhiều hơn 1 phần tử Phân hoạch dãy a[i] a[right] Ví dụ phân hoạch dãy sau: 10 3 7 6 2 5 4 16 Phân hoạch đoạn left = 1, right = 8, x = a[4] = 6 77
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN Phân hoạch đoạn left = 1, right = 4, x = a[2] = 3 Phân hoạch đoạn left = 3, right = 4, x = a[3] = 5 Phân hoạch đoạn left = 6, right = 8, x = a[7] = 10 78
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN QuickSort được cài đặt đệ quy như sau: void QuickSort(int a[], int left, int right) { int i, j; int x; x = a[(left+right)/2]; // chọn phần tử giữa làm gốc i = left; j = right; do{ while (a[i] = x while (a[j] > x) j ; // lặp đến khi a[i] i) // phân hoạch đoạn bên phải QuickSort(a, i, right); } 79
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN 4.3.7 Phương pháp cơ số RadixSort Thuật giải sắp xếp theo phương pháp cơ số khơng quan tâm đến việc so sánh giá trị của các phần tử như các thuật giải trước. RadixSort sử dụng cách thức phân loại các con số trong dãy và thứ tự phân loại con con số này để tạo ra thứ tự cho các phần tử. Đây là cách tiếp cận khác so với các phương pháp sắp xếp trước là so sánh các giá trị của các phần tử. Thuật giải dựa trên ý tưởng chính là sắp xếp từng con số của một dãy các số. Giả sử chúng ta cĩ dãy số như sau: 493 812 715 710 195 437 582 340 385. Đầu tiên sắp xếp các số theo hàng đơn vị: 493 812 715 710 195 437 582 340 385. Ta được bảng kết quả minh họa như sau: Số hàng đơn vị Dãy con 0 710 340 1 - 2 812 582 3 493 4 - 5 715 195 385 6 - 7 437 8 - 9 - Bảng 4.1: Sắp theo hàng đơn vị Lưu ý những phần tử này được đưa vào dãy con theo thứ tự tìm thấy, do đĩ chúng ta cĩ thể thấy là các dãy con chưa cĩ thứ tự. Lúc này chúng ta thu được một danh sách gồm các dãy con từ 0 → 9 như sau: 710 340 812 582 493 715 195 385 437 Tiếp tục chúng ta phân loại các phần tử của dãy trên theo con số của hàng chục: 710 340 812 582 493 715 195 385 437 80
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN Số hàng chục Dãy con 0 - 1 710 812 715 2 - 3 437 4 340 5 - 6 - 7 - 8 582 385 9 493 195 Bảng 4.2: Sắp theo hàng chục Lúc này chúng ta thu được danh sách như sau: 710 812 715 437 340 582 385 493 195 Thực hiện tiếp với phân loại các con số hàng trăm: 710 812 715 437 340 582 385 493 195 Số hàng trăm Dãy con 0 - 1 195 2 - 3 340 385 4 437 493 5 582 6 - 7 710 715 8 812 9 - Bảng 4.3: Sắp theo hàng trăm Thu được danh sách các phần tử từ dãy con được phân loại theo hàng trăm từ 0 → 9. 195 340 385 437 493 582 710 715 812 81
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN Như chúng ta thấy thì lúc này dãy đã được sắp! Tĩm lại để sắp xếp dãy a[1], a[2], , a[n] giải thuật RadixSort thực hiện như sau: Xem mỗi phần tử a[i] trong dãy a[1] a[n] là một số nguyên cĩ tối đa m chữ số Lần lượt phân loại các chữ số theo hàng đơn vị, hàng chục, hàng trăm Tại mỗi bước phân loại ta sẽ nối các dãy con từ danh sách đã phân loại theo thứ tự 0 → 9. Sau khi phân loại xong ở hàng thứ m cao nhất ta sẽ thu được danh sách các phần tử được sắp. Các bước thực hiện thuật giải: Bước 1: k = 0; // k là chữ số phân loại, k = 0 hàng đơn vị, k = 1 hàng chục Bước 2: // Tạo các dãy chứa phần tử phân loại B[0] B[9] Khởi tạo B[0] B[9] rỗng, chưa chứa phần tử nào, B[i] sẽ chứa các phần tử cĩ chữ số thứ k là i. Bước 3: o For i=1 to n do Đặt a[i] vào dãy B[j] với j là chữ số thứ k của a[i]. o Nối B[0], B[1], , B[9] lại theo đúng trình tự thành a. Bước 4: o k = k +1 o Nếu k < m: ⇒ Bước 2. // m là số lượng chữ số tối đa của các số trong mảng o Ngược lại: ⇒ Dừng. Giải thuật sắp xếp theo cơ số RadixSort: Mảng a[MAX] chứa các phần tử của mảng cần sắp tăng. Mảng B[10][MAX] chứa các dãy số được phân tạm thời theo các con số. Ví dụ B[0] chứa các phần tử cĩ con số ở hàng đơn vị là 100, 210, 320 Khi đĩ với mỗi dịng của B thì sẽ phân các phần tử cĩ con số ở hàng thứ i (i từ 0 - 9), các giá trị cột j sẽ lần lượt chứa các phần tử cĩ cùng con số ở hàng thứ i. Mảng Len[10] chứa số lượng các phần tử của các dịng B[i]. Ví dụ B[0] cĩ 3 phần tử thì Len[0] = 3, B[5] cĩ 2 phần tử thì B[5] = 2. Tại mỗi bước trước khi phân các phần tử vào mảng B thì các Len[i] được khởi tạo là 0. Cài đặt RadixSort: 82
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN void RadixSort(long a[], int n) { int i, j, d; int h = 10; // biến để lấy các con số, bắt đầu từ hàng đơn vị long B[10][MAX]; // mảng hai chiều chứa các phần tử phân lơ int Len[10]; // kích thước của từng mảng B[i] // MAXDIGIT là số con số tối đa của các phần tử a[i] for(d = 0; d < MAXDIGIT; d++) { // khởi tạo kích thước các dãy B[i] là 0 for( i = 0; i < 10; i++) Len[i] = 0; // thực hiện phân lơ các phần tử theo con số hàng thứ d tính từ cuối for(i = 0; i < n; i++) // duyệt qua tất cả các phần tử của mảng { digit = (a[i] % h) / (h/ 10); // lấy con số theo hàng h // đưa vào dãy (lơ) B[digit] ở cột Len[digit] B[digit][Len[digit]++] = a[i]; }// end for i // thực hiện nối lại tuần tự từ B[0] – đến B[9] vào mảng a[] ban đầu num = 0; // chỉ số bắt đầu cho mảng a[] for(i = 0; i < 10; i++) // duyệt qua các dãy từ B[0] – đến B[9] { // lấy từng phần tử của từng dãy B[i] for(j =0; j < Len[i]; j++) a[num++] = B[i][j]; }// end for i h *= 10; // qua hàng kế tiếp. }// end for d }// end RadixSort \[ 83
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN Chương 5 Stack - Queue \[ 5.1 Giới thiệu Stack – ngăn xếp Ngăn xếp là kiểu danh sách với hai thao tác đặc trưng bổ sung một phần tử vào cuối danh sách và loại bỏ một phần tử cũng ở cuối danh sách. Nĩi một cách khác là thao tác thêm phần tử và loại phần tử chỉ diễn ra ở một đầu của danh sách. Đưa vào (Push) Lấy ra (Pop) Đỉnh stack (top) Stack Hình 5.1: Minh họa Stack. Chúng ta cĩ thể hình dung một cách đơn giản như hình ảnh một chồng đĩa, đĩa nào được đặt vào chồng sau cùng sẽ nằm trên tất cả đĩa khác và sẽ được lấy ra đầu tiên. Vì nguyên tắc vào sau ra trước đĩ, Stack cịn cĩ tên gọi là danh sách kiểu LIFO (Last In First Out). Vị trí cuối cùng được gọi là đỉnh (top) của ngăn xếp. Hai thao tác chính trên Stack là: 1. Thao tác push: đưa một phần tử vào đỉnh của Stack 2. Thao tác pop: xố đi một phần tử ở đỉnh của Stack. Ví dụ: Cho Stack S và các thao tác như sau: 1. Khởi tạo S là rỗng như hình 5.2.1. 2. Thêm một phần tử vào Stack S: Push(S, A) cĩ kết quả như hình 5.2.2 3. Thêm một phần tử vào Stack S: Push(S, B) cĩ kết quả như hình 5.2.3. 4. Loại phần tử đầu Stack S: Pop(S) ta được Stack S như hình 5.2.4. 84
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN 5. Thêm phần tử vào Stack S: Push(S, C) kết quả Stack S như hình 5.2.5. Hình 5.2: Minh họa các thao tác trên Stack. 5.1.1 Cài đặt Stack dùng CTDL mảng Trong phần này chúng ta sẽ cài đặt một Stack dùng cấu trúc dữ liệu mảng. Để cho tổng quát ta gọi Data là kiểu dữ liệu được định nghĩa mà Stack lưu trữ, ví dụ Data cĩ thể là số nguyên, thực hoặc một cấu trúc dữ liệu nào đĩ: typedef int Data typedef float Data typedef struct { int ID; char Name[50]; float Salary; } Data; Khai báo cấu trúc dữ liệu Stack trên mảng: #define MAX 100 typedef struct{ int top; Data S[MAX]; } Stack; 85
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN Hình 5.3: Minh họa Stack dùng mảng một chiều. Trong cấu trúc Stack này các trường cĩ ý nghĩa như sau: top: chỉ đến đỉnh của Stack, top = -1 ⇒ Stack rỗng, top ≥ 0 ⇒ Stack cĩ phần tử S[MAX]: chứa dữ liệu của Stack lưu trữ, để truy cập đến phần tử đỉnh thì dùng trường top. Các thao tác trên Stack được mơ tả như sau: void Push(Stack &st, Data x): Đưa một phần tử x vào đỉnh của Stack. Data Pop(Stack &st): Lấy một phần tử ở đỉnh ra khỏi Stack. void InitStack(Stack &st): Hàm khởi tạo một Stack mới rỗng int IsEmpty(Stack st): Kiểm tra xem Stack cĩ rỗng hay khơng. int IsFull(Stack st): Kiểm tra xem Stack đầy hay chưa. Data Top(Stack st): Xem một phần tử ở đỉnh (khơng lấy ra). Cài đặt của các thao tác: #define TRUE 1 #define FALSE 0 void Push(Stack &st, Data x) { if (IsFull(st)) { printf(“\nStack full!”); } else st.S[++st.top] = x; } Data Pop(Stack &st) { if (IsEmpty(st)) printf(“\nStack empty!”); else return (st.S[st.top ]); } 86
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN void InitStack(Stack &st) { st.top = -1; } int IsEmpty(Stack st) { if (st.top == -1) return TRUE; else return FALSE; } int IsFull(Stack st) { if (st.top >= MAX) return TRUE; else return FALSE; } Data Top(Stack st) { Data d; if (IsEmpty(st)) printf(“\n Stack empty!”); else d = st.S[st.top]; return d; } 5.1.2 Các ứng dụng stack Thơng thường cấu trúc dữ liệu stack thích hợp cho việc lưu trữ dữ liệu mà trình tự truy xuất ngược với trình tự lưu trữ. Cĩ nghĩa là dữ liệu lưu trữ trước sẽ được lấy ra sau những dữ liệu lưu sau (LIFO). Do đĩ stack cĩ một số ứng dụng như sau: Trong trình biên dịch, stack dùng để lưu trữ các lời gọi hàm, ví dụ như hàm A gọi hàm B, hàm B lại gọi hàm C, khi hàm C thực hiện xong thì sự điều khiển chương trình sẽ trở về thực hiện chương trình B. Rồi khi hàm B thực hiện xong thì sự điều khiển chương trình sẽ được trả về cho A. Khi đĩ ta thấy là hàm C được gọi sau cùng và chúng được thực hiện xong trước tiên rồi mới đến B và A. Đây là dạng thực hiện sau và kết thúc trước. 87
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN Hàm A Hàm B Hàm C Hình 5.4: Minh họa xử lý gọi hàm trong trình biên dịch Lưu trữ dữ liệu để giải các bài tốn lý thuyết đồ thị. Ví dụ như tìm chu trình Euler, tìm đường đi Ngồi ra, stack cịn được sử dụng để khử một số bài tốn đệ quy. Cịn rất nhiều ứng dụng của Stack 5.1.3 Các ví dụ minh họa Chương trình xuất chuỗi ký tự theo thứ tự ngược lại Sử dụng stack chứa dữ liệu là các ký tự, khi đĩ ta sẽ push lần lượt các ký tự của chuỗi vào stack và sau đĩ lấy (Pop) lần lượt các ký tự này ra. Kết quả là chuỗi được xuất dưới dạng đảo ngược lại. #include "stdio.h" #include "conio.h" #include "string.h" #define TRUE 1 #define FALSE 0 #define MAX 100 typedef char Data; typedef struct{ int top; Data S[MAX]; } Stack; void Push(Stack & st, Data x); Data Pop(Stack &st); void InitStack(Stack &st); int IsEmpty(Stack st); int IsFull(Stack st); Data Top(Stack st); void Push(Stack & st, Data x) { if (IsFull(st)) printf("\nStack is full!"); 88
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN else st.S[++st.top] = x; } Data Pop(Stack &st) { if (IsEmpty(st)) printf("\nStack is empty!"); else return (st.S[st.top ]); } void InitStack(Stack &st) { st.top = -1; } int IsEmpty(Stack st) { if (st.top == -1) return TRUE; else return FALSE; } int IsFull(Stack st) { if (st.top >= MAX) return TRUE; else return FALSE; } Data Top(Stack st) { Data d; if (IsEmpty(st)) printf("\n Stack is empty!"); else d = st.S[st.top]; return d; } void main() { char s[MAX]; Stack st; clrscr(); printf("Nhap chuoi: "); 89
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN gets(s); InitStack(st); for(int i=0; i < strlen(s); i++) Push(st, s[i]); printf("\n Chuoi nguoc lai: "); while (!IsEmpty(st)) printf("%c", Pop(st)); getch(); } Chương trình đổi số sang hệ cơ số bất kỳ. #include "stdio.h" #include "conio.h" #include "string.h" #define MAX 100 #define TRUE 1 #define FALSE 0 typedef unsigned int Data; typedef struct{ int top; Data S[MAX]; } Stack; void Push(Stack & st, Data x); Data Pop(Stack &st); void InitStack(Stack &st); int IsEmpty(Stack st); int IsFull(Stack st); Data Top(Stack st); void Push(Stack & st, Data x) { if (IsFull(st)) printf("\nStack is full!"); else st.S[++st.top] = x; } Data Pop(Stack &st) { if (IsEmpty(st)) printf("\nStack is empty!"); else return (st.S[st.top ]); 90
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN } void InitStack(Stack &st) { st.top = -1; } int IsEmpty(Stack st) { if (st.top == -1) return TRUE; else return FALSE; } int IsFull(Stack st) { if (st.top >= MAX) return TRUE; else return FALSE; } Data Top(stack st) { Data d; if (IsEmpty(st)) printf("\n Stack is empty!"); else d = st.S[st.top]; return d; } void main() { char s[MAX]; int coso, so, du; stack st; clrscr(); printf("Nhap co so can doi: "); scanf("%d", &coso); printf("Nhap so:"); scanf("%d",&so); InitStack(st); while (so != 0) { du = so % coso; Push(st, du); 91
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN so = so/coso; } printf("\n Co so : "); while (!IsEmpty(st)) printf("%3X", Pop(st)); getch(); } Bài tốn tháp Hanoi Bài tốn tháp Hanoi thường được giải bằng phương pháp đệ quy, trong chương trước đã trình bày. Tuy nhiên cĩ thể giải bằng cách dùng stack để khử đệ quy. Để thực hiện việc lưu trữ tạm trong quá trình di chuyển chúng ta dùng một stack. Trong đĩ mỗi phần tử của stack này chứa các thơng tin gồm: số đĩa di chuyển (N), cột nguồn bắt đầu di chuyển (Nguon) và cột đích là nơi cần di chuyển đến (Dich). Ở đây khơng cần lưu cột trung gian vì cĩ 3 cột đánh số là 1, 2 và 3 thì cột trung gian để di chuyển là: 6 – (Nguon+Dich). Đầu tiên đưa vào stack thơng tin di chuyển {n, 1, 2}, tức là di chuyển n đĩa từ cột 1 sang cột thứ 2 qua cột trung gian là 6-(1+2) = 3. Tại mỗi bước khi lấy trong stack ra một phần tử, thực hiện như sau: Nếu N = 1: ⇒ di chuyển đĩa từ cột Nguon ⇒ cột Dich Ngược lại (nếu N > 1): • Xác định cột trung gian TrungGian = 6 – (Nguon+Dich) • Push ⇒ stack thơng tin di chuyển {N-1, TrungGian, Dich} • Push ⇒ stack thơng tin di chuyển {1, Nguon, Dich} • Push ⇒ stack thơng tin di chuyển {N-1, Nguon, TrungGian} Quá trình cịn thực hiện khi stack khác rỗng. Nhận xét: lưu ý thứ tự khi đưa vào thơng tin di chuyển vào stack. Trong phần trên thơng tin {N-1, Nguon, TrungGian} được đưa vào stack sau cùng nên chúng sẽ được lấy ra trước tiên, kế đến là thơng tin di chuyển {1, Nguon, Dich} và cuối cùng là thơng tin di chuyển {N-1, TrungGian, Dich}. Chương trình minh họa: #include "stdio.h" #include "conio.h" #define MAX 100 #define TRUE 1 92
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN #define FALSE 0 typedef struct { int N; // số đĩa cần di chuyển int Nguon; // cột bắt đầu di chuyển int Dich; // cột đích đến } Data; typedef struct{ int top; Data S[MAX]; } stack; void Push(stack & st, Data x); Data Pop(stack &st); void InitStack(stack &st); int IsEmpty(stack st); int IsFull(stack st); Data Top(stack st); void Push(stack & st, Data x) { if (IsFull(st)) printf("\nStack full!"); else st.S[++st.top] = x; } Data Pop(stack &st) { if (IsEmpty(st)) printf("\nStack empty!"); else return (st.S[st.top ]); } void InitStack(stack &st) { st.top = -1; } int IsEmpty(stack st) { if (st.top == -1) return TRUE; 93
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN else return FALSE; } int IsFull(stack st) { if (st.top >= MAX) return TRUE; else return FALSE; } Data Top(stack st) { Data d; if (IsEmpty(st)) printf("\n Stack is empty!"); else d = st.S[st.top]; return d; } void Hanoi(int n) { stack st; // stack chứa thơng tin di chuyển InitStack(st); // khởi tạo stack Data d,d1,d2,d3; // các biến tạm chứa thơng tin di chuyển. int TrungGian; // cột trung gian // đưa thơng tin ban đầu vào stack {n, 1, 2} : di chuyển n đĩa từ cột 1 đến 2 d.N = n; d.Nguon = 1; d.Dich = 2; Push(st, d); // đưa vào stack while (!IsEmpty(st)) // lặp khi stack cịn phần tử { d = Pop(st); // lấy một phần tử đầu stack ra thực hiện if (d.N == 1) // nếu chỉ cĩ một đĩa thì di chuyển Nguồn → Đích printf("\nDi chuyen: %d -> %d", d.Nguon, d.Dich); else // nhiều hơn một đĩa { TrungGian = 6 - (d.Nguon+d.Dich); // lấy cột Trung gian 94
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN /* Đưa vào stack theo thứ tự ngược lại. Tức là đưa vào thơng tin: di chuyển N-1 đĩa từ cọc trung gian đến cọc đích, di chuyển 1 đĩa từ nguồn sang đích, và cuối cùng đưa N-1 đĩa từ cọc nguồn sang trung gian. Khi đĩ lấy từ stack ra chúng ta sẽ cĩ thứ tự ngược lại là: di chuyển N-1 đĩa từ cọc nguồn sang trung gian, di chuyển 1 đĩa từ cọc nguồn sang đích và cuối cùng di chuyển N-1 đĩa từ cọc trung gian sang đích. Đây chính là thứ tự mà chúng ta cần thực hiện chuyển N đĩa từ cọc nguồn sang đích. */ // đưa thơng tin di chuyển N-1 đĩa từ Trung gian → Đích d1.N = d.N-1; d1.Nguon = TrungGian; d1.Dich = d.Dich; Push(st,d1); // đưa thơng tin di chuyển 1 đĩa từ Nguồn → Đích d2.N = 1; d2.Nguon = d.Nguon; d2.Dich = d.Dich; Push(st, d2); // đưa thơng tin di chuyển N-1 đĩa từ Nguồn → Trung gian d3.N = d.N -1; d3.Nguon = d.Nguon; d3.Dich = TrungGian; Push(st,d3); } } // end while stack <> ∅ } // end Hanoi int main() { int n; clrscr(); printf("Nhap vao so cot: "); scanf("%d",&n); Hanoi(n); getch(); return 0; } Thuật tốn QuickSort sử dụng stack 95
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN Như chúng ta đã biết thì thuật tốn QuickSort thường được cài đặt bằng giải thuật đệ quy. Tuy nhiên một cách khác là dùng cấu trúc dữ liệu stack để cài đặt cũng tốt. Cách thực hiện là tạo một cấu trúc stack để lưu trữ hai biên trái và phải của một đoạn. Ví dụ như khi phân đoạn left đến right, chúng ta được ba đoạn là [left i] là các phần tử nhỏ hơn x, đoạn [i+1 j-1] là các phần tử bằng x, và đoạn cuối là [j right]. Khi đĩ chúng ta sẽ đưa vào stack đoạn bên phải, nếu đoạn bên trái nhiều hơn một phần tử ta cập nhật lại right = i, khi đĩ chúng ta sẽ lặp lại với đoạn [left i] một cách tương tự, khi đoạn bên trái hết thì chúng ta sẽ lấy từ trong stack ra những đoạn được lưu giữ để thực hiện tiếp tục quá trình thực hiện cho đến khi stack rỗng. #include "stdio.h" #include "conio.h" #include "stdlib.h" #define TRUE 1 #define FALSE 0 #define MAX 100 typedef struct { int left; int right; } Data; typedef struct{ int top; Data S[MAX]; } stack; void Push(stack & st, Data x); Data Pop(stack &st); void InitStack(stack &st); int IsEmpty(stack st); int IsFull(stack st); Data Top(stack st); void Swap(int &a, int &b) { int tmp =a; a = b; b = tmp; } 96
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN void Push(stack & st, Data x) { if (IsFull(st)) printf("\nStack is full!"); else st.S[++st.top] = x; } Data Pop(stack &st) { if (IsEmpty(st)) printf("\nStack is empty!"); else return (st.S[st.top ]); } void InitStack(stack &st) { st.top = -1; } int IsEmpty(stack st) { if (st.top == -1) return TRUE; else return FALSE; } int IsFull(stack st) { if (st.top >= MAX) return TRUE; else return FALSE; } Data Top(stack st) { Data d; if (IsEmpty(st)) printf("\n Stack is empty!"); else d = st.S[st.top]; return d; } void QuickSort(int a[MAX], int n) 97
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN { int i, j, l, r; int x; l = 0; r = n-1; stack st; InitStack(st); while (l x) j ; if ( i i) { Data d; d.left = i; d.right = r; Push(st,d); } if (l < j) { r = j; } else if (!IsEmpty(st)) { Data d = Pop(st); l = d.left; r = d.right; } else 98
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN break; // thoat khoi vong lap -> while (l < r) } } void main() { int a[MAX] ; int n = 30; clrscr(); randomize(); printf("Mang truoc khi sap: \n"); for(int i=0; i < n;i++) { a[i] = random(100); printf("%4d", a[i]); } QuickSort(a,n); printf("\nMang sau khi sap:\n"); for(i=0; i <n; i++) printf("%4d",a[i]); getch(); } Bài tốn chuyển biểu thức trung tố sang hậu tố. Như chúng ta đã biết một biểu thức được biểu diễn dưới dạng hậu tố hay cịn gọi là ký pháp nghịch đảo Ba Lan RPN (Reverse Polish Notation) giúp ích rất nhiều cho việc tính tốn giá trị biểu thức tốt hơn là biểu thức dạng trung tố. Các trình biên dịch máy tính thường chuyển những biểu thức trung tố sang hậu tố để dễ xử lý hơn. Trong phần này chúng ta sẽ tìm hiểu thuật tốn để chuyển một biểu thức dạng trung tố đơn giản sang biểu thức hậu tố tương ứng. Ví dụ một biểu thức trung tố như sau: (6 / 2 + 3) * (7 - 4) được chuyển thành biểu thức hậu tố như sau: 6 2 / 3 + 7 4 - *. Chúng ta cĩ thể thấy cách biểu diễn của trung tố cần phải xử lý dấu ngoặc trong khi biểu thức hậu tố thì khơng cần sử dụng. Đây là ưu điểm của biểu thức hậu tố. Để chuyển đổi chúng ta sử dụng một Stack dùng lưu trữ các tốn tử và dấu ngoặc mở. Ngồi ra cũng quy định độ ưu tiên của các tốn tử thơng qua hàm Priority, trong đĩ phép tốn *, / cĩ độ ưu tiên cao nhất là 2, phép tốn +, - cĩ độ ưu tiên ít hơn là 1, và cuối cùng dấu ngoặc mở ‘(’ là 0. Ý tưởng của thuật tốn: 99
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN Duyệt qua từng phần tử trong biểu thức trung tố, gọi C là phần tử đang xét: Nếu C là ‘(’ thì push vào stack Nếu C là ‘)’ thì lấy trong stack ra cho đến khi gặp ‘(‘: xuất ra những phần tử này. Nếu C là tốn tử ‘+’,’-‘,’*’,’/’: Lấy trong stack ra tất cả những tốn tử cĩ độ ưu tiên cao hơn C, xuất những phần tử này ra ngồi. Sau đĩ đưa C vào stack. Cuối cùng lấy tất cả những phần tử cịn lại trong stack xuất ra ngồi. Thuật tốn chuyển đổi từ trung tố sang hậu tố: Stack = {∅}; // khởi tạo stack rỗng for do { if ( C == ‘(‘ ) Push(Stack, C); // đưa vào stack else if ( C== ‘)’) { do { x = Pop(Stack); // lấy từ stack ra cho đến khi gặp ‘(‘ if (c != ‘(‘) printf(“%c”, x); } while ( x!= ‘(‘) } else if (C == ‘+’ || C ==’-‘ || C == ‘*’ || C==’/’) { while ( !IsEmpty(Stack) && Priority(C) <= Priority(Top(Stack))) printf(“%c”, Pop(Stack)); // nếu độ ưu tiên tốn tử trong // stack lớn hơn thì lấy ra. Push(Stack, C); // đưa tốn tử mới vào stack } else // tốn hạng printf(“%c”,C); } while ( !IsEmpty(Stack)) // lặp để lấy tất cả các phần tử trong stack ra printf(“%c”, Pop(Stack)); Ví dụ khi thực hiện với biểu thức trung tố: (2 * 3 + 7 / 8) * (5 – 1) 100
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN Đọc Xử lý Stack Output ( Đẩy vào stack ( 2 Xuất ( 2 Do ‘*’ ưu tiên hơn ‘(‘ ở đỉnh stack nên đưa ‘*’ * ( * 2 vào stack 3 Xuất ( * 2 3 Do ‘+’ ưu tiên thấp hơn ‘*’ ở đỉnh stack nên ta lấy ‘*’ ra. + ( + 2 3 * Tiếp tục so sánh ‘+’ với ‘(‘ thì ‘+’ ưu tiên cao hơn nên đưa vào stack 7 Xuất ( + 2 3 * 7 Do ‘/’ cĩ độ ưu tiên cao hơn ‘+’ trên đỉnh stack / ( + / 2 3 * 7 nên đưa ‘/’ vào stack. 8 Xuất ( + / 2 3 * 7 8 ) Lấy trong stack ra cho đến khi gặp ngoặc (. 2 3 * 7 8 / + * Đưa vào stack * 2 3 * 7 8 / + ( Đưa vào stack * ( 2 3 * 7 8 / + 5 Xuất * ( 2 3 * 7 8 / + 5 Độ ưu tiên của ‘-‘ cao hơn ‘(‘ trong đỉnh stack - * ( - 2 3 * 7 8 / + 5 nên đưa ‘-‘ vào stack 1 Xuất * ( - 2 3 * 7 8 / + 5 1 ) Lấy trong stack ra cho đến khi gặp ngoặc đĩng * 2 3 * 7 8 / + 5 1 - Lấy những phần tử cịn lại trong stack và hiển 2 3 * 7 8 / + 5 1 - * thị Bài tốn tính giá trị biểu thức hậu tố. Trong những năm đầu 1950 nhà logic học người Ba Lan Jan Lukasiewicz đã chứng minh rằng: biểu thức hậu tố khơng cần cĩ dấu ngoặc vẫn cĩ thể tính đúng bằng cách đọc lần lượt biểu thức từ trái qua phải và dùng một stack để lưu trữ kết quả trung gian. Các bước thực hiện như sau: Bước 1: Khởi tạo một stack = {∅} Bước 2: Đọc lần lượt các phần tử của biểu thức hậu tố từ trái sang phải, với mỗi phần tử đĩ thực hiện kiểm tra: 101