工大后院

标题: 空间换取时间题目,大家来研究下 [打印本页]

---

作者: 小康    时间: 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[l];
int add(int n)
{
        int i,j;
        if(n<l)
        if(s[n]>-1) return s[n];
        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[n]=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;

}

---

欢迎光临 工大后院 (https://www.gdutbbs.com/)

Powered by Discuz! X3.5