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

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+1. ™ Nếu tìm thấy chỉ số i như trên: trong đoạn cuối giảm dần, tìm phần tử ak nhỏ nhất thoả mãn ak > 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ê hoá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() { Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN 44 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; } Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN 45 3.2 Thuật toán quay lui (Back Tracking) Thuật toán quay lui dùng để giải quyết các bài toá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 toán liệt kê khi nhận biết được cấu hình đầu tiên của bài toá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 toán sinh kế tiếp chỉ giải quyết được cái bài toán liệt kê đơn giản. Để giải quyết những bài toán tổ hợp phức tạp, người ta dùng thuật toán quay lui. Nội dung chính của thuật toá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 toá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 toá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 toán trở thành liệt kê tiếp cấu hình n-1 phần tử x = (x2, x3,.., xn). Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN 46 Hình 3.1: Liệt kê các lời giải theo thuật toán quay lui. Mô hình chung của thuật toán quay lui xác định thành phần thứ i được mô tả tổng quát như sau: (thuật toá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 toán quay lui sẽ bắt đầu bằng lời gọi Try(1). 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 Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN 47 3.2.1 Thuật toá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 toá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 toán quay lui return 0; } Khi n = 3, cây tìm kiếm quay lui như sau: Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN 48 Hình 3.2: Cây tìm kiếm quay lui trong bài toán liệt kê dãy nhị phân. 3.2.2 Thuật toá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 toán quay lui liệt kê tập con k phần tử được minh họa như sau: Try(1) Try(2) Try(2) Try(3) Try(3) Try(3) Try(3) 000 x1 = 1 x1 = 0 x2 = 0 x2 = 1 x2 = 0 x2 = 1 x3 = 0 x3 = 0 x3 = 0 x3 = 0 x3 = 1 x3 = 1 x3 = 1 x3 = 1 001 010 011 100 101 110 111 Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN 49 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; 1 2 3 4 5 4 5 3 4 5 3 4 2 3 4 4 5 5 5 N = 5; k = 3 Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN 50 Try(1, B, k, n); return 0; } 3.2.3 Thuật toán quay lui liệt kê hoán vị n phần tử Biểu diễn hoá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. Hình 3.4: Cây liệt kê hoán vị 3 phần tử Chương trình quay lui liệt kê hoá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) 1 2 3 n = 3 2 3 1 3 1 2 3 2 3 1 2 1 Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN 51 { 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 toá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 iDo 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 Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN 52 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 đó. Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN 53 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. Hình 3.8: Các đường chéo Trên Phải - Dưới Trái. 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 0 -1 -7 7 4 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 16 14 9 2 Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN 54 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 toá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 toán sẽ quay lên xét những giá trị còn lại của quân hậu thứ i-1. 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 Đừng chéo TT- DP có chỉ số 0 Đừng chéo TP- DT có chỉ số 10 Ô ( 5, 5) Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN 55 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 toá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 { Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN 56 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) Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN 57 (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 toá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 toá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. Ngoà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 toá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ã. Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN 58 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 ngoà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 ô ngoài biên là -1. Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN 59 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! 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 (-2, 1) (-1, 2) (1, 2) (2, 1) (2, -1) (1, -2) (-1, -2) (-2, -1) Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN 60 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<MAX;i++) for(int j=0;j<MAX;j++) if(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) { Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN 61 for(int k=0; k<7; k++) //duyệt qua các nước đi kế tiếp { if( board[i+dr[k]][j+dc[k]]==0 ) // nếu vị trí này chưa đi qua { Board[i+dr[k]][j+dc[k]]= step+1; // đánh dấu chọn vị trí if(step+1==64) //hoàn tất một kết quả { Show(board); printf("Nhan 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: Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN 62 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. \”[ Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN 63 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ọcCá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 toá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 toá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 toá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]; Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN 64 Khoá cần tìm là x có kiểu nguyên : int x. 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 Ý 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 khoá 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] x: sang bước 3 Bước 3: i = i +1, kiểm tra chỉ số i và kích thước mảng n i. nếu 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++. Tìm kiếm Tìm kiếm tuyến tính Tìm kiếm nhị phân Tập DL bất kỳ Tập DL được sắp x ? a1 a2 a3 an-1 an Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN 65 int Search(int a[], int n, int key) { int i =0; while (i<n) && (key != a[i]) i++; if (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 khoá đã 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 khoá 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[left] đến a[right] chỉ chứa khóa < x, ta tiến hành tìm kiếm từ a[mid+1] đến a[right]. Nếu a[mid] > x thì có nghĩa là đoạn a[m] đến a[right] chỉ chứa khoá > 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 Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN 66 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 Hình 4.2: Tìm kiếm nhị phân. Hàm C minh họa cài đặt thuật toá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 } 1 Left = 5 X = 8 Right = 8 Mid = 6 Đoạn tìm kiếm 2 4 5 6 8 12 15 = 1 Left = 1 X = 8 Right = 8 Mid = 4 Đoạn tìm kiếm 2 4 5 6 8 12 15 Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN 67 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 toá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 toá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 toà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à khoá, việc sắp xếp sẽ được tiến hành dựa vào giá trị khoá 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 toá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: Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN 68 1. Ở lượt thứ nhất, ta chọn trong dãy khoá k[1..n] ra khoá nhỏ nhất và đổi giá trị nó với k[1], khi đó k[1] sẽ trở thành khoá nhỏ nhất. 2. Ở lượt thứ hai, ta chọn trong dãy khoá 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 khoá 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