知识卡片

普通读书笔记卡 · 5626.g.1.d

整数拆分优先三避免余一

理解等级:中级

对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 所示,我们无须通过循环来切分整数,而可以利用