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

没什么注释。。
作过的看看能不能再快一点
主题贴子在这里。。。。
http://www.iteye.com/post/307049

引用

变态比赛规则

为了促进各部门员工的交流，百度举办了一场全公司范围内的“拳皇”（百度内部最流行的格斗游戏）友谊赛，负责组织这场比赛的是百度的超级“拳皇”迷W.Z。W.Z不想用传统的淘汰赛或者循环赛的方式，而是自己制定了一个比赛规则。

由于一些员工（比如同部门或者相邻部门员工）平时接触的机会比较多，为了促进不同部门之间的交流，W.Z希望员工自由分组。不同组之间的每两个人都会进行一场友谊赛而同一组内的人之间不会打任何比赛。

比如4个人，编号为1~4,如果分为两个组并且1，2一个组，3，4一个组，那么一共需要打四场比赛：1 vs 3，1 vs 4，2 vs 3，2 vs 4。 而如

果是1，2，3一组，4单独一组，那么一共需要打三场比赛 1 vs 4，2 vs 4，3 vs 4。


很快W.Z意识到，这样的比赛规则可能会让比赛的场数非常多。W.Z想知道如果有N个人，通过上面这种比赛规则，总比赛场数有可能为K场吗？

比如3个人，如果只分到一组则不需要比赛，如果分到两组则需要2场比赛，如果分为三组则需要3场比赛。但是无论怎么分都不可能恰需要1场比赛。


相信作为编程高手的你一定知道该怎么回答这个问题了吧？ 那么现在请你帮助W.Z吧。

package com.maodajun.javaeye1;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

public class BaiDuQuest {

	public String teamAndImpossable(int peoples,int impossable){
		int maximpossable= maxImpossable(peoples);
		maximpossable -=impossable;
		List list =selfTeam(peoples,maximpossable,new ArrayList());
		if(list!=null){
			return "YES";
		}
		return "NO";	
	}
	//递归算出最大可能。。。循环赛制
	public int maxImpossable(int poples){
		
		if(poples==2){
			return 1;
		}else if(poples<1){
			return 0;
		}
		poples--;
		return maxImpossable(poples)+poples;
	}
	
	public int maxFirstTeam(int peoples, int maximpossable){
		int tmp = 0 ;
		if(maxImpossable(peoples)<maximpossable){
			return -1;
		}
		for(int i = peoples ; i >1 ; i--){
			tmp = maxImpossable(i);
			if(tmp <= maximpossable){
				return i;
			}
		}
		return tmp;
	}
	public List selfTeam(int peoples , int maximpossable ,List list ){
		int max = maxFirstTeam(peoples,maximpossable);
		if(max==0){
			return list;
		}else if (max==-1){
			return null;
		}else{
			list .add(""+max);
			return selfTeam(peoples-max,maximpossable-maxImpossable(max),list);
		}	
	}
	public static  void main(String[] arg){
		BaiDuQuest quest = new BaiDuQuest();
		int people = 5;
		for(int i = quest.maxImpossable(people) ; i >=0; i--){
			List list =quest.selfTeam(people,i,new ArrayList());
			int count = 0 ;
			if(list!=null){
				for(int j = 0 ; j < list.size(); j ++){
					 count +=Integer.parseInt(list.get(j).toString());
					
				}
	
				list.add(""+(people-count));
			}
			System.out.println(quest.maxImpossable(people)-i+":"+list);
		}
	}
	 
	

}

评论

40 楼 Eastsun 2007-06-11  

不过数学在算法这一块起的作用还是很大的.

像那些图论算法,线性规划问题,很多用到了很复杂的数学推理,我看起来都头痛.

39 楼 Eastsun 2007-06-11  

这种问题的效率主要是由算法决定的.
只要算法对了,效率不会差到那儿去,至于用递归还是用递推关系不大.

38 楼 抛出异常的爱 2007-06-11  

我在写代码时不考虑效率。。。
我主要是为了给别人讲一个想法。

PS：java的所有的思想都与清析表达有关。。。

如果说我想的方式大约会达到O（n^2）左右的效率
比遍历要少1/2的时间而已

而你的想法是纯数学推导出来。。。
自然会比我想的要快一些
如果想要看明白先要过数学的关卡。。。（就是上面的数学式）

37 楼 Eastsun 2007-06-11  

longrm 写道

抛出异常的爱 写道

看了一下还真是看不明白呀。。。。

哈哈，偶都明白啦，就是那个计算的还没看出怎么算来的（主要是偶太懒了，嘿嘿）
虽然你的代码长多了，但效率不见得就比他的差，不知道怎么测试

呵呵,我不知道你还记得组合数么.
就是那个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!

36 楼 longrm 2007-06-11  

抛出异常的爱 写道

longrm 写道

抛出异常的爱 写道

看了一下还真是看不明白呀。。。。

哈哈，偶都明白啦，就是那个计算的还没看出怎么算来的（主要是偶太懒了，嘿嘿）
虽然你的代码长多了，但效率不见得就比他的差，不知道怎么测试

嘲笑别人没的好下场

罚你用这种方法作。。。。
http://www.iteye.com/post/309308
换零钱的程序。。。。
你不要说你没毕业不会作噢。。。

寒，八皇后的问题偶大一的时候碰到过，楞是没做出来，直到现在还觉得遗憾，楼上的能贴一下这个的解决代码么，谢谢！

说句实话，你说的太对啦，偶刚大四，还差1个月毕业，嘿嘿

35 楼 抛出异常的爱 2007-06-11  

longrm 写道

抛出异常的爱 写道

看了一下还真是看不明白呀。。。。

哈哈，偶都明白啦，就是那个计算的还没看出怎么算来的（主要是偶太懒了，嘿嘿）
虽然你的代码长多了，但效率不见得就比他的差，不知道怎么测试

嘲笑别人没的好下场

罚你用这种方法作。。。。
http://www.iteye.com/post/309308
换零钱的程序。。。。
你不要说你没毕业不会作噢。。。

34 楼 Eastsun 2007-06-11  

抛出异常的爱 写道

看了一下还真是看不明白呀。。。。

5，0，0，0，0 ＝1
4，1，0，0，0 = 2
3，2. 0, 0, 0 =2
。。。。。

所有的可能性都遍历出来？
头一个可以的就跳出来么？

注意我static{}里面的代码,那是初始状态,把所有的s[n,0]全设为true了.

33 楼 Eastsun 2007-06-11  

longrm 写道

    public static boolean isSuit(int n,int k){   
          if(k<0||k>n*(n-1)/2) return false;   
          int off =offset(n);   
          if(isSolved.get(off+k)) return isSuit.get(off+k);   
          for(int i =1;i<n;i++)   
              if(isSuit(n -i,k -i*(n-i) ) ){   
                  isSolved.set(off +k);   
                  isSuit.set(off +k);   
                  return true;   
              }   
          isSolved.set(off +k);   
          return false;   
    }   

呵呵，这里用递归会影响性能，如果改成循环的话就更好了

这个,改成循环是很简单的时,但实际上事情不完全是这样滴.
对于动态规划,一般有两种形式: 一种是用递归;一种使用循环(递推)
这两种形式的代码都很容易写(前提是你已经得到状态转移方程)

而且两种形式各有所长(循环的不一定比递归的好):
递归形式的代码容易理解,而且可以减少不必要的计算,因为递归的时候只算要算的(后一点对于性能来说是比较重要的)
而如果能确定大多数子状态都需要计算的话,循环就会更快了(但循环会一次性把所有的状态都计算到,因为它知道那些不必要算).


当然,可以改成那种基于栈的循环算法,不过说实话,那种代码读起来就费劲多了.

32 楼 longrm 2007-06-11  

抛出异常的爱 写道

看了一下还真是看不明白呀。。。。

哈哈，偶都明白啦，就是那个计算的还没看出怎么算来的（主要是偶太懒了，嘿嘿）
虽然你的代码长多了，但效率不见得就比他的差，不知道怎么测试

31 楼 抛出异常的爱 2007-06-11  

看了一下还真是看不明白呀。。。。

5，0，0，0，0 ＝1
4，1，0，0，0 = 2
3，2. 0, 0, 0 =2
。。。。。

所有的可能性都遍历出来？
头一个可以的就跳出来么？

30 楼 Eastsun 2007-06-11  

longrm 写道

    private static int offset(int n){  //表示第n个的起始位置   
          return  n*(n-1)*(n-2)/6 + n;   
    }

这个是由Sum{i*(i-1)/2; 1<=i<=n}计算出来的么？偶怎么就算不出来

这个是我代码注释过少的缘故,
==,我在原来代码下面加些注释.

29 楼 longrm 2007-06-11  

抛出异常的爱 写道

longrm 写道

    private static int offset(int n){  //表示第n个的起始位置   
          return  n*(n-1)*(n-2)/6 + n;   

这个是由Sum{i*(i-1)/2; 1<=i<=n}计算出来的么？

这就是引用数学公式的问题，前题是对方得懂公式才可以
"n!/(3!)(n-3)! + n"

为什么是这个公式？？？有点看不懂

28 楼 抛出异常的爱 2007-06-11  

longrm 写道

    private static int offset(int n){  //表示第n个的起始位置   
          return  n*(n-1)*(n-2)/6 + n;   

这个是由Sum{i*(i-1)/2; 1<=i<=n}计算出来的么？

这就是引用数学公式的问题，前题是对方得懂公式才可以
"n!/(3!)(n-3)! + n"

27 楼 longrm 2007-06-11  

    public static boolean isSuit(int n,int k){   
          if(k<0||k>n*(n-1)/2) return false;   
          int off =offset(n);   
          if(isSolved.get(off+k)) return isSuit.get(off+k);   
          for(int i =1;i<n;i++)   
              if(isSuit(n -i,k -i*(n-i) ) ){   
                  isSolved.set(off +k);   
                  isSuit.set(off +k);   
                  return true;   
              }   
          isSolved.set(off +k);   
          return false;   
    }   

呵呵，这里用递归会影响性能，如果改成循环的话就更好了

26 楼 realreal2000 2007-06-11  

Match m = new Match(10); //用于建立多少人的比赛
m.setTimes(32);
比赛一共的场次
m.isCanPlay() //是否存在这样的分组
想法是这样的，计算出10个人最多的比赛数，然后通过要比赛的场次，计算出不需要进行多少场，然后分组，分组的时候计算分组时可以不用参加的比赛，如果存在这样的分组并且人数不大于参赛人数，那么就可行

算法中使用逼近方法，每次分组的时候 小组中不用比赛的次数逼近一共不需要比赛的次数，即一次能分组的最大人数。

(m*m-m)/2 中m取最大值；

并认为如果这种最大分组不存在即不存在这样的分组

25 楼 longrm 2007-06-11  

    private static int offset(int n){  //表示第n个的起始位置   
          return  n*(n-1)*(n-2)/6 + n;   
    }

这个是由Sum{i*(i-1)/2; 1<=i<=n}计算出来的么？偶怎么就算不出来

24 楼 realreal2000 2007-06-11  

写了个程序，不知道对不对，呵呵，不过计算比较麻烦，应该还能简单很多
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();
}
}
}

23 楼 抛出异常的爱 2007-06-11  

等差数列合公式。。。
PS：强烈怀疑你的语言真实性
PS2：学这个公式时老是除出 xxx.5的人飘过。。。。
PS3:n!这东西是个好东西如果有好的手算办法给我发一份。。。

22 楼 ddandyy 2007-06-11  

@_@

Sn(n)是啥东西

21 楼 抛出异常的爱 2007-06-11  

呵呵
如果可以选，我会选给程序员写程序而不是给不懂行的写程序，
但事实总是与我们开玩笑。

我只是说为了合乎逻辑。。。。
防止别人看不懂，但是从早上起N个人问过我为什么不用Sn(n)了。。。
这点的需求作的有点过了。。。