从盒子中获取球的不同方法

Question

你有一个装有球的盒子，我们从盒子里拉出所有的球，
但是我们可以一次拉一个或一次拉三个，
提取的顺序很重要。
问题是有多少种不同的方法可以将球拉出来？
因此，如果 ：
Box 包含 1 个球，则只有 1 个方式。
盒子包含 2 个球只有 1 个方式。
盒子包含 3 个球有 2 路(一次拉 1 个或三个(
盒子包含 4 个球有 3 路：
1111
13
31

给定的是，对于 7 个球，有 9 种不同的方式从盒子中提取球

所以问题给出了盒子里的球的数量，

我想出的解决方案是递归的：

Int calculate(int balls){
If(balls=0) return 0;
If(balls=1) return 1;
If(balls=2) return 1;
If(balls=3) return 2;
If(balls=4) return 3;
return calculate(balls-1) + calculate(balls-3);
}

这是对的吗？
有没有办法不使用递归？

谢谢

Answer 1

您的解决方案是正确的。但是，有一些方法可以使用称为动态规划的技术来提高算法的性能。在这种情况下，您可以记住结果，这意味着在使用递归计算每个中间结果一次后，将所有中间结果存储在查找表中。这允许通常需要指数时间的解决方案在线性时间内完成。下面是 JavaScript 中的一个示例实现：

function calculate (balls, map = []) {
if (balls in map) {
return map[balls]
}
switch (balls) {
case 0:
return 0
case 1:
return 1
case 2:
return 1
case 3:
return 2
default:
return map[balls] = calculate(balls - 1, map) + calculate(balls - 3, map)
}
}
console.time('dynamic')
console.log(calculate(50))
console.timeEnd('dynamic')

将其与朴素算法进行比较：

function calculate (balls) {
switch (balls) {
case 0:
return 0
case 1:
return 1
case 2:
return 1
case 3:
return 2
default:
return calculate(balls - 1) + calculate(balls - 3)
}
}
console.time('naive')
console.log(calculate(50))
console.timeEnd('naive')

Answer 2

你不需要记忆(至少不是所有值(或解决递归来为这种情况或类似情况编写非递归程序。

类似以下内容即可：

function calculate (balls) {
if (balls=0) return 0; /* Or remove this line */
if (balls<3) return 1;
resMinus3=1;  /* The result for i-3 */
resMinus2=1;  /* For i-2 */
resMinus1=1;  /* And for i-1 */
for(i=3;;++i) {
newRes=resMinus1+resMinus3; /* The recursion formula */
if (i>=balls) return newRes;
resMinus3=resMinus2; /* Shifting results */
resMinus2=resMinus1;
resMinus1=newRes;
}
}

原因是要计算球的值，您只需要球-1 和球-3 的值，因此您只需要跟踪以前的三个结果即可更新新结果。或者，您可以将其编写为矩阵更新：

[resMinus1;resMinus2;resMinus3] <-[0,1,0;0,0,1;1,0,1]*[resMinus1;resMinus2;resMinus3]

Answer 3

从评论中的链接中，您可以找到以下等式：

a(n( = Sum_{i=0..floor(n/3(} 二项式(n-2*i， i(

function binom(n, k) {
var coeff = 1;
for (var i = n-k+1; i <= n; i++) coeff *= i;
for (var i = 1;     i <= k; i++) coeff /= i;
return coeff;
}
function calculate (balls) {
sum = 0;
for (i = 0; i <= Math.floor(balls/3); i++){
sum += binom(balls - 2*i, i);
}
return sum;

}
console.time('someMathGenius')
console.log(calculate(50))
console.timeEnd('someMathGenius')

Answer 4

对于 N 个球，您可以在 0 和 floor(n/3( 三元组之间拉动。

对于你拉 k 个三元组的 N 个球，你也拉 N-3k 个单打。

现在问题简化为计算您可以订购一种类型的 k 件东西和另一种类型的 N-3k 件东西的不同方式。这是 choose(k + N-3k， k( = choose(N-2k，k(。

最终答案是从 k=0 到 选择(N-2k，k(的地板(N/3(的总和。

N=0: choose(0,0) = 1 so there is 1 way of choosing nothing.
N=1: choose(1,0) = 1
N=2: choose(2,0) = 1
N=3: choose(3,0) + choose(1,1) = 1+1 = 2
N=4: choose(4,0) + choose(2,1) = 1+2 = 3
...
N=7: choose(7,0) + choose(5,1) + choose(3,2) = 1 + 5 + 3 = 9