Posted on 2007-03-14 11:09
semovy 閱讀(327)
評(píng)論(0) 編輯 收藏 所屬分類:
JAVA基礎(chǔ)
網(wǎng)上看到一道java算法題，題目如下： 用1，2，2，3，4，5，這六個(gè)數(shù)字，用java寫一個(gè)main函數(shù)，打印出所有不同的排列，如：512234，412345等，要求：“4”不能排第3位，“1”與“5”不能相連。
??? 我的解題思路是這樣的：這是一個(gè)典型的遍歷題型，可以用遞歸實(shí)現(xiàn)。在每一次遞歸中，要解決的問題包括，“4”不能排第3位，“1”與“5”不能相連，“2”的個(gè)數(shù)最多為2個(gè)且要保證不能重復(fù)，其他數(shù)字也要不重復(fù)。最難解決的就是要使“2”不重復(fù)，我假定兩個(gè)2的順序不變，也就是在排列組合中兩個(gè)2始終保持一種出現(xiàn)順序，這樣就不會(huì)重復(fù)。其他的約束看一下注釋就可以明白了。網(wǎng)上有個(gè)使用圖的解法，盡管很有創(chuàng)意，但原理性差不多，而使用TreeSet的方法頗讓人跌眼鏡。Java代碼如下：
package?test;
/**?*//**
?*?用1，2，2，3，4，5，這六個(gè)數(shù)字，用java寫一個(gè)main函數(shù)，打印出所有不同的排列，如：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;//組合的個(gè)數(shù)
????????int?pos1=1,pos2=2;//該變量為重復(fù)的2的數(shù)組位置，可以提取出來作為參數(shù)
????????int?emp?=?countOf2(num,index);//得到當(dāng)前的數(shù)組中有幾個(gè)2
????????for(int?i=0;i<num.length;i++){
????????????if(number[i]=='2'){//當(dāng)前的數(shù)字為2
????????????????if(emp?>=?2){//數(shù)組中2的個(gè)數(shù)多于2個(gè)
????????????????????continue;
????????????????}else?if(emp?==?1){//數(shù)組中有一個(gè)2時(shí)，要求當(dāng)前的2不能為位置1的2
????????????????????if(i==pos1)continue;
????????????????}else{
????????????????????if(i==pos2)continue;//數(shù)組中沒有2時(shí)，要求當(dāng)前的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;//去除重復(fù)數(shù)字
????????????}
????????????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();
????}
}