一个递推分数数列的构成规律为: 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项中的最大项
水平有限,不容易看懂啊
追答嗯,好吧,大概说一下自己的想法:
首先为了要求出每次的C,所以需要把已经出现过的c和d都给记录下来,
所以开一个int数组(其实应该开bool数组,不过好像有些C语言编译器不支持bool?)。
开始的时候初始化成全0,然后每次求出c、d,就把他们的位置置1;
选c的方法是扫描那个标记数组,从头开始找到第一个内容为0(未出现过)的数。
关于这个数组的大小,由于n最大是3000,因此c不会取到6000以上的数,因此这样开。
所以在每次把c、d填成1的时候要防止越界。
就这样循环上n次,顺便记录最大数的分子和分母,循环完毕后就有了结果。