Giáo trình Lập trình có cấu trúc

ng đệ qui
Hàm f(n) = n!
Dễ thấy f(0) = 1.
Vì (n+1) ! = 1 . 2.3 . . . n(n+1) = n! (n+1), nên ta có:
f(n+1) = ( n+1) . f(n) với mọi n nguyên dương.
Ví dụ 2.3. Tập hợp định nghĩa bằng đệ qui
Định nghĩa đệ qui tập các xâu : Giả sử Σ* là tập các xâu trên bộ chữ cái Σ. Khi đó Σ*
được định nghĩa bằng đệ qui như sau:
λ ∈ Σ*, trong đó λ là xâu rỗng
wx ∈ Σ* nếu w ∈ Σ* và x ∈ Σ
Ví dụ 2.4. Cấu trúc tự trỏ được định nghĩa bằng đệ qui
	struct node {
int infor;
	struct node *left;
struct node *right;
};
4.1.2. Giải thuật đệ qui
Một thuật toán được gọi là đệ qui nếu nó giải bài toán bằng cách rút gọn bài toán ban đầu thành bài toán tương tự như vậy sau một số hữu hạn lần thực hiện. Trong mỗi lần thực hiện, dữ liệu đầu vào tiệm cận tới tập dữ liệu dừng.
Ví dụ: để giải quyết bài toán tìm ước số chung lớn nhất của hai số nguyên dương a và b với b> a, ta có thể rút gọn về bài toán tìm ước số chung lớn nhất của (b mod a) và a vì USCLN(b mod a, a) = USCLN(a,b). Dãy các rút gọn liên tiếp có thể đạt được cho tới khi đạt điều kiện dừng USCLN(0, a) = USCLN(a, b) = a. Sau đây là ví dụ về một số thuật toán đệ qui thông dụng.
Thuật toán 1: Tính a bằng giải thuật đệ qui, với mọi số thực a và số tự nhiên n.
double power( float a, int n ){
if ( n ==0)
return(1);
return(a *power(a,n-1));
}
Thuật toán 2: Thuật toán đệ qui tính ước số chung lớn nhất của hai số nguyên dương a và b.
int USCLN( int a, int b){
if (a == 0) return(b);
return(USCLN( b % a, a));
}
Thuật toán 3: Thuật toán đệ qui tính n!
long factorial( int n){
if (n ==1)
return(1);
return(n * factorial(n-1));
}
Thuật toán 4: Thuật toán đệ qui tính số fibonacci thứ n
int fibonacci( int n) {
if (n==0) return(0);
else if (n ==1) return(1);
return(fibonacci(n-1) + fibonacci(n-2));
}
4.1.3. Một số ví dụ minh họa
Bài toán tìm ước số chung lớn nhất (UCLN): Cho hai số nguyêna và b, tìm USCLN của hai số theo giải thuật đệ qui. Bài toán có thể được định nghĩa dưới dạng đệ qui như sau:
Nếu b = 0 thì UCLN = a;
Nếu b0 thì UCLN(a, b) = UCLN(b, a mod b).
Từ đó ta có hàm đệ qui để tính UCLN của a và b như sau. 
int USCLN(int a, int b) 
{
if (b==0)
return a;
else
return USCLN(b,a%b);
}
Số Fibinaci: Tính số hạng thứ n của dãy Fibonaci với giải thuật đệ qui. Dãy Fibonaci được định nghĩa như sau:
f(0) = f(1) = 1;
f(n) = f(n-1) + f(n-2) với "n >=2. 
long Fib(int n) 
{ 
long kq; 
if (n==0 || n==1) kq = 1; 
else kq = Fib(n-1) + Fib(n-2); 
return kq; 
} 
Bài toán tháp Hà nội: Có n đĩa với kích thước to, nhỏ khác nhau. Ban đầu sắp xếp các đĩa theo trật tự kích thước vào một cọc sao cho đĩa nhỏ nhất nằm trên cùng, tức là tạo ra một dạng hình nón. Người chơi phải di chuyển toàn bộ số đĩa sang một cọc khác, tuân theo các quy tắc sau:
Một lần chỉ được di chuyển một đĩa;
Một đĩa chỉ có thể được đặt lên một đĩa lớn hơn (không nhất thiết hai đĩa này phải có kích thước liền kề, tức là đĩa nhỏ nhất có thể nằm trên đĩa lớn nhất).
Hình ảnh mô tả bài toán được cho như hình 4.1.3
Hình 4.1.3 - Bài toán tháp Hanoi
Mô tả bài toán:
Đặt tên các cọc là A, B, C và qui ước A là Cọc Nguồn, B là Cọc Đích và C là Cọc Trung Gian;
Gọi n là tổng số đĩa;
Đánh số đĩa từ 1 (nhỏ nhất, trên cùng) đến n (lớn nhất, dưới cùng).
Thuật giải đệ qui: Để chuyển n đĩa từ cọc A sang cọc B với C là cọc trung gian:
- Chuyển n-1 đĩa từ A sang C. Chỉ còn lại đĩa #n trên cọc A;
- Chuyển đĩa #n từ A sang B;
- Chuyển n-1 đĩa từ C sang B cho chúng nằm trên đĩa #n
#include 
#include 
void chuyen(int sodia, char CotNguon, char CotDich, char CotTG)
{
if (sodia>0)
{
chuyen(sodia-1, CotNguon, CotTG, CotDich);
printf(" Chuyen dia %d Tu %c -> %c\n",sodia,CotNguon,CotDich);
chuyen(sodia-1, CotTG, CotDich, CotNguon);
}
}
int main()
{
char CotNguon,CotDich,CotTG;
int n;
printf("\n Hay nhap so dia: ");
scanf("%d",&n);
chuyen(n,'A','B','C');
getch();
}
Kết quả thực hiện ví dụ 4.22 được cho như hình 4.3.
Hình 4.3 - Kết quả thực hiện bài toán tháp Hà nội với n=4
4.2. Tìm kiếm (Searching)
Tìm kiếm là một trong các bài toán cơ bản nhất của tin học. Có thể nói, mọi tương tác giữa con người và hệ thống máy tính về bản chất đều là tìm kiếm và thu thập thông tin. Ẩn sau các quá trình tìm kiếm là việc sắp xếp các đối tượng theo một trật tự nào đó để quá trình tìm kiếm diễn ra nhanh nhất, chính xác và hiệu quả nhất đó là ý nghĩa cơ bản của quá trình sắp xếp. Nội dung chính của chương này tập chung vào các giải thuật sắp xếp và tìm kiếm cơ bản dưới đây:
Tìm kiếm tuần tự (Sequential), tìm kiếm nhị phân (Binary Search) & tìm kiếm trên cây nhị phân (Binary Search).
Tìm kiếm là công việc quan trọng đối với các hệ thống tin học và có liên quan mật thiết với quá trình sắp xếp dữ liệu. Bài toán tìm kiếm tổng quát có thể được phát biểu như sau:
“Cho một bảng gồm n bản ghi R1, R2, . ., Rn. Với mỗi bản ghi Ri được tương ứng với một khoá ki (trường thứ i trong record). Hãy tìm bản ghi có giá trị của khoá bằng X cho trước”.
Nếu chúng ta tìm được bản ghi có giá trị khóa là X thì phép tìm kiếm được thoả (successful). Nếu không có giá trị khóa nào là X thì quá trình tìm kiếm là không thoả (unsuccessful). Sau quá trình tìm kiếm, có thể xuất hiện yêu cầu bổ xung thêm bản ghi mới có giá trị khóa là X thì giải thuật được gọi là giải thuật tìm kiếm bổ sung.
4.2.1. Tìm kiếm tuần tự (Sequential Searching)
Tìm kiếm tuần tự là kỹ thuật tìm kiếm cổ điển trên một danh sách chưa được sắp xếp.
Nội dung cơ bản của phương pháp tìm kiếm tuần tự là duyệt từ bản ghi thứ nhất cho tới bản ghi cuối cùng, và so sánh lần lượt giá trị của khoá với giá trị X cần tìm. Trong quá trình duyệt, nếu có bản ghi trùng với giá trị X thì chúng ta đưa ra vị trí của bản ghi trong dãy, nếu duyệt tới cuối dãy mà không có bản ghi nào có giá trị của khoá trùng với X thì quá trình tìm kiếm trả lại giá trị -1 (-1 được hiểu là giá trị khoá X không thuộc dãy). Chương trình cài đặt phương pháp tìm kiếm tuần tự được thực hiện như sau:
#include	
#include
#include
#include
#include 
int Sequential(int *, int, int);
void Init(int *, int);
void Init(int *A, int n){
int i;
printf("\n Tao lap day so:");
for (i=0; i<n;i++){
A[i]=random(1000);
printf("%5d",A[i]);
}
delay(1000);
}
int Bubble(int *A, int x, int n){
register i,temp;
for (i=0; i<n ; i ++){
if (A[i] == X)
return(i);
}
return(-1);
}
void main(void){
int *A,n, x, k;clrscr();
printf("\n Nhap n="); scanf("%d",&n);
printf(“\n Số x cần tìm:”); scanf(“%d”, &x);
A=(int *) malloc(n*sizeof(int));
k= Sequential(A,x,n);
if ( k>=0)
printf(“\n %d ở vị trí %d”, x,k);
else
printf(“\n %d không thuộc dãy”);
free(A); getch();
}
4.2.2. Tìm kiếm nhị phân (Binary Searching)
Tìm kiếm nhị phân là phương pháp tìm kiếm phổ biến được thực hiện trên một dãy đã được sắp thứ tự. Nội dung của giải thuật được thực hiện như sau: lấy khóa cần tìm kiếm X so sánh với nội dung của khóa của phần tử ở giữa, vị trí của phần tử ở giữa là mid = (low + hight )/ 2, trong đó cận dưới low =0, cận trên hight = n-1. Vì dãy đã được sắp xếp nên nếu nội dung của khóa tại vị trí giữa lớn hơn X thì phần tử cần tìm thuộc khoảng [mid+1, hight], nếu nội dung của khóa tại vị trí giữa nhỏ hơn X thì phần tử cần tìm thuộc khoảng [low, mid- 1], nếu nội dung của khóa tại vị trí giữa trùng với X thì đó chính là phần tử cần tìm. Ở bước tiếp theo, nếu nội dung của khóa tại vị trí giữa lớn hơn X thì ta dịch chuyển cận dưới low lên vị trí mid+ 1, nếu nội dung của khóa tại vị trí giữa nhỏ hơn X thì ta dịch chuyển cận trên về vị trí mid- 1. Quá trình được lặp lại cho tới khi gặp khóa có nội dung trùng với X hoặc cận dưới vượt quá cận trên hay X không thuộc dãy. Thuật toán tìm kiếm nhị phân được minh họa như sau:
int Binary_Search( int *A, int X, int n){
int mid, low=0, hight = n-1;
while ( low<=hight ){ // lặp nếu cận dưới vẫn nhỏ hơn cận trên
mid = (low + hight) /2; // xác định vị trí phần tử ở giữa
if (X > A[mid] ) low = mid +1; // X thuộc [mid+1, hight]
else if (X < A[mid] ) hight = mid- 1; // X thuộc [low, mid-1]
	else return(mid);
}
return(-1); // X không thuộc dãy
}
#include	
#include
#include
#include
#include 
Int Binary_Search( int *, int, int);
void Bubble(int *, int);
void Init(int *, int);
int Binary_Search( int *A, int X, int n) {
int mid, low = 0, hight = n-1;
while (low<=hight){
mid = (low +hight)/2;
if (X >A[mid] ) low = mid +1;
else if (X<A[mid] ) hight = mid -1;
else return (mid);
}
return(-1);
}
void Init(int *A, int n){
int i;
printf("\n Tao lap day so:");
for (i=0; i<n;i++){
A[i]=random(1000);
printf("%5d",A[i]);
}
delay(1000);
}
void Bubble(int *A, int n){
register i,j,temp;
for (i=1; i<n; i++){
for (j=n-1; j>=i;j--){
if (A[j-1]>A[j]){
	temp=A[j-1];
	A[j-1]=A[j];
	A[j]=temp;
	}
	}
	printf("\n Ket qua lan:%d", i);
In(A,n);
}
}
void In(int *A, int n){
register int i;
	for(i=0;i<n;i++)
	printf("%5d",A[i]);
	delay(1000);
}
void main(void){
int *A,n, X, k;clrscr();
	printf("\n Nhap n="); scanf("%d",&n);
printf(“\n Số cần tìm X=”); scanf(“%d”,&X);
A=(int *) malloc(n*sizeof(int));
Init(A,n);Bubble(A,n); k= Binary_Search(A, X, n);
if ( k>0)
printf (“\n %d ở vị trí số %d”, X, k);
else
printf(“\n %d không thuộc dãy”);
getch();
free(A);
}
Bài tập Đệ quy
Nhập số nguyên dương N. Viết hàm đệ qui tính:
Nhập số nguyên dương n. Viết hàm đệ qui tính:
 n dấu căn
 n dấu chia
Viết hàm đệ qui tính n!. áp dụng chương trình con này tính tổ hợp chập k theo công thức truy hồi: C(n, k) = n!/(k! (n-k)!)
Viết hàm đệ qui tính số fibonaci thứ n. Dùng chương trình con này tính f(2) + f(4) + f(6) + f(8).
Viết dưới dạng đệ qui các hàm 
daoxau 	b. UCLN 	c. Fibonaci	d.Tháp Hà Nội
Viết macro tráo đổi nội dung 2 biến. AD: Sắp xếp dãy số.
Tài liêụ tham khảo: 
[1] Phạm Văn Ất, Kỹ thuật lập trình C, NXB Thống kê, 2003
[2] Lê Hoài Bắc, Nguyễn Thanh Nghị, Kỹ năng lập trình, nhà xuất bản Khoa học và kỹ thuật – Hà Nội, 2005
 [3] Đinh Mạnh Tường, Cấu trúc dữ liệu và giải thuật, NXB Giáo dục, 2002