5元10元找钱问题

问题：有10个人去买票，票价5元，其中5个人有5元的钱，另外5个只有10元的钱。售票员没有5元的钱，每个人只买一张票，为使售票员的5元钱够用，这10个人有多少种排法？

 

分析：用‘1’表示有5元的人，‘0’表示有10元的人。问题实际上是求由5个0和5个1排列的字符串，从1开始到长度为k(k<=10)的子串中任何时候1出现的次数要比0出现的多。比如：排列1111100000是符合要求的。

我的实现方式：

 

public class PermutationForChange {

	/**
	 * @author:lilywangcn
	 * @date:2010-12-14
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		String arr_Str="01";
		StringBuilder sb=new StringBuilder();
		permutationForChange(0,arr_Str,sb,10,0,0);
	}
	
	//num1:当前字符串中字符1的个数
	//num0:当前字符串中字符0的个数
	//n:字符串总长度
	//sb：已经排好的字符串
	//index:已排好的字符串长度
	public static void permutationForChange(int index, String arr_Str,StringBuilder sb,int n,int num1, int num0){
		if(index==n){
			System.out.println(sb);
		}else{
			StringBuilder tmp=new StringBuilder(sb);
			char ch;
			if(num1<=num0 && num1<n/2){
				ch='1';
				num1++;
				tmp.insert(index, ch);
				permutationForChange(index+1,arr_Str,tmp,n,num1,num0);
			}else if(num1>=n/2){
				ch='0';
				num0++;
				tmp.insert(index, ch);
				permutationForChange(index+1,arr_Str,tmp,n,num1,num0);
			}else{
				for(int i=0;i<arr_Str.length();i++){
					ch=arr_Str.charAt(i);
					if(ch=='0') num0++;
					else num1++;
					tmp.insert(index, ch);
					permutationForChange(index+1,arr_Str,tmp,n,num1,num0);
					if(tmp.charAt(index)=='0') num0--;
					else num1--;
					tmp=new StringBuilder(sb);
				}
			}
		}
	}

}

  

结果：有42种方式

  

1010101010
1010101100
1010110010
1010110100
1010111000
1011001010
1011001100
1011010010
1011010100
1011011000
1011100010
1011100100
1011101000
1011110000
1100101010
1100101100
1100110010
1100110100
1100111000
1101001010
1101001100
1101010010
1101010100
1101011000
1101100010
1101100100
1101101000
1101110000
1110001010
1110001100
1110010010
1110010100
1110011000
1110100010
1110100100
1110101000
1110110000
1111000010
1111000100
1111001000
1111010000
1111100000