এই সমস্যায় ধনাত্মক পূর্ণসংখ্যাগুলোর একটি তালিকা দেওয়া আছে। প্রতিটি পূর্ণসংখ্যা নির্দেশ করে বর্তমান উপাদান থেকে সর্বোচ্চ কতটি ধাপ নেওয়া যাবে। প্রথম উপাদান থেকে শুরু করে তালিকার শেষ উপাদানে পৌঁছাতে ন্যূনতম কতবার জাম্প দরকার তা বের করতে হবে।
ডাইনামিক প্রোগ্রামিং পদ্ধতিতে jumps অ্যারে সংজ্ঞায়িত করা হয় ন্যূনতম জাম্প সংখ্যা সংরক্ষণ করার জন্য। jumps[i]-এর মান নির্দেশ করে ০-তম ইন্ডেক্স থেকে i-তম ইন্ডেক্সে পৌঁছাতে ন্যূনতম কতবার জাম্প লাগবে।
ইনপুট এবং আউটপুট
ইনপুট: পূর্ণসংখ্যাগুলোর একটি তালিকা।
{1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9}
আউটপুট: শেষ অবস্থানে পৌঁছানোর ন্যূনতম জাম্প সংখ্যা। এটি ৩।
১ থেকে শুরু করে ৩-এ যান। তারপর ৩ মান জাম্প দিয়ে ৮-এ পৌঁছান। তারপর ৮ মান জাম্প দিয়ে শেষ উপাদানে পৌঁছান।
অ্যালগরিদম
minPossibleJump(list, n)
ইনপুট: সংখ্যা অ্যারে, অ্যারেতে উপাদান সংখ্যা।
আউটপুট: শেষে পৌঁছানোর জন্য প্রয়োজনীয় ন্যূনতম জাম্প সংখ্যা।
শুরু
n আকারের jump অ্যারে সংজ্ঞায়িত করুন
যদি n = 0 বা list[0] = 0 হয়, তবে
ফেরত দিন ∞
jump[0] := 0
i := 1 থেকে n পর্যন্ত, করুন
jumps[i] := ∞
j := 0 থেকে i পর্যন্ত, করুন
যদি i <= j + list[j] এবং jump[j] ≠ ∞ হয়, তবে
jump[i] := jump[i] এবং (jump[j] + 1) এর মধ্যে ন্যূনতম
লুপ ব্রেক করুন
끝난
끝난
jump[n-1] ফেরত দিন
শেষ
উদাহরণ (C++)
#include <iostream>
using namespace std;
int min(int x, int y) { return (x < y) ? x : y; }
int minPossibleJump(int list[], int n) {
int *jumps = new int[n];
if (n == 0 || list[0] == 0)
return INT_MAX;
jumps[0] = 0;
for (int i = 1; i < n; i++) {
jumps[i] = INT_MAX;
for (int j = 0; j < i; j++) {
if (i <= j + list[j] && jumps[j] != INT_MAX) {
jumps[i] = min(jumps[i], jumps[j] + 1);
break;
}
}
}
return jumps[n-1];
}
int main() {
int list[] = {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9};
int size = 11;
cout << "Minimum number of jumps to reach end is: " << minPossibleJump(list, size);
return 0;
}
আউটপুট
Minimum number of jumps to reach end is: 3
