在Python中查找数字的最大复合被加数数
假设我们有一个给定的数N,它在(1<=N<=10^9)范围内,我们必须将N表示为最大可能数量的复合被加数的总和并返回这个最大数,否则当我们找不到任何拆分,然后返回-1。
因此,如果输入像16,那么输出将是4,因为16可以写为4+4+4+4或8+8,但是(4+4+4+4)具有最大被加数。
在线示例
让我们看看以下实现以获得更好的理解-
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