Xem mẫu
- Cấu trúc dữ liệu và giải thuật
Bài 12. Khử đệ quy
Giảng viên: TS. Ngo Huu Phuc
Tel: 0438 326 077
Mob: 098 5696 580
Email: ngohuuphuc76@gmail.com
1 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
- 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.
2 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
- 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.
3 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
- 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.
4 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
- 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.
5 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
- 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.
6 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
- 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.
7 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
- 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.
8 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
- 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ố.
9 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
- 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);
}
10 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
- 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.
11 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
- 12.2. Khử đệ quy cho bài toán tính giai thừa(3/4)
#include "conio.h" long nonFactorial(int n) {
#include "stdio.h" StackClass stack;
#define MaxEntry 100 if(n
- 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;
13 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
- 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));
14 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
- 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.
15 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
- 12.3. Khử đệ quy cho bài toán Fibonacci đuôi (3/4)
#include "conio.h" long nonFibonaccy(int n) {
#include "stdio.h" StackClass stack;
#define MaxEntry 100 if(n==1) return 1;
#include "StackClass.h"
else {
int nonN=n;
long nonFibonaccy(int n);
while(nonN>1) {
stack.push(nonN);
void main()
{ nonN--; }
int n; long fibonaccy=0;
printf("Nhap vao mot so: "); int a=0,b=1;
scanf("%d",&n); while(!stack.isEmpty()) {
printf("Gia tri fibonaccy cua %d la: stack.pop(&nonN);
%ld",n,nonFibonaccy(n));
fibonaccy=a+b;
getch();
a=b;
}
b=fibonaccy; }
return fibonaccy; }
}
16 PhD. Ngo Huu Phuc, Le Quy Don Technical University
- 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;
17 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
- 12.4. Khử đệ quy cho bài toán QuickSort (1/6)
void qsort(int list[],int m,int n) while(i
- 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;
};
19 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
- 12.4. Khử đệ quy cho bài toán QuickSort (3/6)
#include "conio.h" void main() {
#include "stdio.h" int n;
#define MaxEntry 100
printf("Nhap so p.tu cho mang, max = 100\n");
#include "StackClass.h"
scanf("%d",&n);
#define MaxElement 100
// voi truong hop it phan tu, su dung pp khac inputdata(list,n);
#define SmallSize 10 printf("Cac phan tu da nhap:\n");
int list[MaxElement]; printlist(list,n);
struct index{
quicksort(n);
int left;
printf("\nCac phan tu da sap xep:\n");
int right; };
void inputdata(int list[],int n); printlist(list,n);
void printlist(int list[],int n); getch();
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);
20 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
nguon tai.lieu . vn
