这几天比较忙,所以没有及时回复,抱歉

基本上都没有问题.

I喜欢C版主的的确如11楼所说少了点.
16楼效率故然很高,但所占的空间似乎太大,大家再想想看能不能找到一种能够达到题目的效率又不会使用这么大的空间的算法

另外题目好像出的比较简单,在加一个给大家热热身

大家不要觉得自己英语不好,大家本来英语都不好,都是自己积累的,我四级都没过,现在用英文的操作系统,做英文题目,不懂就去查,多用几次就记住了,其实学电脑可以学到很多英语的东西,大家不防试试,比那些整天拿着一本厚厚的字典背单词强多了,英语是一个积累的过程,有不懂的就问,给大家一个在线词典的网站
http://www.iciba.com/

遇到不懂的英语单词到这去查一般都有解释,如果还是不懂意思,就到论坛上来问

第三题
最先想到的是DP,但不知道怎么写,然后用深搜了下,但是发现当n>=600时速度很慢
#include<iostream>
using namespace std;
int a[11]={1,2,4,8,16,32,64,128,256,512,1024};
int sum;
void dfs(int u,int cnt)
{
int i;
if(a[u]==1) {sum++;return;}
for(i=cnt/a[u];i>=0;i--)
{
if(cnt-a[u]*i>0)
dfs(u-1,cnt-a[u]*i);
else sum++;
}
}
int main()
{
int i,j,k,n;
while(cin >> n)
{
for(k=0;k<11;k++)
if(a[k]>n) break;
sum=0;
dfs(k-1,n);
cout << sum << endl;

}
}

我的也很慢，但比你的快

#include <stdio.h>

#define N 64

int f(int position, int number, int *flag)
{
int i;
unsigned long sum = 0;

if (position == 1)
return number + 1;

for (i = 0; i <= number; i++)
sum += f(position - 1, (number-i) * 2 + flag[position-1], flag);

return sum;
}

int main()
{
int flag[N] = {0};
int i;
unsigned int n;

scanf("%d", &n);
for (i = 0; i < sizeof(unsigned int) * 8; i++)
if (n & (1U << i))
flag[i] = 1;
for (i = N - 1; i >= 0; i--)
if (flag[i])
break;
printf("%d", f(i, 1, flag));
printf("\n");

return 0;
}

哈哈，现在改成非递归的了，速度飞快

#include <stdio.h>

#define N 10
#define M 1000U

unsigned long f(int *flag, int pos)
{
int i, j, k;
unsigned long count[N][M+1] = {0};

for (i = 0; i <= pos; i++)
for (j = 0; j <= M / (1U<<i); j++)
{
if (i == 0)
count[i][j] = 1;
else
{
for (k = 0; k <= j; k++)
count[i][j] += count[i-1][(j-k)*2 + flag[i-1]];

}
}
return count[pos][1];
}

int main()
{
int i;
unsigned int n;

while (scanf("%d", &n) != EOF)
{
int flag[N] = {0};
for (i = 0; i < N; i++)
if (n & (1U << i))
flag[i] = 1;
for (i = N - 1; i >= 0; i--)
if (flag[i])
break;
printf("%ld\n", f(flag, i));
}

return 0;
}

[此贴子已经被作者于2007-4-21 21:36:28编辑过]

第一题:

#include<stdio.h>
#include<math.h>
int a[168]={2};

void init(void) //储存1000内的素数
{
int i,j,k=1,sure=1;
for(j=3;j<1000;j++)
{
for(i=2;i<=sqrt(j);i++)
if(j%i==0)
{
sure=0;
break;
}
if(sure)
a[k++]=j;
sure=1;
}
}

int prime(long n) //判断是否为素数
{
int i;
if(n<2)
return 0;
if(n==2)
return 1;
for(i=0;i<168;i++)
{
if(a[i]>sqrt(n))
break;
if(n%a[i]==0)
return 0;
}
return 1;
}

int main(void)
{
long n,i;
init();
while(scanf("%ld",&n))
{
for(i=3;;i++)
if(prime(i))
if(prime(n-i))
{ printf("%ld=%d+%ld\n",n,i,n-i);
break;
}
}
return 0;
}

第三题(只适合2N以内的数)

#include <stdio.h>
#define N 501 为了算更大的数,将N定义得更大点,不过空间方面就浪费了

int a[N]={0};
void init(void) //初始化先算出1000以内的数的种数,存储在数组中
{
int i;
for(i=0;i<N;i++)
{
if(i==0)
a[i]=1;
else
if(i==1)
a[i]=2;
else
a[i]=a[i-1]+a[i/2];
}

}

int main(void)
{
int n;
init();
while(scanf("%d",&n))
printf("%d\n",a[n/2]); //2N与2N+1是一样的.
return 0;
}

第二题我还在找一种使得空间和时间方面最佳的情况,暂不发上来

[此贴子已经被作者于2007-4-22 9:03:23编辑过]