不同的方式 int n 可以分成 1 或 2 组

Question

这是向我提出的作业问题：

A patient has n pills to take. In each day, he can take either one pill or two pills until all pills are gone. Let T(n) denote the number of different ways the patient can take all n pills. Give a closed form for T(n). (Note that – for example – the two sequences (1, 2, 2) and (2, 1, 2) are considered as two different ways of taking 5 pills.)

我已经尝试处理 n = 1 到 8 的集合，看看是否可以找到这样的模式：

n=1 {1} n=2 {{1,1},{2}} n=3 {{1,1,1},{1,2},{2,1}} n=4 {{1,1,1,1},{1,1,2},{1,2,1},{2,1,1},{2,2}} ...

但是没能做到。 n=1-8 的组合是 1,2,3,5,8,12,18,25

有人有想法吗？

Answer 1

您的示例在 8 之后显示了错误的值（应该是 13...）。

考虑下一个方法：在最后一天患者可以吃一颗或两颗药丸（n = (n-1) + 1 或 n = (n-2) + 2 ）。所以组成 T(n) 值的方法数是

T(n) = T(n-1) + T(n-2)

对 T(n-1) 和 T(n-2) 重复相同的过程，您将在 T(0) 或 T(1) 处完成 - 这些值显然等于 1。

因此构建递归序列并解决任何 n 的递归问题。

请注意，您可以从末尾展开递归（递归方法）并从 0/1 - 迭代方法开始。

当您找到正确的值时，您可能会发现它们形成著名的序列并阅读更多相关信息。

Answer 2

这里有另一种方法来解决这个问题，当你把它看成一个排列组合问题时，它就变成了一个非常有趣的问题。

让我们

n = 6 as a example,

假设

d = number of days patient takes to take all n pills

maximum number of days patient can take those pills are 6. (1 for each day).
minimum would be 3. (2 for every day).

when d = 6 => {1,1,1,1,1,1} 
so when d = 3 => {2,2,2}

when d = 4 => {1,1,2,2}. patient can take this pills in any order in those 4 days. 
so number of combinations are = 4!/2!2! = 4C2.

when d = 5 => {1,1,1,1,2}.
number of combinations = 5!/4!1! = 5C1.

when d = 6 => {1,1,1,1,1,1}. 
number of combinations = 6!/6!0! = 6C0.

让我们回到最短天数，

when d = 3 => {2,2,2} => 3!/0!3! => 3C3.

现在您可以很容易地在阶乘中看到一个模式，

 when d = d => d!/(numberOf1s)!*(numberOf2s)!.

这么多不同的方式患者可以服用全部 6 粒药

T(6) = 3C3 + 4C2 + 5C1 + 6C0.
T(6) = 1 + 6 + 5 + 1 
T(6) = 13;

根据上面的模式，这里是算法，

d_M - maximum number of days;

d_m - minimum number of days;

T(n) -  number of different ways the patient can take all n pills

这就是您可以使用简单 javascript、

的方法

function numberOfDiffWays(n){

  var dmin = Math.ceil(n/2);
  var dmax = n;
  var sum = 0;

  for(var d= dmin; d<=dmax; d++){
    sum = sum + nCr(d,(2*d-dmax));
  }
  return sum;
}

function nCr(n,r) { 
    return fact(n) / (fact(r) * fact(n - r)); 
} 

function fact(n) { 
  return n==0 ? 1: n*fact(n-1);
} 

console.log("n=1: " + numberOfDiffWays(1)); // 1
console.log("n=2: " + numberOfDiffWays(2)); // 2
console.log("n=3: " + numberOfDiffWays(3)); // 3
console.log("n=4: " + numberOfDiffWays(4)); // 5
console.log("n=5: " + numberOfDiffWays(5)); // 8
console.log("n=6: " + numberOfDiffWays(6)); // 13
console.log("n=7: " + numberOfDiffWays(7)); // 21

希望对您有所帮助。

不同的方式 int n 可以分成 1 或 2 组

Different way int n can be split in groups of 1 or 2

algorithm

time

combinatorics

time-complexity