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

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

มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน

อินพุต

N = 4

ผลลัพธ์

5

คำอธิบาย

4 can be written as the sum in these ways,
4, 3+1, 2+2, 2+1+1, 1+1+1+1

เพื่อแก้ปัญหานี้ เราจะใช้สูตรการเกิดซ้ำของออยเลอร์ สำหรับจำนวน n จำนวนวิธีทั้งหมดที่สร้าง p(n) โดย,

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

เมื่อใช้สูตรนี้ เราจะได้สูตรสำหรับ p(n),p(n) =p(n-1) + p(n-2) - p(n-5) - p(n-7) + … + ( -1) ^(k-1) ((k(3k-1))/2)

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

ตัวอย่าง

#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<<"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