c# 斐波那契数 80

Question

为什么我的代码不适用于 50 或更高的数字？对于阶乘它有效但不适用于斐波那契。它似乎在计算一些东西，但总是在那里显示黑色控制台

using System;
using System.Numerics;

namespace Training_Project
{
    internal class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine(Fib(50));
            Console.WriteLine(Factorial(100));
        }
      
        static BigInteger Factorial(int n)
        {
            if (n == 0)
                return 1;
            else
                return n * Factorial(n - 1);
        }
        static BigInteger Fib(int n) 
        {
            if (n <= 2)
                return 1;

            return Fib(n - 1) + Fib(n - 2);
        }

    }
}

Answer 1

如果您缓存已经计算出的斐波那契数，则可以省去一些麻烦（参考 Saleh Ahmadi 对您的 post 的评论）。

你可以，例如将 Dictionary 添加到您的 class 以跟踪您已经计算的内容

static Dictionary<int, BigInteger> _fibonacciOfNumber = new();

，并在存在时从那里查找值：

static BigInteger Fib(int n) 
{
    if (n <= 2)
    {
        return 1;
    }

    if (!_fibonacciOfNumber.ContainsKey(n))
    {
        _fibonacciOfNumber[n] = Fib(n - 1) + Fib(n - 2);
    }

    return _fibonacciOfNumber[n];
}

示例 fiddle here.

使用缓存，例如计算斐波那契数30 需要 57 次调用 Fib()；而 1.664.079 对 Fib() 的调用不需要缓存。

要查看两种不同方法调用 Fib( ) 次数的比较，请参阅 this fiddle。

c# 斐波那契数 80

c# Fibonacci number 80

c#

visual-studio

fibonacci

factorial