Home / Tin Tức / bài tập đệ quy c++

Bài tập đệ quy c++

admin 29/08/2023

Đệ quy là gì?

Đệ quy trong C là quy trình trong đó một thủ tục gọi lại chủ yếu nó một cách liên tiếp. Một cách thức trong C gọi lại thiết yếu nó được điện thoại tư vấn là cách thức đệ quy.

Cú pháp:

Bạn đang xem: Bài tập đệ quy c++

kieu_tra_ve tenhamdequi() // your code tenhamdequi(); /* goi lai chinh no */int main() tenhamdequi();
ngôn từ lập trình C cung ứng đệ quy, ví dụ, một hàm hoàn toàn có thể gọi đến bao gồm nó. Nhưng khi bạn sử dụng hàm đệ quy, lập trình sẵn viên nên phải cẩn thận định nghĩa đk thoát ngoài hàm, phòng khi gặp gỡ phải vòng lặp vô hạn.

Hàm đệ quy rất hữu dụng để giải quyết các vụ việc trong toán học như thống kê giám sát giai thừa, sản xuất dãy Fibonacci, …

bài bác tập Đệ quy trong C
Dưới đó là các bài bác tập C giúp bạn hiểu kỹ năng cơ phiên bản về Đệ quy trong C:
Tính hàng số Fibonacci áp dụng đệ quy
Ví dụ công tác C kiếm tìm 10 số Fibonacci thứ nhất sử dụng phương pháp đệ quy:

Chạy chương trình C bên trên cho công dụng như sau:

Tính giai thừa áp dụng đệ quy
Ví dụ lịch trình tính giai vượt trong C bao gồm sử dụng phương thức đệ quy:

return giai thua thảm cua so n */long tinhGiaithua(int n) if (n > 0) return n * tinhGiaithua(n - 1); else return 1; /** * yêu thích main */int main() int a = 5; int b = 0; int c = 10; printf("Giai lose cua %d la: %d ", a, tinhGiaithua(a)); printf("Giai thua thảm cua %d la: %d ", b, tinhGiaithua(b)); printf("Giai thua trận cua %d la: %d", c, tinhGiaithua(c));
Chạy chương trình C bên trên cho kết quả như sau:
search USCLN với BSCNN của 2 số a cùng b áp dụng đệ quy
Ví dụ dưới đây sử dụng giải thuật Euclid để xử lý bài toán tìm ước số chung lớn số 1 (USCLN) cùng bội số chung nhỏ dại nhất (BSCNN) của nhị số nguyên dương a cùng b:

/** * Chuong trinh tim uoc bình thường lon nhat (USCLN) * va boi so thông thường nho nhat (BSCNN) cua 2 so a và b * *
author racingbananas.com */#include /** * Tim uoc so tầm thường lon nhat (USCLN) */int USCLN(int a, int b) if (b == 0) return a; return USCLN(b, a % b); /** * Tim boi so phổ biến nho nhat (BSCNN) */int BSCNN(int a, int b) return (a * b) / USCLN(a, b); /** * say mê main */int main() int a, b; printf("Nhap so nguyen duong a = "); scanf("%d", &a); printf("Nhap so nguyen duong b = "); scanf("%d", &b); // tinh USCLN cua a cùng b printf(" USCLN cua %d va %d la: %d", a, b, USCLN(a, b)); // tinh BSCNN cua a cùng b printf(" USCLN cua %d va %d la: %d", a, b, BSCNN(a, b));
Xem thêm: Phim Truy Tìm Tượng Phật 2 (Ong Bak 2) Thuyết Minh, Phim Truy Tìm Tượng Phật 1
Chạy công tác C bên trên cho tác dụng như sau:

Tính tổng n số áp dụng đệ quy
Ví dụ chương trình tổng của n số vào C có sử dụng phương pháp đệ quy:

/** * Chuong trinh tong cua n so tu nhien * *
author racingbananas.com */#includeint calculateSum(int);int main() int i, num; int result; printf("Nhap mot so bat ky: "); scanf("%d", &num); result = calculateSum(num); printf(" Tong 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);
Chạy chương trình C trên cho tác dụng như sau:
bài toán Tháp tp. Hà nội (Tower of Hanoi) áp dụng đệ quy
Trước khi khám phá lời giải cho việc Tháp tp. Hà nội (Tower of Hanoi), mình xin nhắc lại một số trong những qui tắc của trò chơi toán Tháp tp. Hà nội này:
Tháp hà thành (Tower of Hanoi) là gì ?
việc Tháp thủ đô (Tower of Hanoi) là 1 trò chơi toán học bao hàm 3 cột cùng với số đĩa nhiều hơn nữa 1.
Dưới đấy là hình minh họa việc Tháp tp. Hà nội (Tower of Hanoi) với ngôi trường hợp gồm 3 đĩa.
những đĩa tất cả kích cỡ không giống nhau và xếp theo trường đoản cú tự tăng dần về kích thước từ bên trên xuống: đĩa nhỏ hơn ngơi nghỉ trên đĩa béo hơn. Với số đĩa không giống nhau thì ta có những bài toán Tháp thủ đô (Tower of Hanoi) khác nhau, tuy vậy lời giải cho những bài toán này là tương tự như nhau. Giải thuật tối ưu cho câu hỏi Tháp thủ đô hà nội (Tower of Hanoi) là khi trò nghịch 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 thủ đô hà nội (Tower of Hanoi)
trọng trách của trò chơi là dịch rời các đĩa bao gồm kích cỡ khác biệt sang cột khác thế nào cho vẫn đảm bảo an toàn thứ tự thuở đầu của các đĩa: đĩa nhỏ tuổi nằm trên đĩa lớn. Dưới đấy là một số qui tắc mang lại trò nghịch toán học Tháp hà thành (Tower of Hanoi):
Mỗi lần chỉ hoàn toàn có thể di đưa một đĩa từ cột này thanh lịch cột khác. Chỉ được dịch chuyển đĩa nằm trên thuộc (không được di chuyển các đĩa ở giữa). Đĩa có size lớn hơn chẳng thể được đặt lên trên đĩa có kích thước nhỏ hơn.
Dưới đó là hình minh họa biện pháp giải vấn đề Tháp thành phố hà nội (Tower of Hanoi) với trường hợp bao gồm 3 đĩa.

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

chương trình C: thực hiện đệ quy

Dưới đó là chương trình C để giải việc Tháp tp. Hà nội (Tower of Hanoi) áp dụng đệ quy vào C trong C:

/** * Chuong trinh giai bai toan Thap Ha Noi * *
author racingbananas.com */#includevoid TOH(int num, char x, char y, char z);int main() int num; printf(" Nhap 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(" %c -> %c", x, y); TOH(num - 1, z, y, x);
Chạy lịch trình C trên cho tác dụng như sau: