Posted on 2007-03-14 11:09
semovy 閱讀(327)
評論(0) 編輯 收藏 所屬分類:
JAVA基礎
網上看到一道java算法題，題目如下： 用1，2，2，3，4，5，這六個數字，用java寫一個main函數，打印出所有不同的排列，如：512234，412345等，要求：“4”不能排第3位，“1”與“5”不能相連。
??? 我的解題思路是這樣的：這是一個典型的遍歷題型，可以用遞歸實現。在每一次遞歸中，要解決的問題包括，“4”不能排第3位，“1”與“5”不能相連，“2”的個數最多為2個且要保證不能重復，其他數字也要不重復。最難解決的就是要使“2”不重復，我假定兩個2的順序不變，也就是在排列組合中兩個2始終保持一種出現順序，這樣就不會重復。其他的約束看一下注釋就可以明白了。網上有個使用圖的解法，盡管很有創意，但原理性差不多，而使用TreeSet的方法頗讓人跌眼鏡。Java代碼如下：
package?test;
/**?*//**
?*?用1，2，2，3，4，5，這六個數字，用java寫一個main函數，打印出所有不同的排列，如：512234，412345等，要求：“4”不能排第3位，“1”與“5”不能相連。
?*?@author?kafka0102
?*
?*/
public?class?ATest?
{
????private?static?boolean?is1Or5(char?a,char?b){
????????if(a=='1'?&&?b=='5')return?true;
????????if(a=='5'?&&?b=='1')return?true;
????????return?false;
????}
????
????private?static?int?countOf2(char[]?num,int?index){
????????int?n=0;
????????for(int?i=0;i<index;i++){
????????????if(num[i]=='2')n++;
????????}
????????return?n;
????}
????
????private?static?boolean?hasSameNumber(int?index,char?a,?char[]?num){
????????for(int?i=0;i<index;i++){
????????????if(num[i]==a)return?true;
????????}
????????return?false;
????}
????
????public?static?int?testArrange(char[]?number,char[]?num,int?index){
????????int?size?=?0;//組合的個數
????????int?pos1=1,pos2=2;//該變量為重復的2的數組位置，可以提取出來作為參數
????????int?emp?=?countOf2(num,index);//得到當前的數組中有幾個2
????????for(int?i=0;i<num.length;i++){
????????????if(number[i]=='2'){//當前的數字為2
????????????????if(emp?>=?2){//數組中2的個數多于2個
????????????????????continue;
????????????????}else?if(emp?==?1){//數組中有一個2時，要求當前的2不能為位置1的2
????????????????????if(i==pos1)continue;
????????????????}else{
????????????????????if(i==pos2)continue;//數組中沒有2時，要求當前的2不能為位置2的2
????????????????}
????????????}else{
????????????????if(index==2?&&?number[i]=='4')continue;//去除4
????????????????if(index>0?&&?is1Or5(num[index-1],number[i]))continue;//去除相鄰的1和5
????????????????if(hasSameNumber(index,number[i],?num))continue;//去除重復數字
????????????}
????????????num[index]?=?number[i];
????????????if(index==5){
????????????????System.out.println(num);
????????????????size++;
????????????}else{
????????????????size?=?size?+?testArrange(number,num,index+1);
????????????}
????????}
????????return?size;
????}
????
????public?static?void?aTest(){
????????char[]?number?=?{'1','2','2','3','4','5'};
????????char[]?num?=?new?char[number.length];
????????int?size?=0;
????????size?=?testArrange(number,num,0);
????????System.out.println("size="+size);
????}
????
????public?static?void?main(String[]?args)?{
????????aTest();
????}
}