पायथन में अमल स्टोन गेम जीत सकता है या नहीं यह जांचने के लिए प्रोग्राम

मान लीजिए कि दो खिलाड़ी अमल और बिमल हैं, वे एक खेल खेल रहे हैं, और अमल के साथ पहले शुरू होता है। प्रारंभ में, ढेर में n अलग-अलग पत्थर होते हैं। प्रत्येक खिलाड़ी की बारी पर, वह ढेर से पत्थरों के किसी भी वर्ग संख्या (गैर-शून्य) को हटाने के साथ एक चाल चलता है। साथ ही, यदि कोई खिलाड़ी चाल चलने में असमर्थ होता है, तो वह खेल हार जाता है। इसलिए अगर हमारे पास n है, तो हमें यह देखना होगा कि अमल गेम जीत सकता है या नहीं।

इसलिए, यदि इनपुट n =21 जैसा है, तो आउटपुट ट्रू होगा क्योंकि पहले अमल 16 ले सकता है, फिर बिमल 4 लेता है, फिर अमल 1 लेता है और गेम जीत जाता है।

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

वर्ग :=एक नई सूची
वर्ग :=1
वृद्धि :=3
जबकि वर्ग <=n, करें
- वर्गों के अंत में वर्ग डालें
- वर्ग :=वर्ग + वृद्धि
- वृद्धि :=वृद्धि + 2
वर्गों के अंत में वर्ग डालें
dp :=आकार की एक खाली सूची (n + 1)
डीपी [0] :=झूठा
1 से n की श्रेणी में k के लिए, करें
- एस:=0
- डीपी [के]:=झूठा
- जबकि वर्ग[s] <=k और dp[k] खाली है, करें
  - अगर dp[k - वर्ग[s]] खाली है, तो
    - डीपी [के] :=सच
  - एस:=एस + 1
डीपी का अंतिम तत्व लौटाएं

उदाहरण

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

def solve(n):
   squares = []
   square = 1
   increase = 3
   while square <= n:
      squares.append(square)
      square += increase
      increase += 2
   squares.append(square)

   dp = [None] * (n + 1)
   dp[0] = False
   for k in range(1, n + 1):
      s = 0
      dp[k] = False
      while squares[s] <= k and not dp[k]:
         if not dp[k - squares[s]]:
            dp[k] = True
         s += 1
   return dp[-1]

n = 21
print(solve(n))

इनपुट

आउटपुट

True