Dùng stack để khử thuật tóan đệ quy nhánh

Chia sẻ: Khoa CNTT DTU D15TMT | Ngày: | Loại File: DOC | Số trang:14

Thêm vào BST

Báo xấu

348
lượt xem 84
download

Dùng stack để khử thuật tóan đệ quy nhánh

Mô tả tài liệu

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

Tham khảo tài liệu 'dùng stack để khử thuật tóan đệ quy nhánh', khoa học tự nhiên, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả

Chủ đề:

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

Lưu

Nội dung Text: Dùng stack để khử thuật tóan đệ quy nhánh

Phần 2: dùng stack để khử thuật tóan đệ quy nhánh Như chúng ta đã biết, sự thực hiện của đệ quy chính là s ự th ực hi ện l ại chính b ản thân nó với dữ liệu nhỏ hơn, nên khi gọi hàm đệ quy thì máy s ẽ c ấp phát m ột vùng nh ớ có c ơ chế hoạt động như Stack (ngăn xếp) cho hàm đ ệ quy đó. C ơ ch ế này ho ạt đ ộng nh ư kiểu LIFO( last in first out – vào sau ra trước), tức là vi ệc thêm vào hay l ấy ra đ ều th ực hiện thông qua một đầu ra duy nhất ra vào Đỉnh Vào sau Stack(Ngăn xếp) Nếu một chương trình con đệ qui P(x) được gọi từ chương trình chính ta nói ch ương Vào trước trình con được thực hiện ở mức 1. Chương trình con này g ọi chính nó, ta nói nó đi sâu vào mức 2... và cho đến một mức k. Rõ ràng mức k phải th ực hi ện xong thì m ức k-1 m ới được thực hiện tiếp tục, hay ta còn nói là chương trình con quay v ề m ức k-1. Trong khi một chương trình con từ mức i đi vào m ức i+1 thì các bi ến c ục b ộ c ủa m ức i và địa chỉ của mã lệnh còn dang dở phải được lưu tr ữ, đ ịa ch ỉ này g ọi là đ ịa ch ỉ tr ở v ề. Khi từ mức i+1 quay về mức i các giá trị đó đ ược s ử d ụng. Nh ư v ậy nh ững bi ến c ục b ộ và địa chỉ lưu sau được dùng trước. Tính chất này gợi ý cho ta dùng m ột stack đ ể l ưu gi ữ các giá trị cần thiết của mỗi lần gọi tới chương trình con nh ư biến cục bộ, các tham số. Mỗi khi lùi về một mức thì các giá trị này đ ược l ấy ra đ ể ti ếp t ục th ực hi ện m ức này. Ta tóm tắt quá trình: Bưóc 1: Tạo 1 stack rỗng •  Bưóc 2: Lưu các tham số hình thức ở mức 1 vào stack. •  Bước 3: Lặp cho đến khi stack rỗng •  1. Lấy ra 1 phần tử X khỏi stack
2. Nếu X thoả điều kiện dừng của đệ qui (NEO) thì xử lý dữ liệu Ngược lại (phần đệ qui) Xử lý theo thuật tóan Xác định lời gọi đệ quy với các tham số tương ứng và nạp các tham số đó vào stack Bước 4: Kết thúc thuật toán  Một số ví dụ về dùng Stack để khử đệ qui Ví dụ 1: Bài toán Tháp Hà Nội Có ba cọc A,B,C. Khởi đầu cọc A có một số đĩa xếp theo thứ tự nhỏ dần lên trên đ ỉnh. Bài toán đặt ra là phải chuyển toàn bộ chồng đĩa từ A sang C. M ỗi l ần th ực hi ện chuy ển một đĩa từ một cọc sang một cọc khác và không được đặt đĩa l ớn nằm trên đĩa nh ỏ Phân tích bài toán: Trường hợp 1 đĩa: Chuyển thẳng từ A sang C. Đây là trường hợp suy bi ến Trường hợp 2 đĩa: Chuyển 1 đĩa từ A sang B Chuyển 1 đĩa từ A sang C Chuyển 1 đĩa từ B sang C Trường hợp chung n>1 đĩa; Ta coi n-1 đĩa trên nh ư là 1 đĩa và ta áp d ụng trong tr ường hợp 2 đĩa
Chuyển n-1 đĩa từ A sang B ( dùng cọc C làm trung gian)  Chuyển 1 đĩa từ A sang C  Chuyển n-1 đĩa từ B sang C (dùng cọc A làm trung gian)  thuật toán đệ qui mô phỏng như sau: // Chuyển n đĩa từ cọc A sang cọc C Proc Move(n,A,B,C) If n=1 Then chuyển (A,’’,C) Else { Call Move(n-1, A, C, B) Call Move(1, A, B, C) Call Move(n-1, B, A, C) } Return Quá trình thực hiện chương trình con được minh hoạ với 3 đĩa (n=3) nh ư sau: Move(1,A,B,C) A->B Move(2,A,C,B) Move(1,A,C,B) A->C Move(1,B,C,A) B->C move(3,A,B,C) Move(1,A,B,C) A->B Move(1,C,A,B) C->A Move(2,C,B,A) Move(1,C,B,A) C->B Move(1,A,B,C) A->B Mức 1 mức 2 mức 3 Cây đệ quy trên được mô phỏng qua việc dùng stack để giải quyết nh ư sau:
Quá trình chuyển đĩa (3,A,B,C) (2,A,C,B) 2ACB1ABC2BAC 1ABC1ACB1CAB 1ABC2BAC A->C A->B C->B A->C 3 A B C 1BCA1BAC1ABC 2BAC (2,B,A,C) B->A B->C A->C Từ đây, ta xây dựng cấu trúc của mỗi phần t ử đ ược lưu trong stack đ ể gi ải quy ết bài toán tháp Hà nội như sau: struct Item_Tower{ // số đĩa int num; char sour, midl, dest; void assign(int n, char a, char b, char c){ // hàm gán t ừng giá tr ị cho các thu ộc tính num = n; sour = a; midl = b, dest = c; } }; Thuật toán khử đệ qui
void haNoi_Tower(int n, char a, char b, char c){ Stack sTower; // Khai báo stack ki ểu Item_Tower Item_Tower t; int d = 0; t.assign(n, a, b, c); sTower.push(t); while (sTower.isEmpty() == false){ Item_Tower temp = sTower.topOfStack(); sTower.pop(); if(temp.num == 1) cout
Với bàn cờ cỡ n= 8 Thuật tóan: Từ bàn cờ kích thước cỡ 2 n * 2n với n>0 và 1 ô có tọa độ (x,y) bị đánh dấu, ta chia bàn c ờ thành 4 bàn cờ con, với tâm bàn cờ là 1 con tromino có ph ần khuy ết h ướng v ề phía ô b ị đánh dấu X X X X Như vậy ta được 4 bàn cờ con, mỗi bàn cờ con có kích th ước 2 n-1 * 2n-1 với 1 ô bị đánh dấu, vì mỗi góc của con tromino vừa đặt vào tâm trở thành ô b ị đánh d ấu trong m ỗi bàn cờ con mới. Với mỗi bàn cờ con, ta lại tiếp tục thực hiện cho đến khi mọi ô trong bàn c ờ b ị đánh d ấu.
Như vậy, bài toán này trở thành 4 bài toán con tương t ự với 4 lần g ọi đ ệ quy Thuật toán Proc Tromino( {a, b}, {x, y}, n) /* trong do {a, b} là tọa độ góc trên bến trái của bàn c ờ {x, y} là tọa độ ô bị đánh dấu n là kích thước của bàn cờ */ if(n>1){ s = n/2 ; // slà kích thước của 4 bàn cờ con xác định các bộ giá trị của 4 bàn cờ con ({ai, bi}, {xi, yi}) với i = 1..4 call Tromino({a1,b1}, {x1, y1}, s); call Tromino({a2,b2}, {x2, y2}, s); call Tromino({a3,b3}, {x3, y3}, s); call Tromino({a4,b4}, {x4, y4}, s);, } Return Từ đây, ta xây dựng cấu trúc của mỗi phần t ử đ ược lưu trong stack đ ể gi ải quy ết bài Tromino như sau: struct Item_Tromino{ int a, b, x, y, n; void assign(int a1, int b1, int x1, int y1, int n1){ a = a1, b = b1, x = x1, y = y1, n = n1; } }; void Tromino(){ Stack sTromino;
Item_Tromino t; // đưa dữ liệu của bàn cờ đầu tiên vào stack t.assign(1,1,x,y,n); sTromino.push(t); //dùng để đánh dấu d = 0; while (sTromino.isEmpty()==false){ Item_Tromino temp = sTromino.topOfStack(); sTromino.pop(); if(temp.n>1){ int a, b, x, y, d, a1, b1, a2, b2, a3, b3, a4, b4, x1, y1, x2, y2, x3, y3, x4, y4, s; // s là kích thước của mỗi bàn cờ con s = temp.n/2; a = temp.a; b = temp.b; x = temp.x; y = temp.y; //Xác định tọa độ trên bên trái của 4 bàn cờ con a1 = a; b1 = b; a2 = a; b2 = b + s ; a3 = a1 + s; b3 = b1 + s; a4 = a + s ; b4 = b; //xác định vị trí đánh dấu của các bàn cờ con x1 = a + s -1; y1 = b + s -1; x2 = x1, y2 = y1 + 1; x3 = x1 + 1; y3 = y2; x4 = x1 + 1; y4 = y1; // đánh dấu vào các ô bị đánh dấu ở mỗi bàn cờ con (tr ừ ô ban đ ầu) d++;
if( x< a + s && y< b+ s ) {x1 = x, y1 =y ;M[x2][y2] = M[x3][y3] = M[x4][y4] = d;} if( x< a + s && y>= b+ s ) {x2 = x, y2 =y ;M[x1][y1] = M[x3][y3] = M[x4][y4] = d;} if( x>= a + s && y< b+ s ) {x4= x, y4 =y ;M[x1][y1] = M[x2][y2] = M[x3][y3] = d;} if( x>= a + s && y>= b+ s ) {x3 = x, y3 =y ;M[x1][y1] = M[x2][y2] = M[x4][y4] = d;} // Lần lượt đưa các tham số ({ai, bi}{xi, yi}, s) vào stack t.assign(a4,b4,x4,y4,s); // góc phần tư thứ 4 sTromino.push(t); t.assign(a3,b3,x3,y3,s); // góc phần t ư thứ 3 sTromino.push(t); t.assign(a2,b2,x2,y2,s); // góc phần t ư thứ 2 sTromino.push(t); t.assign(a1,b1,x1,y1,s); // góc phần tư th ứ 1 sTromino.push(t); } } }
Một kết quả khi chạy chương trình
Ví dụ 3:Thuật toán QuickSort Mục đích: Sắp xếp dãy khoá có n phần tử Ml, Ml+1, Ml+2,…,Mh (n=h-l+1) theo thứ tự tăng dần với độ phức tạp O(nlgn) Đầu vào: dãy Ml, Ml+1, Ml+2,…,Mh chưa có thứ tự Đầu ra: dãy Ml, Ml+1, Ml+2,…,Mh có thứ tự không giảm ( Mi ≤ Mj với l≤ i
Func Partition(low, hight) // low chỉ số cận trái và hight chỉ số cận phải của dãy // X là giá trị được dùng để phân hoạch thành 3 dãy con X = Mlow //là chỉ số cuối cùng của dãy
//gọi đệ qui cho nửa ≥ MPos Call QuickSort(Pos+1, Right) } Return Vậy ta dùng 1 stack để lưu trữ 2 chỉ số của cận dưới và cận trên của dãy cần sắp xếp. Chỉ cần phân hoạch đối với dãy có hơn 1 giá trị Mỗi phần tử của stack được định nghĩa như sau: struct Item_QS{ int left, right; void assign(int a, int b){ left = a; right = b; } }; Thuật toán quicksort không đệ qui như sau: void quicksort( int l, int r ){ Stack sQS; Item_QS t; t.assign(l, r); // đưa chỉ số cận trái và cận phải vào stack sQS.push(t); while(sQS.isEmpty()==false) { Item_QS temp; // lấy ra cặp chỉ số của dãy temp = sQS.topOfStack(); sQS.pop(); if (temp.left < temp.right){ int pos = partition(temp.left, temp.right); // nếu dãy con bên phải có >1 phần tử if(pos+1 < temp.right){ t.assign(pos +1, temp.right);
// đưa cặp chỉ số dãy con bên phải vào stack sQS.push(t); } // nếu dãy con bên trái có >1 phần tử if(temp.left < pos-1){ t.assign(temp.left, pos -1); // đưa cặp chỉ số dãy con bên phải vào stack sQS.push(t); } } } }