数据结构
网络
关系数据库管理系统
操作系统
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 次浏览
广告