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.

#include<stdio.h>
long f(long n)
{   long p;
    if(n<3) p=n;
    else p=f(n-1)+f(n-3);
    return p;
}
int main()
{
    long n,m,a;
    while(scanf("%ld%ld",&n,&m)&&(n||m))
    {
        while((n<1)||(n>10000)||(m>10000)||(m<2))
        {
            scanf("%ld%ld",&n,&m);
        }
        a=f(n);
        printf("%ld\n",a%m);
    }
    return 0;
}
n>=50就卡住了

这个一定要注意栈的大小！（很容易耗尽）

把递归改为非递归的算法！！！

怎么改啊

#include <stdio.h>
int main()
{
    int n,m,a,b,c,d,i;
    while(scanf("%d%d",&n,&m)&&(m||n))
    {
        while((n<1)||(n>10000)||(m>10000)||(m<2))
            scanf("%d%d",&n,&m);
        if(n<=3) printf("%d\n",n%m);
        else
        {
            a=1;
            b=2;
            c=3;
            for(i=0; i<n-3; i++)
            {
                d=a+c;
                a=b;
                b=c;
                c=c+a;
            }
            printf("%d\n",d%m);
        }
    }
    return 0;
}

改了一下好像又错了

[ 本帖最后由 septemp 于 2010-10-31 08:41 编辑 ]

#include <stdio.h>
#define N 1000
int main()
{
    int a[N];
    int m,n;
    while(scanf("%d%d",&n,&m)&&(m||n))
    {
        if((n<1)||(n>10000)||(m>10000)||(m<2))
        {
            fflush(stdin);
            printf("error,please input again!\n");
            continue;
        }
        else if(n<=3)
        {
            printf("%d\n",n%m);
        }
        else
        {
            a[1]=1;
            a[2]=2;
            a[3]=3;
            int i;
            for( i=4;i<=n;i++)
                a[i]=a[i-1]+a[i-3];
            printf("%d\n",a[i-1]%m);
        }
    }
}

这样就可以算出n在1000的范围内