जांचें कि क्या पायथन में तीन ऑपरेशनों द्वारा सरणी योग को K बनाया जा सकता है

मान लीजिए कि हमारे पास संख्याओं की एक सूची है जिसे अंक कहा जाता है और एक सकारात्मक मान K भी है। हम इन तीनों में से कोई भी ऑपरेशन अंकों पर कर सकते हैं -

• एक नंबर को नेगेटिव बनाएं,
• संख्या का अनुक्रमणिका (सूचकांक 1 से प्रारंभ करें) स्वयं संख्या में जोड़ें
• संख्या के सूचकांक को संख्या से ही घटाएं।

अंत में, हमें यह जांचना होगा कि क्या दिए गए सरणी को रूपांतरित किया जा सकता है क्योंकि सरणी का योग k हो जाता है, प्रत्येक तत्व पर इन कार्यों को केवल एक बार करके।

इसलिए, यदि इनपुट nums =[1,2,3,7] k =8 जैसा है, तो आउटपुट ट्रू होगा क्योंकि हम 2 और 3 से 2 और 3 के इंडेक्स को घटाकर [1, 0, जैसे एरे बना सकते हैं। 0, 7], तो अब योग 8 =k है।

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

• आकार :=100
• एक फ़ंक्शन परिभाषित करें is_ok() । इसमें i, Total, k, nums, table
लगेगा
• n :=अंकों का आकार
• यदि कुल <=0, तो
  • झूठी वापसी
• अगर मैं>=n, तो
  • यदि योग k के समान है, तो
    • सही लौटें
• झूठी वापसी
• यदि तालिका [i, कुल] -1 नहीं है, तो
  • रिटर्न टेबल[i, कुल]
• तालिका[i, कुल] :=1 जब (is_ok(i+1, Total - 2 * nums[i], k, nums, table) गैर-शून्य है या is_ok(i+1, Total, k, अंक, तालिका) गैर-शून्य है), अन्यथा 0
• तालिका[i, कुल] :=1 जब (is_ok(i+1, Total -(i+1) , k, nums, तालिका) या तालिका[i, कुल]), अन्यथा 0
• तालिका[i, कुल] :=1 जब (is_ok(i+1, कुल + i + 1, k, अंक, तालिका) या तालिका[i, कुल]), अन्यथा 0
• रिटर्न टेबल[i, कुल]
• मुख्य विधि से निम्न कार्य करें -
• कुल :=अंकों में सभी तत्वों का योग
• तालिका :=आकार के समान लंबाई की एक सरणी और -1 से भरें
• मैं के लिए 0 से आकार की सीमा में, करते हैं
  • तालिका[i] :=आकार के समान लंबाई की एक सरणी और -1 से भरें
• वापसी is_ok(0, कुल, k, अंक, तालिका)

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

उदाहरण

size = 100
def is_ok(i, total, k, nums, table):
   n = len(nums)
   if total <= 0:
      return False
   if i >= n:
      if total == k:
         return True
      return False
   if table[i][total] != -1:
      return table[i][total]
   table[i][total] = is_ok(i+1, total - 2 * nums[i], k, nums, table) or is_ok(i+1, total, k, nums, table)
   table[i][total] = is_ok(i+1, total - (i+1), k, nums, table) or table[i][total] table[i][total] = is_ok(i+1, total + i + 1, k, nums, table) or table[i][total]
   return table[i][total]
def solve(nums, k):
   total = sum(nums)
   table = [-1]*size
   for i in range(size):
      table[i] = [-1]*size
   return is_ok(0, total, k, nums, table)
nums = [1,2,3,7]
k = 8
print(solve(nums, k))

इनपुट

[1,2,3,7], 8

आउटपुट

True