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.
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
27 trang |
Chia sẻ: thanhle95 | Lượt xem: 1123 | Lượt tải: 1
Bạn đang xem trước 20 trang tài liệu 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, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
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);
}
}
}