数出至少拿一根棍子的方法

Question

有N根棍子放在一条直线上。鲍勃打算少拿这些棍子。但无论他要拿多少根棍子，他都不会连续拿两根棍子。(也就是说，如果他拿的是一根棍子，他就不会拿i-1和i+1棍子。)

因此，给定N，我们需要计算出他可以选择多少个不同的棍子。他至少要坚持住。

示例:让N=3回答为4。

这4组是：(1，3)，(1)，(2)，(3)

主要的问题是我比简单的递归更想要解。他们能成为任何公式吗？因为我无法破解

Answer 1

几乎和斐波那契一样。最后的解决方案实际上是fibonacci(N)-1，但是让我们用实际的棍棒来解释它。

首先，我们忽视了他至少需要拿一根棍子的事实。本例中的解决方案如下：

1. 如果N = 0，则有1种解决方案(他拿起0根棍子的解)
2. 如果N = 1，有两个解决方案(拿起棍子，或者不拿)
3. 否则他可以选择
   1. 拿起第一根棍子，在N-2上恢复(因为第二根棒需要丢弃)，或者
   2. 把第一根棍子放进N-1上

​

在计算完成后，我们从结果中删除1，以避免计算他总共捡起0根棍子的情况。

伪代码的最终解决方案：

int numSticks(int N) {
    return N == 0 ? 1
         : N == 1 ? 2
         : numSticks(N-2) + numSticks(N-1);
}

solution = numSticks(X) - 1;

如您所见，numSticks实际上是Fibonacci，它可以是有效解决使用的回忆录。

Answer 2

让鲍勃拿的棍子数是r。

该问题有一个双射的二进制向量数与精确的r 1，而没有两个相邻的1's。

这是可以解决的，首先放置的r 1，你留下了确切的n-r 0's之间，并在他们的两侧。但是，您必须将r-1 0放在1之间，这样您就完全可以使用n-r-(r-1) = n-2r+1“空闲”0了。

排列这类向量的方法现在如下：

(1) = Choose(n-2r+1 + (r+1) -1 , n-2r+1) = Choose(n-r+1, n-2r+1)

• 公式(1)来源于从n-2r+1 替换的不同可能性中选择r+1元素的方法的数目

因为我们对r的一个特定值进行了求解，并且您对所有的r>=1都感兴趣，所以您需要为每个1<=r<=n求和。

因此，这个问题的解决是用封闭公式给出的：

(2) = Sum{ Choose(n-r+1, n-2r+1) | for each 1<=r<=n }

免责声明：

(固定r问题的一个密切变体是在本学期的课程I am TAing中给出了HW，主要区别是需要对r的各种值进行求和。)