C++で異なる値を持つ連続した要素を持つ配列の数

入力として3つの変数size、max_val、last_elementが与えられます。目標は、サイズ要素があり、1からmax_valまでの要素があり、最初の要素が常に1で、最後の要素が常にmax_valになるような方法で形成できるさまざまな配列の数を見つけることです。また、2つの連続する要素が同じでないことを確認してください。

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

例

入力- サイズ=5、max_val =3、last_element =3

出力- 値が異なる連続した要素を持つ配列の数は次のとおりです。5

説明- 配列は次のようになります：-

[1、2、3、1、3]、[1、2、3、2、3]、[1、2、1、2、3]、[1、3、1、2、3]、[1 、3、2、1、3]。

入力- サイズ=3max_val =2 last_element =2

出力- 異なる値を持つ連続した要素を持つ配列の数は次のとおりです：0

説明- 3つの要素で配列を作成することはできません。また、[1、_、2]を連続する要素として使用することはできません。これは、中央の要素の1または2以外は埋めることができず、連続する異なる要素の条件に違反するためです。

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

• このアプローチでは、動的計画法と組み合わせ論を使用して、そのような配列数を見つけます。
• 最初と最後の要素は1とlast_elementとして固定されます。どのサイズの配列でも、それを埋める方法はサイズ2の要素のみです。
• サイズ2の場所に入力する[1からmax_val]要素を入力する場合。ウェイはway（max_val）=Ways（size）/（max_val-1）になります
• 1からiの範囲ごとに、wayはways（i）=Ways（size）/（max_val-1）[ways（size）=最後の要素に2からmax_valまでの数値を入力できるウェイの数）になります。
• last_elementが1の場合、最後の要素は1のみであるため、wayはways（size-1）になります。
• 最後から2番目の要素は常に1からmax_valの間にすることができます。
• 最後から2番目の要素が1でない場合、ウェイは（max_val-2）* Ways（i-1）になります。これは、arr _iを1またはarr_i-1>
• 最後から2番目の要素が1の場合、wayは（max_val-1）* Ways（i-1）as arr _i-1 は1で、arr _i-2 1ではありません。
• Ways（i）は次のようになります:-( max_val-2）* Ways（i-2）+（max_val-2）* Ways（i-1）
• 変数size、max_val、last_elementを入力として受け取ります。
• 関数diff_val（int size、int max_val、int last_element）はすべての入力を受け取り、異なる値を持つ連続した要素を持つ配列の数を返します。
• 初期カウントを0とします。
• 配列を埋める方法の数を格納する配列arr[Max_N]={0}を取得します。 arr [0]を0で初期化し、arr[1]を1で初期化します。
• i=2からi
• temp_1 =（max_val-2）* arr[i-1]およびtemp_2=（max_val-1）* arr [i-2]
を取得します。
• arr [i] =temp_1+temp_2を設定します。
• last_element ==1の場合、count =（max_val-1）*arr[size-2]を設定します。
• それ以外の場合は、arr[size-1]を返します。
• 最後に結果としてカウントを返します。

例

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

int diff_val(int size, int max_val, int last_element) {
   int count = 0;
   int arr[Max_N] = {
      0
   };
   arr[0] = 0;
   arr[1] = 1;
   for (int i = 2; i < size; i++) {
      int temp_1 = (max_val - 2) * arr[i - 1];
      int temp_2 = (max_val - 1) * arr[i - 2];
      arr[i] = temp_1 + temp_2;
   }
   if (last_element == 1) {
      count = (max_val - 1) * arr[size - 2];
   } else {
      return arr[size - 1];
   }
   return count;
}
int main() {
   int size = 5;
   int max_val = 3;
   int last_element = 3;
   cout << "Count of arrays having consecutive element with different values are: " << diff_val(size, max_val, last_element);
   return 0;
}

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

出力

Count of arrays having consecutive element with different values are: 5