Bài Tập Đệ Quy

Chào mừng các bạn đến với bài viết thú vị về đệ quy trên trang web Izumi.Edu.VN! Trong bài viết này, chúng ta sẽ tìm hiểu về các bài toán đệ quy và cách giải chúng.

Có thể bạn quan tâm

Số Fibonacci, Tổ Hợp

Số Fibonacci

Số Fibonacci là một dãy số được tính bằng cách sử dụng hàm đệ quy dựa trên bài toán cơ sở và công thức truy hồi:

Bạn đang xem: Bài Tập Đệ Quy

Bài toán cơ sở: F0 = 0, F1 = 1
Công thức truy hồi: Fn = Fn-1 + Fn-2, với n > 1

Dưới đây là đoạn code để tính số Fibonacci:

#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;
}

Kết quả đầu ra là: 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)

Dưới đây là đoạn code để tính tổ hợp chập K của N:

#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;
}

Kết quả đầu ra là: 66

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, ta thực hiện quá trình chia N cho 2 cho tới khi N = 0. Sau đó, viết ngược lại các số dư của N trong quá trình chia cho 2 để đượ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

Dưới đây là đoạn code để chuyển từ số thập phân sang nhị phân:

#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;
}

Kết quả đầu ra là: 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 đến 9 và các chữ cái từ A đến F. Tương tự như chuyển từ hệ thập phân sang hệ 16, ta thực hiện chia cho 16 và lưu lại số dư trong quá trình chia. Sau đó, viết ngược lại số dư trong quá trình chia để được biểu diễn dưới hệ số 16.

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

Dưới đây là đoạn code để chuyển từ số thập phân sang hệ thập lục phân:

#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;
}

Kết quả đầu ra là: 2FA 41D9E11BCC

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 đếm số chữ số của số N được giải quyết bằng đệ 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ở: D(N) = 1 nếu N < 10
Công thức truy hồi: D(N) = 1 + D(N / 10) nếu N ≥ 10

Dưới đây là đoạn code để đếm số chữ số của số N:

#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;
}

Kết quả đầu ra là: 8

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

Bài toán tính tổng chữ số của số N được giải quyết bằng đệ 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ở: 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

Dưới đây là đoạn code để tính tổng chữ số của số N:

#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;
}

Kết quả đầu ra là: 40

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

Bài toán tính tổng chữ số chẵn (lẻ) của N được giải quyết bằng đệ 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ở: 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

Dưới đây là đoạn code để tính tổng chữ số chẵn (lẻ) của N:

#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;
}

Kết quả đầu ra là: 20

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

Bài toán tìm chữ số lớn nhất (nhỏ nhất) của N được giải quyết bằng đệ 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ở: 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

Dưới đây là đoạn code để tìm chữ số lớn nhất (nhỏ nhất) của N:

#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;
}

Kết quả đầu ra là: 9

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 tính tổng tự nhiên liên tiếp S(n) = 1 + 2 + 3 + … + n được giải quyết bằng đệ 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ở: S(n) = 1 nếu n = 1
Công thức truy hồi: S(n) = n + S(n – 1) với n > 1

Dưới đây là đoạn code để tính tổng tự nhiên liên tiếp S(n):

#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;
}

Kết quả đầu ra là: 55

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

Bài toán tính tổng bình phương liên tiếp S(n) = 12 + 22 + 32 + … + n2 được giải quyết bằng đệ 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ở: S(n) = 1 nếu n = 1
Công thức truy hồi: S(n) = n2 + S(n – 1) với n > 1

Dưới đây là đoạn code để tính tổng bình phương liên tiếp S(n):

#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;
}

Kết quả đầu ra là: 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 tính tổng bình phương liên tiếp S(n) = 1/1 + 1/2 + 1/3 + …. + 1/n được giải quyết bằng đệ 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ở: 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

Dưới đây là đoạn code để tính tổng bình phương liên tiếp S(n):

#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;
}

Kết quả đầu ra là: 2.93

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, hãy tham khảo phần mảng trên trang web Izumi.Edu.VN trước khi làm các bài tập trong mục này.

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

Dưới đây là đoạn code để tính tổng các số chẵn trong mảng:

#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;
}

Kết quả đầu ra là: 12

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

Dưới đây là đoạn code để kiểm tra mảng đối xứng:

#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;
}

Kết quả đầu ra là: 1

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

Dưới đây là đoạn code để in ra mảng từ trái qua phải:

#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;
}

Kết quả đầu ra là: 1 2 3 4 5 6

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

Dưới đây là đoạn code để in ra mảng từ phải qua trái:

#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;
}

Kết quả đầu ra là: 6 5 4 3 2 1

Đó là một số bài toán đệ quy thú vị mà chúng ta đã tìm hiểu trong bài viết này. Hy vọng rằng các bạn đã thấy thú vị và có thể áp dụng những kiến thức này vào thực tế. Đừng quên truy cập Izumi.Edu.VN để tìm hiểu thêm nhiều kiến thức bổ ích khác nhé!

Nguồn: https://izumi.edu.vn/
Danh mục: Kiến thức chung