Program C untuk mencari bilangan lompatan minimum untuk mencapai penghujung

Diberi tatasusunan integer bukan negatif, mewakili nombor maksimum Langkah-langkah yang boleh diambil ke hadapan daripada elemen ini. Penunjuk pada mulanya terletak pada indeks pertama [indeks 0] tatasusunan. Matlamat anda adalah untuk mencapai penghujung Indeks ke dalam tatasusunan dalam bilangan langkah minimum. jika tidak dapat dihubungi hujung tatasusunan, kemudian cetak integer terbesar.

Pendekatan naif ialah bermula dengan komponen {utama} awal dan secara rekursif memanggil semua komponen yang boleh diakses daripada elemen pertama. Julat lompatan minimum dari yang pertama hingga akhir dikira menggunakan julat lompat minimum yang diperlukan untuk mencapai penghujung dari elemen pertama yang boleh diakses.

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

Di sini kita akan menggunakan pendekatan pengaturcaraan dinamik atas ke bawah. Kami akan menggunakan Hashmap untuk menyimpan hasil sub-masalah dan setiap kali kami mencipta penyelesaian, semak dahulu sama ada sub-masalah telah diselesaikan dan jika ya kemudian gunakannya.

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

Penjelasan

Elemen pertama ialah 1, jadi ia hanya boleh pergi ke 2. Elemen kedua ialah 2, jadi anda boleh naik ke 2 langkah, mis. daripada mencapai 1 hingga 4, dan Dan seterusnya.

Kerumitan kaedah pengaturcaraan dinamik untuk mencari nombor minimum Bilangan lompatan untuk mencapai penghujung tatasusunan ialah O(n^2), dan kerumitan ruang ialah O(n)

Contoh

Demonstrasi masa nyata

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

Output

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

Atas ialah kandungan terperinci Program C untuk mencari bilangan lompatan minimum untuk mencapai penghujung. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!