Question

一个程序设计的问题请教，一个递推分数数列的构成规律为: 1/2, 3/5, 4/7, 6/10,...。C语言实现！

一个递推分数数列的构成规律为: 1/2, 3/5, 4/7, 6/10,...。设每一项的分子c与分母d(c、d为正整数),第i项的分母d与分子c存在以下关系:d=c+i；而c为与前i-1项中的所有分子分母均不相同的最小正整数。
求出该数列的第n(1<n<3000)项,并求出前n项中的最大项。
注：标准输入设备输入 n。

【样例输入】
1000
【样例输出】
1618/2618 //第n项
987/1597 //前n项中的最大项

Answer 1

#include<stdio.h>
int sign[6002] = {0};
int main()
{
int n,c=1,d,i,max_c=1,max_d=2;
float tmp1,tmp2;
sign[1] = sign[2] = 1;
tmp2 = max_c*1.0/max_d;
scanf("%i",&n);
for(i=2;i<=n;i++)
{
for(int j=1;j<=6002;j++)
{
if(!sign[j])
{
c = j;
break;
}
}
d = c+i;
tmp1 = c*1.0/d;
if(tmp2<tmp1)
{
max_c = c;
max_d = d;
tmp2 = max_c*1.0/max_d;
}
if(c<6002)
sign[c] = 1;
if(d<6002)
sign[d] = 1;
}
printf("%i/%i\n",c,d);
printf("%i/%i",max_c,max_d);
return 0;
}
代码略丑，见谅，复杂度虽然不好看，不过这题好像3000也只要19毫秒而已。

追问

水平有限，不容易看懂啊

追答

嗯，好吧，大概说一下自己的想法：
首先为了要求出每次的C，所以需要把已经出现过的c和d都给记录下来，
所以开一个int数组（其实应该开bool数组，不过好像有些C语言编译器不支持bool？）。
开始的时候初始化成全0，然后每次求出c、d，就把他们的位置置1；
选c的方法是扫描那个标记数组，从头开始找到第一个内容为0（未出现过）的数。
关于这个数组的大小，由于n最大是3000，因此c不会取到6000以上的数，因此这样开。
所以在每次把c、d填成1的时候要防止越界。
就这样循环上n次，顺便记录最大数的分子和分母，循环完毕后就有了结果。