Programme C pour trouver le nombre minimum de sauts pour arriver à la fin

Étant donné un tableau d'entiers non négatifs, représentant le nombre maximum Mesures qui peuvent être prises à partir de cet élément. Le pointeur est initialement situé au premier index [index 0] du tableau. Votre objectif est d'atteindre la fin L'index dans le tableau en un nombre minimum d'étapes. si inaccessible fin du tableau, puis imprime le plus grand entier.

L'approche naïve consiste à commencer par le composant {main} initial et à appeler récursivement tous les composants accessibles à partir du premier élément. La portée minimale de saut du premier à la fin est calculée en utilisant la portée minimale de saut requise pour atteindre la fin à partir du premier élément accessible.

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

Ici, nous utiliserons une approche de programmation dynamique descendante. Nous utiliserons Hashmap pour stocker les résultats des sous-problèmes et chaque fois que nous créerons une solution, vérifiez d'abord si le sous-problème a été résolu et si c'est le cas, utilisez-le.

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

Explication

Le premier élément est 1, il ne peut donc aller qu'à 2. Le deuxième élément est 2, vous pouvez donc monter jusqu'à 2 étapes, par exemple jusqu'à 4 ou 1. de la portée 1 à 4, et Et ainsi de suite.

Complexité des méthodes de programmation dynamique pour trouver des nombres minimaux Le nombre de sauts pour atteindre la fin du tableau est O(n^2), et la complexité spatiale est O(n)

Exemple

Démonstration en temps réel

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

Sortie

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

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!