3

假设整数表示为斐波那契数的总和而不是 2 的幂，所以100101表示F(6)+F(3)+F(1)=8+2+1=11（我们假设F(1)=F(2)=1）。我想在 O(1) 摊销时间内在这个表示下增加一个整数。

我有递增算法：直觉是不应该有两个连续的 1 位。所以我首先将最低有效位 0 设置为 1，然后从最高有效位开始，如果数字有两个连续的 1 位，例如位 i 和 i-1，将它们都设置为 0 并设置 i+1位为 1。递归执行此操作，直到没有两个连续的 1 位。

我使用会计方法进行摊销分析。因此，对于每个增量操作，我将授予 k 美元，并且每个位翻转将花费 1 美元。但是，我无法设置和证明 k 的正确值。从经验上我认为k=3可以工作，但我不知道如何去证明这一点。

4

3 回答 3

0

以下是如何进行的概述。

首先，证明每个整数在斐波那契数中n都有唯一的表示，没有两个连续的 1 位。（更正，最低位为 0。我将其称为 0。）因此，您将从 1 开始，应用您的算法，最后以 1 结束。

其次，证明如果i在操作过程中第 th 位翻转，您提出的表示将在位 1、2、3、...、i-1 中全为 0。（更正说明，我忽略了第 0 位。）

接下来，如果第ith 位在翻转之前为 0，让我们将翻转它的成本归功于它自己。如果第ith 位在翻转之前是 1，让我们将翻转它的成本记为 2，因为你必须翻转它和它之前的那个。（位 1 的特殊情况除外。）

如果第ith 位结束为 0，那么在你有前面的序列之前你不会再次翻转...010101。你从开始，...000下一个数字就是Fib(i)这些位翻转之间的时间。i由此，您可以设置将第 th 位从翻转0到的成本上限1。（上限是它始终为 0。）

如果第ith 位以 1 结束，那么在您拥有前面的序列之前，您不会再次翻转...101010。你从开始，...000下一个数字就是Fib(i-1)这些位翻转之间的时间。i由此，您可以设置将第 th 位从翻转1到的成本上限0。（上限是它始终为 1。）在Fib(i-1)小于Fib(i)的事实和我们将此操作归功于 2 位翻转的事实之间，此界限将大于前一个界限。

i将这两个界限相加，您将得出翻转第th 位的成本的摊销上限。这个上限将呈指数衰减。

将所有可能位的上限相加，您将获得每次操作的位翻转摊销成本的上限。这将是一个有限的数字。:-)

于 2016-05-17T19:38:42.827 回答
0

以下是一些得出k=3结论的命题和观察结果：

  1. 该算法的应用由单个增量（从0到1）和零个或多个三重翻转（从011到100）组成。

  2. 运行算法后，可以保证位模式中不再有11 个模式。

  3. 增量应用于最右边的位，或者在其左边的位，因为在算法开始时它们不都是1 。

  4. 增量之后，11形态可能出现在最右边或左边一个位置。可能两者都是（111），但是算法会选择左边的。

  5. 翻转始终执行此子模式转换：011 -> 100，因此每次三重翻转时 1 位的数量都会减少。此外，在三重翻转后剩余的 1 位仅在其右侧有 0 位，除了最右边的位可能是1（在增量阶段导致...111的情况下）。

  6. 在三元组翻转之后，新的11模式可能出现的唯一位置是前一次出现左侧的两个位位置。因此，可能会出现向左方向的一连串三重翻转。这个过程是有限的，因为 1 位的数量随着每个三元组翻转而减少。

  7. 该算法是正确的，因为增量发生在表示值 1 的位上（最右边两位表示的两个斐波那契数都是 1），因此表示的值随着 1 增加。三重翻转不会改变表示的值，因为斐波那契属性。

  8. 除了最右边的 2 位外，所有其他位只能通过在某个点成为三元组翻转的最左边的位才能变成 1 位。

  9. 为F i +1生成的表示，其中F i是大于 2的第i个斐波那契数，总是正好有两个 1 位，包括最右边的位。这是因为与值F i对应的位是在所有其他位为0的时刻设置的，除了最右边的位。如果最右边的位不是1，那么它将在下次应用算法时变为1 。所以保证会产生模式10...01，其值为F i +1。

  10. 从0到F i +1的增量显然是F i +1。从0到F i +1的三次翻转次数是F i -1。这是因为增量将模式中的 1 位的数量增加 1，而三重翻转会将该数量减少 1。由于F i +1比0的表示多两个 1 位，因此三重翻转的数量为2 小于增量数。

结论

为了增加i ，达到F i +1的增量和三重翻转数之间的比率收敛到 1，因为 2 的差异变得可以忽略不计。这意味着问题中的k收敛到 3（三次翻转由 3 个翻转组成）。

演示

请参阅这个重复应用算法的 JS Fiddle，显示位表示、增量和三重翻转的总数以及它们的比率。看看比率（非常）如何缓慢收敛到 1。

上述fiddle中算法的实现如下：

// Apply the algorithm once
var mask; 
this.bits |= 1 << (this.bits & 1);
this.increments++;
mask = (this.bits & 6) === 6 ? 4 
     : (this.bits & 3) === 3 ? 2 : 0;
while (this.bits & mask) {
    this.bits ^= mask * 3.5; // 3 flips
    mask <<= 2;
    this.flips++;
}
于 2016-05-18T18:32:06.980 回答
0

使用势能方法，让表示的势能是其中 1 的位数。然后将最低位增加 1，因此它仍然是摊销的常数时间，并且每个进位都是免费摊销的，因为它通过将两个 1 位转换为一个 1 位来释放一个单位的势能。

于 2016-05-18T14:12:53.453 回答