首页 > 代码库 > 递归的美妙

递归的美妙

分数序列

问题的提出:

1/2,3/5,4/7,6/10,8/13,9/15....上述的数列的规律:

1:第i项的分母d与分子c的关系是d = c+i.

2:第i项的分子c与前i-1项的分子分母都不相同。

试着求出第2010项,并求出前 2010项中的最大项。

设计:

设置数组c(i)表示第i项的分子,数组d(i)表示分母,初始值c(1) = 1,d(1) = 2.

已知前i-1项的时候如何确定c(i)?显而易见c(i) > c(i-1),通过上述的数列可以知道第i项的分子总是小于第i-1项的分母。

设置k在区间(c(i-1),d(i-1))取值,k分别与分母的每一项比较如果有相同,就k加一再比较,如果没有相同的就产生第i项作赋值:c(i) = k,d(i) = k+i.

求前n项的最大项,设置最大项是第x项(x赋值为1)每次产生第i项如果有c(i)/d(i) > c(x)/d(x)就 x = i

import java.util.Scanner;public class Main {    /**     * @param args     */    private static int c[] = new int [3001];//表示分子    private static int d[] = new int [3001];//表示分母    private static int max;//最大项    public static void main(String[] args) {        Scanner input = new Scanner(System.in);        System.out.println("请输入一个(1-3000)的数字");        int number = input.nextInt();        c[1] = 1;        d[1] = 2;        c[2] = 3;        d[2] = 5;        max = 1;//假设第一项是最大项        for(int i = 3;i<=number;i++)        {            for(int k = c[i-1]+1;k<d[i-1];k++)            {                int t=0;                for(int j=1;j<=i-1;j++)                {                    if(k == d[j])                    {                        t=1;                        break;                    }                }                if(t == 0)                {                    c[i] = k;                    d[i] = k+i;                    break;                }            }            if(c[i] * d[max] >c[max]*d[i])//找最大项            {                max = i;            }                    }                        //输出        System.out.println("第"+number+"为"+c[number]+"/"+d[number]);        System.out.println("输出第"+max+"项是最大项");        for(int i = 1;i<=number;i++)        {            if(c[i] * d[max]==c[max]*d[i])            {                System.out.println("第"+i+"项是最大项:"+c[i]+"/"+d[i]);            }        }            }}

测试结果:

请输入一个(1-3000)的数字
2010
第2010为3252/5262
输出第1597项是最大项
第1597项是最大项:2584/4181

 

 

 

递归的美妙