1
TIN HỌC ĐẠI CƯƠNG
www.uit.edu.vn
BÀI 11
BÀI 11
ĐỆ QUY
ĐỆ QUY
TẬP TIN
TẬP TIN
Tin học đại cương
2
ĐỆ QUY
11
NỘI DUNG
NỘI DUNG
Tin học đại cương
3

Khái niệm

Phân loại các hàm đệ qui:

Đệ qui tuyến tính

Đệ qui nhị phân

Đệ qui hỗ tương

Đệ qui phi tuyến
NỘI DUNG BÀI ĐỆ QUY

giờ sai
Đệ qui tồi hơn, nó liên tục đưa ra các lời gọi
hàm làm tốn thời gian xử lý và không gian
nhớ. Mỗi lần gọi hàm, lại cần thêm một bản
sao của hàm, tốn thêm bộ nhớ (lưu các biến
của hàm, địa chỉ trở về của hàm ).
Phương pháp lặp được
chuộng hơn
Tuy nhiên, có nhiều bài toán có thể giải bằng
đệ qui lại tốt hơn (các bài toán cổ điển: tháp
Hà Nội, mã đi tuần, 8 hậu, sắp xếp
QuickSort…)
SO SÁNH ĐỆ QUY VÀ LẶP
SO SÁNH ĐỆ QUY VÀ LẶP
Tin học đại cương
6

Đệ qui tuyến tính

Đệ qui nhị phân

Đệ qui hỗ tương

Đệ qui phi tuyến
PHÂN LOẠI CÁC DẠNG ĐỆ QUY
PHÂN LOẠI CÁC DẠNG ĐỆ QUY
Tin học đại cương
7

Một hàm được gọi là đệ qui tuyến tính khi nó có

n-1
*x.
float xn(float x, int n)
{
if (n==0)
return 1;
else
return xn(x,n-1)*x;
}
VÍ DỤ VỀ ĐỆ QUY TUYẾN TÍNH
VÍ DỤ VỀ ĐỆ QUY TUYẾN TÍNH
Tin học đại cương
9

Một hàm được gọi là đệ qui nhị phân khi nó có dạng:
<KDL> < tênhàm>
{
if < điều kiện dừng >
/*Trả về gtrị hay kthúc công việc */
else
{
/*Làm một số công việc */
/*Gọi đqui đến <tên> để
giải quyết vấn đề nhỏ hơn */
/*Gọi đqui đến <tên> để
giải quyết vấn đề còn lại */
}
}
ĐỆ QUY NHỊ PHÂN
ĐỆ QUY NHỊ PHÂN

return <giátrị>;
}
}
ĐỆ QUY PHI TUYẾN
ĐỆ QUY PHI TUYẾN
Tin học đại cương
12

Tính: x(0)=1 với n=0;
x(n)=n
2
x(0)+(n-1)
2
x(1)+…+1
2
x(n-1) với n>0;

Xây dựng:
int x(int n)
{
if (n==0) return 1;
else
{ int t=0;
for (int i=0; i<n;i++)
t=t+(n-i)*(n-i)*x(i);
return t;
}
}
VÍ DỤ VỀ ĐỆ QUY PHI TUYẾN
VÍ DỤ VỀ ĐỆ QUY PHI TUYẾN

X
n
= X
n-1
+ Y
n-1

Y
n
= n
2
X
n-1
+ Y
n-1

Viết hai hàm đệ qui tính số hạng thứ N của hai
dãy trên
VÍ DỤ VỀ ĐỆ QUY HỖ TƯƠNG
VÍ DỤ VỀ ĐỆ QUY HỖ TƯƠNG
Tin học đại cương
15
/* Prototype */
unsigned long TinhY(int n);
unsigned long TinhX(int n);
/* Implementation */
unsigned long TinhY(int n)
{
if (n==0) return 1;
return TinhX(n-1) + TinhY(n-1);


Tập tin là một loại dữ liệu có thể ghi lên đĩa để
dùng nhiều lần.

Có 2 loại tập tin:

Tập tin văn bản (text file, ASCII file): *.PAS, *.C,
… (các tập tin mã nguồn chương trình). Mỗi tập
tin văn bản gồm nhiều dòng. Mã ngăn cách
dòng (chuyển dòng khác) là mã 10 ($OA), được
tách ra thành mã 13 ($OD) và mã 10 ($OA). Mã
kết thúc tập tin là mã 26 ($O1A). Các ký tự trên
mỗi dòng đều phải có mã ASCII từ khoảng trắng
(#32 hay $O20) trở lên, nếu nhỏ hơn $O20 thì
phải là các ký tự điều khiển hợp lệ.

Tập tin nhị phân (binary file): *.COM, *.EXE,
*.DOC, *.XLS, *BMP, *PCX, *.GIF,…

Dữ liệu ghi lên tập tin không bị thay đổi và khi ta
đóng tập tin thì mã kết thúc tập tin sẽ được ghi
lên đĩa là -1.
KHÁI NIỆM TẬP TIN
KHÁI NIỆM TẬP TIN
Tin học đại cương
19

Việc sử dụng file được thực hiện qua 3 bước cơ bản:

Mở file (fopen)

truy xuất tập tin là cuối tập tin vừa mở.
t Mở tập tập tin kiểu văn bản.
b Mở tập tập tin kiểu nhị phân (binary data)
CÁC CHẾ ĐỘ LÀM VIỆC TRÊN FILE
CÁC CHẾ ĐỘ LÀM VIỆC TRÊN FILE
Tin học đại cương
21

int putc (int ch, FILE *f);
int fputc(int ch, FILE *f);
int getc (FILE *f);
int fgetc(FILE *f);

int fputs (const char *s, FILE *f);
char *fgets(const char *s, int n, FILE
*f);

int fprintf(FILE *f, const char
*dac_ta, );
fscanf (FILE *f, const char
*dac_ta, );

int putw(int n, FILE *f);
int getw(FILE *f);

int fwrite(void *ptr, int size, int n,
FILE *f);
int fread (void *ptr, int size, int n,
FILE *f);
CÁC HÀM NHẬP XUẤT

24
#include <stdio.h>
void main() /* FCOPY.C */
{
char in_name[25], out_name[25];
FILE *in_file, *out_file;
int c;
printf("File to be copied:\n");
gets("%s", in_name);
printf("Output filename:\n");
gets("%s", out_name);
VÍ DỤ MINH HỌA
VÍ DỤ MINH HỌA
Tin học đại cương
25
in_file = fopen ( in_name, "r");
if( in_file == NULL )
printf(“Cannot open”);
else
{
out_file = fopen (out_name, "w");
if( out_file == NULL )
printf(“Can't open”);
else
{
VÍ DỤ MINH HỌA
VÍ DỤ MINH HỌA