c# - 查找帕多万数的优化方法

Question

找到Padovan number 的最优化方法是什么？ ？这就是我目前所拥有的。即使它返回正确的结果，我也想知道最快的方法是什么。

        long Sum = 0;
        public long Get(int number)
        {
            Sum = 0;      
            if (number == 0 || number == 1 || number == 2)
                return 1;
            return GetPadovanAlt(number);
        }

        public long GetPadovanAlt(int n)
        {
          if(n == 0 || n == 1 || n == 2)
          return 1;
          return GetPadovanAlt(n - 2) + GetPadovanAlt(n - 3);

        }

Answer 1

Ol' For 循环可能不像递归那么花哨。
但如果它完成了工作，就没有理由看不起它。

public static BigInteger GetPadovan(int n)
{
    if (n > 156 || n < -316) return GetBigPadovan(n);
    return GetSmallPadovan(n);
}

static BigInteger GetBigPadovan(int n)
{
    if (n == 0) return 1;
    if (n == 1 || n == 2) return 1;

    BigInteger padovan = 0, prev1 = 1, prev2 = 1, prev3 = 1;
            
    if (n > 2)
    {
        for (var i = 2; i < n; i++)
        {
            padovan = prev2 + prev3;
            prev3 = prev2;
            prev2 = prev1;
            prev1 = padovan;
        }
    }
    else if (n < 0)
    {
        for (var i = 0; i > n; i--)
        {
            padovan = prev3 - prev1;
            prev3 = prev2;
            prev2 = prev1;
            prev1 = padovan;
        }
    }

    return padovan;
}

static long GetSmallPadovan(int n)
{
    if (n == 0) return 1;
    if (n == 1 || n == 2) return 1;
    if (n > 156 || n < -316) return 0;

    long padovan = 0, prev1 = 1, prev2 = 1, prev3 = 1;

    if (n > 2)
    {
        for (var i = 2; i < n; i++)
        {
            padovan = prev2 + prev3;
            prev3 = prev2;
            prev2 = prev1;
            prev1 = padovan;
        }
    }
    else if (n < 0)
    {
        for (var i = 0; i > n; i--)
        {
            padovan = prev3 - prev1;
            prev3 = prev2;
            prev2 = prev1;
            prev1 = padovan;
        }
    }

    return padovan;
}

该代码还将计算负数。
并且可以处理N大于156的P(N)
(因为 Int64 对于较大的 padovans 来说太小了)

测试:

for (var i = 0; i <= 21; i++) Console.Write("{0} ", GetPadovan(i)); 

重新测试 here

返回:

1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, 28, 37, 49, 65, 86, 114, 151, 200, 265,

其他方法

新的更快的递归:

通过使用参数，可以在不激增 fork 函数调用的情况下完成。使用 long 类型，因此 P(N) 仅适用于 -316 到 156 之间的 N。

static public long GetPadovanRecursive(int n, long prev1 = 1, long prev2 = 1, long prev3 = 1)
{
    if (n > 156 || n < -316) return 0;
    if (n > 2) return GetPadovanRecursive(--n, prev2 + prev3, prev1, prev2);
    if (n < 0) return GetPadovanRecursive(++n, prev3 - prev1, prev1, prev2);
    return prev1;
}

旧的慢速递归:

static public long GetPadovanSlowRecursive(int n)
{
    if (n == 0 || n == 1 || n == 2) return 1;
    if (n < 0 || n > 156) return 0;
    return GetPadovanSlowRecursive(n - 2) + GetPadovanSlowRecursive(n - 3);
}

二项式方法:

public static BigInteger GetPadovanBinomial(int n)
{
    BigInteger result = 0;
    int k = n + 2;
              
    for (int m = k/3; m <= k/2; m++)
    {
        result += GetBinomialCoefficient(m,(k-m*2));
    }
    return result;
}

public static BigInteger GetBinomialCoefficient(int n, int k)
{
    BigInteger result = 1;
    for (int i = 1; i <= k; i++)
    {
        result *= n - (k - i);
        result /= i;
    }
    return result;
}

组合方法:

这利用了一个特殊的事实，即 P(n) 是将 (n + 2) 写为 2 和 3 之和的方法数。

static BigInteger GetPadovanSumCombos(int n)
{
    if (n < 0) return 0;
    int m = n + 2;
    int min3 = m % 2;
    int max2 = (min3 == 0) ? m / 2 : (m / 2) - 1;
    BigInteger result = 0;

    var factorials = new BigInteger[min3 + max2 + 1];
    factorials[1] = 1;
    for (int i = 2; i <= min3 + max2; i++) factorials[i] = i*factorials[i-1];

    for (int m2 = max2, m3 = min3; m2 >= 0; m2 -= 3, m3 += 2)
    {
        if (m2 == 0||m3 == 0) result += 1;
        else if (m3 == 2) result += (((m2+1) * (m2 + 2)) / 2);
        else result += factorials[m2 + m3] / (factorials[m3] * factorials[m2]);
    }

    return result;
}

比较速度:

var timer = new System.Diagnostics.Stopwatch(); timer.Stop();
var padovan = new BigInteger();
int num = 72;

timer.Restart(); padovan = GetPadovanSlowRecursive(num); timer.Stop();
Console.WriteLine("GetPadovanSlowRecursive({0}):\t{1}\t{2,12:F6} ms", num, padovan, timer.Elapsed.TotalMilliseconds);

timer.Restart(); padovan = GetPadovanRecursive(num); timer.Stop();
Console.WriteLine("GetPadovanRecursive({0}):\t{1}\t{2,12:F6} ms", num, padovan, timer.Elapsed.TotalMilliseconds);

timer.Restart(); padovan = GetPadovanBinomial(num); timer.Stop();
Console.WriteLine("GetPadovanBinomial({0}):\t\t{1}\t{2,12:F6} ms", num, padovan, timer.Elapsed.TotalMilliseconds);

timer.Restart(); padovan = GetPadovanSumCombos(num); timer.Stop();
Console.WriteLine("GetPadovanSumCombos({0}):\t{1}\t{2,12:F6} ms", num, padovan, timer.Elapsed.TotalMilliseconds);

timer.Restart(); padovan = GetPadovan(num); timer.Stop();
Console.WriteLine("GetPadovan({0}):\t\t\t{1}\t{2,12:F6} ms", num, padovan, timer.Elapsed.TotalMilliseconds);

返回:

GetPadovanSlowRecursive(72):    448227521       13283,251300 ms
GetPadovanRecursive(72):        448227521           0,278300 ms
GetPadovanBinomial(72):         448227521           0,486300 ms
GetPadovanSumCombos(72):        448227521           0,722400 ms
GetPadovan(72):                 448227521           0,365900 ms