আমরা পাথর দিয়ে নদী পার হতে পারি নাকি পাইথনে নয় তা পরীক্ষা করার জন্য প্রোগ্রাম

ধরুন আমাদের কাছে বাছাই করা সংখ্যার একটি তালিকা রয়েছে যাকে বলা হয় পাথর এবং এটি একটি নদীর উপর পাথরের অবস্থানের প্রতিনিধিত্ব করছে যা আমরা অতিক্রম করার চেষ্টা করছি। নদী পার হতে হলে শেষ পাথরে শেষ করতে হবে। এখন প্রতিটি ধাপে, আমরা লাফ দিতে পারি (k - 1, k, বা k + 1) ধাপ এগিয়ে যেখানে k হল শেষ লাফের দূরত্ব। আমরা নদী পার হতে পারব কি না তা পরীক্ষা করতে হবে।

সুতরাং, ইনপুট যদি পাথরের মত হয় =[0, 1, 3, 4, 5, 6, 8, 9, 13], তাহলে আউটপুট হবে True, যেমন আমরা 0 থেকে শুরু করতে পারি, তারপর 1 ইউনিট লাফ দিয়ে পাথরে যেতে পারি। 1, তারপর 2 ইউনিট 3 যেতে, তারপর 2 ইউনিট 5, তারপর 3 ইউনিট 8, এবং অবশেষে 5 ইউনিট 13 যেতে, এবং এটি চূড়ান্ত স্থান।

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

• start :=A[0], end :=A এর শেষ উপাদান
• A :=A এর সমস্ত অনন্য উপাদানের একটি সেট
• একটি ফাংশন চেক() সংজ্ঞায়িত করুন। এটি pos:=start, prev:=0
লাগবে
• যদি pos শেষের মত হয়, তাহলে
  • সত্য ফেরান
• প্রতিটি লাফের জন্য [পূর্ব - 1, পূর্ববর্তী, পূর্ববর্তী + 1], করুন
  • যদি লাফ দেয়>=1, তাহলে
    • next_pos :=jump + pos
    • যদি next_pos A তে থাকে এবং চেক করুন (next_pos, jump) সত্য হয়, তাহলে
      • সত্য ফেরান
• মিথ্যে ফেরত দিন
• প্রধান পদ্ধতি থেকে কল চেক() এবং রিটার্ন ফলাফল

উদাহরণ (পাইথন)

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

class Solution:
   def solve(self, A):
      start, end = A[0], A[-1]
      A = set(A)
      def check(pos=start, prev=0):
         if pos == end:
            return True
         for jump in [prev - 1, prev, prev + 1]:
            if jump >= 1:
               next_pos = jump + pos
               if next_pos in A and check(next_pos, jump):
                  return True
         return False
      return check()
ob = Solution()
stones = [0, 1, 3, 4, 5, 6, 8, 9, 13]
print(ob.solve(stones))

ইনপুট

[0, 1, 3, 4, 5, 6, 8, 9, 13]

আউটপুট

True