অমল পাথরের খেলায় পাইথনে জিততে পারে কি না তা পরীক্ষা করার জন্য প্রোগ্রাম

ধরুন অমল ও বিমল নামে দুইজন খেলোয়ার আছে, তারা একটা খেলা খেলছে, আর অমল দিয়ে প্রথমে শুরু হয়। প্রাথমিকভাবে, একটি গাদা মধ্যে n বিভিন্ন পাথর আছে. প্রতিটি খেলোয়াড়ের পালাক্রমে, তিনি স্তূপ থেকে যেকোনো বর্গ সংখ্যা (শূন্য নয়) পাথর অপসারণের সমন্বয়ে একটি পদক্ষেপ করেন। এছাড়াও, যদি একজন খেলোয়াড় একটি সরাতে অক্ষম হয়, তবে সে খেলাটি হারায়। তাই যদি আমাদের n থাকে, আমাদের পরীক্ষা করতে হবে যে অমল গেমটি জিততে পারে কি না।

সুতরাং, যদি ইনপুটটি n =21 এর মত হয়, তাহলে আউটপুটটি True হবে কারণ প্রথমে Amal 16 নিতে পারে, তারপর বিমল 4 নেয়, তারপর Amal 1 নেয় এবং গেমটি জিতে নেয়।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• বর্গক্ষেত্র :=একটি নতুন তালিকা

• বর্গ :=1

• বৃদ্ধি :=3

• যখন বর্গক্ষেত্র <=n, করবেন

  • বর্গক্ষেত্রের শেষে বর্গক্ষেত্র সন্নিবেশ করুন

  • বর্গ :=বর্গ + বৃদ্ধি

  • বৃদ্ধি :=বৃদ্ধি + 2

• বর্গক্ষেত্রের শেষে বর্গক্ষেত্র সন্নিবেশ করুন

• dp :=আকারের একটি ফাঁকা তালিকা (n + 1)

• dp[0] :=মিথ্যা

• 1 থেকে n রেঞ্জের k-এর জন্য, করুন

  • s :=0

  • dp[k] :=মিথ্যা

  • যখন বর্গক্ষেত্র[s] <=k এবং dp[k] খালি থাকে, কর

    • যদি dp[k - স্কোয়ার[s]] খালি থাকে, তাহলে

      • dp[k] :=সত্য

    • s :=s + 1

• dp

  এর শেষ উপাদান ফেরত দিন

উদাহরণ

আরও ভালোভাবে বোঝার জন্য আসুন নিম্নলিখিত বাস্তবায়ন দেখি

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))

ইনপুট

21

আউটপুট

True