मान लीजिए कि हम एक अनोखा खेल खेल रहे हैं और हमारे पास तीन मान n, k, और h हैं। हम 0 अंक से शुरू करते हैं, फिर हम 1 और एच (समावेशी) के बीच यादृच्छिक रूप से एक संख्या का चयन कर सकते हैं और हमें कई अंक मिलेंगे। जब हम न्यूनतम k अंक प्राप्त कर लेते हैं तो हम रुक जाते हैं। हमें n या उससे कम अंक मिलने की प्रायिकता ज्ञात करनी है। यहां किसी भी संख्या को यादृच्छिक रूप से चुना जा सकता है और सभी परिणामों की संभावना समान होती है।
इसलिए, यदि इनपुट n =2, k =2, h =10 जैसा है, तो आउटपुट 0.11 होगा।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
एक फ़ंक्शन को परिभाषित करें dp() । यह रास्ता अपनाएगा।
-
यदि पथ k − 1 के समान है, तो
-
वापसी (न्यूनतम n - k + 1 और h) / h
-
-
यदि पथ> n, तो
-
वापसी 0
-
-
यदि पथ>=k, तो
-
वापसी 1
-
-
वापसी डीपी (पथ + 1) - (डीपी (पथ + एच + 1) - डीपी (पथ + 1)) / एच
-
-
मुख्य कार्य से, निम्न कार्य करें -
-
अगर k शून्य है, तो
-
वापसी 1
-
-
यदि n
-
वापसी 0
-
-
वापसी डीपी(0)
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
class Solution: def solve(self, n, k, h): if not k: return 1 if n < k: return 0 def dp(path): if path == k− 1: return min((n− k + 1), h) / h if path > n: return 0 if path >= k: return 1 return dp(path + 1)− (dp(path + h + 1)− dp(path + 1)) / h return dp(0) ob = Solution() print(ob.solve(2,2,10))
इनपुट
2,2,10
आउटपुट
0.11