終端に到達するための最小ホップ数を見つけるための C プログラム

最大数を表す、負ではない整数の配列が与えられる この要素から実行できる手順。ポインタは最初、配列の最初のインデックス [0 インデックス] に配置されます。あなたの目標は最後まで到達することです 最小ステップ数での配列へのインデックス。到達できない場合 配列の末尾を調べてから、最大の整数を出力します。

素朴なアプローチ は、最初の {main} コンポーネントから始めて、最初の要素からアクセスできるすべてのコンポーネントを再帰的に呼び出すことです。最初から最後までの最小ジャンプ範囲は、最初にアクセス可能な要素から最後に到達するために必要な最小ジャンプ範囲を使用して計算されます。

minJumps(start, end) = Min ( minJumps(k, end) )
for all k accessible from the start

ここでは、トップダウンの動的プログラミング アプローチを使用します。ハッシュマップを使用して部分問題の結果を保存し、解決策を作成するたびに、最初に部分問題が解決されているかどうかを確認し、解決されている場合はそれを使用します。

Input: { 1, 2, 4, 1, 2, 2, 1, 1, 3, 8 }
Output: Minimum number of steps = 6 {1-->2-->4-->1-->3-->8}

説明

最初の要素は 1 なので、2 までしか進むことができません。 2番目の要素は 2 なので、最大 2 ステップ、たとえば 4 または 1 に進むことができます。リーチ1からリーチ4まで、 などなど。

最小値を求める動的プログラミング手法の複雑さ 配列の最後に到達するまでのジャンプ数は O(n^2)、空間複雑度は O(n)です。

例

リアルタイム デモンストレーション

#include<stdio.h>
#include<limits.h>
int min_steps (int arr[], int n){
   int steps[n];
   int i, j;
   if (n == 0 || arr[0] == 0)
      return INT_MAX;
   steps[0] = 0;
   for (i = 1; i < n; i++){
      steps[i] = INT_MAX;
      for (j = 0; j < i; j++){
         if (i <= j + arr[j] && steps[j] != INT_MAX){
            steps[i] = (steps[i] < (steps[j] + 1)) ? steps[i] : steps[j] + 1;
            break;
         }
      }
   }
   return steps[n - 1];
}
int main (){
   int arr[100];
   int n;
   printf ("Enter size of the array:");
   scanf ("%d", &n);
   printf ("Enter elements in the array:");
   for (int i = 0; i < n; i++){
      scanf ("%d", &arr[i]);
   }
   printf ("Minimum number of steps : %d", min_steps (arr, n));
   return 0;
}

出力

Enter size of array : 7
Enter elements in the array :2 1 1 5 2 1 1
Minimum number of steps : 3

以上が終端に到達するための最小ホップ数を見つけるための C プログラムの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。