论坛 › 【编程】编程圣殿 › 空间换取时间题目,大家来研究下

小康 发表于 2005-7-25 23:26

空间换取时间题目,大家来研究下

http://acm.zju.edu.cn/show_problem.php?pid=1539

0.26秒
#include<stdio.h>
int add(int n)
{
        int i,j;
        if(n<3) return 0;
        else if(n==3) return 1;
        else
        {
                i=n/2;
                j=n-i;
                i=add(i);
                j=add(j);
                return i+j;

        }
}
int main()
{
        int i,j,k,n;
        while (scanf("%d",&n)!=EOF)
        {
                printf("%d\n",add(n));
        }
        return 0;

}

小康 发表于 2005-7-25 23:30

0秒
#include<stdio.h>
const int l=10000;
int s;
int add(int n)
{
        int i,j;
        if(n<l)
        if(s>-1) return s;
        if(n<3) return 0;
        else if(n==3) return 1;
        else
        {
                i=n/2;
                j=n-i;
                i=add(i);
                j=add(j);
                if(n<l)
                s=i+j;
                return i+j;

        }
}
int main()
{
        int i,j,k,n;
        for (i=0;i<l;i++) s=-1;
        while (scanf(\"%d\",&n)!=EOF)
        {
                printf(\"%d\\n\",add(n));
        }
        return 0;

}

查看完整版本: 空间换取时间题目,大家来研究下