C-Programm, um die Mindestanzahl an Sprüngen zu ermitteln, um das Ende zu erreichen

Gegeben ist ein Array nicht negativer Ganzzahlen, das die maximale Anzahl darstellt Schritte, die von diesem Element aus vorangetrieben werden können. Der Zeiger befindet sich zunächst am ersten Index [0 Index] des Arrays. Ihr Ziel ist es, das Ende zu erreichen Der Index im Array in der minimalen Anzahl von Schritten. wenn nicht erreichbar Ende des Arrays und geben Sie dann die größte Ganzzahl aus.

Der naive Ansatz besteht darin, mit der anfänglichen {Haupt}-Komponente zu beginnen und alle Komponenten, auf die vom ersten Element aus zugegriffen werden kann, rekursiv aufzurufen. Die minimale Sprungweite vom ersten bis zum Ende wird anhand der minimalen Sprungweite berechnet, die erforderlich ist, um vom ersten zugänglichen Element aus das Ende zu erreichen.

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

Hier verwenden wir den Top-Down-Ansatz der dynamischen Programmierung. Wir werden Hashmap verwenden, um Teilproblemergebnisse zu speichern. Wenn wir eine Lösung erstellen, prüfen wir zunächst, ob das Teilproblem gelöst wurde, und verwenden es gegebenenfalls.

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

Erklärung

Das erste Element ist 1, daher kann es nur bis 2 gehen. Das zweite Element ist 2, Sie können also bis zu 2 Schritte gehen, z. B. 4 oder 1. von 1 bis 4 erreichen, und Und so weiter.

Komplexität dynamischer Programmiermethoden zum Finden von Mindestzahlen Die Anzahl der Sprünge, um das Ende des Arrays zu erreichen, beträgt O(n^2) und die Raumkomplexität ist O(n)

Beispiel

Echtzeitdemonstration

#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;
}

Ausgabe

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

Das obige ist der detaillierte Inhalt vonC-Programm, um die Mindestanzahl an Sprüngen zu ermitteln, um das Ende zu erreichen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!