資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究在 Python 中查詢數字的最大合數加數
假設我們有一個給定的數字 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))
輸入
16
輸出
4
更新於: 2020年8月20日
183 次瀏覽
廣告