# Q：bytelandian金币的解释吗？[重复]

I was trying The Bytelandian Gold coin problem mentioned here - http://www.codechef.com/problems/COINS/ here is one of its solution-

``````#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];
}
``````

In this code I cannot understand two points- 1-the size of array a[30][19] which is based on the maximum number of times the maximum value of the input number is divisible by 2 or 3 for which they use some log base 2 or 3 formula to find.Can someone please explain this formula,is this some mathematical property if yes where can I find more information about it. 2-to stop the recursion n<12 condition was used as all numbers below 12 will have values equal to itself as max value.I cannot understand how it was found.I mean how they find 12 is the limiting value also if I replaced the original recur function with this I get wrong answer-

``````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 would be grateful if someone please explains the above 2 points

``````#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];
}
``````

In this code I cannot understand two points- 1-the size of array a[30][19] which is based on the maximum number of times the maximum value of the input number is divisible by 2 or 3 for which they use some log base 2 or 3 formula to find.Can someone please explain this formula,is this some mathematical property if yes where can I find more information about it. 2-to stop the recursion n<12 condition was used as all numbers below 12 will have values equal to itself as max value.I cannot understand how it was found.I mean how they find 12 is the limiting value also if I replaced the original recur function with this I get wrong answer-

``````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];
}
``````

1. An upper limit for i results from the condition 2i ≤ 109 (the number of times 109 can be divided by 2 until reaching 1 is equal to the number of times 1 can be multiplied by 2 until reaching 109); solving for i yields i ≤ log2(109) ≅ 29.9.
Another way to look at it is by expressing 109 as a binary number 1110111001101011001010000000002; this number has 30 digits, each integer division by 2 yields one digit less (removing the rightmost digit), so after 29 divisions we arrive at 1.
As JohnH correctly stated in his comment above, the maximum value of i is still lower than 29, because the recursion doesn't go down to n &equals; 1, but stops at n < 12.
About the same goes for the upper limit of j and division by 3. 109 as a ternary number is 21202002000210100013; this number has 19 digits; after 17 integer divisions by 3 we arrive at 213 &equals; 7, where the recursion stops.

2. To find out that all numbers below 12 are equal to their maximum exchange amount, we can simply try them all out:

``` n  n/2  n/3  n/4  sum of the 3 exchanged coins
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
```

We see that 12 is the lowest number that yields a value higher than itself when exchanged.

if I replaced the original recur function with this I get wrong answer-

From n &equals; 509607936 on you get "wrong answer" because long int t etc. overflows to negative values. Curiously enough, with the original recur function this error is compensated by another error, namely the wrong conversion specification %lld noted by BLUEPIXY. The program can be corrected by defining a, recur, t and v with type unsigned long int and using the appropriate conversion specification %lu.

1. An upper limit for i results from the condition 2i ≤ 109 (the number of times 109 can be divided by 2 until reaching 1 is equal to the number of times 1 can be multiplied by 2 until reaching 109); solving for i yields i ≤ log2(109) ≅ 29.9.
Another way to look at it is by expressing 109 as a binary number 1110111001101011001010000000002; this number has 30 digits, each integer division by 2 yields one digit less (removing the rightmost digit), so after 29 divisions we arrive at 1.
As JohnH correctly stated in his comment above, the maximum value of i is still lower than 29, because the recursion doesn't go down to n &equals; 1, but stops at n < 12.
About the same goes for the upper limit of j and division by 3. 109 as a ternary number is 21202002000210100013; this number has 19 digits; after 17 integer divisions by 3 we arrive at 213 &equals; 7, where the recursion stops.

2. 若要找出低于12的所有数字等于它们的最大交换量，我们可以简单地尝试它们：

``` n  n/2  n/3  n/4  sum of the 3 exchanged coins
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是在交换时产生高于自身值的最低数字。

if I replaced the original recur function with this I get wrong answer-

从N &；等于；509607936你得到错误的答案“因为long int t等负面价值溢出。奇怪的是，与原来的发生函数这个错误是由另一个误差补偿，即错误的转换规格为LLD指出的bluepixy。该程序可以进行定义，复发，T和V型无符号长整型数和使用适当的转换规格%lu。

c  recursion  dynamic-programming  memoization