Khởi động

Câu hỏi. An được giao tìm một thiết kế mới cho bài toán tính tổng Sín) = 1 +2 +... +n. An nhận thấy S(n) có thế được viết như sau: S(n-1)= 1+2+..+n = 1+2+...+ n - 1 + n = S(n - 1) + n. Do đó, việc tính S(n) có thể được tính từ S(n - 1), tương tự S(n - 1) lại có thể được tính từ S(n - 2), cứ như vậy, cuối cùng sẽ dẫn đến cần tính S(0), nhưng S(0) = 0.

Em có thể giúp An hoàn thiện ý tưởng trên thành một chương trình hay không?

Giải chi tiết:

• B1. Bài toán yêu cầu tính tổng n số nguyên từ 1 đến n. Cần thiết lập hàm S(n) trả về giá trị cần tìm.
• B2. Điều kiện n>0
• B3. Công thức truy hồi của hàm S(n)

1. Ý tưởng thiết kế theo đệ quy

Câu hỏi 1. Hãy chỉ ra phần cơ sở và phần đệ quy của các chương trình trên.

Giải chi tiết:

Thuật toán 1

- Phần cơ sở: return 0

- Phần đệ quy: if n == 0, else

Thuật toán 2

- Phần cơ sở:return 1/ return a*exp(a, n-1)

- Phần đệ quy: if n == 0, else

Thuật toán 3

- Phần cơ sở: return 1/ return a*giaithua (n-1)
- Phần đệ quy: if n == 0, else

Câu hỏi 2. Vì sao trong ý tưởng thiết kế đệ quy trên, yêu cầu từ bài toán với kích thước lớn cần phải đưa về cùng bài toán đó với kích thước nhỏ hơn?

Giải chi tiết:

• Ý tưởng chính của kĩ thuật đệ quy là biến đổi bài toán ban đầu về bài toán với kích thước nhỏ hơn. Nếu bài toán có kích thƯớc nhỏ có thể giải được thì có thể thiết lập lời giải đệ quy cho bài toán này. Lời giải của các bài toán sờ dụng đệ quy thường ngắn gọn và dễ hiểu.

2. Thuật toán tìmkiếm nhị phân

Câu hỏi 1. Nêu ý tưởng chính của giải thuật tìm kiếm nhị phân sử dụng đệ quy.

Giải chi tiết:

Do tính chất mảng đã sắp xếp, công việc tìm kiếm phần tử x có thể triển khai như sau:

1. Xét đoạn mảng arr[left…right] cần tìm kiếm phần tử x. Ta so sánh x với phần tử ở vị trí giữa của mảng(mid = (left + right)/2). Nếu:
2. Nếu phần tử arr[mid] = x. Kết luận và thoát chương trình.
3. Nếu arr[mid] < x. Chỉ thực hiện tìm kiếm trên đoạn arr[mid+1…right].
4. Nếu arr[mid] > x. Chỉ thực hiện tìm kiếm trên đoạn arr[left…mid-1].

Câu hỏi 2. Vị trí nào trong thuật toán có thể gợi ý cho kĩ thuật đệ quy?

Giải chi tiết:

• Khi đưa bài toán tìm kiếm về chính bài toán đó

Câu hỏi 3. Phần cơ sở của thiết kế đệ quy nằm ở bước nào?

Giải chi tiết:

• Bước 3 đóng vai trò phần cơ sở đệ quy, khi độ dài của dãy cần tìm kiếm bằng 0 thì chương trình sẽ dừng lại và thông báo không tìm thấy

Câu hỏi 4. Nêu ý tưởng chính của giải thuật tìm kiếm nhị phân sử dụng đệ quy.

Giải chi tiết:

Tìm kiếm nhị phân chỉ có thể cài đặt trong một mảng đã được sắp xếp. Nếu mảng đó chưa được sắp xếp, hãy sắp xếp nó trước trước khi cài đặt thuật toán.

Có 2 cách để cài đặt thuật toán Tìm kiếm nhị phân:

1. Sử dụng vòng lặp
2. Sử dụng đệ quy

Trong bài viết này, mình sẽ hướng dẫn các bạn sử dụng đệ quy để cài đặt thuật toán. Phương pháp đệ quy này tuân theo nguyên tắc “chia để trị” gồm những bước như sau:

• Bước 1: Khởi tạo mảng và sắp xếp các phần tử trong mảng (theo thứ tự bé đến lớn) và mình chọn phần tử x = 4 là phần tử cần được tìm kiếm.
• Bước 2: Đặt 2 con trỏ low và high ở vị trí đầu và cuối của mảng tương ứng với phần tử nhỏ nhất và phần tử lớn nhất của mảng.
• Bước 3: Tìm phần tử ở giữa mảng mid = (low + high) / 2.
• Bước 4: Nếu x = arr[mid] thì trả về mid, nếu không ta tiếp tục so sánh.
• Bước 5: Nếu x > arr[mid], so sánh x với các phần tử ở phía bên phải của mid bằng cách thay low = mid + 1.
• Bước 6: Nếu x < arr[mid], so sánh x với các phần tử ở phía bên trái của mid bằng cách thay high = mid – 1.
• Bước 7: Lặp lại từ bước 3 đến bước 6 cho đến khi con trỏ low gặp high.
• Bước 8: Và cuối cùng phần tử x = 4 đã được tìm thấy.

Câu hỏi 1. Trong chương trình trên lệnh nào đóng vai trò là phần cơ sở của đệ quy?

Giải chi tiết:

• Lệnh if và else if

Câu hỏi 2. Giả sử A = [1. 3. 7, 9] và K = 10. Nếu áp dụng chương trình trên thì cần mấy lần gọi hàm đệ quy?

Giải chi tiết:

• Cần 5 lần gọi hàm đệ quy

Luyện tập

Câu hỏi 1. Viết chương trình theo kĩ thuật đệ quy để tính hàm SL(n) là tổng các số tự nhiên lẻ nhỏ hơn hoặc bằng n.

Giải chi tiết:

//Viết chương trình tính tổng các giá trị lẻ nguyên dương nhỏ hơn N

#include <stdio.h>

int main() {

//khai báo biến n là số nguyên dương và sum = 0 là tổng các số lẻ từ 1 đến n

int n, sum = 0;

//sử dụng printf() và scanf() để yêu cầu người dùng nhập vào số nguyên n

printf("\nNhập vào số nguyên dương n: ");

scanf("%d", n);

//sử dụng vòng lặp for lặp từ 1 đến n với bước nhảy là i += 2 để lấy các số lẻ

for(int i = 1; i < n; i +=2){

//cứ sau mỗi vòng lặp thì sum = sum + i

sum = sum + i;

}

//sử dụng vòng lặp while để tính

// int i = 1;

// while(i < n){

// sum += i;

// i += 2;

// }

//hiển thị sum ra màn hình

printf("\nTổng các số lẻ từ 1 đến %d là: %d", n, sum);

printf("\n--------------------------------------\n");

printf("Chương trình này được đăng tại Freetuts.net");

}

Câu hỏi 2. Cho trước dãy A, Viết chương trình đệ quy để in dãy A theo thứ tự ngược lại.

Giải chi tiết:

#include<stdio.h>

int main(){

int num,reverse_number;

//User nhap so can dao nguoc

printf("\nNhap mot so bat ki:");

scanf("%d", num);

//Goi ham de quy

reverse_number = reverse_function(num);

printf("\nSau khi dao nguoc :%d", reverse_number);

return 0;

}

int reverse_function(int num){

int sum = 0, rem;

if(num){

rem = num % 10;

sum = (sum*10) + rem;

reverse_function(num/10);

}

else

return sum; // điều kiện dừng

return sum;

}

Vận dụng

Câu 1. Viết chương trình tính tổng S = 1! + 2! +... + n! theo hai cách:

a) Không sử dụng đệ quy.

b) Có sử dụng kĩ thuật đệ quy.

Giải chi tiết:

a)

Viết chương trình tính tổng S = 1! + 2! +... + n! theo hai cách: