C++ में अंत तक पहुंचने के लिए जंप के तरीकों की संख्या गिनें

समस्या विवरण

सकारात्मक संख्याओं की एक सरणी दी गई है। प्रत्येक तत्व उस इंडेक्स से सरणी के अंत तक पहुंचने के लिए किए जा सकने वाले अधिकतम जंप की संख्या दर्शाता है। लक्ष्य उस तत्व से अंत तक पहुंचने के लिए किए जा सकने वाले जंप की संख्या ज्ञात करना है। यदि arr[] है [1,2,3] तो 1 के लिए जंप 1 हो सकते हैं, 2 के लिए जंप 1 या 2 हो सकते हैं और 3 के लिए जंप 1, 2 या 3 हो सकते हैं।

उदाहरण

इनपुट

arr[] = {1,2,3}

आउटपुट

अंत तक पहुंचने के जंप के तरीकों की संख्या: 1 1 0

व्याख्या

1 के लिए जंप: 1, 2 के लिए जंप 1 या 2, अंत तक पहुंचने के लिए सिर्फ 1 जंप चाहिए। 3 के लिए जंप 1,2 या 3, इसके अंत में किसी जंप की जरूरत नहीं।

इनपुट

arr[] = {4,3,6,2}

आउटपुट

अंत तक पहुंचने के जंप के तरीकों की संख्या: 4 2 1 0

व्याख्या

4 के लिए जंप: 1, 2, 3 या 4। अंत तक पहुंचने के लिए केवल 1,2 या 3 चाहिए। तरीके: 4-3-6-2, 4-6-2, 4-2, 4-3-2। कुल 4। 3 के लिए जंप 1, 2 या 3, अंत तक पहुंचने के लिए दोनों चाहिए। तरीके: 3-6-2, 3-2। कुल 2। 6 के लिए जंप 1 से 5, अंत तक पहुंचने के लिए 1 चाहिए। तरीके: 6-2। कुल 1। 2 के लिए जंप 1 या 2, इसके अंत में किसी जंप की जरूरत नहीं।

दृष्टिकोण

इस दृष्टिकोण में प्रत्येक तत्व arr[i] के लिए हम उन सभी तत्वों के अंत तक पहुंचने के तरीकों की गिनती जोड़ेंगे जो आगे arr[i] हैं और वर्तमान तत्व से पहुंच योग्य हैं। यदि हम arr[i] से सीधे एक जंप में अंत तक पहुंच सकते हैं तो इस गिनती में 1 जोड़ें।

एल्गोरिदम चरण

एक पूर्णांक सरणी arr[] लें।
फंक्शन reach_end(int arr[], int size) एक सरणी लेता है और अंत तक पहुंचने के जंप के तरीकों की संख्या लौटाता है।
सरणी arr_2[] लें arr[] के प्रत्येक तत्व से अंत तक पहुंचने के तरीकों को संग्रहीत करने के लिए।
memset(arr_2, 0, sizeof(arr_2)) का उपयोग करके पूरे arr_2[] को 0 से प्रारंभ करें।
for लूप का उपयोग करके i=size-2 से i=0 तक arr[] को पार करें, क्योंकि अंतिम तत्व पर विचार नहीं किया जाएगा।
temp = size - i - 1 लें। यदि temp >= arr[i] तो हम एक जंप का उपयोग करके सीधे अंत तक पहुंच सकते हैं। arr_2[i]++ का उपयोग करके arr[i] के लिए तरीकों की गिनती बढ़ाएं।
अब उन सभी अन्य तत्वों के लिए जो अंत तक पहुंच सकते हैं और जिन तक हम arr[i] से पहुंच सकते हैं, उनके तरीकों की गिनती arr_2[i] में जोड़ें।
उपरोक्त के लिए for लूप का उपयोग करके j=i+1 से j<size-1 और j<=arr[i]+i तक पार करें। यदि कोई arr[j] -1 नहीं है, तो इसे arr_2[i] में जोड़ें।
यदि अभी भी arr_2[i] 0 है तो इसे -1 पर सेट करें, जिसका अर्थ है कि यह अंत तक नहीं पहुंच सकता।
सभी लूप के अंत में हमारे पास arr_2[] होगा जिसमें arr[] के प्रत्येक तत्व के लिए अंत तक पहुंचने के तरीके होंगे।
for लूप का उपयोग करके arr_2 प्रिंट करें परिणाम के रूप में।

C++ कोड उदाहरण

#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 << "अंत तक पहुंचने के जंप के तरीकों की संख्या: ";
    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;
}

आउटपुट

अंत तक पहुंचने के जंप के तरीकों की संख्या: 8 5 3 1 1 0