[算法]最少比赛次数

题目：

公司组织一次羽毛球比赛，采用淘汰机制，假设公司有1001个人，如果要评出“公司羽毛球第一高手”的称号，至少需要进行多少场比赛？请简述设计过程，并写出代码模拟比赛过程。

一对一的比赛，一场只能淘汰一个人，因此需要1000此比赛。

比赛过程：

View Code

1 import java.util.ArrayList;

2

3

4 /*

5 * 公司组织一次羽毛球比赛，采用淘汰机制，假设公司有1001个人，如果要评出“公司羽毛球第一高手”的称号，至少需要进行多少场比赛？请简述设计过程，并写出代码模拟比赛过程

6 * 比赛过程

7 */

8 public class Competition {

9

10 public static void main(String[] args) {

11 int n=1001;

12 ArrayList thisRound=new ArrayList();

13 ArrayList nextRound=new ArrayList();

14 int c=0;

15

16 for(int i=0;i

17 thisRound.add(i+1);

18 }

19

20

21 shuffle(thisRound);

22 //随机选出23人，轮空

23 System.out.println("the following competitors will go into the next without competitions ");

24 for(int i=0;i<23;i++){

25 System.out.print(thisRound.get(i)+" ");

26 nextRound.add(thisRound.get(i));

27 thisRound.remove(i);

28 }

29 System.out.println();

30 do{

31 shuffle(thisRound);

32 for(int i=0;i

33 System.out.println("the "+(++c)+" competition:"+thisRound.get(i)+" vs "+thisRound.get(i+1));

34 int winner=(int)Math.floor(Math.random()*10)%2==0?i:i+1;

35 System.out.println("the "+(c)+" competition result:"+thisRound.get(winner)+" wins");

36 nextRound.add(thisRound.get(winner));

37 }

38 thisRound=nextRound;

39 nextRound=new ArrayList();

40 }

41 while(thisRound.size()>1);

42 System.out.println("the final winner is:"+thisRound.get(0));

43 }

44

45 public static void shuffle(ArrayList A){

46 for(int i=0;i

47 int r=(int) Math.floor(Math.random()*A.size());

48 int tem=A.get(r);

49 A.set(r,A.get(i));

50 A.set(i,tem);

51 }

52 }

53 }

比赛有多种形式，淘汰赛就是1对1比，每轮淘汰一半，直到只剩下一个人。循环赛，是每个队都能和其他队比赛一次或两次，最后按成绩计算名次。第一次有23人轮空，就是为了产生第二轮512人的比赛，从而可以不再需要轮空某些队。