c# - 在 C# 中有大量数字的斐波那契数列

Question

我正在尝试找到第一个包含 1000 位数字的 fib 数字。因为我没有能够保存这样一个数字的数据类型，所以我创建了一个名为 hugeNumber 的类，它保存列表中的数字，以十进制为基数。我在生成“hugenum”类的列表时遇到堆栈溢出 - 我不确定为什么(这真的不是正确的方法吗？有更好的方法吗？)

这是我的代码:

class hugeNum
{
    List<int> digits = new List<int>();
    public hugeNum(int basic)
    {
        digits.Add(basic);
    }
    public hugeNum()
    {
    }
    public static hugeNum operator +(hugeNum first, hugeNum second)
    {
        hugeNum generated = new hugeNum();
        hugeNum finalIter = null;
        int carry = 0;
        int i = 0;
        for (i = 0; i<second.digits.Count && i<first.digits.Count; i++)
        {
            generated.digits.Add(first.digits[i] + second.digits[i] + carry);
            if (generated.digits[i] >= 10)
            {
                carry = 1;
                generated.digits[i] -= 10;
            }
            else
                carry = 0;
        }
        finalIter = first;
        if (i==first.digits.Count)
        {
            finalIter = second;
        }
        while (i<finalIter.digits.Count)
        {
            generated.digits.Add(finalIter.digits[i]);
            i++;
        }
        return generated;
    }
    public int amountOfDigits()
    {
        return this.digits.Count;
    }
}
class Program
{
    public static int fibHugesUntilIter(hugeNum huge1, hugeNum huge2, int reqDigits, int iter)
    {
        if (huge2.amountOfDigits() == reqDigits)
            return iter;
        return fibHugesUntilIter(huge2, huge1 + huge2, reqDigits, iter + 1);
    }
    static void Main(string[] args)
    {
        Console.WriteLine(fibHugesUntilIter(new hugeNum(1), new hugeNum(1), 1000, 1));
    }
}

Answer 1

您可以使用 BigInteger没有递归:

public static int FibHugesUntil(BigInteger huge1, BigInteger huge2, int reqDigits)
{
    int number = 1;
    while (huge2.ToString().Length < reqDigits)
    {
        var huge3 = huge1 + huge2;
        huge1 = huge2;
        huge2 = huge3;
        number++;
    }
    return number;
}

static void Main(string[] args)
{
    Console.WriteLine(FibHugesUntil(BigInteger.Zero, BigInteger.One, 1000));
}

答案:4782