Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में T सेकंड के बाद मेंढक की स्थिति

मान लीजिए हमारे पास n शीर्षों वाला एक अविकल्पित वृक्ष है। शीर्ष 1 से n तक संख्यांकित हैं। अब एक मेंढक शीर्ष 1 से कूदना शुरू करता है। मेंढक अपने वर्तमान शीर्ष से दूसरे अनदेखे शीर्ष पर कूद सकता है यदि वे आसन्न हैं, एक सेकंड में। मेंढक किसी देखे गए शीर्ष पर वापस नहीं कूद सकता। यदि मेंढक कई शीर्षों पर कूद सकता है तो वह उनमें से किसी एक पर यादृच्छिक रूप से कूदता है जहां संभावना समान होती है, अन्यथा जब मेंढक किसी अनदेखे शीर्ष पर नहीं कूद सकता तो वह उसी शीर्ष पर हमेशा के लिए कूदता रहता है।

वृक्ष को किनारों की सरणी के रूप में दिया गया है। हमें वह संभावना ज्ञात करनी है कि t सेकंड के बाद मेंढक शीर्ष target पर है।

यदि इनपुट है: n = 7, t = 2, target = 4 और वृक्ष है -

C++ में T सेकंड के बाद मेंढक की स्थिति

तो आउटपुट 0.1666 होगा, क्योंकि ग्राफ से: मेंढक शीर्ष 1 से शुरू होता है, 0.3333 संभावना के साथ 1 सेकंड के बाद शीर्ष 2 पर कूदता है और फिर 0.5 संभावना के साथ 2 सेकंड के बाद शीर्ष 4 पर कूदता है। इस प्रकार 2 सेकंड के बाद मेंढक के शीर्ष 4 पर होने की संभावना 0.3333 * 0.5 = 0.16665 है।

हल करने के चरण

  • ret := 1

  • एक सेट visited परिभाषित करें

  • एक फ़ंक्शन dfs() परिभाषित करें, जो node, start, किनारों की सूची g, time, t, एक स्टैक st लेगा

  • यदि node visited का सदस्य है, तो false वापस करें

  • node को visited में डालें

  • यदि node 1 के समान है, तो tt := time, ok := true, true वापस करें

  • g[node] के सभी आसन्न शीर्षों के लिए पुनरावृत्ति करें

  • मुख्य विधि से: ret := 1, ok := false, ग्राफ बनाएं, dfs कॉल करें, स्टैक से संभावना की गणना करें

  • यदि tt > t तो 0 वापस करें, यदि tt == t तो ret वापस करें, अन्यथा शर्तों के अनुसार 0 या ret वापस करें

उदाहरण

#include <bits/stdc++.h> 
using namespace std; 

class Solution { 
public: 
    double ret = 1; 
    bool ok; 
    set<int> visited; 
    int tt; 
    
    bool dfs(int node, int start, vector<int> g[], int time, int t, stack<int>& st) { 
        if (visited.count(node)) return false; 
        visited.insert(node); 
        if (node == 1) { 
            tt = time; 
            ok = true; 
            return true; 
        } 
        for (int i = 0; i < g[node].size(); i++) { 
            st.push(g[node][i]); 
            if (dfs(g[node][i], start, g, time + 1, t, st)) return true; 
            st.pop(); 
        } 
        return false; 
    } 
    
    double frogPosition(int n, vector<vector<int> >& edges, int t, int target) { 
        ret = 1; 
        ok = false; 
        vector<int> graph[n + 1]; 
        for (int i = 0; i < edges.size(); i++) { 
            graph[edges[i][0]].push_back(edges[i][1]); 
            graph[edges[i][1]].push_back(edges[i][0]); 
        } 
        stack<int> st; 
        dfs(target, target, graph, 0, t, st); 
        while (!st.empty()) { 
            int node = st.top(); 
            double sz = (double)graph[node].size(); 
            if (node != 1) sz--; 
            ret *= (1.0 / sz); 
            st.pop(); 
        } 
        if (tt > t) return 0; 
        if (tt == t) return ret; 
        if (tt < t && target == 1 && graph[target].size() >= 1) return 0; 
        return (tt < t && graph[target].size() > 1) ? 0 : ret; 
    } 
}; 

int main() { 
    Solution ob; 
    vector<vector<int>> v = {{1,2},{1,3},{1,7},{2,4},{2,6},{3,5}}; 
    cout << (ob.frogPosition(7, v, 2, 4)); 
    return 0; 
}

इनपुट

7, {{1,2},{1,3},{1,7},{2,4},{2,6},{3,5}}, 2, 4

आउटपुट

0.166667
  1. C++ में वृत्त पर विपरीत दिशा में खड़े व्यक्ति की स्थिति C++ में वृत्त पर विपरीत दिशा में खड़े व्यक्ति की स्थिति

    इस समस्या में, हमें दो पूर्णांक N और M दिए गए हैं। एक वृत्त है और N लोग उस पर खड़े हैं। M एक व्यक्ति की स्थिति को दर्शाता है। हमारा कार्य M के विपरीत व्यक्ति की स्थिति प्रिंट करना है। समस्या को समझने के लिए एक उदाहरण लेते हैं, इनपुट - N = 6, M = 3 आउटपुट - 6 व्याख्या - इस समस्या को हल करने के लिए,

  1. - C++ में सबस्ट्रिंग

    सबस्ट्रिंग एक स्ट्रिंग का हिस्सा है। C++ में सबस्ट्रिंग प्राप्त करने के लिए एक फ़ंक्शन substr() है। इस फ़ंक्शन में दो पैरामीटर्स होते हैं: pos और len। pos पैरामीटर सबस्ट्रिंग की शुरुआती पोजीशन निर्दिष्ट करता है और len सबस्ट्रिंग में कैरेक्टर्स की संख्या दर्शाता है। उदाहरण #include <iostream>

  1. - C++ प्रोग्राम में } के बाद सेमीकॉलन कब अनिवार्य है?

    यदि यह घोषणा का अंत है तो क्लोज ब्रेस के बाद एक सेमीकॉलन अनिवार्य है। ब्रेसेस के मामले में, उनका उपयोग क्लास, एनम, स्ट्रक्चर, और इनिशियलाइज़ेशन सिंटैक्स की घोषणाओं में किया जाता है। इनमें से प्रत्येक स्टेटमेंट के अंत में, हमें एक सेमीकॉलन लगाने की आवश्यकता होती है। उदाहरण के लिए: class X {}; // स्ट