c - Bytelandian金币的解释？

This question already has answers here:

Closed 3 years ago.

Bytelandian Gold Coin , Dynamic programming , explanation?
（3个答案）
我在试着解决这里提到的拜特兰迪金币问题-http://www.codechef.com/problems/COINS/这里是它的一个解决方案-

#include <stdio.h>
long int a[30][19];  //1
long int recur(long int n, int i, int j);
int main()
{
    long int n;
    int i, j;
    while (scanf("%lld", &n) != EOF)
    {
        for (i = 0; i < 30;i++)
        for (j = 0; j < 19; j++)
            a[i][j] = 0;
        long int v = recur(n, 0, 0);
        printf("%lld\n", v);
    }
    return 0;
}
long int recur(long int n, int i, int j)
{
    if (n <12 )  //2
        return n;
    else if (!a[i][j])
    {
        long int t = recur(n / 2, i + 1, j) + recur(n / 3, i, j + 1) + recur(n / 4, i + 2, j);
        a[i][j] = t;
    }

    return a[i][j];
}

在这段代码中，我不能理解两点-
1数组A（30）〔19〕的大小是基于输入数的最大值的最大次数可被2或3整除的，它们使用一些对数基2或3公式来寻找。有人能解释这个公式吗？这是一些数学性质，如果是的话，我能在哪里找到关于它的更多信息。
2-为了停止递归，使用了n

long int recur(long int n, int i, int j)
{
    if ((n == 0) || (n == 1) || (n == 2) )
        return n;
    else if (!a[i][j])
    {
        long int t = recur(n / 2, i + 1, j) + recur(n / 3, i, j + 1) + recur(n / 4, i + 2, j);
        a[i][j] = n> t ? n : t;
    }

    return a[i][j];
}

如果有人能解释一下以上两点，我将不胜感激

最佳答案

i的上限是由条件2i≤109得出的（109的次数可以除以2，直到达到1等于1的次数可以乘以2，直到达到109）；求解i得到i≤log2（109）≅29.9。
另一种方法是将109表示为二进制数1110110111011001010000000002；这个数字有30个数字，每个整数除以2得到的结果是少一个数字（去掉最右边的数字），所以在29个除法之后我们得到1。
正如JohnH在上面的评论中正确地指出的，i的最大值仍然低于29，因为递归不降到n＝1，而是在n＜12时停止。
j的上限和除以3的情况也差不多。109作为三元数是21202002000210100013；这个数有19位；经过17个整数除以3，我们得到213=7，递归停止。
为了找出低于12的所有数字等于它们的最大交换量，我们可以简单地尝试它们全部出来：
n n/2 n/3 n/4三个交换硬币之和
1 0 0 0 0
2 1 0 0 1
3 1 1 0 2
4 2 1 1 4
5 2 1 1 4年
6 3 2 1 6
7 3 2 1 6
8 4 2 2 8年
9 4 3 2 9年
10 5 3 2 10
11 5 3 2 10年
12 6 4 3 13年
我们看到，当交换时，12是产生高于自身的值的最低数。
如果我用这个替换了原来的递归函数，我就错了
回答-
从n=509607936开始，你会得到“错误的答案”，因为long int t等会溢出到负值。奇怪的是，使用最初的recur函数，这个错误被另一个错误补偿，即BLUEPIXY指出的错误转换规范%lld。该程序可以通过用a类型定义recur、t、v和unsigned long int并使用适当的转换规范%lu来修正。