C++で最後までジャンプする方法の数を数える

例

入力

arr[] = {1,2,3}

出力

Count of number of ways to jump to reach end are: 1 1 0

説明

For 1 we have jumps : 1,
For 2 we have jumps 1 or 2, to reach the end we need just one jump of 1.
For 3 we have jumps 1,2 or 3, as at its end we need no jumps.

入力

arr[] = {4,3,6,2}

出力

Count of number of ways to jump to reach end are: 4 2 1 0

説明

For 4 we have jumps : 1, 2, 3 or 4. To reach the end we need only 1,2 or
3. Ways will be 4−3−6−2, 4−6−2, 4−2, 4−3−2. Total 4. For 3 we have jumps 1, 2 or 3 to reach the end we need both. Ways will be 3−6−2, 3−2. Total 2. For 6 we have jumps 1 to 5, to reach the end we need 1. Ways will be 6−2. Total 1.
For 2 we have jumps 1or 2, as at its end we need no jumps.

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

各要素arr[i]に対するこのアプローチでは、arr [i]の前にあり、現在の要素から到達可能なすべての要素について、配列の最後に到達する方法の数を追加します。 1回のジャンプでarr[i]から直接到達して終了できる場合は、このカウントにarr[i]の方法に1を追加します。

• 整数配列arr[]を取ります。

• 関数reach_end（int arr []、int size）は配列を受け取り、最後に到達するためにジャンプする方法の数を返します。

• 配列arr_2[]を使用して、arr[]の各要素から最後に到達する方法を格納します。

• memset（arr_2、0、sizeof（arr_2））を使用してarr_2[]全体を0で初期化します。

• 最後の要素は考慮されないため、i=size-2からi=0までのforループを使用してarr[]をトラバースします。

• temp =size − i −1を取ります。temp> =arr [i]の場合、1回のジャンプで直接最後に到達できます。増分方法は、arr_2[i]++を使用してarr[i]をカウントします。

• ここで、最後まで到達でき、arr [i]から到達できる他のすべての要素について、arr_2[i]にウェイの数を追加します。

• 上記のトラバースでは、j =i+1からj

• それでもarr_2[i]が0の場合は、-1に設定します。これは、最後まで到達できないことを意味します。

• すべてのループの終わりに、arr[]の各要素の終わりに到達する方法を持つarr_2[]があります。

• 結果としてforループを使用してarr_2を出力します。

例

#include <bits/stdc++.h>
using namespace std;
void reach_end(int arr[], int size){
   int arr_2[size];
   memset(arr_2, 0, sizeof(arr_2));
   for (int i = size−2; i >= 0; i−−){
      int temp = size − i − 1;
      if (arr[i] >= temp){
         arr_2[i]++;
      }
      for (int j = i+1; j < size−1 && j <= arr[i] + i; j++){
         if (arr_2[j] != −1){
            arr_2[i] = arr_2[i] + arr_2[j];
         }
      }
      if(arr_2[i] == 0){
         arr_2[i] = −1;
      }
   }
   cout<<"Count of number of ways to jump to reach end are: ";
   for (int i=0; i < size; i++){
      cout<<arr_2[i] << " ";
   }
}
int main(){
   int arr[] = {2, 3, 7, 1, 8, 9};
   int size = sizeof(arr) / sizeof(arr[0]);
   reach_end(arr, size);
   return 0;
}

出力

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

Count of number of ways to jump to reach end are: 8 5 3 1 1 0