Programme PHP pour un nombre minimum de sauts pour atteindre la fin

Qu'est-ce que PHP ?

PHP (Hypertext Preprocessor) est un langage de script côté serveur largement utilisé pour le développement Web. Il permet aux développeurs d'intégrer du code dans des fichiers HTML, permettant la création de pages Web dynamiques et d'interactions avec des bases de données. PHP est connu pour sa simplicité, sa polyvalence et ses capacités d'intégration étendues avec les bases de données populaires. Il propose une large gamme d'extensions et dispose d'une large communauté de développeurs, garantissant des ressources et un support suffisants.

Programme PHP pour un nombre minimum de sauts pour atteindre la fin

Méthode 1 : Approche récursive naïve

L'approche récursive naïve est une approche algorithmique de base dans laquelle un problème est résolu en le décomposant de manière récursive en sous-problèmes plus petits. Dans le contexte de la recherche du nombre minimum de sauts pour atteindre la fin d’un tableau, l’approche récursive naïve consiste à explorer récursivement tous les chemins possibles à partir de chaque position et à choisir le nombre minimum de sauts.

Exemple

<?php
function minJumpsRecursive($arr, $start, $end) {
   // Base case: If the starting index is the last index, no jumps are needed
   if ($start == $end) {
      return 0;
   }
   // If the current element is 0, it is not possible to make any further jumps
   if ($arr[$start] == 0) {
      return PHP_INT_MAX;
   }
 // Initialize the minimum number of jumps to a large value
   $minJumps = PHP_INT_MAX;
   // Try all possible jumps from the current position
   // and choose the one that requires the minimum number of jumps
   for ($i = $start + 1; $i <= $end && $i <= $start + $arr[$start]; $i++) {
      $jumps = minJumpsRecursive($arr, $i, $end);
      if ($jumps != PHP_INT_MAX && $jumps + 1 < $minJumps) {
         $minJumps = $jumps + 1;
      }
   }
   return $minJumps;
}
// Example usage:
$arr = [1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9];
$n = count($arr);
$minJumps = minJumpsRecursive($arr, 0, $n - 1);
if ($minJumps != PHP_INT_MAX) {
   echo "Minimum number of jumps required to reach the end: " . $minJumps;
} else {
   echo "It is not possible to reach the end.";
}
?>

Sortie

Minimum number of jumps required to reach the end: 3

Méthode 2 : Programmation dynamique

La programmation dynamique est une technique utilisée en programmation informatique pour résoudre des problèmes complexes en les décomposant en sous-problèmes qui se chevauchent et en résolvant chaque sous-problème une seule fois. Il stocke les solutions des sous-problèmes dans une table ou un tableau, permettant une recherche et une réutilisation efficaces des résultats précédemment calculés. Cette approche permet d'éviter les calculs redondants et d'améliorer l'efficacité globale de l'algorithme.

Exemple

<?php
function minJumpsDynamic($arr, $n) {
   // Create an array to store the minimum number of jumps needed
   $minJumps = array_fill(0, $n, PHP_INT_MAX);
   $minJumps[0] = 0; // Base case: No jumps needed to reach the first element
   // Calculate the minimum number of jumps for each position
   for ($i = 1; $i < $n; $i++) {
      for ($j = 0; $j < $i; $j++) {
         // Check if it is possible to reach position $i from position $j
         if ($j + $arr[$j] >= $i) {
            // Update the minimum number of jumps for position $i
            // by considering the minimum of the current jumps and jumps from position $j plus one
            $minJumps[$i] = min($minJumps[$i], $minJumps[$j] + 1);
         }
      }
   }
   // Return the minimum number of jumps needed to reach the end
   return $minJumps[$n - 1];
}
// Example usage:
$arr = [1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9];
$n = count($arr);
$minJumps = minJumpsDynamic($arr, $n);
if ($minJumps != PHP_INT_MAX) {
   echo "Minimum number of jumps required to reach the end: " . $minJumps;
} else {
   echo "It is not possible to reach the end.";
}
?>

Sortie

Minimum number of jumps required to reach the end: 3

Conclusion

En conclusion, le programme PHP permettant de trouver le nombre minimum de sauts pour atteindre la fin d'un tableau peut être implémenté selon différentes approches. L’approche récursive naïve explore tous les chemins possibles, mais elle souffre d’une complexité temporelle exponentielle et n’est pas efficace pour les grands tableaux. L’approche de programmation dynamique, quant à elle, optimise la solution en divisant le problème en sous-problèmes qui se chevauchent et en stockant les solutions dans un tableau. Cette approche élimine les calculs redondants et améliore considérablement l’efficacité de l’algorithme, le rendant ainsi adapté aux tableaux plus grands. En tirant parti des techniques de programmation dynamique, le programme PHP peut déterminer efficacement le nombre minimum de sauts requis pour atteindre la fin du tableau.

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!