有一系列 n 次操作，如果 i 是 2 的精确幂，则第 i 次操作花费 2i，如果 i 是 3 的精确幂，则花费 3i，所有其他操作花费 1。
嗨，首先我想说这是一个家庭作业问题，我不想让你为我解决它。我已经使用聚合方法解决了它。为此，我将 2 的幂级数和 3 的幂级数相加，得到 10 的摊余成本。然后我使用会计方法对其进行了检查，对于非常长的序列，它并没有失败。但我的问题是如何证明它永远不会失败，我可以展示我想要的任意长序列，但它仍然不能保证它在一段时间后不会失败。
我也尝试用潜在函数方法解决它，这是我真正陷入困境的地方，要设置潜在函数我认为你需要非常有创意，我找不到一些条件表明此时这将始终成立，需要那里也有一些帮助。
只是一些关于如何在会计方法中证明它以及如何设计潜在功能的想法就足够了。谢谢
首先，暂时忘记“1 表示所有其他操作”和“3 的精确幂”位。如果当 i 是 2 的精确幂时成本只是 2i 怎么办？
好吧，假设我们假设每个操作花费四。也就是说，对于每次操作，我们将四个硬币放入我们的“IOU 堆”中......然后当我们达到 2 的实际幂时，我们使用这些硬币来“支付”。（这是描述势函数方法的一种方式。）
第一步：存入四枚硬币。需要支付 2*1 = 2，所以我们的硬币堆是 2。
第 2 步：再存入四个硬币。需要支付 2*2 = 4，所以我们的堆又是 2。
第三步：存入四枚硬币。桩现在有六个硬币。
第四步：存入四枚硬币。堆现在有十个硬币，但 4 是 2 的幂，所以是时候支付 4*2 = 8，所以我们的堆再次减少到两个硬币。
步骤 5-7：每人存入四枚硬币。现在总共是 14 个硬币。
第8步：存入4个硬币（总计=18），花费8*2 = 16，再次剩下2个硬币。
很容易证明这里的稳定状态是我们不断消耗我们的硬币到一个常数（2），但我们永远不会低于。因此，摊销成本为每次操作四个单位。
现在，假设当 i 是 2 的幂（否则为零）时，操作 X 的成本为 2i。假设当 i 是 3 的幂（否则为零）时，操作 Y 的成本为 3i。并假设操作 Z 成本为 1，除非 i 是 2 的幂或 3 的幂。观察到您的问题等同于执行操作 X和Y和Z 为每次迭代......所以如果你能算出摊销成本X、Y 和 Z 分开，您可以将它们相加得到总摊销成本。
我刚刚给了你X；我把 Y 和 Z 作为练习。（虽然我不相信最终的答案是 10。接近 10，也许......）