Bài giảng Cấu trúc dữ liệu và giải thuật - Bài 12: Khử đệ quy - Ngô Hữu Phước

Giảng viên: TS. Ngo Huu Phuc Tel: 0438 326 077 Mob: 098 5696 580 Email: ngohuuphuc76@gmail.com Cấu trúc dữ liệu và giải thuật Bài 12. Khử đệ quy @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University1 Bài 12. Khử đệ quy Nội dung bài học: 12.1. Khái niệm chung 12.2. Khử đệ quy cho bài toán tính giai thừa. 12.3. Khử đệ quy cho bài toán Fibonacci. 12.4. Khử đệ quy cho bài toán tháp Hanoi. 12.5. Khử đệ quy cho bài toán QuickSort. Tham khảo: 1. Data structures and Algorithms Stacks.htm 2. Kyle Loudon Mastering Algorithms, Chapter 6 Stacks and Queues 3. Elliz Horowitz – Fundamentals of Data Structures, Chapter 3 Stacks and Queues 4. Deshpande Kakle – C and Data Structures, Chapter 19. Stacks and Queues. 5. Bài giảng TS Nguyễn Nam Hồng. @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University2 12.1. Khái niệm chung (1/7) Đối với hệ điều hành, thông thường, khi một chương trình con được gọi, nó sẽ thực hiện: 1. Trước hết, hệ điều hành lưu tất cả các thông tin cần thiết của chương trình con (thông tin cần thiết). 2. Tiếp theo, chuẩn bị gọi chương trình và chuyển quyền điều khiển cho chương trình con. 3. Sau đó, khi kết thúc chương trình con, hệ điều hành lấy lại các thông tin đã lưu ở bước 1 và chuyển quyền điều khiển đến nơi gọi chương trình con. Lưu ý: các thông tin được lưu tại Stack của chương trình. @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University3 12.1. Khái niệm chung (2/7) Stack chương trình: Đối với các ngôn ngữ bậc cao, sẽ sử dụng Stack chương trình cho mỗi lời gọi chương trình con. Như vậy, khi chương trình con được gọi, mọi thông tin của môi trường (tại nơi gọi chương trình con) sẽ được đưa vào stack chương trình. Khi quay trở lại nơi gọi chương trình con, các thông tin được lấy lại từ stack chương trình. Với cách này, bộ nhớ cần thiết sẽ rất lớn khi áp dụng cho bài toán đệ quy. @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University4 12.1. Khái niệm chung (3/7) Sử dụng bản ghi dạng stack riêng: Một phương pháp đơn giản để có thể kiểm soát được bộ nhớ của những lời gọi chương trình con, sử dụng stack riêng để lưu các biến, địa chỉ cần thiết. Về mặt bản chất, gần giống với hệ thống, tuy nhiên chỉ lưu trữ thông tin cần thiết (không phải toàn bộ thông tin trước lời gọi chương trình con). Quá trình lưu và lấy lại tương tự như thao tác trên stack. @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University5 12.1. Khái niệm chung (4/7) Với cách sử dụng Stack riêng, lưu ý:  Sử dụng biến để lưu địa chỉ nơi gọi chương trình con.  Với các tham số dạng giá trị, tạo bản copy của nó khi lưu.  Với các biến dạng tham chiếu, lưu trữ địa chỉ của chúng.  Với các biến cục bộ (khai báo trong đoạn chương trình), tạo bản copy và lưu chúng. @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University6 12.1. Khái niệm chung (5/7) Các bước gợi ý trong việc khử đệ quy tổng quát: Có thể tạo một stack riêng để chứa các bản ghi. Lệnh gọi đệ quy và lệnh trả về từ hàm đệ quy có thể được thay thế như sau:  Đưa vào stack một bản ghi chứa các biến cục bộ, các tham số và vị trí dòng lệnh ngay sau lệnh gọi đệ quy.  Gán mọi tham số về các trị mới thích hợp.  Trở về thực hiện dòng lệnh đầu tiên trong giải thuật đệ quy.  Mỗi lệnh trả về của hàm đệ quy được thay đổi:  Lấy lại từ stack để phục hồi mọi biến, tham số.  Bắt đầu thực hiện dòng lệnh tại vị trí mà trước đó đã được cất trong stack. @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University7 12.1. Khái niệm chung (6/7) Các bước gợi ý trong việc khử đệ quy đuôi: 1. Sử dụng một biến để thay thế cho việc gọi đệ quy. 2. Sử dụng một vòng lặp với điều kiện kết thúc giống như điều kiện dừng của đệ quy. 3. Đặt tất cả các lệnh vốn cần thực hiện trong lần gọi đệ quy đuôi vào trong vòng lặp. 4. Thay lệnh gọi đệ quy bằng phép gán. 5. Dùng các lệnh gán để gán các trị như các tham số mà hàm đệ quy lẽ ra nhận được. 6. Trả về trị cho biến đã định nghĩa ở bước 1. @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University8 12.1. Khái niệm chung (7/7) Một số lưu ý khi sử dụng:  Nếu tất cả các tham số có cùng kiểu: Sử dụng nhiều thao tác push vào stack. Sau đó, sử dụng nhiều thao tác pop để phục hồi thông tin.  Nếu các tham số có kiểu khác nhau: Sử dụng cấu trúc hoặc, Sử dụng nhiều stack cho mỗi loại tham số. @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University9 12.2. Khử đệ quy cho bài toán tính giai thừa(1/4) Xét lại đoạn chương trình tính n! long factorial(int n) { if((n==0)||(n==1)) return 1; else return n*factorial(n-1); } @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University10 12.2. Khử đệ quy cho bài toán tính giai thừa(2/4) Trong ví dụ trên, phần đệ quy chỉ gọi lại chính nó 1 lần, do đó các bước để khử đệ quy như sau:  Sử dụng một Stack để lưu giá trị động nonN.  Làm rỗng Stack.  Sử dụng vòng lặp để đưa nonN vào Stack.  Sử dụng vòng lặp thứ 2 để lấy giá trị từ Stack và thực hiện phép nhân.  Lưu ý, địa chỉ lưu vị trí dòng lệnh gọi được đặt tại phép nhân. @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University11 12.2. Khử đệ quy cho bài toán tính giai thừa(3/4) PhD. Ngo Huu Phuc, Le Quy Don Technical University12 #include "conio.h" #include "stdio.h" #define MaxEntry 100 #include "StackClass.h“ long nonFactorial(int n); void main() { int n; printf("Nhap vao mot so: "); scanf("%d",&n); printf("Gia tri cua giai thua: %ld",nonFactorial(n)); getch(); } long nonFactorial(int n) { StackClass stack; if(n<=1) return 1; else { int nonN=n; while(nonN>1) { stack.push(nonN); nonN--; } long factorial=1; while(!stack.isEmpty()) { stack.pop(&nonN); factorial=factorial*nonN; } return factorial; } } 12.2. Khử đệ quy cho bài toán tính giai thừa(4/4) Thực hiện hàm nonFactorial (4) nonN = 4; stack.push(4); nonN=4-1=3; stack.push(3); nonN=3-1=2; stack.push(2); nonN=2-1=1; factorial = 1; stack.pop(&nonN); nonN=2; factorial = 2*1 = 2; stack.pop(&nonN); nonN=3; factorial = 2*3 = 6; stack.pop(&nonN); nonN=4; factorial = 6*4 = 24; @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University13 12.3. Khử đệ quy cho bài toán Fibonacci đuôi (1/4) Phân tích lại bài toán tính Fibonaccy đuôi: long fibonacci(int n, int a, int b) { if(n==1) return b; else return fibonacci(n-1,b,a+b); } Lời gọi hàm tương ứng, ví dụ: printf("Fibonacci cua %d: %ld",n,fibonacci(n,0,1)); @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University14 12.3. Khử đệ quy cho bài toán Fibonacci đuôi (2/4) Trong ví dụ trên, phần đệ quy đuôi chỉ gọi lại chính nó 1 lần, do đó các bước để khử đệ quy, có thể dùng như sau:  Sử dụng một Stack để lưu giá trị động nonN.  Làm rỗng Stack.  Sử dụng vòng lặp để đưa nonN vào Stack.  Sử dụng vòng lặp thứ 2 để lấy giá trị từ Stack và thực hiện phép cộng.  Lưu ý, địa chỉ lưu vị trí dòng lệnh gọi được đặt tại phép cộng. @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University15 12.3. Khử đệ quy cho bài toán Fibonacci đuôi (3/4) PhD. Ngo Huu Phuc, Le Quy Don Technical University16 #include "conio.h" #include "stdio.h" #define MaxEntry 100 #include "StackClass.h" long nonFibonaccy(int n); void main() { int n; printf("Nhap vao mot so: "); scanf("%d",&n); printf("Gia tri fibonaccy cua %d la: %ld",n,nonFibonaccy(n)); getch(); } long nonFibonaccy(int n) { StackClass stack; if(n==1) return 1; else { int nonN=n; while(nonN>1) { stack.push(nonN); nonN--; } long fibonaccy=0; int a=0,b=1; while(!stack.isEmpty()) { stack.pop(&nonN); fibonaccy=a+b; a=b; b=fibonaccy; } return fibonaccy; } } 12.3. Khử đệ quy cho bài toán Fibonacci đuôi (4/4) Thực hiện hàm nonFibonacci(4) nonN = 4; stack.push(4); nonN=4-1=3; stack.push(3); nonN=3-1=2; stack.push(2); nonN=2-1=1; fibonacci = 0; a = 0; b = 1; stack.pop(&nonN); fibonacci=0+1=1; a=1; b=1; stack.pop(&nonN); fibonacci=1+1=2; a=1; b=2; stack.pop(&nonN); fibonacci=1+2=3; a=2; b=3; @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University17 12.4. Khử đệ quy cho bài toán QuickSort (1/6) void qsort(int list[],int m,int n) { int key,i,j,k; if( m < n) { k = getkeyposition(m,n); swap(&list[m],&list[k]); key = list[m]; i = m+1; j = n; @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University18 while(i <= j) { while((i <= n) && (list[i] <= key)) i++; while((j >= m) && (list[j] > key)) j--; if( i < j) swap(&list[i],&list[j]); } swap(&list[m],&list[j]); qsort(list,m,j-1); qsort(list,j+1,n); } } 12.4. Khử đệ quy cho bài toán QuickSort (2/6) Quá trình khử đệ quy cho bài toán QuickSort:  Để khử đệ quy cho bài toán này, sử dụng Stack, lưu vị trí bắt đầu và vị trí kết thúc của mỗi đoạn.  Trong quá trình chọn khóa, có thể sử dụng điểm trung vị, điểm giữa hay điểm cuối để giảm xác suất của trường hợp tồi nhất.  Như vậy, sẽ sử dụng nhiều chiến lược chọn khóa khác nhau.  Bên cạnh đó, đối với những khoảng con có kích thước nhỏ (nhỏ hơn 10 phần tử), sử dụng phương pháp insert sort thay cho QuickSort. Lưu ý: Sử dụng cấu trúc sau để lưu đoạn cần thực hiện việc sắp xếp: struct index{ int left; int right; }; @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University19 12.4. Khử đệ quy cho bài toán QuickSort (3/6) #include "conio.h" #include "stdio.h" #define MaxEntry 100 #include "StackClass.h" #define MaxElement 100 // voi truong hop it phan tu, su dung pp khac #define SmallSize 10 int list[MaxElement]; struct index{ int left; int right; }; void inputdata(int list[],int n); void printlist(int list[],int n); void interchange(int *x,int *y); void split(int first,int last,int *splitpoint); void insertion_sort(int first,int last); void quicksort(int n); @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University20 void main() { int n; printf("Nhap so p.tu cho mang, max = 100\n"); scanf("%d",&n); inputdata(list,n); printf("Cac phan tu da nhap:\n"); printlist(list,n); quicksort(n); printf("\nCac phan tu da sap xep:\n"); printlist(list,n); getch(); } 12.4. Khử đệ quy cho bài toán QuickSort (4/6) void inputdata(int list[],int n) { int i; printf("Nhap cac phan tu cho mang\n"); for(i=0;i<n;i++) scanf("%d",&list[i]); fflush(stdin); } void printlist(int list[],int n) { int i; printf("Cac phan tu trong mang: \n"); for(i=0;i<n;i++) printf("%d\t",list[i]); printf("\n"); } void interchange(int *x,int *y) { int temp; temp=*x; *x=*y; *y=temp; } @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University21 void split(int first,int last,int *splitpoint) { int x,i,j,s,g; // tim trung vi if (list[first]<list[(first+last)/2]) { s=first; g=(first+last)/2; } else { g=first; s=(first+last)/2; } if (list[last]<=list[s]) x=s; else if (list[last]<=list[g]) x=last; else x=g; //trao doi giua khoa va phan tu dau tien interchange(&list[x],&list[first]); x=list[first]; 12.4. Khử đệ quy cho bài toán QuickSort (5/6) // thuc hien phan chia i=first+1; j=last; while (i<=j) { while ((list[j]>=x)&&(j>first)) j--; while ((list[i]<x)&&(i<last)) i++; if(i<j) interchange(&list[i],&list[j]); } interchange(&list[first],&list[j]); //Khoa duoc tra ve *splitpoint=j; } @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University22 void insertion_sort(int first,int last) { int i,j,c; for (i=first;i<=last;i++) { j=list[i]; c=i; while ((list[c-1]>j)&&(c>first)) { list[c]=list[c-1]; c--; } list[c]=j; } } 12.4. Khử đệ quy cho bài toán QuickSort (6/6) void quicksort(int n) { StackClass stack; index point; int first,last,splitpoint; point.left=0; point.right=n-1; stack.push(point); while (!stack.isEmpty()) { stack.pop(&point); first = point.left; last = point.right; for (;;) { if (last-first>SmallSize) { //Kich thuoc lon hon SmallSize split(first,last,&splitpoint); //push doan nho vao stack @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University23 if (last-splitpoint<splitpoint-first) { point.left=first; point.right=splitpoint-1; stack.push(point); first=splitpoint+1; } else { point.left=splitpoint+1; point.right=last; stack.push(point); last=splitpoint-1; } } else { //sap xep doan nho insertion_sort(first,last); break; } } } } 12.5. Khử đệ quy cho bài toán tháp Hanoi (1/5) Xem xét lại bài toán tháp Hanoi dạng đệ quy: void HanoiTower(int m, char a, char b, char c) { if(m>0) { HanoiTower(m-1,a,c,b); printf("Chuyen dia %d tu %c sang %c\n",m,a,b); HanoiTower(m-1,c,b,a); } } @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University24 12.5. Khử đệ quy cho bài toán tháp Hanoi (1/3) Giải quyết bài toán:  Tương tự như các ví dụ trước, sử dụng Stack để thực hiện khử đệ quy. Một số khai báo: nonN: Số đĩa cần chuyển. nonT: Chỉ số tương ứng với đĩa cần chuyển. nonA: tên của cọc nguồn. nonB:tên cọc trung gian. nonC: tên của cọc đích. stack: Stack được dùng. @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University25 Cấu trúc dữ liệu cho Stack: struct StackValue { int nonN; int nonT; char nonA; char nonB; char nonC; }; 12.5. Khử đệ quy cho bài toán tháp Hanoi (2/3) #include "conio.h" #include "stdio.h" #define MaxEntry 100 #include "StackClass.h“ struct StackValue { int nonN; int nonT; char nonA; char nonB; char nonC; }; void nonHanoiTower(int n); StackValue CreateValue(int n, int t, char a, char b, char c); void main() { int n; printf("Nhap vao so dia m = "); scanf("%d",&n); @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University26 printf("Ket qua cac buoc \n"); nonHanoiTower(n); getch(); } StackValue CreateValue(int n, int t, char a, char b, char c) { StackValue value; value.nonN = n; value.nonT = t; value.nonA = a; value.nonB = b; value.nonC = c; return value; } 12.5. Khử đệ quy cho bài toán tháp Hanoi (3/3) void nonHanoiTower(int n) { StackClass stack; StackValue value; if(n==1) value = CreateValue(n,1,'A','B','C'); else value = CreateValue(n,0,'A','B','C'); stack.push(value); StackValue temp; while (!stack.isEmpty()) { stack.pop(&value); temp=value; if((temp.nonN==1)&&(temp.nonT>0)) printf("\nChuyen dia %d tu %c sang %c",temp.nonT,temp.nonA,temp.nonC); else @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University27/27 { value = CreateValue(temp.nonN- 1,temp.nonN==2?1:0,temp.nonB,temp.nonA,temp .nonC); stack.push(value); value = CreateValue(1,temp.nonN, temp.nonA,temp.nonB,temp.nonC); stack.push(value); value = CreateValue(temp.nonN-1 , temp.nonN==2?1:0,temp.nonA,temp.nonC,temp.n onB); stack.push(value); } } }