ধনাত্মক সংখ্যার একটি অ্যারে দেওয়া হয়েছে৷ প্রতিটি উপাদান অ্যারের শেষ পর্যন্ত পৌঁছানোর জন্য সেই সূচক থেকে সর্বোচ্চ সংখ্যক লাফের প্রতিনিধিত্ব করে। লক্ষ্য হল শেষ পর্যন্ত পৌঁছানোর জন্য সেই উপাদান থেকে কত লাফ দেওয়া যায় তা খুঁজে বের করা। যদি arr[] হয় [ 1,2,3 ] তাহলে 1টি লাফের জন্য 1 হতে পারে, 2টি লাফের জন্য 1 বা 2 এবং 3টি লাফের জন্য 1, 2 বা 3 হতে পারে৷
উদাহরণস্বরূপ
ইনপুট
arr[] = {1,2,3} আউটপুট
Count of number of ways to jump to reach end are: 1 1 0
ব্যাখ্যা
For 1 we have jumps : 1, For 2 we have jumps 1 or 2, to reach the end we need just one jump of 1. For 3 we have jumps 1,2 or 3, as at its end we need no jumps.
ইনপুট
arr[] = {4,3,6,2} আউটপুট
Count of number of ways to jump to reach end are: 4 2 1 0
ব্যাখ্যা
For 4 we have jumps : 1, 2, 3 or 4. To reach the end we need only 1,2 or 3. Ways will be 4−3−6−2, 4−6−2, 4−2, 4−3−2. Total 4. For 3 we have jumps 1, 2 or 3 to reach the end we need both. Ways will be 3−6−2, 3−2. Total 2. For 6 we have jumps 1 to 5, to reach the end we need 1. Ways will be 6−2. Total 1. For 2 we have jumps 1or 2, as at its end we need no jumps.
নিম্নলিখিত প্রোগ্রামে ব্যবহৃত পদ্ধতি −
প্রতিটি উপাদান arr[i] এর জন্য এই পদ্ধতিতে আমরা এগিয়ে থাকা সমস্ত উপাদানগুলির জন্য অ্যারের শেষ পর্যন্ত পৌঁছানোর উপায়গুলির সংখ্যা যোগ করব যা arr[i] এবং বর্তমান উপাদান থেকে পৌঁছানো যায়। arr[i] এর উপায়গুলির জন্য এই গণনায় 1 যোগ করুন যদি আমরা সরাসরি arr[i] থেকে এক লাফে শেষ পর্যন্ত পৌঁছাতে পারি।
-
একটি পূর্ণসংখ্যা অ্যারে arr[] নিন।
-
ফাংশন পৌঁছানোর_এন্ড(int arr[], int size) একটি অ্যারে নেয় এবং প্রান্তে পৌঁছাতে লাফানোর উপায়ের সংখ্যা ফেরত দেয়।
-
arr[]-এর প্রতিটি উপাদান থেকে শেষ পর্যন্ত পৌঁছানোর উপায়গুলি সঞ্চয় করতে অ্যারে arr_2[] নিন।
-
memset(arr_2, 0, sizeof(arr_2)) ব্যবহার করে 0 দিয়ে পুরো arr_2[] শুরু করুন।
-
ট্রাভার্স arr[] i=size-2 থেকে i=0 পর্যন্ত লুপ ব্যবহার করে, কারণ শেষ উপাদানটি বিবেচনা করা হবে না।
-
temp =আকার − i − 1 নিন। যদি temp> =arr[i] হয় তবে আমরা সরাসরি একটি লাফ দিয়ে শেষ পর্যন্ত পৌঁছাতে পারি। arr_2[i]++ ব্যবহার করে arr[i] এর জন্য বৃদ্ধির উপায় গণনা করে।
-
এখন অন্যান্য সমস্ত উপাদানের জন্য যা শেষ পর্যন্ত পৌঁছাতে পারে এবং যেখানে আমরা arr[i] থেকে পৌঁছাতে পারি, arr_2[i]-এ অনেক উপায় যোগ করুন।
-
উপরের ট্রাভার্সের জন্য j=i+1 থেকে j
-
যদি এখনও arr_2[i] 0 থাকে তবে এটিকে −1 এ সেট করুন, যার মানে এটি শেষ পর্যন্ত পৌঁছাতে পারে না।
-
সমস্ত লুপের শেষে আমাদের থাকবে arr_2[] এর প্রতিটি উপাদানের জন্য শেষ পর্যন্ত পৌঁছানোর উপায় থাকবে।
-
ফলস্বরূপ লুপ ব্যবহার করে arr_2 প্রিন্ট করুন।
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
void reach_end(int arr[], int size){
int arr_2[size];
memset(arr_2, 0, sizeof(arr_2));
for (int i = size−2; i >= 0; i−−){
int temp = size − i − 1;
if (arr[i] >= temp){
arr_2[i]++;
}
for (int j = i+1; j < size−1 && j <= arr[i] + i; j++){
if (arr_2[j] != −1){
arr_2[i] = arr_2[i] + arr_2[j];
}
}
if(arr_2[i] == 0){
arr_2[i] = −1;
}
}
cout<<"Count of number of ways to jump to reach end are: ";
for (int i=0; i < size; i++){
cout<<arr_2[i] << " ";
}
}
int main(){
int arr[] = {2, 3, 7, 1, 8, 9};
int size = sizeof(arr) / sizeof(arr[0]);
reach_end(arr, size);
return 0;
} আউটপুট
যদি আমরা উপরের কোডটি চালাই তবে এটি নিম্নলিখিত আউটপুট −
উৎপন্ন করবেCount of number of ways to jump to reach end are: 8 5 3 1 1 0
