Cấutrúcdữ liệuvàgiải thuật
Người thực hiện: Đỗ Tuấn Anh
Email: [email protected]
ĐT: 0989095167
Nộidung
z Chương 1 – Thiếtkế và phân tích (5 tiết)
z Chương 2 – Giảithuật đệ quy (10 tiết)
z Chương 3 – Mảng và danh sách (5 tiết)
z Chương 4 – Ngănxếp và hàng đợi (10 tiết)
z Chương 5 – Cấu trúc cây (10 tiết)
z Chương 8 – Tìm kiếm(5 tiết)
z Chương 7 – Sắpxếp (10 tiết)
z Chương 6 – Đồ thị (5 tiết)
Chương 2 – Giảithuật đệ quy
1. Khái niệm
2. Thiếtkế giảithuật đệ quy
3. Hiệulựccủa đệ quy
4. Đệ quy và quy nạp toán học
5. Đệ quy quay lui
1. Khái niệm
z Là mộtkỹ thuậtgiải quyết bài toán quan
trọng trong đó:
{Phân tích đốitượng thành các thành phầnnhỏ
hơn mang tính chấtcủa chính đốitượng đó.
z Ví dụ:
{Định nghĩasố tự nhiên:
z1 là mộtsố tự nhiên
zx là mộtsố tự nhiên nếux-1 làmộtsố tự nhiên
Ví dụ 1 - Tính giai thừa
z Hàm tính giai thừachomộtsố nguyên:
z Định nghĩa đệ quy:

{Phảikiểmtrađiểmdừng
Giảithuật đệ quy – ví dụ
z Tìm file trong thư mục trên máy tính
z Tra từ trong từđiển Anh-Anh
2. Thiếtkế giảithuật đệ quy
z 3 bước:
{Thông số hóa bài toán
{Tìm điềukiệndừng
{Phân rã bài toán
z Ví dụ bài toán: Tính N!
Bước 1: Thông số hóa bài toán
z Tìm các thông số biểuthị kích thướccủa
bài toán
z Quyết định độ phứctạpcủa bài toán
z Ví dụ: Tính N!
{ N trong hàm tính giai thừacủaN
Bước2: Tìmđiềukiệndừng
z Là trường hợpgiải không đệ quy
z Là trường hợpkíchthước bài toán nhỏ
nhất
z Ví dụ: Tính N!
{ 0! = 1
Bước 3: Phân rã bài toán
z Phân rã bài toán thành các thành phần:
{ Hoặc không đệ quy
{ Hoặc là bài toán trên nhưng kích thướcnhỏ
hơn
z Bài toán viết đượcdướidạng công thức
đệ quy => đơngiản
z Ví dụ: Tính N!

112
6
24
Factorial(4)
Factorial(3)4
3
Factorial(2)
Factorial(0)
2
Factorial(1)
1
*
*
*
*
1
1
2
6
24
Điềukiện đệ quy
Phảicóđiểmdừng: nếu không sẽ tạo thành một
chuỗivôhạn các lờigọihàm
long Factorial(long n){
return n * Factorial(n-1);
}
Phải làm cho bài toán đơngiảnhơn:
long Factorial(long n){
if (n==0)
return 1;

z Định nghĩa theo đệ quy:
{F(0) = 0;
{F(1) = 1;
{F(n) = F(n-1)+ F(n-2);
class="bi x3c y77 w0 h1b"
Dãy số Fibonacci – Thủ tục đệ quy
//Tính số Fibonacci sử dụng hàm đệ quy.
int fib(int number)
{
if (number == 0) return 0;
if (number == 1) return 1;
return (fib(number-1) + fib(number-2));
}
int main(){
int inp_number;
printf ("Please enter an integer: “);
scanf (“%d”, &inp_number);
int intfib = fib(inp_number);
printf("The Fibonacci number for %d is %d\n“,inp_number,intfib);
return 0;
}
Cơ chế thựchiện
z Tính fibonacci của 4, num=4:
fib(4):
4 == 0 ? Sai; 4 == 1? Sai.
fib(4) = fib(3) + fib(2)
fib(3):
3 == 0 ? Sai; 3 == 1? Sai.
fib(3) = fib(2) + fib(1)
fib(2):

fib(3) = 1 + 1 = 2;
return fib(3)
Cơ chế thựchiện
fib(2):
2 == 0 ? Sai; 2 == 1? Sai.
fib(2) = fib(1) + fib(0)
fib(1):
1== 0 ? Sai; 1 == 1? Đúng.
fib(1) = 1;
return fib(1);
fib(0):
0 == 0 ? Đúng.
fib(0) = 0;
return fib(0);
fib(2) = 1 + 0 = 1;
return fib(2);
fib(4) = fib(3) + fib(2)
= 2 + 1 = 3;
return fib(4);
Thủ tục đệ quy tổng quát
int Hàm_đệ_quy(DS tham số){
if(thỏa mãn điềukiệndừng)
return giá_trị_dừng_tương_ứng;
// other stopping conditions if needed
return hàm_đệ_quy(tham số suy giảm)
}
BàitoánthápHàNội
Ban đầu:
Cột1
Kếtthúc: