百度“变态比赛规则”算法题 java 的解法

呵呵,我不知道你还记得组合数么.
就是那个C(n,k),从n个元素里面取k个的方法数.

然后有个公式:  C(n+1,k+1) =C(n,k)+C(n,k+1)
(可以这样理解:从n+1个东西取k+1个,计某个元素为A,那么每种取法都属于下面的两种情形之一:
1:包含A ......相当于从另n个里面取k个
2:不包含A ....相当于从另n个里面取k+1个
从而有 C(n+1,k+1) =C(n,k)+C(n,k+1)
)

注意到 m*(m-1)/2 =C(m,2) =C(m+1,2+1) -C(m,2+1)(用了上面的公式)
从而:
                Sum{m*(m-1)/2 : 0<=m<=n-1}
             =  Sum{C(m+1,3)-C(m,3) :0<=m<=n-1}   (注意,抵消了很多)
             =  C(n,3) -C(0,3)
             =  C(n,3)
             =  n*(n-1)*(n-2)/3!

写了个程序，不知道对不对，呵呵，不过计算比较麻烦，应该还能简单很多

public class Team {
	private int membercount;
	
	private int times;

	/**
	 * @return membercount
	 */
	public int getMembercount() {
		return membercount;
	}

	/**
	 * @param membercount 
	 */
	public void setMembercount(int membercount) {
		this.membercount = membercount;
	}

	/**
	 * @return times
	 */
	public int getTimes() {
		initTimes();
		return times;
	}

	private void initTimes() {
		times = (membercount*membercount-membercount)/2;		
	}

}

写了个算法

import java.util.*;

public class Match {
	private int totalcount;
	
	private int mostTimes;
	
	private int leastTimes;
	
	private int times;
	
	private int remaintimes;
	
	private List<Team> teams = new ArrayList();
	
	private int teamMemebers;

	/**
	 * @return leastTimes
	 */
	public int getLeastTimes() {
		return leastTimes;
	}

	/**
	 * @return mostTimes
	 */
	public int getMostTimes() {
		return mostTimes;
	}
	
	public Match(int totalcount){
		this.totalcount = totalcount;
		leastTimes = totalcount-1;
		mostTimes = countTimes(totalcount);
	}

	/**
	 * @return totalcount
	 */
	public int getTotalcount() {
		return totalcount;
	}
	
	public static int countTimes(int i){
		if(i==1)
			return 0;
		if(i==2)
		return 1;
		return (i*i-i)/2;
	}
	
	public boolean isCanPlay(){
		boolean result = false;
		if(times<leastTimes)
			return false;
		if(times>mostTimes)
			return false;
		if(times==leastTimes)
			return true;
		if(times==mostTimes)
			return true;
		while(remaintimes!=0){
			if(teamMemebers>totalcount)
				return false;
			createTeam(remaintimes);			
		}
		if(teamMemebers>totalcount)
			return false;
		return true;
	}
	
	public void createTeam(int m){
		Team team = new Team();
		if(m==1){
			team.setMembercount(2);
			teamMemebers = teamMemebers+2;
			teams.add(team);
			remaintimes = remaintimes-1;
			System.out.println("teamMemebers is "+teamMemebers);
			return;
		}
		int j = (m<=2)?5:2*m;
		for(int i =2;i<=j;i++){
			System.out.println("i is "+i);
			if(countTimes(i)>m){
				remaintimes = remaintimes-countTimes(i-1);
				teamMemebers = teamMemebers+i-1;
				System.out.println("teamMemebers is "+teamMemebers);
				team.setMembercount(i-1);
				return;
			}
		}
		teams.add(team);
	}

	/**
	 * @return times
	 */
	public int getTimes() {
		return times;
	}

	/**
	 * @param times 要设置的 times
	 */
	public void setTimes(int times) {
		this.times = times;
		System.out.println("mostTimes is "+mostTimes);
		this.remaintimes = this.mostTimes - times;
		System.out.println("remaintimes is "+remaintimes);
	}
	
	public static void main(String[] args){
		Match m = new Match(10);
		m.setTimes(32);
		try{
			if(m.isCanPlay()){
				System.out.println("Can");
			}else{
				System.out.println("Can not");
			}
		}catch(Exception e){
			e.printStackTrace();
		}
	}
}

         int j = (m<=2)?5:2*m;  
         for(int i =2;i<=j;i++){  

n个人能够比k场实际上是问: n能否存在一个分解 xi(xi>0)使得
Sum{xi} =n, Sum{xi*xj: i!=j} =k;

import java.util.*;

public class BaiduQuest {
	private ArrayList teamList; // 可以实现时保存分组情况
	private boolean solve;   // 保存是否可以实现
	
	public BaiduQuest(int n, int k) {
		teamList = new ArrayList();
		sum = 0;
		solve = isSolved(n, k);
	}
	
	// 递归解决是否可以实现
	public boolean isSolved(int n, int k) {
		if(n<=0) {
			System.out.println("Wrong number entered!");
			return false;
		}
		if(k<0 || k>n*(n-1)/2)
		  return false;
		else if(k==0) {
			teamList.add(n);
		  return true;
		}
		  
		for(int i=1; i<n; i++)
			if(isSolved(n-i, k-i*(n-i))){
				teamList.add(i);
				return true;
			}
			
		return false;
	}
	
	public void print() {
		System.out.println(String.valueOf(solve));
		
		// 输出分组情况
		for(int i=0; i<teamList.size(); i++)
		  System.out.println(teamList.get(i));
	}
	
	public static void main(String[] args) {
		// 直接在控制台获取数据n, k
		if(args.length!=2) {
		  System.out.println("Please enter right data!");
		  return;
		}
		BaiduQuest test = new BaiduQuest(Integer.parseInt(args[0]), Integer.parseInt(args[1]));
		test.print();
	}
}

呵呵,楼上实际上是把我代码中关于动态规划的部分去掉了(就是保存计算结果的步聚).
但是这样效率会明显降低,因为里面做了很多重复计算.而动态规划由于保存了计算结果就避免了重复计算,
另一方面考虑到测试的时候是用多个测试数据,保存的计算结果就更能够提高效率了.

==,writing