题目:
对任何一个正整数 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");//输出格式的要求
因为排序出了错而报错了,要重新好好研究一下排序了…基本功太汗颜了
本文来自网络收集，不代表计算机技术网立场，如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址：https://www.ctvol.com/c-cdevelopment/604536.html