Số cách viết N thành tổng của hai hoặc nhiều số nguyên dương trong C++

Trong bài toán này, chúng ta được cho một số nguyên n. Nhiệm vụ là tìm tổng số cách nó có thể biểu diễn thành tổng của hai hoặc nhiều số nguyên dương.

Hãy xem ví dụ để hiểu bài toán,

Đầu vào

N = 4

Đầu ra

5

Giải thích

4 có thể viết thành tổng theo các cách: 4, 3+1, 2+2, 2+1+1, 1+1+1+1

Để giải bài toán này, chúng ta sẽ dùng công thức truy hồi Euler. Đối với một số n, tổng số cách nó có thể tạo ra p(n) bằng,

Σ∞n=0 p(n)xn = Π∞k=1 (1/(1-xk ))

Sử dụng công thức này, chúng ta sẽ suy ra công thức cho p(n), p(n) = p(n-1) + p(n-2) - p(n-5) - p(n-7) + … + (-1)^(k-1)((k(3k-1))/2)

Chương trình minh họa triển khai giải pháp,

Ví dụ

#include <bits/stdc++.h> using namespace std; long long postiveSum(int n){    vector<long long> p(n + 1, 0);    p[0] = 1;    for (int i = 1; i <= n; ++i) {       int k = 1;       while ((k * (3 * k - 1)) / 2 <= i) {          p[i] += (k % 2 ? 1 : -1) * p[i - (k * (3 * k - 1)) / 2];          if (k > 0)             k *= -1;          else             k = 1 - k;       }    }    return p[n]; } int main(){    int N = 12;    cout<<"Số cách "<<N<<" viết thành tổng hai hoặc nhiều số dương là "      <<postiveSum(N);    return 0; }

Đầu ra

Số cách 12 viết thành tổng hai hoặc nhiều số dương là 77