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

}

评论

60 楼 eboge 2007-06-21  

百度题见解：
N人分为m(0<m<=N)组，总比赛数用S代表，xi代表当前组的人数（注意：i是下标)
当m=1时，S=0；
当m=2时，S=(N-x)x；
当m=3时，S=(N-x0)x0+(N-x0-x1)x1
.....
当m时，S=(N-x0)x0+(N-x0-x1)x1+…+(N-x0-x1-…-x(m-2))x(m-2)
数学归纳法很容易证明
有了公式，再来解题就应该很容易了 ^_^

59 楼 williamy 2007-06-17  

如果是公平的比賽，淘汰率不可能高於一侷比賽淘汰一個這種效率，這種效率是固定的，就是1場比賽出局一個，或者3場比賽出局一個，或者。。。。。或者。。。。（1/2*n+1，n=0 1 2 3 4...），總之就是這個意思，意思是一場比賽，出局一個，沒見過別的更高效率的公平的比賽，當然你可以給那些比較猛的加一些權重，讓他們本身就有更高的優勢，既然你需要更高的淘汰率，那麽就直接來一個不公平的比賽嘍，隨便怎麽設定，根據個人喜好，你加多少料就加多少料，自助餐一樣哦，所以你可先排出一個1 2 3 4。。。來，然後先問前後兩個是否認可，認可就直接淘汰，不認可就打一侷，很簡單哦，很高效哦，很適合你們baidu的風格，這樣的效率zai 0.5--1之間，這麽牛的公司的這麽牛的問題，只適合這麽牛的回答，I think

58 楼 longrm 2007-06-14  

xmx111 写道

longrm 写道

解释解释了，这个代码很难懂滴

个人觉得注释得很清楚

以前他是没有注释的，后来加上的

自己写了段代码，只能找出一个解，以前学的动态规划都忘的差不多了，看来得找时间补补啦

import java.util.*;

public class Queen {
	private int chess[][] = new int[8][8];
	private int a[] = new int[8];
	private int b[] = new int[15];
	private int c[] = new int[15];
	private ArrayList colList = new ArrayList(); // 记录第i行皇后放置的列数
	
	// 占据位置i,j
	private void possess(int i, int j) {
		chess[i][j]=1;
		a[j]=1;
		b[i+j]=1;
		c[7+j-i]=1;
		colList.add(String.valueOf(j));
	}
	
	// 放弃
	private void giveUp(int i, int j) {
		chess[i][j]=0;
		a[j]=0;
		b[i+j]=0;
		c[7+j-i]=0;
		colList.remove(i);
	}
	
	// 判断位置i,j上是否可以被其他皇后攻击到
	private boolean isAttacked(int i, int j) {
		if(a[j]==1 || b[i+j]==1 || c[7+j-i]==1)
			return true;
		return false;
	}
	
	public void findPosition(int i, int j) {
		int col;
		if(i>7)
			return;
		if(j>7) {
			col = Integer.parseInt((String)colList.get(i-1));
			giveUp(i-1, col);
			col = Integer.parseInt((String)colList.get(i-2));
			giveUp(i-2, col);
			findPosition(i-2, col+1);
			return;
		}
		for(; j<8; j++) {
			if(!isAttacked(i, j)) {
				possess(i, j);
				findPosition(i+1, 0);
				return;
			}
		}
		col = Integer.parseInt((String)colList.get(i-1));
		giveUp(i-1, col);
		findPosition(i-1, col+1);
	}
	
	// 输出棋盘
	public void print() {
		for(int i=0; i<8; i++) {
			for(int j=0; j<8; j++)
				System.out.print(chess[i][j]+"---");
			System.out.println();
		}
	}
	
	public static void main(String[] args) {
		Queen q = new Queen();
		q.findPosition(0,0);
		q.print();
	}
}

57 楼 xmx111 2007-06-14  

longrm 写道

解释解释了，这个代码很难懂滴

个人觉得注释得很清楚

56 楼 抛出异常的爱 2007-06-13  

Eastsun 写道

呵呵,我在原来代码上做些注释吧...
ps:在这个贴讨论与主题无关的时,楼主会不会不高兴丫

不会的。。。
反正改一下题目就可以了。。。

55 楼 Eastsun 2007-06-12  

呵呵,我在原来代码上做些注释吧...
ps:在这个贴讨论与主题无关的时,楼主会不会不高兴丫

54 楼 longrm 2007-06-12  

解释解释了，这个代码很难懂滴

53 楼 Eastsun 2007-06-12  

楼上的链接打不开

52 楼 longrm 2007-06-12  

....

网速问题，延迟的厉害，偶还以为没提交呢，，，

你的代码我看看啦，不会再到这问你啦，嘿嘿

51 楼 Eastsun 2007-06-12  

在GCC下编译通过
ps:八皇后问题就是在8*8的棋盘中每行每列各放一个皇后,并使它们互不攻击

50 楼 Eastsun 2007-06-12  

算了,不测试了:

#include<stdio.h>
#include<conio.h>
#define NUM 8
int flags[NUM][NUM];      //这个用来记录已经摆好的棋子的影响的范围
char sets[NUM][NUM];      //这个用来记录那些位置摆了棋子

void check(int row,int col){
    int i,j;
    if(row>=NUM){//如果row>=NUM说明前8行都摆好了棋子,因此已经得到一个解
        for(i=0;i<NUM;i++){
            for(j=0;j<NUM;j++)
                printf(sets[i][j]?"*":"#");
            printf("\n");
        }
        printf("----------------------\n");
        return;
    }
    if(col>=NUM) return;    //这个说明这一行已经摆不下棋子了,无解,再往上回溯求解
    if(!flags[row][col]){   //flags[row][col]==0说明这个位置可以摆子
        i =1;
        while(i+row<NUM){   //将这个位置布子后所影响到的位置加1,注意,因为我们只需要知道对以后棋子的影响
                            //所以只对左下斜对角,列下,右下斜对角做了标记
            flags[i+row][col] ++;
            if(col+i<NUM) flags[i+row][i+col]++;
            if(col-i>=0)  flags[i+row][col-i]++;
            i++;
        }
        sets[row][col] =1;  //记录棋子位置
        check(row+1,0);     //因为这一行已经布好子,所以从下一行的开始位置开始check
        i =1;
        while(i+row<NUM){   //撤销上面做的标记
            flags[i+row][col] --;
            if(col+i<NUM) flags[i+row][i+col]--;
            if(col-i>=0)  flags[i+row][col-i]--;
            i++;
        }
        sets[row][col] =0;  //撤销棋子
    }
    check(row,col+1);       //继续试探这行的下一个位置
}
int main(){
    check(0,0);
    getch();
}

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

Eastsun 写道

==,writing

说写就能写出来哟。。。
PS什么叫八皇后的问题？

48 楼 Eastsun 2007-06-12  

==,writing

47 楼 longrm 2007-06-12  

Eastsun 写道

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

恩，偶知道的，你代码中那个BitSet就是来保存结果滴，偶这样写只是展示个最简单明了的过程啦

PS：你有没有八皇后的代码啊，贴一下啦（没有的话就临时做个好了，嘿嘿）

46 楼 Eastsun 2007-06-12  

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

45 楼 longrm 2007-06-12  

谁有八皇后的代码（最好将题目也贴出来），麻烦贴一下，谢谢

44 楼 longrm 2007-06-12  

引用

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();
	}
}

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

realreal2000 写道

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

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();
		}
	}
}

把范围缩小
0到max
0+x到max+y

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

这几行的魔术数字给卡住了。。

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

Eastsun 写道

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!

真精典，终于看明白了。。。

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

都差不多。。。。数学家分两种。
一种熟练把现实的问题用公式表现出来
另一种发现新的规率。。。。