จำนวนวิธีเขียน N เป็นผลรวมของจำนวนเต็มบวกสองจำนวนขึ้นไปใน C++

ในโจทย์นี้ เราได้รับจำนวนเต็ม n งานของเราคือหาจำนวนวิธีทั้งหมดที่มันสามารถแสดงเป็นผลรวมของจำนวนเต็มบวกสองจำนวนขึ้นไปได้

ตัวอย่าง

อินพุต

N = 4

เอาต์พุต

5

คำอธิบาย

4 สามารถเขียนเป็นผลรวมได้ในวิธีเหล่านี้: 4, 3+1, 2+2, 2+1+1, 1+1+1+1

เพื่อแก้ปัญหานี้ เราจะใช้ สูตรเวียนเกิดของออยเลอร์ (Euler's recurrence formula) สำหรับจำนวน n จำนวนวิธีทั้งหมดที่มันสามารถสร้างได้ p(n) คือ:

Σₙ₌₀^∞ p(n)xⁿ = Πₖ₌₁^∞ (1/(1-xᵏ))

ใช้สูตรนี้ เราจะได้สูตรสำหรับ p(n):

p(n) = p(n-1) + p(n-2) - p(n-5) - p(n-7) + ... + (-1)ᵏ⁻¹ * (k(3k-1))/2

โปรแกรมแสดงการนำโซลูชันของเราไปใช้

#include <bits/stdc++.h>
using namespace std;

long long postiveSum(int n) {
    vector 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 << "The number of ways " << N << " can be written as sum of two or more positive numbers is "
         << postiveSum(N);
    return 0;
}

ผลลัพธ์

The number of ways 12 can be written as sum of two or more positive numbers is 77