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

C++ में वजन के साथ यादृच्छिक चयन


मान लीजिए हमारे पास धनात्मक पूर्णांकों की एक सरणी w है, जहां w[i] इंडेक्स i का वजन दर्शाता है, हमें एक फ़ंक्शन pickIndex() परिभाषित करना है जो उसके वजन के अनुपात में यादृच्छिक रूप से एक इंडेक्स चुनता है।

इसलिए यदि इनपुट [1,3] है, pickIndex() को पांच बार कॉल करें, तो उत्तर आ सकता है: 0, 1, 1, 1, 0।

हल का दृष्टिकोण

इसे हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे:

  • एक सरणी v परिभाषित करें,
  • आरंभकर्ता के माध्यम से, निम्नानुसार आरंभ करें:
    • n := w[0]
    • i = 1 से w का आकार तक:
      • w[i] := w[i] + w[i-1]
      • n := w[i]
    • v = w
  • pickIndex() निम्नानुसार काम करेगा:
    • एक यादृच्छिक संख्या r लें, r mod v के अंतिम तत्व का प्रदर्शन करें
    • v से r से छोटी नहीं सबसे छोटी संख्या लें, फिर v के पहले तत्व को तत्व से घटाएं और लौटाएं।

उदाहरण

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

class Solution { 
public: 
    int n; 
    vector<int> v; 
    Solution(vector<int>& w) { 
        srand(time(NULL)); 
        n = w[0]; 
        for(int i = 1; i < w.size(); i++){ 
            w[i] += w[i - 1]; 
            n = w[i]; 
        } 
        v = w; 
    } 
    int pickIndex() { 
        return upper_bound(v.begin(), v.end(), rand() % v.back()) - v.begin(); 
    } 
}; 

int main(){ 
    vector<int> v = {1,3}; 
    Solution ob(v); 
    cout << (ob.pickIndex()) << endl; 
    cout << (ob.pickIndex()) << endl; 
    cout << (ob.pickIndex()) << endl; 
    cout << (ob.pickIndex()) << endl; 
    cout << (ob.pickIndex()) << endl; 
}

इनपुट

[1, 3] से आरंभ करें और pickIndex को पांच बार कॉल करें

आउटपुट

1 1 1 1 0

  1. C++ में रैंडम पॉइंटर के साथ लिस्ट कॉपी करें C++ में रैंडम पॉइंटर के साथ लिस्ट कॉपी करें

    लिंक्ड लिस्ट एक रैखिक डेटा संरचना है जिसमें प्रत्येक नोड के दो ब्लॉक होते हैं जैसे कि एक ब्लॉक में नोड का मान या डेटा होता है और दूसरा ब्लॉक अगले फील्ड का पता रखता है। मान लीजिए हमारे पास एक लिंक्ड लिस्ट है जैसे कि प्रत्येक नोड में एक रैंडम पॉइंटर होता है जो लिस्ट में अन्य नोड्स की ओर इंगित करता है।

  1. C++ में उदाहरण के साथ एक्सप्रेशन ट्री C++ में उदाहरण के साथ एक्सप्रेशन ट्री

    एक एक्सप्रेशन ट्री एक विशेष प्रकार का बाइनरी ट्री है जिसमें ट्री का प्रत्येक नोड या तो एक ऑपरेटर या ऑपरेंड से बना होता है। लीफ नोड्स ट्री के एक ऑपरेंड को दर्शाते हैं। नॉन-लीफ नोड्स ट्री के एक ऑपरेटर को दर्शाते हैं। उदाहरण: इनफिक्स एक्सप्रेशन प्राप्त करने के लिए जिसे आसानी से हल किया जा सकता है, हम

  1. C++ में 3n स्लाइस वाली पिज्जा C++ में 3n स्लाइस वाली पिज्जा

    समस्या विवरण मान लीजिए 3n स्लाइस वाली एक पिज्जा है जिसके स्लाइस विभिन्न आकार के हैं। मैं और मेरे दो दोस्त पिज्जा के स्लाइस निम्नानुसार लेंगे: मैं कोई भी पिज्जा स्लाइस चुनूंगा। मेरा दोस्त अमल मेरे चुने हुए स्लाइस के एंटी-क्लॉकवाइज दिशा में अगला स्लाइस लेगा। मेरा दोस्त बिमल मेरे चुने हुए स्लाइस के क