有一个包含 n 个操作的序列，如果 i 是 2 的精确幂，则第 i 个操作的成本为 2i；如果 i 是 3 的精确幂，则第 i 个操作的成本为 3i；对于所有其他操作，成本为 1。
Hi first up I want to say that it is a homework problem and I don't want you to solve it for me.
我已经用聚合方法解决了这个问题。为此，我对 2 的幂级数和 3 的幂级数求和，得到摊余成本 10。然后，我使用会计方法对其进行了检查，对于非常长的序列，它没有失败。但我的问题是如何证明它永远不会失败，我可以显示我想要的尽可能长的序列，但它仍然不能保证它在一段时间后不会失败。
我也尝试用势函数方法来解决它，这就是我真正陷入困境的地方，要设计一个势函数，我认为你需要真正的创造力，我找不到一些条件表明在这一点上这将永远成立，需要那里也有一些帮助。
只需一些关于如何在会计方法中证明它以及如何设计潜在功能的想法就足够了。
谢谢
首先，暂时忘掉“1 用于所有其他操作”和“3 的精确幂”位。如果当 i 是 2 的精确幂时，成本仅为 2i 会怎样？
好吧，假设我们假设每次操作花费四。也就是说，对于每次操作，我们将四个硬币放入“IOU 堆”中...然后，当我们达到 2 的实际幂时，我们使用这些硬币来“支付”。（这是描述势函数方法的一种方式。）
步骤1：存入四枚硬币。需要支付2*1=2，所以我们的币堆是2。
步骤2：再存入四枚硬币。需要支付 2*2 = 4，所以我们的堆又是 2。
第三步：存入四枚硬币。桩现在有六枚硬币。
第四步：存入四枚硬币。现在一堆硬币有十个，但 4 是 2 的幂，所以是时候支付 4*2 = 8，所以我们的一堆硬币又减少到两个硬币。
步骤 5-7：每人存入 4 个硬币。现在总共有 14 个硬币。
步骤8：存入4个币（总计=18），花费8*2=16，再次剩下2个币。
很容易证明这里的稳定状态是我们不断将代币消耗到一个常数 (2)，但我们永远不会低于这个值。因此，每次操作的摊余成本为四个单位。
现在，假设当 i 是 2 的幂（否则为零）时，操作 X 的成本为 2i。假设当 i 是 3 的幂（否则为零）时，操作 Y 的成本为 3i。假设操作 Z 的成本为 1，除非 i 是 2 的幂或 3 的幂。观察您的问题相当于执行操作 Xand Y and每次迭代的 Z...因此，如果您可以分别计算出 X、Y 和 Z 的摊余成本，则只需将它们相加即可得到总体摊余成本。
我刚刚给了你X；我把 Y 和 Z 作为练习。 （虽然我不相信最终答案是10。接近10，也许......）
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
