C++で数値を部分的に分割する方法の数を数える

正の数Nが与えられます。目標は、数Nを3つの部分に分割できる方法の数を数えることです。パーツは等しい場合と等しくない場合があります。 Nは範囲[1,5000]にあります。

これを行うには、数値の3つの部分に3つのforループを使用します。最も内側のループで、3つすべての合計がNに等しいことを確認します。trueの場合は、ウェイの数を増やします。

例を挙げて理解しましょう。

入力 − n =5

出力 − Nを3つの部分に分割する方法の数：2

説明 − 5は、（1,1,3）と（1,2,2）の合計として表示できます

入力 − n =9

出力 − Nを3つの部分に分割する方法の数：7

説明 − 9は、（1、1、7）、（1、2、6）、（1、3、5）、（1、4、4）、（2、2、5）、（ 2、3、4）および（3、3、3）。

以下のプログラムで使用されているアプローチは次のとおりです

• 1から5000までの値で初期化された整数Nを取ります。

• 関数divideN（int n）はnを取り、nを3つの部分に分割できる方法の数を返します。

• ウェイの数として、初期変数カウントを0とします。

• 番号の各部分に3つのforループを使用してトラバースします。

• 1 <=i

• i、j、kの合計がnに等しいかどうかを確認します。 trueの場合、カウントをインクリメントします。

• すべてのループの終わりに、カウントにはnを3つの部分に分割する方法の総数があります。

• 結果としてカウントを返します。

例

#include <bits/stdc++.h>
using namespace std;
int divideN(int n){
   int count = 0;
   for (int i = 1; i < n; i++){
      for (int j = i ; j < n; j++){
         for (int k = j; k < n; k++){
            int sum=i+j+k;
            if(sum==n)
               { count++; }
         }
      }
   }
   return count;
}
int main(){
   int N=500;
   cout <<endl<< "Number of ways to divide N in 3 parts : "<<divideN(N);
   return 0;
}

出力

上記のコードを実行すると、次の出力が生成されます-

Number of ways to divide N in 3 parts: 20833