পাইথনে কোনো খেলায় আমরা জিতেছি কিনা তা খুঁজে বের করার প্রোগ্রাম

ধরুন আমরা একটি দুই খেলোয়াড়ের খেলা খেলছি যেখানে n সংখ্যার মার্বেল আছে এবং প্রতিটি রাউন্ডে একজন খেলোয়াড়কে একটি ধনাত্মক বর্গ সংখ্যক মার্বেল নিতে হবে। যদি একজন খেলোয়াড় মার্বেলের বর্গ সংখ্যা নিতে না পারে, তাহলে সে হারবে। সুতরাং, একটি সংখ্যা n দেওয়া হলে, আমাদের খুঁজে বের করতে হবে যে আমরা গেমটি জিততে পারি কি না। আমরা সর্বদা প্রথম পালা করি এবং সর্বোত্তম সংখ্যক মার্বেল নির্বাচন করি।

সুতরাং, যদি ইনপুট 14 এর মত হয়, তাহলে আউটপুটটি True হবে। কারণ প্রথম মোড়ে আমরা 9টি মার্বেল নিই। এটি 5টি মার্বেল ছেড়ে যায় যা থেকে অন্য খেলোয়াড় 1টি মার্বেল রেখে সর্বাধিক 4টি মার্বেল নিতে পারে৷ সুতরাং, পরবর্তী পালা, আমরা প্রতিপক্ষের পিছনে 0 মার্বেল রেখে শেষ মার্বেলটি নিই, যা প্রতিপক্ষ একটি সরাতে পারবে না। এইভাবে, আমরা জিতেছি।

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

• যদি n <=0 হয়, তাহলে
  • মিথ্যে ফেরত দিন
• উত্তর :=মিথ্যা
• এর জন্য (n) এর বর্গমূল থেকে -1 পর্যন্ত পরিসীমা পূর্ণসংখ্যা অংশে, 1 দ্বারা হ্রাস করুন, করুন
  • যদি i * i> n হয়, তাহলে
    • লুপ থেকে বেরিয়ে আসুন
  • উত্তর :=উত্তর বা (সল্ভ নয়(n - i * i))
  • যদি উত্তর সত্য হয়, তাহলে
    • উত্তর ফেরত দিন
• উত্তর ফেরত দিন

উদাহরণ

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

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

ইনপুট

14

আউটপুট

True