本文目录一览：
- 1、用Java写的pat 1002题格式出错（想知道Java写pat要注意什么呢）
- 2、用JAVA写出combination的算法： 在A,B,C,D,E中选出3个，列出所有可能的数组
- 3、浙大的PAT考试只能用C/C++吗？可不可以用JAVA
- 4、1005. 继续(3n+1)猜想pat-Java
用Java写的pat 1002题格式出错（想知道Java写pat要注意什么呢）
Java只有Oracle的认证，不过感觉没啥用，不受人重视。不管是我被面试，还是我面试别人，从没人问过。不如考国家的计算机相关认证。
用JAVA写出combination的算法： 在A,B,C,D,E中选出3个，列出所有可能的数组
// 直接贴代码了
public class Java196100137 {
public static void main(String args[]) {
new Java196100137().combination(new String[] { "A", "B", "C", "D" }, 3);
}
/**
*
* @param a记录组合序列数组
* @param n总数
* @param r选取的个数
* @param k1数组坐标
* (初始传入0)
* @param k2辅助参数
* (初始传入0)
*/
public void combination(int record[], String info[], int n, int r, int k1,
int k2) {
if (k1 == r) { // 输出当前序列
for (int i = 0; i r; ++i)
System.out.print(info[record[i] - 1] + " ");
System.out.println();
} else
for (int i = k2; i n; ++i) {
record[k1] = i + 1; // 子序列赋值
combination(record, info, n, r, k1 + 1, i + 1); // 递归回溯
}
}
/**
*
* @param a记录组合序列数组
* @param n总数
* @param r选取的个数
*/
public void combination(String info[], int r) {
int record[] = new int[r];
int n = info.length;
combination(record, info, n, r, 0, 0);
}
}
// 你看看，还有没有什么疑问？
浙大的PAT考试只能用C/C++吗？可不可以用JAVA
可以啊，网站上有介绍
考试主服务器可以接受二十余种编程语言，但各考场只保证提供C、C++、Java的程序编译调试环境如下：
-- 杭州浙江大学玉泉考点：MS Visual Studio 2010 旗舰版, Eclipse (Kepler Release, Build id: 20130614-0229)
-- 杭州浙江大学紫金港考点：VC++ 6.0, C-Free 标准版, DEV-C++, Turbo C 2.0, Eclipse SDK
-- 宁波浙江大学宁波理工学院考点：VC++ 6.0, VS2010, Eclipse 3.7
-- 宁波浙江大学软件学院考点：Eclipse 3.5.2, Visual Studio 6.0, TurboC 3.0
-- 福州福州大学考点：VC++ 6.0, VS2005, VS2008, Myeclipse 9, Myeclipse 10
-- 西安西安交通大学考点：VC++, VS2008, VS2012
-- 杭州临安浙江农林大学考点：VC++ 6.0
-- 杭州下沙浙江传媒学院考点：VC++ 6.0, VS 2005/2010, Eclipse
-- 烟台烟台大学考点：MS Visual Studio 2010 旗舰版, Eclipse 3.5.2, Visual Studio 6.0
-- 郑州河南中医学院信息技术学院考点：VC++ 6.0, MS Visual Studio 2010, Myeclipse 8
-- 青岛青岛大学信息工程学院考点：MinGW+codeblocks12.11, VC++6.0, jdk6+Eclipse Juno
-- 嘉兴嘉兴学院数理与信息工程学院考点：VC++ 6.0, VS2008, Myeclipse
-- 杭州浙江大学城市学院计算机与计算科学学院考点：VC++ 6.0，Eclipse V3.5.2
-- 南昌航空大学数学与信息科学学院考点：Win-TC，Dev-C++，VC++ 6.0，Eclipse SDK
-- 兰州交通大学国家级计算机科学与技术实验教学示范中心考点：Turbo C 2.0, VC++ 6.0, Eclipse SDK 3.41
-- 苏州大学计算机科学与技术学院考点：VS2005, VS2010, Eclipse SDK 3.1
1005. 继续(3n+1)猜想pat-Java
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-leftBlength)||(B[A-left])||(Aleftright)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的元素;还有当内层循环出现在区间内已标记为删除状态的元素中时,这时内层循环可终止.
