पायथन में किसी संख्या के अधिकतम कम्पोजिट समन्वयों की संख्या खोजें

मान लीजिए हमारे पास एक दी गई संख्या 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() फंक्शन परिभाषित करें। यह लेगा:
table := max_val आकार की एक सूची, फिर प्रत्येक स्थान पर -1 स्टोर करें
table[0] := 0
v := [4, 6, 9]
i को 1 से max_val तक, 1 से बढ़ाकर, करें:
- k को 0 से 2 तक के लिए, करें:
  - j := v[k]
  - यदि i >= j और table[i-j] -1 नहीं है, तो:
    - table[i] := table[i] और table[i-j] + 1 का अधिकतम
table लौटाएं
max_summ() फंक्शन परिभाषित करें। यह table, n लेगा।
यदि n < max_val, तो:
- table[n] लौटाएं
अन्यथा,
- t := ((n - max_val) / 4) + 1 का पूर्णांक
- t + table[n - 4*t] लौटाएं
मुख्य विधि से, निम्नलिखित करें:
table := pre_calc()
max_summ(table, 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))