[C]. Bài Tập Đệ Quy

main

1.Số Fibonacci, Tổ Hợp

Số Fibonacci

Số Fibonacci có thể tính bằng hàm đệ quy dựa trên bài toán cơ sở và công thức truy hồi :

Bài toán cơ sở : F0 = 0, F1 = 1

Công thức truy hồi : Fn = Fn-1 + Fn-2, n > 1

Code :

#include "stdio.h" int F(int n){ if(n == 0 || n == 1){ return n; } else{ return F(n - 1) + F(n - 2); } } int main(){ printf("%d", F(12)); return 0; }

Output :

144

Tổ hợp chập K của N

Tổ hợp chập K của N (C(n, k)) được tính đệ quy dựa vào bài toán cơ sở và công thức truy hồi sau :

Bài toán cơ sở : C(n, 0) = 1 và C(n, n) = 1

Công thức truy hồi : C(n, k) = C(n - 1, k - 1) + C(n - 1, k)

Code :

#include "stdio.h" int C(int n, int k){ if(n == k || k == 0){ return 1; } else{ return C(n - 1, k - 1) + C(n - 1, k); } } int main(){ printf("%d", C(12, 2)); return 0; }

Output :

66

2.Chuyển Đổi Cơ Số

Hệ nhị phân

Hệ nhị phân biểu diễn số dưới 2 bit là 0 và 1, khi chuyển từ số thập phân N sang số nhị phân bạn thực hiện quá trình chia N cho 2 cho tới khi N = 0, viết ngược lại các số dư của N trong quá trình chia cho 2 đó sẽ được biểu diễn dưới dạng nhị phân.

Ví dụ N = 37 thì biểu diễn nhị phân của N sẽ là 100101

NN / 2N % 2371811890941420210101

Code :

#include "stdio.h" void dec_to_bin(long long n){ if(n < 2){ printf("%d", n); } else{ dec_to_bin(n / 2); printf("%d", n % 2); } } int main(){ dec_to_bin(37); printf("n"); dec_to_bin(282828282828); return 0; }

Output :

100101 100000111011001111000010001101111001100

Hệ thập lục phân

Hệ thập lục phân hay hệ 16 biểu diễn số thông qua 16 ký tự gồm các chữ số từ 0 tới 9, các số từ 10 tới 15 được thay thế thành các chữ cái từ A tới F.

Tương tự như chuyển từ hệ thập phân sang hệ 16 thì ta thực hiện chia cho 16 và lưu lại số dư trong quá trình chia, viết ngược lại số dư trong quá trình chia ta được biểu diễn dưới hệ số 16

Ví dụ N = 762 thì biểu diễn hệ 16 là 2FA

NN / 16N % 167624710 (A)47215 (F)202

Code :

#include "stdio.h" void dec_to_hex(long long n){ if(n < 16){ if(n < 10){ printf("%d", n); } else{ printf("%c", (55 + n)); } } else{ dec_to_hex(n / 16); int r = n % 16; if(r < 10){ printf("%d", r); } else{ printf("%c", (55 + r)); } } } int main(){ dec_to_hex(762); printf("n"); dec_to_hex(282828282828); return 0; }

Output :

2FA 41D9E11BCC

3.Các Bài Toán Liên Quan Tới Chữ Số

Bài 1. Đếm số chữ số của số N

Bài toán cơ sở : D(N) = 1 nếu N < 10

Công thức truy hồi : D(N) = 1 + D(N / 10) nếu N ≥ 10

Code :

#include "stdio.h" int D(long long n){ if(n < 10){ return 1; } else{ return 1 + D(n / 10); } } int main(){ long long n = 28282828; printf("%d", D(n)); return 0; }

Output :

8

Bài 2 : Tính tổng chữ số của số N

Bài toán cơ sở : S(N) = N nếu N < 10

Công thức truy hồi : S(N) = N % 10 + S(N / 10) nếu N ≥ 10

Code :

#include "stdio.h" int S(long long n){ if(n < 10){ return n; } else{ return n % 10 + S(n / 10); } } int main(){ long long n = 28282828; printf("%d", S(n)); return 0; }

Output :

40

Bài 3. Tính tổng chữ số chẵn (lẻ) của N

Bài toán cơ sở : S(N) = 0 nếu N lẻ, N nếu N chẵn với N < 10

Công thức truy hồi : S(N) = S(N / 10) nếu N lẻ, N % 10 + S(N / 10) nếu N chẵn với N ≥ 10

Code :

#include "stdio.h" int S(long long n){ if(n < 10){ if(n % 2 == 1) return 0; else return n; } else{ if(n % 2 == 1) return S(n / 10); else return n % 10 + S(n / 10); } } int main(){ long long n = 12345678; printf("%d", S(n)); return 0; }

Output :

20

Bài 4. Tìm chữ số lớn nhất (nhỏ nhất) của N

Bài toán cơ sở : F(N) = N nếu N < 10

Công thức truy hồi : F(N) = max(N % 10, F(N / 10)) với N ≥ 10

Code :

#include "stdio.h" int F(long long n){ if(n < 10){ return n; } else{ int tmp = F(n / 10); return n % 10 > tmp ? n % 10 : tmp; } } int main(){ long long n = 12349567; printf("%d", F(n)); return 0; }

Output :

9

4. Các Bài Toán Liên Quan Tới Tổng Dãy Số

Bài 1. Tổng tự nhiên liên tiếp S(n) = 1 + 2 + 3 + ... + n

Bài toán cơ sở : S(n) = 1 nếu n = 1

Công thức truy hồi : S(n) = n + S(n - 1) với n > 1

Code :

#include "stdio.h" int S(int n){ if(n == 1){ return 1; } else{ return n + S(n - 1); } } int main(){ int n = 10; printf("%d", S(n)); return 0; }

Output :

55

Bài 2. Tổng bình phương liên tiếp S(n) = 12 + 22 + 32 + ... + n2

Bài toán cơ sở : S(n) = 1 nếu n = 1

Công thức truy hồi : S(n) = n2 + S(n - 1) với n > 1

Code :

#include "stdio.h" int S(int n){ if(n == 1){ return 1; } else{ return n * n + S(n - 1); } } int main(){ int n = 10; printf("%d", S(n)); return 0; }

Output :

385

Bài 3. Tổng bình phương liên tiếp S(n) = 1/1 + 1/2 + 1/3 + .... + 1/n

Bài toán cơ sở : S(n) = 1 nếu n = 1

Công thức truy hồi : S(n) = 1/n + S(n - 1) với n > 1

Code :

#include "stdio.h" double S(int n){ if(n == 1){ return 1; } else{ return (double)1 / n + S(n - 1); } } int main(){ int n = 10; printf("%.2lf", S(n)); return 0; }

Output :

2.93

5. Các Bài Toán Liên Quan Tới Mảng

Nếu bạn chưa học lý thuyết về mảng thì có thể học phần mảng trước khi làm các bài tập mục này.

Bài 1. Tính tổng các số chẵn trong mảng

Code :

#include "stdio.h" int even_sum(int a[], int n){ if(n == 0){ return 0; } else{ if(a[n - 1] % 2 == 0){ return a[n - 1] + even_sum(a, n - 1); } else{ return even_sum(a, n - 1); } } } int main(){ int n = 6; int a[6] = {1, 2, 3, 4, 5, 6}; printf("%dn", even_sum(a, n)); return 0; }

Output :

12

Bài 2 . Kiểm tra mảng đối xứng

Code :

#include "stdio.h" int doixung(int a[], int left, int right){ if(left > right){ return 1; } else{ if(a[left] != a[right]){ return 0; } else{ return doixung(a, left + 1, right - 1); } } } int main(){ int n = 6; int a[6] = {1, 2, 3, 3, 2, 1}; printf("%dn", doixung(a, 0, n - 1)); return 0; }

Output :

1

Bài 3. In ra mảng từ trái qua phải

Code :

#include "stdio.h" void left_to_right(int a[], int n){ if(n > 0){ left_to_right(a, n - 1); printf("%d ", a[n - 1]); } } int main(){ int n = 6; int a[6] = {1, 2, 3, 4, 5, 6}; left_to_right(a, 6); return 0; }

Output :

1 2 3 4 5 6

Bài 4. In ra mảng từ phải qua trái

Code :

#include "stdio.h" void left_to_right(int a[], int n){ if(n > 0){ printf("%d ", a[n - 1]); left_to_right(a, n - 1); } } int main(){ int n = 6; int a[6] = {1, 2, 3, 4, 5, 6}; left_to_right(a, 6); return 0; }

Output :

6 5 4 3 2 1