代码之家 › 专栏 › 技术社区 › JavaSheriff

从盒子里拿球的不同方法

algorithm

JavaSheriff · 技术社区 · 6 年前

提取顺序也很重要。
问题是有多少种不同的方法可以把球拉出来?
因此,如果:
盒子里有一个球只有一条路。
盒子里有两个球只有一条路。

盒子里有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);
}

是这样吗?
有没有不使用递归的方法?

谢谢你

4 回复 | 直到 6 年前

Patrick Roberts Benjamin Gruenbaum 6 年前

你的解决方案是正确的。然而,有一些方法可以使用一种称为动态规划的技术来提高算法的性能。在这种情况下,您可以记忆结果,这意味着在使用递归计算每个中间结果一次之后,将所有中间结果存储在查找表中。这使得通常需要指数时间才能在线性时间内完成的解决方案成为可能。下面是一个用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')

将其与naive算法进行比较:

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')

Hans Olsson 6 年前

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;
   }
}

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

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

Patrick Roberts Benjamin Gruenbaum 6 年前

从 link in the comments ,你可以找到这个方程:

a(n)=和{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')

Dave 6 年前

对于N个球,你可以拉0到地板(N/3)三个球。

对于N个球,你拉k个三人组,你也拉N-3k个单打。

现在问题被简化为计算一种类型的k个事物和另一种类型的N-3k个事物的不同排序方式。这是choose(k+N-3k,k)=choose(N-2k,k)。

最终答案是从k=0到choose(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