C ++
 Computer >> コンピューター >  >> プログラミング >> C ++

C++で2つ以上の正の整数の合計としてNを記述する方法


この問題では、整数nが与えられます。私たちの仕事は、2つ以上の正の整数の合計として表現できる方法の総数を見つけることです。

問題を理解するために例を見てみましょう

入力

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

  1. TwoSumIV-入力はC++のBSTです

    二分探索木と1つのターゲット値があるとします。合計が指定されたターゲットと等しくなるように、BSTに2つの要素が存在するかどうかを確認する必要があります。 したがって、入力が次のような場合 その場合、出力はTrueになります。 これを解決するには、次の手順に従います- 配列を定義するv 関数inorder()を定義します。これはルートになります ルートがnullの場合、- 戻る 順序なし(ルートの左側) ルートの値をvに挿入 順序なし(ルートの左側) 関数findnode()を定義します。これにはkがかかります n:=vのサ

  2. Pythonの2つの整数の合計

    2つの整数aとbがあるとします。私たちの仕事は、これら2つの整数の合計を見つけることです。 1つの制約は、+や-のような演算子は使用できないということです。したがって、a=5およびb=7の場合、結果は12になります。 これを解決するには、次の手順に従います- 解決には、ビット単位の論理演算子を使用します b =0の場合、aを返します それ以外の場合は、XOR bを指定して合計関数を再帰的に使用し、結果を1回左シフトした後にANDbを使用します 例(Python) 理解を深めるために、次の実装を見てみましょう- #include <iostream> using names