为什么最后两个测试点不对,下面是代码

Question

import java.util.*;import java.io.*;public class Main {public static void main(String arg[])throws IOException{Reader.init(System.in);PrintStream out=new PrintStream(System.out);int k=Reader.nextInt();int sr[]=new int[k];boolean pd[]=new boolean[150];int i,j,n=0;for(i=0;i<k;i++) sr[i]=Reader.nextInt();for(i=0;i<150;i++) pd[i]=false;i=0;while(i!=k){if(pd[sr[i]]==false){j=sr[i];while(pd[1]==false){if(j%2==0) j=j/2;else j=(3*j+1)/2;pd[j]=true;}pd[1]=false;}i++;}for(i=0;i<k;i++)//递减排序{for(n=i+1;n<k;n++){if(sr[i]<sr[n]){int temp;temp=sr[i];sr[i]=sr[n];sr[n]=temp;}}}for(i=0,n=0;i<k;i++) if(pd[sr[i]]==false) n++; for(i=0;i<k;i++){if(pd[sr[i]]==false){out.print(sr[i]);if(n!=1) out.print(" ");out.flush();n--;}}//保证末尾无空格}public static class Reader{  static BufferedReader reader; static StringTokenizer tokenizer; static void init(InputStream input){reader=new BufferedReader(new InputStreamReader(input));tokenizer=new StringTokenizer("");}static String next() throws IOException{while(!tokenizer.hasMoreTokens()){tokenizer = new StringTokenizer(reader.readLine());}return tokenizer.nextToken();}static int nextInt()throws IOException{return Integer.parseInt(next());}static double nextDouble() throws IOException{return Double.parseDouble(next());}}  }

Answer 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的元素;还有当内层循环出现在区间内已标记为删除状态的元素中时,这时内层循环可终止.