菜鸟记

题目:

对任何一个正整数 n，如果它是偶数，那么把它砍掉一半；如果它是奇数，那么把 (3n+1) 砍掉一半。

 

当我们验证卡拉兹猜想的时候，为了避免重复计算，可以记录下递推过程中遇到的每一个数。例如对 n=3 进行验证的时候，我们需要计算 3、5、8、4、2、1，则当我们对 n=5、8、4、2 进行验证的时候，就可以直接判定卡拉兹猜想的真伪，而不需要重复计算，因为这 4 个数已经在验证3的时候遇到过了，我们称 5、8、4、2 是被 3“覆盖”的数。我们称一个数列中的某个数 n 为“关键数”，如果 n 不能被数列中的其他数字所覆盖。

现在给定一系列待验证的数字，我们只需要验证其中的几个关键数，就可以不必再重复验证余下的数字。你的任务就是找出这些关键数字，并按从大到小的顺序输出它们。

 

思路:

一开始是没有清晰的思路的,在纸上做下草稿,发现关键的点在于如何判定覆盖以及判定覆盖后怎样进行处理?那就用一个很笨的办法

1.设定一个数组用来存放每个数验证时所需计算的数字,然后将其和已知数列一一比较

2.比较过后将原数列中被覆盖的数置零,从这点又引申出来的想法是在第一层循环中加入if判定是否为零,若为零可直接跳过比较,这样也省去了不必要的步骤

递推过程函数较为简单,传入n(给定数列的个数),比较数组(copy[]),返回值为int,即递推过程中的数的个数

int callatz(int n,int copy[]){

    int i = 0;

    do{

        if(n%2==0)  n = n/2;

        else n = (n*3+1)/2;

        copy[i++] = n;

    }while (n!=1);

    i = i-1;

    return i;

}

 

 

主函数,题目要求是将结果从大到小顺序输出,那首先要把它们找出来放到数组里,用循环来搞定

 

 

   int n;

    (void)scanf("%d",&n);

    int str[n];//存放已知数列

    int copy[size];//存放递推过程里的数

    for(int i = 0;i < n;i++){

        (void)scanf("%d",&str[i]);

    }

    for(int y = 0;y < n;y++){

        if(str[y]!=0){//判定是否为零,为零说明该数已被覆盖

            int size = callatz(str[y], copy);//递推过程中数的个数

　　　　//开始和已知数列比较,同时更新已知数列

            for(int i = 0;i < size;i++){

                for(int z = 0;z < n;z++){

                    if(str[z]==copy[i])

                        str[z] = 0;

                }

            }

        }        

    }

 

然后定义一个新数组存放结果,进行排序然后输出

  

    int z = 0;

    int new[n];

    for(int i = 0;i < n;i++){

        if(str[i]!=0)

            new[z++] =str[i];

    }

   //排序 最简单的选择排序....

    int min = 0,temp;

    

    for(int i = 0;i < z-1;i++){

        temp = i;

        for(int j = i+1;j <z;j++){

            if(new[j] > new[temp]){

                temp = j;

            }

        }

        min = new[i];

        new[i] = new[temp];

        new[temp] = min;

    }

    int i = 0;

    for(i = 0;i < z-1;i++){

        printf("%d ",new[i]);

    }

    printf("%d",new[z-1]);

    printf("\n");//输出格式的要求

 

 

因为排序出了错而报错了,要重新好好研究一下排序了...基本功太汗颜了