1.1.27

上次更新:2019-04-17
发现了题解错误/代码缺陷/排版问题?请点这里:如何:提交反馈

解答

与之前的斐波那契数列类似,都是重复计算的问题。

答案是 7751 次。

代码

class Program
{
    static int BinomialCalled = 0;  //计算递归调用次数
    static double?[,] BinomialCache;    //保存计算结果的数组

    static void Main(string[] args)
    {
        BinomialCache = new double?[101, 51];
        Console.WriteLine(Binomial(100, 50, 0.25));
        Console.WriteLine(BinomialCalled);
    }

    public static double? Binomial(int N, int k, double p)
    {
        BinomialCalled++;
        if (N == 0 && k == 0)
            return 1.0;
        if (N < 0 || k < 0)
            return 0.0;
        if (BinomialCache[N, k] != null)
        {
            return BinomialCache[N, k];
        }
        else
        {
            BinomialCache[N, k] = (1.0 - p) * Binomial(N - 1, k, p) + p * Binomial(N - 1, k - 1, p);
            return BinomialCache[N, k];
        }
    }
}
上一题 下一题