1005. 继续(3n+1)猜想pat-Java

C++ PAT1005“继续3n+1猜想” 两个测试点不通过~

唯一错的一点就是没有排序，其他的都没错

思路应该就是这样的，没有错误

UVa3n+1问题1.问题描述编号:100.简单描述:就是对一个整数(大于等于1),不断按照这样的规律进行运算,即如果当前数是偶数,则下一个数为当前数除以2,如果当前数为奇数,则下一个数为当前数乘3加1,整个过程直到计算到1为止.那么形成的数列的长度称为cycle-length.问题的输入是:给定一个区间[a,b]问题的输出为:输出给定区间(含端点)所以数的cycle-length的最大的cycle-length.详细描述可参见这里.2.问题分析2.1直观分析最直观的方法当然是采用蛮力法(即brute-force),将给定区间的每个数求出其cycle-length,然后在所以的cycle-length中找出最大的即可.2.2优化优化是建立在分析的基础之上.我们先对一个简单例子进行实验.例如给定区间为B[1,10],即1,2,3,4,5,6,7,8,9,10通过简单分析我们可以知道,通常较大的数具有较大的cycle-length,所以我们可以首先取A=9(为什么不取10,是因为9在一次处理后可变为28,大于10)按照给定的规律来进行如下:928147221134175226134020105168421可以看出,上面红色标记的部分,处于给定的区间内,而且它们的cycle-length显然是小于当前的数9的cycle-length,所以这些数可以从给定的区间内剔除掉,记住当前的cycle-length,于是经过一次的操作后,给定的区间变为3,6继续按照这个方法进行,直至这个区间为空,停止,其中最大的cycle-length即为所求.2.3得出算法算法的描述同2.2处优化部分的分析,具体的算法描述可见3.3.算法描述算法伪代码(类C)描述如下:functiongetMCLB[left,right];//为给定的区间mcl=0;//mcl指max-cycle-lengthwhile!B.empty(){A=getCandidate(B);//这个函数是用来找出B区间内当前最适合处理的元素,//一般是最大的奇数,即预计可能具有较大cycle-length的元素ccl=1;//ccl是指current-cycle-lengthwhile(A!=1){ccl++;A=(A%2)?(3*A+1):(A/2);iffind(B,A)//这个函数是用来判断B区间内是否存在中间结果Apop(B,A);//有则剔除}mcl=(mcl4.具体实现Cpp代码#include"iostream"usingnamespacestd;intgetCandidate(intB[],intbase,intn){inti;for(i=n-1;i>=0;i--){if(((base+i)%2)&&(B[i]==0))returni;}for(i=n-1;i>=0;i--){if(!B[i])returni;}return-1;}intnadd2(intleft,intright){intBlength=right-left+1;intlength=Blength;int*B=newint[length];for(inti=0;i0){intccl=1;intpos=getCandidate(B,left,Blength);if(pos==-1)break;B[pos]=1;length--;intA=pos+left;while(A!=1){ccl++;A=(A%2)?(3*A+1):(A/2);intApos;if((A-left>Blength)||(B[A-left])||(A>left>>right)cout5.复杂性分析主要的耗时部分是二层循环部分,而外层循环的次数主要取决于内层循环在区间内的命中率.没有进行过统计学的分析,但只要candidate选取合适,每次内层循环会有大于50%的命中率.假设区间内数A的内层循环次数(即由A按照规则变为1的cycle-length)为X,平均命中率为p,那么时间复杂度为:T(n)=X*T(n*(1-p))//其中X为平均的cycle-length6.备注在实现过程中,最初使用的是C++中的vector,但运行时的实际耗时比使用数组的蛮力法还要长,经过分析,这是因为编译器在维护vector这个数据结构时所耗时长是比较大的,特别是当使用vector的earse方法来删除某个特定元素时.所以最后还是使用最基本的数组来实现,用标记来指示删除状态.所以在实际的算法实现中,数据结构的选取也是非常重要的,所谓的程序=算法+数据结构是也.可以改进的地方包括有:getCandidate函数的算法,即如何预估一个具有较长cycle-length的元素;还有当内层循环出现在区间内已标记为删除状态的元素中时,这时内层循环可终止.

---

萝北县13249946422： 1005. 继续(3n+1)猜想pat - Java - ？
五索伏络： UVa3n+1问题1.问题描述编号:100.简单描述:就是对一个整数(大于等于1),不断按照这样的规律进行运算,即如果当前数是偶数,则下一个数为当前数除以2,如果当前数为奇数,则下一个数为当前数乘3加1,整个过程直到计算到1为止....

萝北县13249946422： 1005. 继续(3n+1)猜想 (25) 浙大PAT java写的 请教 急急急急急急急急 - ？
五索伏络： 你看看我的吧 private static int []nums; private static int []nums2; public static int[] toTest(int [] nums){ for (int i = 0; iwhile(nums[i]!=1){ if(nums[i]%2==0){ nums[i] = nums[i] /2; removeNum(nums[i]); }else{ nums[i] = (nums[i] *3+1)/2; removeNum(nums[i]);...

萝北县13249946422： C++ PAT1005“继续3n+1猜想” 两个测试点不通过 - ？
五索伏络： 唯一错的一点就是没有排序,其他的都没错

萝北县13249946422： 考拉兹猜想又名3n+1猜想,是指对于每一个正整数,如果它是奇数,则对它乘3再加1;如果它是偶数,则对它除以2.如此循环,最终都能得到1.阅读如图所... - ？
五索伏络：[选项] A. 4 B. 5 C. 6 D. 7

萝北县13249946422： 【3n+1】问题:猜想:对任意大于1的自然数n,若n为奇数,则将n变为3n+1,否则变为n的一半.经过若干次这样的变换,一定会使n变为1.例如:3→10→5... - ？
五索伏络：[答案] 可以设计一个算法将算出的结果拆成几段数字放到数组里,这样就不会出现乘法溢出的情况

萝北县13249946422： 3n+1问题 目前有被证明出来吗 - ？
五索伏络： 因为这个问题常被称作冰雹猜想我怕有人不知道这个名字先赘述一下.“3n+1问题是一个简单有趣而又没有解决的数学问题.这个问题是由L. Collatz在1937年提出的.克拉兹问题(Collatz problem)也被叫做hailstone问题、3n+1问题、Hasse算法问题、Kakutani算法问题、Thwaites猜想或者Ulam问题.问题如下:(1)输入一个正整数n;(2)如果n=1则结束;(3)如果n是奇数,则n变为3n+1,否则n变为n/2;(4)转入第(2)步.” 那么是否对任意的n,都能在有限步内结束呢?该问题于2017年由郝生旺给出直接证明.但我还没有看过,我不能保证它的正确性.就转载范围来看似乎有点小?

萝北县13249946422： 高中数学:{y|y=3n+1,n属于Z}与{y|y=3p - 2,p属于Z}为什么表示的是同一个集合?请说明理由.希望是具体的! - ？
五索伏络： 当n=p时,(3n+1)=(3p-2)+3,而3n和3p是3的倍数,所以只要n=p+1,就有3p-2=3n+1,而n,p属于Z,所以在整数范围内,任取一个p,总有n=p+1,使3p-2=3n+1,所以这两个集合相等

萝北县13249946422： 一道数学归纳法题求解？
五索伏络： 解:(1)根据已知条件可得a3=1/4,a4=1/7,从而可猜想 an=1/(3n-2) (2)证明:由(1)猜想得an+1=1/(3n+1) bn=√an√a(n+1)/(√an+√a(n+1)) =1/[√(1/an)+√1/a(n+1)] =1/(√(3n+1)+√(3n-2)) =1/3*(√(3n+1)-√(3n-2)).............................此处为分子...

萝北县13249946422： 数列{AN}的通项公式是AN=1/(3N - 1)(3N+2),若前N项和为3/20,则项数N? - ？
五索伏络： 解:AN=1/(3N-1)(3N+2)= [1/(3N-1)-1/(3N+2)]*(1/3) 所以,前N项和=(1/3)[1/2-1/5+1/5-1/8+1/8-1/11+......+1/(3N-1)-1/(3N+2)] =(1/3)[1/2-1/(3N+2)] =(1/3)*(3N)/(6N+4)=3/20 N/(6N+4)=3/20 20N=18N+12 N=6

萝北县13249946422： 从第3项到第n+1项 共有多少项 - ？
五索伏络： 3-1=2:从第一项到第三项,一共是三项,从题目得知从第三项起,实则三项中减去第三项本身还剩下两项,是不计算在总共项的个数中;本身第n项的n可以确定是下标,即表明了项的个数.假设我们带入,n=3,那么n+1-(3-1)=2,也就是第三项和第四项,即共有两项;n=4,那么n+1-(3-1)=3,也就是第三项、第四项和第五项,即共有三项;由此可得出通项式n+1-(3-1)=n-1.所以第三项到第n+1项 ,共有n-1项.