百度“变态比赛规则”算法题 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);
		}
	}
	 
	

}

评论

20 楼 Eastsun 2007-06-11  

抛出异常的爱 写道

引用

其实由代码已经可以推导出maxImpossable( poples) =poples*(poples-1)/2

如果对方不记得Sn(n) 的公式，又是一堆口水。。。。

我认为用java开发就用java来思考，
用所能用的最好理解的方式，
用代码说出思考的过程。

这个...
如果连

引用

1+2+...+n =n*(n+1)/2

这个公式在10秒钟内推导(不是记住)不出来,我有理由怀疑他有没有做程序员的能力.
而且我不赞同JAVA的思考方式是这样的.

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

Eastsun 写道

另外,为什么不直接建立一个List<Integer>而要弄个List<String>,搞得后面还要解析一次?

1.4是客户服务器的主流配置，
虽然我有1.5，为了防止我要教的人不会因为版本问题调程序
只要写1.4的方式，可以少考虑很多问题。。。

引用

其实由代码已经可以推导出maxImpossable( poples) =poples*(poples-1)/2

如果对方不记得Sn(n) 的公式，又是一堆口水。。。。

我认为用java开发就用java来思考，
用所能用的最好理解的方式，
用代码说出思考的过程。

18 楼 Eastsun 2007-06-11  

另外,为什么不直接建立一个List<Integer>而要弄个List<String>,搞得后面还要解析一次?

17 楼 Eastsun 2007-06-11  

话说看别人写的代码还真是件很痛苦的事情,尤其涉及到算法....
不过觉得楼主的代码还有优化的余地.
比如"

public int maxImpossable(int poples){   
           
        if(poples==2){   
            return 1;   
        }else if(poples<1){   
            return 0;   
        }   
        poples--;   
        return maxImpossable(poples)+poples;   
    }  

其实由代码已经可以推导出maxImpossable( poples) =poples*(poples-1)/2
这样就可以将时间复杂度为O(N)的方法降低到O(1)了.

再看看,看不懂就不看了.

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

如果只是为了得出结论上周四我就完成了。。。
我只是想把想法试着讲给四个人听，
现在还有一个不懂。。。。
正在努力中。。。。
由于语文能力有限，
浪费了很多口舌，
用图一次完成了。。。二个人的理解。

如果想看明白代码的朋友先可以运行一下main方法，
之后改动people的值来看看其工作流程

再看junit的测试方法，
我写的顺序与编码顺序是一样的，

如果能理解测试用例之后再看代码。
代码为了能看明白没用经典数学公式。


一句话，只是让别人看明白的代码段。。。

15 楼 Eastsun 2007-06-11  

其实我也没仔细看楼主的代码,不过楼主的话到让我有了看楼主代码的兴趣.
let me 瞧瞧,o(∩_∩)o...

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

又问了几个人，发现还是有看不懂的画个图看看还有没有进步

得出结论，如果两个小组合并为一个的话，

总场次数＝原场次数  －（减去） 两小组之间的场次数

两个小组之间的场次数为两个小组人数相乘。（2，3）总场次数为6场。

13 楼 Eastsun 2007-06-11  

这个我咋知道哩,是由baidu来测试的.
不过我对我现在的算法很有信心,得到的结果应该是没问题的.

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

Eastsun 写道

皑皑,当时我比赛的时候做这个题用的是分类搜索,结果只通过3个数据集.

楼上把所有的数据集都给出来试试。。。

11 楼 Eastsun 2007-06-11  

皑皑,当时我比赛的时候做这个题用的是分类搜索,结果只通过3个数据集.

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

longrm 写道

引用

10人的话：
最多可以多少场？
1，1，1，1，1，1，1，1，1，1
这样每个人都要与其它人踢。。。
10+9+8+7+6+5+4+3+2+1＝
2，1，1，1，1，1，1，1，1
这样只会少一场。。。就是第一队中的两个人不用互踢
10+9+8+7+6+5+4+3+2=

这个好像错了，自己是不会和自己踢的
1，1，1，1，1，1，1，1，1，1
场数应该是9+8+7+6+5+4+3+2+1＝
......

终于发现写代码时有个bug改了又改，就是不合理，
发现原来这个原因。。。
PS：由于有测试用例。。。。一点点改
终于写出如下的代码，但这么写对于我的构想只是MS正确而已

	public int maxImpossable(int poples){
		
		if(poples==2){
			return 1;
		}else if(poples<1){
			return 0;
		}
		poples--;
		return maxImpossable(poples)+poples;//这里的+poples的解释很头痛
	}

9 楼 realreal2000 2007-06-11  

这个算法就是N个人，最多的时候1个人一组需要
N-1+....+1;
最少时候就是N-1,1
需要N-1组，
具体是，如果有m 个人组成一组，那么就少，m-1+...1 (m>=2)

8 楼 longrm 2007-06-11  

引用

10人的话：
最多可以多少场？
1，1，1，1，1，1，1，1，1，1
这样每个人都要与其它人踢。。。
10+9+8+7+6+5+4+3+2+1＝
2，1，1，1，1，1，1，1，1
这样只会少一场。。。就是第一队中的两个人不用互踢
10+9+8+7+6+5+4+3+2=

这个好像错了，自己是不会和自己踢的
1，1，1，1，1，1，1，1，1，1
场数应该是9+8+7+6+5+4+3+2+1＝
......

7 楼 qinysong 2007-06-11  

也把我的解法发上来，思路很简单，按照状态机路径图，从最大分组（全1）到最小分组（一个组）进行遍历追溯，直到找到符合比赛次数的分组方案

此方法效率较低，只是思路简单

分组方案类

package qinysong.arithmetic.btrules;

import java.util.*;

public class Decomposition {

  public static final int maxNumber = 100;

  private int[] groups;  //分组情况，从小到大顺序，格式为0,0,...0,1,...,x1,x2,xn
  private int leftNotZeroIndex;  //最左边不为零的数组索引
  private int matchTime;  //该分组情况下的比赛次数
  
  public Decomposition(int[] groups, int leftNotZeroIndex, int matchTime){
    this.groups = groups;
    this.leftNotZeroIndex = leftNotZeroIndex;
    this.matchTime = matchTime;
  }
  
  /**
   * 取得最大分组，即每组只有一个人的情况
   * @param peopleNumber int
   * @return Decomposition
   */
  public static Decomposition getTheMaxGroup(int peopleNumber){
    int[] groups = new int[maxNumber];
    for (int i = maxNumber - peopleNumber; i < maxNumber; i++){
      groups[i] = 1;
    }
    return new Decomposition(groups,maxNumber - peopleNumber,peopleNumber*(peopleNumber-1)/2);
  }
  
  /**
   * 从groupings分组情况及可导向子分组，比赛次数为checkTime的分组方案
   * @param groupings Set  分组情况集合
   * @param checkTime int  期待比赛次数
   * @return Decomposition  满足比赛次数的分组方案
   */
  public static Decomposition getSuitableGrouping(Set groupings, int checkTime){
    if (groupings.size() == 0) return null;
    Decomposition decomposition = null;
    Set childrenGroups = new HashSet();
    for (Iterator iterator = groupings.iterator(); iterator.hasNext(); ){
      decomposition = (Decomposition) iterator.next();
      if (decomposition.matchTime == checkTime) return decomposition;
      childrenGroups.addAll(decomposition.getUniteChildren(checkTime));
    }
    return getSuitableGrouping(childrenGroups, checkTime);
  }
  
  /**
   * 取得当前分组的可导向子分组
   * 子分组为将当前分组最左边的1，分别加入到后面的分组中
   * 若：当前分组的最左不为零的数大于1，则不必继续求子分组
   * 若：子分组的比赛次数小于checkTime，则舍弃
   * @param checkTime int  设定的比赛次数
   * @return Set
   */
  public Set getUniteChildren(int checkTime){
    Set uniteChildren = new HashSet();
    if (groups[leftNotZeroIndex] > 1) return uniteChildren;
    int unitedMatchTime = 0;
    for (int uniteTo = leftNotZeroIndex + 1; uniteTo < maxNumber; uniteTo++){
      while ((uniteTo != maxNumber-1) && (groups[uniteTo + 1] == groups[uniteTo])){
        uniteTo += 1;
      }
      unitedMatchTime = matchTime - groups[uniteTo];
      if (unitedMatchTime < checkTime ){
        break;
      }
      int[] newGroups = new int[maxNumber];
      System.arraycopy(groups,0,newGroups,0,maxNumber);
      newGroups[uniteTo] += newGroups[leftNotZeroIndex];
      newGroups[leftNotZeroIndex] = 0;
      Decomposition decomposition = new Decomposition(newGroups,leftNotZeroIndex + 1,unitedMatchTime);
      uniteChildren.add(decomposition);
    }
    return uniteChildren;
  }

  public void setGroups(int[] groups) {
    this.groups = groups;
  }
  public void setMatchTime(int matchTime) {
    this.matchTime = matchTime;
  }
  public void setLeftNotZeroIndex(int leftNotZeroIndex) {
    this.leftNotZeroIndex = leftNotZeroIndex;
  }
  public int[] getGroups() {
    return groups;
  }
  public boolean equals(Object decomp2){
    Decomposition decomposition2 = (Decomposition) decomp2;
    return Arrays.equals(groups, decomposition2.groups);
  }
  public int hashCode(){
    return matchTime;
  }
}

测试类

package qinysong.arithmetic.btrules;

import java.util.*;

public class CountCheck {

  public static void main(String[] args) {
    System.out.println("CountCheck.main begin ...");
    int peopleNumber = 20;
    int checkTime = 120;
    Decomposition maxDecomposition = Decomposition.getTheMaxGroup(peopleNumber);
    Set groups = new HashSet();
    groups.add(maxDecomposition);
    Decomposition suitableDecomposition = Decomposition.getSuitableGrouping(groups, checkTime);
    if (suitableDecomposition == null) {
      System.out.println("CountCheck.main 判定结果:" + peopleNumber + "个人不可能产生" + checkTime + "场比赛！");
    } else {
      System.out.println("CountCheck.main 判定结果:" + peopleNumber + "个人可以产生" + checkTime + "场比赛！");
      int[] suitableGrouping = suitableDecomposition.getGroups();
      for (int i = Decomposition.maxNumber-1; suitableGrouping[i] != 0; i--){
        System.out.println(suitableGrouping[i] + "/");
      }
    }
    System.out.println("CountCheck.main begin ...");
  }
}

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

public interface BTQuest {
        //题目需要的方法（作什么用的可以看题）
	public String teamAndImpossable(int peoples,int impossable);
	//算出N人最多可以比多少场
	public int maxImpossable(int poples);
	//算出如果分组的话第一组最多可能有多少人时，减少的场次数小于总数－N
	public int maxFirstTeam(int peoples, int maximpossable);
	//将第一组结果放入list后，由剩下的人组成新的组。。递归运算。。。
	public List selfTeam(int peoples , int maximpossable ,List list );
	}

问了三个人，都说看不懂，加入一个接口与中文解释再看有没有人能看的懂，

实现中的main方法是要打出people=5时所有的可能性。

5 楼 Eastsun 2007-06-09  

呵呵,再来个C的:

/**
* BTGame.c
* DP解法
* By Eastsun
*/
#include<stdio.h>
#define OFFSET(n) ((n)*((n)-1)*((n)-2)/6 +(n))
#define GetBit(a,n) (a[(n)>>3]&(1<<((n)&7)))
#define SetBit(a,n) (a[(n)>>3] |=1<<((n)&7))
#define MAX 500
char suit[OFFSET(MAX+1)/8+1],solved[OFFSET(MAX+1)/8+1];
void init(){
	  int k;
	  for(k=0;k<=MAX;k++){SetBit(suit,OFFSET(k)); SetBit(solved,OFFSET(k));}
}
char isSuit(int n,int k){
	 int off =OFFSET(n),i;
	 if(k<0||k>n*(n-1)/2) return 0;
	 if(GetBit(solved,off+k)) return GetBit(suit,off+k);
	 for(i =1;i<n;i++)
	    if(isSuit(n-i,k-i*(n-i))){
	    	  SetBit(solved,off+k);
	    	  SetBit(suit,off+k);
	    	  return 1;
	    }
	  SetBit(solved,off+k);
	  return 0;
}
int main(){
	  int n,k;
	  init();
	  while(scanf("%d%d",&n,&k)!=EOF){
	  	  printf(isSuit(n,k)?"YES\n":"NO\n");
	  }
      return 0;
}

4 楼 Eastsun 2007-06-09  

稍微解释下:
BitSet isSolved,isSuit
中的isSolved.get(n,k)表示(n,k)是否已经求解过
isSuit.get(n,k)为true表示n个人可能为k场
简记isSuit.get(n,k)为s[n,k].

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

                      = Sum{xi*xi} +2 *Sum{xi*xj: i!=j}
又易知   n <=Sum{xi*xi} <= n*n
故可得k的取值范围为:       0<=k <= n*(n-1)/2
因此我们只需判断  k在 [0,n*(n-1)/2]中的取值.



下面我们来推导DP状态转移方程:

假设n存在分解 n = Sum{xi: 1<=i<=L}
使得          k = Sum{xi*xj: 1<=i,j<=L,i!=j}
有:         k = Sum{x1*xi: i!=1} +Sum{xi*xj: 2<=i,j<=L,i!=j}
              = x1*(n-x1) +Sum{xi*xj:2<=i,j<=L,i!=j}
可以看出:     {xi: 2<=i<=L}是 k- x1*(n-x1)的一个满足条件的分解
从而我们有:
        s[n,k] = OR{s[n-m,k-m*(n-m)] : 1<=m<n}
其中OR表示逻辑或运算.


6.11添加:对offset()方法的说明
对于每一个n,我只需计算s[n,0],s[n,1],....,s[n,n*(n-1)/2]
很容易可以想到可以用一个二维boolean数组来保存s的值:
boolean[][] s =new boolean[MAX+1][];       //用MAX+1是因为把n=0的情形也包含进出了
然后:
            s[n] =new boolean[n*(n-1)/2+1]
不过,这里我没有采用boolean数组,而是采用一个BitSet(后面的C代码用的是一个char数组,然后用其每一个bit保存一个值).
BitSet可以看成是一个一维bit数组,但这里我们就要考虑如何将原来的二维boolean数组"拉直"成一维数组了:
显然,我们只要知道s[n]对应的BitSet位置就可以了,这就是offset方法要干的事.
由于s[0]要占1个位,s[1]要占一个位,....,更一般的:
              s[m]的取值是0到m*(m-1)/2
因此,s[m]要占 1+m*(m-1)/2 个位 (呵呵,不要把这个1漏了)
这样,我们可以计算s[n]的在BitSet的偏移位置应该是前s[0],...s[n-1]所占位置的总和,也就是:
     Sum{1+m*(m-1)/2 : 0<=m<=n-1}
唔,这个求和公式比1加到100要难一些(当然,如果你和我一样是学数学的话就不会觉得难了)
总而言之,求和的结果就是:

引用

                 offset(n) =Sum{1+m*(m-1)/2 : 0<=m<=n-1}
                           =n*(n-1)*(n-2)/6 +n

                       

3 楼 Eastsun 2007-06-09  

呵呵,我也来写个(DP):

/**
*@author  Eastsun
*@version 1.0 2007/6/9
*/
import java.util.BitSet;
public class BTGame{
    private static final int MAX  = 500;
    private static BitSet isSuit =new BitSet(offset(MAX+1)), isSolved =new BitSet(offset(MAX+1));
    static{
    	for(int k=0;k<=MAX;k++){isSuit.set(offset(k)); isSolved.set(offset(k));}
    }
    private static int offset(int n){  //表示第n个的起始位置
    	  return  n*(n-1)*(n-2)/6 + n;
    }
    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;
    }
    
    public static void test(int n,int k){
    	  System.out.println(isSuit(n,k)?"YES":"NO");
    }

    public static void main(String[] args){
        test(2,0);
        test(2,1);
        test(3,1);
        test(3,2);
        test(5,4);
        test(5,5);
    }
    
}

2 楼 抛出异常的爱 2007-06-08  

想法：

10人的话：
最多可以多少场？
1，1，1，1，1，1，1，1，1，1
这样每个人都要与其它人踢。。。
10+9+8+7+6+5+4+3+2+1＝
2，1，1，1，1，1，1，1，1
这样只会少一场。。。就是第一队中的两个人不用互踢
10+9+8+7+6+5+4+3+2=
3,1,1,1,1,1,1,1
以上一次少二场。。。就是有同一队中三个人不用互踢（比上上次要少 2+1场）
10+9+8+7+6+5+4+3＝
3，2，1，1，1，1，1
比上一个少一场
3，3，1，1，1，1
比上一个少二场
。。。。。。。
总场数为：
Sn(总人数)-Sn(第一组人数)－Sn(第二组人数)－Sn(第三组人数)
＝N
等比数列
Sn(总人数)－N＝Sn(team1)+Sn(team2)....
假设
Sn(team1)<Sn(总数)－N<Sn(team1+1)
得出tean1=为所有的组中人数最多的一组
之后
把这组的人数刨去，节省下来的场次数也减去之后
那么就得出一个少了team1人的一个更小的组，重复再找多最大可能的人数。。。。

到，节省不了了为止，如为0则可如为负则不可。。。。

1 楼 抛出异常的爱 2007-06-08  

junit :
这东西真是好东西以前要写这么一个东西
想明白到写好至少要调个一两天

package com.maodajun.javaeye1;

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

import junit.framework.TestCase;

/**
 * @author maodajun327
 *
 */
public class BaiDuQuestTest extends TestCase {
	BaiDuQuest quest = null;
	public static void main(String[] args) {
		junit.textui.TestRunner.run(BaiDuQuestTest.class);
	}

	public void setUp(){
		quest =new BaiDuQuest();;
	}

	public void testMaxImpossable(){
		assertEquals(0,quest.maxImpossable(1));
		assertEquals(1,quest.maxImpossable(2));
		assertEquals(3,quest.maxImpossable(3));
		assertEquals(6,quest.maxImpossable(4));
		assertEquals(10,quest.maxImpossable(5));
	}
	public void testListMax(){
		assertEquals(1,quest.maxFirstTeam(4,0));//如果有6－1场赛时第一组1人
		assertEquals(2,quest.maxFirstTeam(4,2));//如果有6－3场赛时第一组2人
		assertEquals(3,quest.maxFirstTeam(4,3));//如果有6－4场赛时第一组3人
		assertEquals(4,quest.maxFirstTeam(4,6));//如果有6－6场赛时第一组为4人
		assertEquals(-1,quest.maxFirstTeam(4,7));//小于0场时第一组为－1人		
	}
	public void testSelfTeam(){

		List list =null;
		list = quest.selfTeam(5,6,new ArrayList());
		assertNotNull(list);
		list = quest.selfTeam(5,7,new ArrayList());
		assertNull(list);
	}
	public void testTeamAndImpossable(){

		 String tmp=null;
		 tmp = quest.teamAndImpossable(5,4);
		assertEquals("YES",tmp);
		tmp = quest.teamAndImpossable(5,5);
		assertEquals("NO",tmp);
	}

}