/**
?*?清華大學軟件學院程序設計語言考試練習題
?*?題目:請編寫程序求解籃球錯排問題。已知n個籃子一字排開（n為用戶輸入的
?*?任意正整數），從左到右分別標著號：1，2，...?...，n；每個球也有
?*?編號，分別也是1，2，...?...，n。現要將這n個球全部放入這n個籃子
?*?中，滿足：每個籃子放置1個球，球的號不能與其所在的籃子的號相同
?*?，且在相鄰籃子內的球的球號不能相鄰。例如，如果在相鄰兩個籃子內
?*?的球的球號分別為9和10，則是不允許的。請輸出所有符合要求的放球
?*?方式（對于每種符合要求的放球方式，都應輸出在每個籃子中的球號）。
?*?@author?THSS?MSE08?HUANGBIN
?*
?*/
public?class?BascketBallSort?{

	//籃子
	private?String[]?basckets;
	//籃球
	private?String[]?balls;
	
	public?BascketBallSort（int?n）?{
		//初始化籃子
		basckets=new?String[n];
		for（int?i=0;i			basckets[i]=String.valueOf（i+1）;
		}
		//初始化籃球
		balls=new?String[n];
		for（int?i=0;i			balls[i]=String.valueOf（i+1）;
		}
		//對n個籃球進行全排列
		perm（balls0balls.length-1）;
	}
	
	//對n個籃球進行全排列，采用分治策略進行遞歸求解
	public?void?perm（String?[]bufint?startint?end）{
		
		if（start==end）{//只有一個球進行全排列時，則不需要再遞歸
			//檢查是否符合要求，如果符合要求，則輸出
			if（check（buf））{
				for（int?i=0;i					System.out.print（basckets[i]+“（“+buf[i]+“）?“）;
				}
				System.out.println（）;
			}
		}else{
			for（int?i=start;i<=end;i++）{
				//交換i與start元素的值
				String?temp=buf[i];
				buf[i]=buf[start];
				buf[start]=temp;
				
				perm（bufstart+1end）;//遞歸求解球的全排列
				
				//還原i與start元素的值
				temp=buf[i];
				buf[i]=buf[start];
				buf[start]=temp;
			}
		}		
	}
	
	//對每一個全排列結果進行檢查，保證籃子號與球號不一樣，并且球號不相鄰
	public?boolean?check（String?tempBalls[]）{
		//球號與籃子號不能相同
		for（int?i=0;i			if（tempBalls[i].equals（basckets[i]））{
				return?false;
			}
		}
		//相鄰籃子內的球號不能相鄰
		for（int?i=0;i			if（Math.abs（Integer.parseInt（tempBalls[i]）-Integer.parseInt（tempBalls[i+1]））==1）
				return?false;		
		}				
		return?true;
	}
}

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----

?????文件????????232??2009-01-13?20:49??求解籃球錯排問題\源代碼\.classpath

?????文件????????387??2009-01-13?20:49??求解籃球錯排問題\源代碼\.project

?????文件???????1840??2009-01-13?20:49??求解籃球錯排問題\源代碼\bin\BascketBallSort.class

?????文件????????404??2009-01-13?20:49??求解籃球錯排問題\源代碼\bin\Demo.class

?????文件???????2125??2009-01-13?20:49??求解籃球錯排問題\源代碼\src\BascketBallSort.java

?????文件????????751??2009-01-13?20:49??求解籃球錯排問題\源代碼\src\Demo.java

?????文件????????434??2009-01-13?20:40??求解籃球錯排問題\題目.txt

?????目錄??????????0??2009-01-13?20:49??求解籃球錯排問題\源代碼\bin

?????目錄??????????0??2009-01-13?20:49??求解籃球錯排問題\源代碼\src

?????目錄??????????0??2009-01-13?20:49??求解籃球錯排問題\源代碼

?????目錄??????????0??2009-01-13?20:50??求解籃球錯排問題

-----------?---------??----------?-----??----

?????????????????6173????????????????????11