仅使用 2 或 3 从 0 达到 N 的方法有多少种？

Question

我正在解决这个问题，我们需要从 X=0 到达 X=N.We 一次只能走 2 步或 3 步。

对于2的每一步我们有0.2的概率，对于3的每一步我们有0的概率。8.How我们能找到达到N的总概率吗？

e.g. for reaching 5,

2+3 with probability =0.2 * 0.8=0.16

3+2 with probability =0.8 * 0.2=0.16 total = 0.32.

我的初步想法：

通过简单的斐波那契数列就可以找出许多种方法。 f(n)=f(n-3)+f(n-2); 但是我们如何记住这些数字，以便我们可以将它们相乘来找到概率呢？

Answer 1

f(n, p) = f(n-3, p*.8) + f(n -2, p*.2)

p 从 1 开始。

如果 n=0 return p，如果 n <0 return 0.

Answer 2

这可以使用 Dynamic programming 来解决。

让我们调用函数 F(N) = 在 the starting number is N

时仅使用 2 和 3 达到 0 的概率

F(N) = 0.2*F(N-2) + 0.3*F(N-3)

基本案例：

F(0) = 1 and F(k)= 0 where k< 0

所以 DP 代码应该是这样的：

F[0] = 1;
for(int i = 1;i<=N;i++){
     if(i>=3)
         F[i] = 0.2*F[i-2] + 0.8*F[i-3];
     else if(i>=2)
         F[i] = 0.2*F[i-2];
     else
         F[i] = 0;
}
return F[N];

此算法会运行在 O(N)

Answer 3

与其使用（非常低效的）递归算法，不如从头开始计算可以到达后续步骤的方式，即使用 'dynamic programming'。这样，您可以轻松计算概率，并且复杂度仅为 O(n) 来计算直到步骤 n.[= 的所有内容21=]

对于每一步，记住到达那一步的可能方式（如果有的话）（无论如何），以及到达那一步的概率。对于第零步（开始），这是 (1, 1.0)。

steps = [(1, 1.0)]

现在，对于每个连续的步骤 n，获取先前计算的可能方式 poss 和概率 prob 以达到步骤 n-2 和 n-3（或 (0, 0.0) 在 n < 2 或 n < 3 的情况下），将这些添加到组合可能性和概率中以达到新步骤，并将它们添加到列表中。

for n in range(1, 10):
    poss2, prob2 = steps[n-2] if n >= 2 else (0, 0.0)
    poss3, prob3 = steps[n-3] if n >= 3 else (0, 0.0)
    steps.append( (poss2 + poss3, prob2 * 0.2 + prob3 * 0.8) )

现在您可以从该列表中获取数字：

>>> for n, (poss, prob) in enumerate(steps):
...     print "%s\t%s\t%s" % (n, poss, prob)
0   1   1.0
1   0   0.0
2   1   0.2
3   1   0.8
4   1   0.04
5   2   0.32        <-- 2 ways to get to 5 with combined prob. of 0.32
6   2   0.648
7   3   0.096
8   4   0.3856
9   5   0.5376

（代码在Python）

请注意，这将使您到达特定步骤的可能方式的数量（例如 "first 2, then 3" 或 "first 3, then 2" 为 5），and一次到达那一步的概率。当然，如果你只需要概率，你可以直接用单数代替元组。

Answer 4

关于此解决方案的一些说明：我假设从 2s 和 3s 生成数字的唯一允许操作是加法（您的定义也允许减法）并且输入数字始终有效（2 <= 输入）。定义：唯一的一行数字意味着：在另一个顺序中没有其他具有相同数量的 3 和 2 的行在范围内。

我们可以将问题分解成多个更小的问题：

问题 A：找到所有可以和给定数字相加的数字序列。（仅限唯一的数字行）
首先找到构建给定数字所需的最小 3 数，即 input % 2。可用于构建输入的最大 3 数可以这样计算：

int max_3 = (int) (input / 3);
if(input - max_3 == 1)
    --max_3;

现在所有总和为 input 的数字序列必须保持在 input % 2 和 max_3 3 秒之间。 2 可以很容易地从给定数量的 3 中计算出来。

问题 B：计算给定列表的概率及其排列结果 对于每一行唯一的数字，我们可以很容易地推导出所有排列。由于它们由相同的数字组成，因此它们出现并产生相同总和的可能性相同。可以从行中轻松计算出可能性：0.8 ^ number_of_3s * 0.2 ^ number_of_2s。下一步是计算不同排列的数量。可以通过以下方式计算具有特定数量的 2 和 3 的所有不同集合：计算集合中 2 的所有可能分布：(number_of_2s + number_of_3s)! / (number_of_3s! * numer_of_2s!)。基本上只是可能的不同排列的数量。

现在从理论到实践
由于给出了数学，剩下的就很简单了：

define prob:
    input: int num
    output: double

    double result = 0.0

    int min_3s = (num % 2)
    int max_3s = (int) (num / 3)
    if(num - max_3 == 1)
        --max_3

    for int c3s in [min_3s , max_3s]
        int c2s = (num - (c3s * 3)) / 2

        double p = 0.8 ^ c3s * 0.2 * c2s
        p *= (c3s + c2s)! / (c3s! * c2s!)

        result += p

    return result

Answer 5

您可以使用数学而不是跳入编程。

令 p(n) 为您到达 n 步外位置的概率。

基本案例：

p(0)=1
p(1)=0
p(2)=0.2

Linear recurrence relation

p(n+3)=0.2 p(n+1) + 0.8 p(n)

您可以通过找到线性递归关系的指数解以封闭形式解决此问题。

c^3 = 0.2 c + 0.8

c = 1, (-5 +- sqrt(55)i)/10

尽管这是三次方，但 c=1 将始终是此类问题的解，因为存在常数非零解。

因为根不同，所以所有解的形式都是 a1(1)^n + a2((-5+sqrt(55)i) / 10)^n + a3((-5-sqrt( 55)i)/10)^n。您可以使用初始条件求解 a1、a2 和 a3：

a1=5/14 
a2=(99-sqrt(55)i)/308
a3=(99+sqrt(55)i)/308

这为您提供了 p(n) 的非递归公式：

p(n)=5/14+(99-sqrt(55)i)/308((-5+sqrt(55)i)/10)^n+(99+sqrt(55)i)/308((-5-sqrt(55)i)/10)^n

非递归公式的一个很好的属性是你可以读出5/14的渐近值，但是这也很清楚，因为跳跃的平均值是2(1/5) + 3(4/5) = 14/5，您几乎可以肯定会找到一个整数密度为 1/(14/5) 的集合。您可以使用其他根的大小 2/sqrt(5)~0.894 来查看概率接近渐近线的速度有多快。

5/14 - (|a2|+|a3|) 0.894^n < p(n) < 5/14 + (|a2|+|a3|) 0.894^n
|5/14 - p(n)| < (|a2|+|a3|) 0.894^n

仅使用 2 或 3 从 0 达到 N 的方法有多少种？

Number of ways to reach N from 0 using only 2 or 3?

algorithm

fibonacci