【问题】假设有 个选手进行竞技淘汰赛，最后决出冠军的选手，请设计竞技淘汰比赛的过程。

【想法】竞技淘汰比赛最自然的想法是将所有选手分成两部分，每部分决出胜者后，让这两个胜者进行比赛，再决出最后的冠军，这属于分治法，显然满足如下递推式：

应用扩展递归技术求解这个递推式，得到 。 下面考虑采用减治法，开始时将所有选手分成 n/2 组，每组两个选手进行比赛，被淘汰者不参加以后的比赛，然后再将剩余选手分成 n/4 组，每组两个选手进行比赛，......直到剩余最后两个选手，进行一次比赛即可选出最后的冠军。下图（减治法求解淘汰赛冠军问题示例图）给出了一个减治技术解决淘汰赛冠军问题的过程示例（假设按照字符编码进行比较）。

【算法分析】设 n=2，则外层的 while 循环共执行 k 次，在每一次执行时，内层的 for 循环的执行次数分别是 n/2，n/4，…，1，而函数 Comp 可以在常数时间内完成，因此，算法的执行时间为：

【算法实现】设函数 Comp 模拟两位选手 mem1 和 mem2 的比赛，若 mem1 获胜则函数 Comp 返回 1，否则返回 0，并假定可以在常数时间内完成函数 Comp 的执行，简单起见，用字符表示选手，设字符数组 r[n] 存储 n 个选手，算法用JAVA语言描述如下：

public class Comp {

public static void main(String[] args)

{

char[] r=new char[]{'A','F','G','B','E','H','C','D'};

char c=Game(r,8);

System.out.println("最后的冠军是："+c);

}

static boolean Comp(char a, char b)

{

if(a>b) return false;

else return true;

}

static char Game(char[] r, int n)

{

int i = n;

while (i > 1) //比赛直到剩余1人即为冠军

{

i = i/2;

for (int j = 0; j < i; j++)

if (Comp(r[j+i], r[j])) //胜者存入r[j]中

r[j] = r[j+i];

}

return r[0];

}

}

运行结果如下：

from：算法设计与分析（第2版）——王红梅 胡明 编著——清华大学出版社