Program PHP untuk Bilangan Minimum Lompatan untuk Mencapai Tamat

Apakah itu PHP?

PHP (Hypertext Preprocessor) ialah bahasa skrip bahagian pelayan yang digunakan secara meluas untuk pembangunan web. Ia membenarkan pembangun membenamkan kod dalam fail HTML, membolehkan penciptaan halaman web dinamik dan interaksi dengan pangkalan data. PHP terkenal dengan kesederhanaan, serba boleh dan keupayaan penyepaduan yang meluas dengan pangkalan data yang popular. Ia menawarkan rangkaian sambungan yang luas dan mempunyai komuniti pembangun yang besar, memastikan sumber dan sokongan yang mencukupi.

Program PHP untuk Jumlah lompatan minimum untuk mencapai penghujung

Kaedah 1: Pendekatan Rekursif Naif

Pendekatan rekursif naif ialah pendekatan algoritma asas di mana masalah diselesaikan dengan memecahkannya secara rekursif kepada submasalah yang lebih kecil. Dalam konteks mencari bilangan lompatan minimum untuk mencapai penghujung tatasusunan, pendekatan rekursif naif melibatkan penerokaan secara rekursif semua laluan yang mungkin dari setiap kedudukan dan memilih bilangan lompatan minimum.

Contoh

<?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.";
}
?>

Output

Minimum number of jumps required to reach the end: 3

Kaedah 2: Pengaturcaraan Dinamik

Pengaturcaraan dinamik ialah teknik yang digunakan dalam pengaturcaraan komputer untuk menyelesaikan masalah yang kompleks dengan memecahkannya kepada submasalah yang bertindih dan menyelesaikan setiap submasalah sekali sahaja. Ia menyimpan penyelesaian submasalah dalam jadual atau tatasusunan, membolehkan carian cekap dan penggunaan semula hasil yang dikira sebelum ini. Pendekatan ini membantu mengelakkan pengiraan berlebihan dan meningkatkan kecekapan keseluruhan algoritma.

Contoh

<?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.";
}
?>

Output

Minimum number of jumps required to reach the end: 3

Kesimpulan

Kesimpulannya, program PHP untuk mencari bilangan lompatan minimum untuk mencapai penghujung tatasusunan boleh dilaksanakan menggunakan pelbagai pendekatan. Pendekatan rekursif naif meneroka semua laluan yang mungkin, tetapi ia mengalami kerumitan masa eksponen dan tidak cekap untuk tatasusunan besar. Pendekatan pengaturcaraan dinamik, sebaliknya, mengoptimumkan penyelesaian dengan memecahkan masalah kepada submasalah yang bertindih dan menyimpan penyelesaian dalam tatasusunan. Pendekatan ini menghapuskan pengiraan berlebihan dan meningkatkan kecekapan algoritma dengan ketara, menjadikannya sesuai untuk tatasusunan yang lebih besar. Dengan memanfaatkan teknik pengaturcaraan dinamik, program PHP boleh menentukan bilangan lompatan minimum yang diperlukan untuk mencapai penghujung tatasusunan dengan cekap.

Atas ialah kandungan terperinci Program PHP untuk Bilangan Minimum Lompatan untuk Mencapai Tamat. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!