Đếm số cách biểu diễn n dưới dạng tổng các số lẻ trong C++

Cho một số nguyên n làm đầu vào. Mục tiêu là tìm số cách mà chúng ta có thể biểu diễn n dưới dạng tổng các số lẻ. Ví dụ, nếu n là 3, nó có thể biểu diễn dưới dạng tổng (1+1+1) và (3) nên tổng 2 cách.

Ví dụ

Đầu vào

n=6

Đầu ra

Số cách biểu diễn 'n' dưới dạng tổng các số lẻ là: 8

Giải thích

Các cách biểu diễn 'n' dưới dạng tổng các số lẻ: 1. 1+1+1+1+1+1 2. 3+1+1+1 3. 1+3+1+1 4. 1+1+3+1 5. 1+1+1+3 6. 3+3 7. 1+5 8. 5+1

Đầu vào

n=9

Đầu ra

Số cách biểu diễn 'n' dưới dạng tổng các số lẻ là: 34

Giải thích

Một số cách biểu diễn 'n' dưới dạng tổng các số lẻ: 1. 1+1+1+1+1+1+1+1+1 2. 3+3+3 3. 5+3+1 4. 7+1+1 5. ...và các tổ hợp khác

Phương pháp sử dụng

Trong phương pháp này, chúng ta sẽ kiểm tra các cách biểu diễn một số dưới dạng tổng các số lẻ từ các số trước đó là n-1 và n-2. Số cách sẽ là ways(n-1) + ways(n-2).

• Nhận số nguyên n làm đầu vào.
• Hàm odd_ways(int n) nhận một số và trả về số cách biểu diễn n dưới dạng tổng các số lẻ.
• Tạo mảng arr độ dài n+1 để lưu số cách biểu diễn các số dưới dạng tổng các số lẻ.
• Đối với số 0, không có cách nào nên đặt arr[0] bằng 0.
• Đối với số 1 chỉ có một cách nên đặt arr[1] bằng 1.
• Đối với các số còn lại, ta có thể đặt arr[i] bằng arr[i-1] + arr[i-2] cho i từ 2 đến n.
• Cuối cùng, chúng ta có arr[n] cho số cách mà n được biểu diễn dưới dạng tổng các số lẻ.
• Trả về arr[n] làm kết quả.

Ví dụ mã

#include <iostream> 
using namespace std; 

int odd_ways(int n) {
    int arr[n+1];
    arr[0] = 0;
    arr[1] = 1;
    
    for(int i = 2; i <= n; i++) {
        arr[i] = arr[i-1] + arr[i-2];
    }
    
    return arr[n];
}

int main() {
    int n = 6;
    cout << "Số cách biểu diễn 'n' dưới dạng tổng các số lẻ là: " << odd_ways(n);
    return 0;
}

Đầu ra

Nếu chạy mã trên, sẽ tạo ra đầu ra sau:

Số cách biểu diễn 'n' dưới dạng tổng các số lẻ là: 8