Bài Tập Về Đệ Quy Trong C

Đệ quy là gì ?

Đệ quy là quá trình lặp đi lặp lại một thành phần theo cùng một cách. Dưới đây là một ví dụ minh họa tổng quát:

void tenhamdequi() { tenhamdequi(); /* goi chinh no */ } int main() { tenhamdequi(); }

Ngôn ngữ lập trình C hỗ trợ đệ quy, ví dụ, một hàm có thể gọi đến chính nó. Nhưng khi bạn sử dụng hàm đệ quy, lập trình viên cần phải cẩn thận định nghĩa điều kiện thoát khỏi hàm, phòng khi gặp phải vòng lặp vô hạn.

Hàm lặp đệ quy rất hữu dụng để giải quyết các vấn đề trong toán học như tính toán giai thừa, tạo dãy Fibonacci, …

1. Bài tập C: Tính tổng n số sử dụng đệ quy

Đây là bài tập C khá đơn giản giúp bạn hiểu cách sử dụng đệ quy trong ngôn ngữ lập trình C.

Chương trình C

Dưới đây là chương trình C để giải bài tập tính tổng n số sử dụng đệ quy trong C:

#include<stdio.h> int calculateSum(int); int main() { int i, num; int result; printf("Nhap mot so bat ky: "); scanf("%d", &num); result = calculateSum(num); printf("\nTong cac so tu 1 toi %d la: %d", num, result); return (0); } int calculateSum(int num) { int res; if (num == 1) { return (1); } else { res = num + calculateSum(num - 1); } return (res); }

Biên dịch chương trình C trên sẽ cho kết quả:

2. Bài tập C: Tính giai thừa bởi sử dụng đệ quy

Giai thừa của một số n là tích các số từ 1 tới n. Ví dụ, giai thừa của 4 là (4 * 3 * 2 * 1 = 24). Đây là bài tập C khá đơn giản giúp bạn làm quen với cách sử dụng đệ quy trong C.

Chương trình C

Dưới đây là chương trình C để giải bài tập tính giai thừa bởi sử dụng đệ quy trong C:

#include <stdio.h> int tinhgiaithua(unsigned int i) { if(i <= 1) { return 1; } return i * tinhgiaithua(i - 1); } int main() { int i = 10; printf("Gia tri giai thua cua %d la %d\n", i, tinhgiaithua(i)); printf("\n===========================\n"); printf("VietJack chuc cac ban hoc tot! \n"); return 0; }

Biên dịch và thực thi chương trình C trên sẽ cho kết quả sau:

3. Bài tập C: Giải bài toán Tháp Hà Nội (Tower of Hanoi) sử dụng đệ quy

Trước khi tìm hiểu lời giải cho bài toán Tháp Hà Nội (Tower of Hanoi), mình xin nhắc lại một số qui tắc của trò chơi toán Tháp Hà Nội này:

Tháp Hà Nội (Tower of Hanoi) là gì ?

Bài toán Tháp Hà Nội (Tower of Hanoi) là một trò chơi toán học bao gồm 3 cột và với số đĩa nhiều hơn 1.

Dưới đây là hình minh họa bài toán Tháp Hà Nội (Tower of Hanoi) với trường hợp có 3 đĩa.

Các đĩa có kích cỡ khác nhau và xếp theo tự tự tăng dần về kích cỡ từ trên xuống: đĩa nhỏ hơn ở trên đĩa lớn hơn. Với số đĩa khác nhau thì ta có các bài toán Tháp Hà Nội (Tower of Hanoi) khác nhau, tuy nhiên lời giải cho các bài toán này là tương tự nhau. Lời giải tối ưu cho bài toán Tháp Hà Nội (Tower of Hanoi) là khi trò chơi chỉ có 3 cọc. Với số cọc lớn hơn thì lời giải bài toán vẫn chưa được khẳng định.

Qui tắc trò chơi toán học Tháp Hà Nội (Tower of Hanoi)

Nhiệm vụ của trò chơi là di chuyển các đĩa có kích cỡ khác nhau sang cột khác sao cho vẫn đảm bảo thứ tự ban đầu của các đĩa: đĩa nhỏ nằm trên đĩa lớn. Dưới đây là một số qui tắc cho trò chơi toán học Tháp Hà Nội (Tower of Hanoi):

• Mỗi lần chỉ có thể di chuyển một đĩa từ cột này sang cột khác.
• Chỉ được di chuyển đĩa nằm trên cùng (không được di chuyển các đĩa nằm giữa).
• Đĩa có kích thước lớn hơn không thể được đặt trên đĩa có kích thước nhỏ hơn.

Dưới đây là hình minh họa cách giải bài toán Tháp Hà Nội (Tower of Hanoi) với trường hợp có 3 đĩa.

Bài toán Tháp Hà Nội (Tower of Hanoi) với số đĩa là n có thể được giải với số bước tối thiểu là 2n−1. Do đó, với trường hợp 3 đĩa, bài toán Tháp Hà Nội (Tower of Hanoi) có thể được giải sau 23−1 = 7 bước.

Phần dưới đây mình trình bày hai cách giải: sử dụng đệ quy và KHÔNG sử dụng đệ quy trong C.

Chương trình C: sử dụng đệ quy

Dưới đây là chương trình C để giải bài toán Tháp Hà Nội (Tower of Hanoi) sử dụng đệ quy trong C trong C:

#include<stdio.h> void TOH(int num, char x, char y, char z); int main() { int num; printf("\nNhap so dia:"); scanf("%d", &num); TOH(num - 1, 'A', 'B', 'C'); return (0); } void TOH(int num, char x, char y, char z) { if (num > 0) { TOH(num - 1, x, z, y); printf("\n%c -> %c", x, y); TOH(num - 1, z, y, x); } }

Biên dịch chương trình C trên sẽ cho kết quả:

Bài tập C: In dãy Fibonacci sử dụng đệ quy

Dãy Fibonacci là dãy số được tạo bằng cách: số kế tiếp bằng tổng của hai số liền trước. Dãy Fibonacci bắt đầu từ hai số F0 & F1. Giá trị ban đầu của F0 & F1 có thể tương ứng là 0, 1 hoặc 1, 1.

Điều kiện của dãy Fibonacci có thể tổng quát lại như sau:

Fn = Fn-1 + Fn-2

Dưới đây là ví dụ hai Fibonacci

F8 = 0 1 1 2 3 5 8 13

hoặc:

F8 = 1 1 2 3 5 8 13 21

Trong chương này chúng ta sẽ giải bài tập C này bởi sử dụng khái niệm đệ quy. Mời bạn theo dõi chương trình C dưới đây.

Chương trình C

Dưới đây là chương trình C để giải bài tập in dãy Fibonacci sử dụng đệ quy trong C:

#include <stdio.h> int day_fibonaci(int i) { if(i == 0) { return 0; } if(i == 1) { return 1; } return day_fibonaci(i-1) + day_fibonaci(i-2); } int main() { int i; for (i = 0; i < 10; i++) { printf("%d\t%n", day_fibonaci(i)); } printf("\n===========================\n"); printf("VietJack chuc cac ban hoc tot! \n"); return 0; }

Biên dịch và thực thi chương trình C trên sẽ cho kết quả sau:

 

Chia sẻ:

• X
• Facebook

Thích Đang tải...