पायथन में खेल में जीत की जांच करने का प्रोग्राम

मान लीजिए हम एक दो-खिलाड़ी खेल खेल रहे हैं जहां n संख्या में कंचे हैं और प्रत्येक दौर में, एक खिलाड़ी को एक धनात्मक वर्ग संख्या में कंचे लेने होंगे। यदि कोई खिलाड़ी उतने वर्ग संख्या में कंचे नहीं ले सकता, तो वह हार जाता है। इसलिए, दी गई संख्या n को देखते हुए, हमें यह पता लगाना है कि हम खेल जीत सकते हैं या नहीं। हम हमेशा पहला चाल चलते हैं और इष्टतम संख्या में कंचे चुनते हैं।

इसलिए, यदि इनपुट है 14, तो आउटपुट होगा True। क्योंकि पहली चाल में, हम 9 कंचे लेते हैं। इससे 5 कंचे बचते हैं जिनसे दूसरा खिलाड़ी अधिकतम 4 कंचे ले सकता है जिससे 1 कंचा बच जाता है। तो अगली चाल में, हम अंतिम कंचा लेते हैं जिससे प्रतिद्वंद्वी कोई चाल नहीं चल सकता। इस प्रकार, हम जीतते हैं।

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

यदि n <= 0, तो:
- False लौटाएं
ans := False
i के लिए int(sqrt(n)) से -1 तक, 1 से घटाते हुए, करें:
- यदि i * i > n, तो:
  - लूप से बाहर निकलें
- ans := ans OR (not solve(n - i * i))
- यदि ans True है, तो:
  - ans लौटाएं
ans लौटाएं

उदाहरण

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

from math import sqrt
def solve(n):
    if n <= 0:
        return False
    ans = False
    for i in range(int(sqrt(n)), 0, -1):
        if i * i > n:
            break
        ans = ans | (not solve(n - i * i))
        if ans:
            return ans
    return ans
print(solve(14))

इनपुट

आउटपुट

True