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

मान लीजिए कि हमारे पास क्रमबद्ध संख्याओं की एक सूची है जिसे पत्थर कहा जाता है और यह नदी पर पत्थरों की स्थिति का प्रतिनिधित्व कर रहा है जिसे हम पार करने की कोशिश कर रहे हैं। नदी पार करने के लिए, हमें अंतिम पत्थर पर समाप्त करना होगा। अब प्रत्येक चरण में, हम (k - 1, k, या k + 1) कदम आगे बढ़ सकते हैं, जहां k अंतिम छलांग की दूरी है। हमें यह देखना होगा कि हम नदी पार कर सकते हैं या नहीं।

इसलिए, यदि इनपुट पत्थरों की तरह है =[0, 1, 3, 4, 5, 6, 8, 9, 13], तो आउटपुट ट्रू होगा, जैसा कि हम 0 से शुरू कर सकते हैं, फिर स्टोन जाने के लिए 1 यूनिट कूदें 1, फिर 2 इकाइयों को 3, उसके बाद 2 इकाइयों को 5, फिर 3 इकाइयों को 8, और अंत में 5 इकाइयों को 13 जाना है, और यह अंतिम स्थान है।

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

• प्रारंभ:=A[0], अंत:=A का अंतिम तत्व
• A :=A के सभी अद्वितीय तत्वों का एक सेट
• एक फ़ंक्शन को परिभाषित करें check() । यह स्थिति लेगा:=प्रारंभ, पिछला:=0
• यदि स्थिति अंत के समान है, तो
  • सही लौटें
• [पिछला -1, पिछला, पिछला + 1] में प्रत्येक छलांग के लिए, करें
  • अगर कूदो>=1, तो
    • next_pos :=जम्प + पॉज़
    • अगर next_pos A में है और check(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