UC知道有关递归效率
来源：百度知道 编辑：UC知道 时间：2024/06/08 03:55:02
题目如下,要求输入=10000,=999要在短时间内算出,我试了一下递归,几乎算不出,望高手指点~
Function f( n ) is recursively defined as:
f( n ) = f(n-1) + f(n-3), n > 3
f( n ) = n, n <= 3
Write a program to calculate f( n ) modulo m.
n <= 10000, 2 <= m <= 10000.
Hint
If n is a negative number, use (n % m + m) % m to calculate n modulo m.
Input
There are multiple test cases. Each test case consists of two integers: n and m. n = 0 and m = 0 denotes the end of input, and you should not process this case.
Output
For each test case, print f( n ) modulo m in a single line.
Sample Input
1 2
10000 999
0 0Sample Output
1
433
Function f( n ) is recursively defined as:
f( n ) = f(n-1) + f(n-3), n > 3
f( n ) = n, n <= 3
Write a program to calculate f( n ) modulo m.
n <= 10000, 2 <= m <= 10000.
Hint
If n is a negative number, use (n % m + m) % m to calculate n modulo m.
Input
There are multiple test cases. Each test case consists of two integers: n and m. n = 0 and m = 0 denotes the end of input, and you should not process this case.
Output
For each test case, print f( n ) modulo m in a single line.
Sample Input
1 2
10000 999
0 0Sample Output
1
433
这个堆栈肯定不会溢出的，关键是运用动态规划思想，算过的数就记录下来，下次如果再算它就可以直接返回值就可以了。
#include <cstdio>
int n, m, f[ 10001 ];
int work( int p )
{
if ( f[ p ] != -1 )
return f[ p ];
return f[ p ] = ( work( p - 3 ) + work( p - 1 ) ) % m;
}
int main( )
{
int i;
while ( scanf("%d%d", &n, &m) != EOF )
{
if ( n == 0 && m == 0 )
break;
for ( i = 1; i <= 3; i++ )
f[ i ] = i % m;
for ( i = 4; i <= n; i++ )
f[ i ] = -1;
&nb