শেষ পর্যন্ত পৌঁছানোর জন্য ন্যূনতম সংখ্যক লাফের জন্য সি প্রোগ্রাম

আমাদের দেওয়া হল, অ-ঋণাত্মক পূর্ণসংখ্যার একটি অ্যারে যা সেই উপাদান থেকে সর্বোচ্চ সংখ্যক ধাপকে নির্দেশ করে। পয়েন্টারটি প্রাথমিকভাবে অ্যারের প্রথম সূচক [0 সূচক] এ অবস্থিত। আপনার লক্ষ্য হল ন্যূনতম সংখ্যক ধাপে অ্যারের শেষ সূচকে পৌঁছানো। যদি অ্যারের শেষ পর্যন্ত পৌঁছানো সম্ভব না হয় তাহলে সর্বোচ্চ পূর্ণসংখ্যা মুদ্রণ করুন।

নিষ্পাপ পদ্ধতি প্রারম্ভিক{প্রাথমিক} উপাদান থেকে শুরু করতে হবে এবং প্রথম উপাদান থেকে অ্যাক্সেসযোগ্য সমস্ত উপাদানের জন্য পুনরাবৃত্তিমূলকভাবে কল করতে হবে। প্রথম থেকে শেষ পর্যন্ত পৌঁছানোর জন্য লাফের ন্যূনতম পরিসর গণনা করা হয় প্রথম থেকে অ্যাক্সেসযোগ্য উপাদানগুলি থেকে শেষ অর্জনের জন্য লাফের ন্যূনতম পরিসর ব্যবহার করে।

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

এখানে আমরা ডায়নামিক প্রোগ্রামিং এর টপ-ডাউন পদ্ধতি ব্যবহার করব। আমরা সাব-প্রবলেম ফলাফল সংরক্ষণ করতে হ্যাশম্যাপ ব্যবহার করব এবং যখনই আমরা একটি সমাধান তৈরি করব, প্রথমে উপসমস্যাটি ইতিমধ্যে সমাধান করা হয়েছে কিনা তা পরীক্ষা করুন, যদি হ্যাঁ হয় তবে এটি ব্যবহার করুন।

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

ব্যাখ্যা

প্রথম উপাদানটি হল 1, তাই এটি শুধুমাত্র 2-এ যেতে পারে৷ দ্বিতীয় উপাদানটি হল 2, তাই সর্বাধিক 2টি ধাপ করতে পারে যেমন 4 বা 1 পর্যন্ত৷ এটি 4-এ যায় যেখান থেকে এটি 1 এবং আরও অনেক কিছুতে পৌঁছায়৷

একটি অ্যারের শেষ পর্যন্ত পৌঁছানোর জন্য ন্যূনতম সংখ্যক জাম্প খুঁজে বের করার জন্য গতিশীল প্রোগ্রামিং পদ্ধতির জটিলতা হল O(n^2) এবং O(n)

উদাহরণ

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

আউটপুট

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