पायथन में किसी संख्या के समग्र योगों की अधिकतम संख्या ज्ञात करें

मान लीजिए कि हमारे पास एक दी गई संख्या N है, जो कि श्रेणी (1<=N<=10^9) में है, हमें N को समग्र योगों की सबसे बड़ी संभव संख्या के योग के रूप में प्रस्तुत करना होगा और इस सबसे बड़ी संख्या को वापस करें, अन्यथा जब हमें कोई विभाजन नहीं मिल रहा है, तो -1 लौटा दें।

इसलिए, यदि इनपुट 16 की तरह है, तो आउटपुट 4 होगा क्योंकि 16 को 4 + 4 + 4 + 4 या 8 + 8 के रूप में लिखा जा सकता है, लेकिन (4 + 4 + 4 + 4) में अधिकतम योग हैं।

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

• max_val :=16

• एक फ़ंक्शन को परिभाषित करें pre_calc() । इसमें लगेगा

• तालिका:=आकार max_val की एक सूची, फिर प्रत्येक स्थान पर -1 स्टोर करें

• टेबल [0] :=0

• वी:=[4, 6, 9]

• मैं के लिए 1 से max_val की सीमा में, 1 की वृद्धि करें

  • के लिए 0 से 2 की सीमा में, करें

    • जे:=वी[के]

    • अगर i>=j और टेबल[i - j] -1 नहीं है, तो

      • तालिका [i]:=अधिकतम तालिका [i], तालिका [i - j] + 1

• वापसी तालिका

• एक फ़ंक्शन को परिभाषित करें max_summ() । यह तालिका लेगा, n

• अगर n

  • वापसी तालिका[n]

• अन्यथा,

  • t :=पूर्णांक ((n - max_val) / 4) + 1

  • रिटर्न टी + टेबल [एन -4 * टी]

• मुख्य विधि से, निम्न कार्य करें -

• तालिका:=pre_calc ()

• प्रदर्शन max_summ(तालिका, n)

उदाहरण

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

global max_val
max_val = 16
def pre_calc():
   table = [-1 for i in range(max_val)]
   table[0] = 0
   v = [4, 6, 9]
   for i in range(1, max_val, 1):
      for k in range(3):
         j = v[k]
         if (i >= j and table[i - j] != -1):
            table[i] = max(table[i], table[i - j] + 1)
   return table
def max_summ(table, n):
   if (n < max_val):
      return table[n]
   else:
      t = int((n - max_val) / 4)+ 1
      return t + table[n - 4 * t]
n = 16
table = pre_calc()
print(max_summ(table, n))

इनपुट

16

आउटपुट

4