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

C++ में नया 21 गेम


मान लीजिए रीमा निम्नलिखित गेम खेलती है, जो कार्ड गेम "21" पर आधारित है। तो रीमा 0 अंकों से शुरू करती है, और जब तक उसके पास K से कम अंक हैं, तब तक संख्याएं निकालती है। अब, प्रत्येक ड्रॉ के दौरान, वह [1, W] रेंज से यादृच्छिक रूप से एक पूर्णांक संख्या में अंक प्राप्त करती है, जहां W दिया गया है, और यह एक पूर्णांक है। अब प्रत्येक ड्रॉ स्वतंत्र है और परिणामों की समान संभावनाएं हैं। रीमा संख्याएं निकालना बंद कर देती है जब उसे K या अधिक अंक मिलते हैं। हमें यह पता लगाना है कि उसके N या कम अंक होने की संभावना क्या है?

तो यदि N = 6, K 1 है और W 10 है, तो उत्तर 0.6 होगा, क्योंकि रीमा को एक कार्ड मिलता है, फिर रुक जाती है, 10 संभावनाओं में से 6 में, वह N = 6 अंकों पर या उससे नीचे है।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

  • यदि k 0 है, या N >= K + W है, तो 1 लौटाएं
  • आकार N + 1 की एक सरणी dp बनाएं, dp[0] := 1 सेट करें
  • wsum := 1.0, ret := 0.0 सेट करें
  • i को 1 से N की रेंज में
    • dp[i] := wsum / W
    • यदि i < K, तो wsum := wsum + dp[i], अन्यथा ret := ret + dp[i]
    • यदि i - W >= 0, तो wsum := wsum - dp[i - W]
  • ret लौटाएं

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

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

class Solution {
public:
    double new21Game(int N, int K, int W) {
        if(K == 0 || N >= K + W) return 1.0;
        vector <double> dp (N + 1);
        dp[0] = 1;
        double Wsum = 1.0;
        double ret = 0.0;
        for(int i = 1; i <= N; i++){
            dp[i] = Wsum / W;
            if(i < K){
                Wsum += dp[i];
            }else ret += dp[i];
            if(i - W >= 0) Wsum -= dp[i - W];
        }
        return ret;
    }
};

main(){
    Solution ob;
    cout << (ob.new21Game(6, 1, 10));
}

इनपुट

6 1 10

आउटपुट

0.6

  1. C++ में जंप गेम IV C++ में जंप गेम IV

    मान लीजिए हमारे पास arr नामक पूर्णांकों की एक सरणी है। हम प्रारंभ में इंडेक्स 0 पर हैं। एक चरण में हम इंडेक्स i से i + x पर कूद सकते हैं जहां: i + x = 0, j जहां: arr[i] और arr[j] समान हैं और i और j समान नहीं हैं। यहां n सरणी का आकार है। हमें सरणी के अंतिम इंडेक्स तक पहुंचने के लिए न्यूनतम चरणों की स

  1. C++ में जंप गेम V C++ में जंप गेम V

    मान लीजिए हमारे पास arr नामक पूर्णांकों की एक सरणी और एक पूर्णांक d है। एक चरण में हम इंडेक्स i से कूद सकते हैं: i + x जहां: i + x < n और x की सीमा 1 से d है। = 0 और x की सीमा 1 से d है। arr[k] हो। हम सरणी के किसी भी इंडेक्स से कूदना शुरू कर सकते हैं। हमें अधिकतम इंडेक्स की संख्या ज्ञात करनी है ज

  1. - C++ में new और delete ऑपरेटर्स

    new ऑपरेटर हीप में मेमोरी आवंटन का अनुरोध करता है। यदि पर्याप्त मेमोरी उपलब्ध है, तो पॉइंटर वेरिएबल को आरंभ करके उसका पता लौटाता है। सिंटैक्स pointer_variable = new datatype; आरंभीकरण के साथ pointer_variable = new datatype(value); ब्लॉक आवंटन (ऐरे) pointer_variable = new datatype[size]; उदाहरण