知识卡片
整数拆分优先三避免余一
对n≥4,因子大于等于4可进一步改成2和其余而不降低乘积,4拆2+2只是相等;可选择一个最优方案仅含2和3。三个2换成两个3会增大乘积,因此尽量用3,余1时把3+1换成2+2。
n=2或3又要求至少两段,需单独处理。原书Go用math.Pow浮点取幂转int,不保证大结果精确或不溢出;若用任意精度整数,还要计位长运算成本,不能只按固定字长乘法次数算。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- · 查看原书依据
当余数为 2. 代码实现 时,代表 是 的倍数,因此不做任何处理。 2 ×2 > 1 × 3 时,不继续划分,保留。 时,由于 ,因此应将最后一个 替换为 。 如图15‑16 所示,我们无须通过循环来切分整数,而可以利用
参考来源
- 位置:《Hello 算法--Go版本》第15章《贪心》(来源项目book-sources:extracted/Hello 算法--Go版本/_epub-src/OEBPS/Text/8.html;spine 7,归一字符[10606,10716))
- 结论依据:实际策略/代码分余数1/2/0及n≤3边界,图15-14/15已读确认4相等。
- 原始内容:当余数为 2. 代码实现 时,代表 是 的倍数,因此不做任何处理。 2 ×2 > 1 × 3 时,不继续划分,保留。 时,由于 ,因此应将最后一个 替换为 。 如图15‑16 所示,我们无须通过循环来切分整数,而可以利用