用java寫pat演算法題,PAT演算法題

本文目錄一覽：

• 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的元素;還有當內層循環出現在區間內已標記為刪除狀態的元素中時,這時內層循環可終止.