袁绍性格特点及事例:什么叫winner tree

这叫做赢者树,是竞赛树中的一个,还有一个输者树.

1．基本东西：
形象来说，外部节点表示选手捉对厮杀，内部节点表示比赛的胜者（败者）。定
义如下：对于n名选手，赢者树是一棵含n个外部节点，n-1个内部节点的完全二叉树
，其中每个内部节点记录了相应赛局的赢家（或输家）。
赢者树的一个优点在于即使一名选手得分改变了，也只需修改从它到根的那条路径
，而不必改变其他比赛结果。

2．抽象数据描述-WinnerTree
WinnerTree{
实例：
完全二叉树，每个节点表示相应比赛的赢者，外部节点表示选手；
操作：
Creat()---创建一个空的赢者树；
Initialize(a,n)：对有n个选手a[1:n]的赢者树进行初始化；
Winner()---返回比赛的赢者；
Replay(i)---选手i变化时，重组赢者树；
}；

3．类WinnerTree （202.38.64.10/~wurong/Ctree.rar）
n名选手的赢者树需要n-1个内部节点t[1:n-1]。选手（外部节点）用e[1:n]表示
。故t[i]为数组e的一个索引而且类型为int。t[i]给出了赢者树中节点i对应比赛的
赢者。为了实现ADT操作，必须能够确定外部节点e[i]的父节点t[p]。根据赢者树完
全二叉树的特点，最低层最左端的内部节点编号为2S,这里s=log2(n-1)因此最低层
内部节点数目为n-2S，那么相应的最低层的外部节点数目LowExt应该为这个数值的
2倍，那么倒数第二层的最左端外部节点号为LowExt+1，设offset=2S+1-1，可知对
于任何外部节点e[i]，其父节点t[p]满足一下关系：

p== (i+offset)/2 i<=LowExt

(i-LowExt+n-1)/2 i>LowExt

类定义：私有成员包括：MaxSize(允许最大选手数),n(赢者树初始化时选手数)
,t(内部节点数组),e(外部节点数组),LowExt和Offset。通过适当定义Winner，可以
构造最小赢者树，最大赢者树等。初始化和replay函数是通过比赛来进行的。

4．输者树
对于函数RePlay(i)函数，采用输者树效率比赢者树高，但是也仅限于这个情况
而已。

5．应用
①最先匹配法求解箱子装载问题：
问题描述：若干个容量为c的箱子和n个待装入箱子的物品，物品i需要占用s[i]
个单元，所谓成功装载是把所有物品装入箱子而不溢出，而最优装载则是指使用了
最少箱子的成功装载。

对于此类箱子问题，流行4种算法：
A．最先匹配法（FF）：物品按照1,2,…,n的顺序装入箱子，假设箱子从左向右
排列，每一物品i放入可盛载它的最左箱子。
B．最优匹配法（BF）：设cAvail[j]为箱子j的可用容量，出示时所有都为c，物
品i放入具有最小cAvail且容量大于s[i]的箱子中
C．最先匹配递减法（FFD）：与FF类似，区别在于各物品首先按照容量递减的次
序排列。
D．最优匹配递减法（BFD）：于BF类似，区别在于各物品首先按照容量递减的次序
排列。

这里设计最先匹配程序。程序首先要求输入物品数量n及每个箱子的容量c。假定容
量及空间需求均为整数，接下来程序要求输入n个物品并限制每个物品孔间<=c。最
后再调用函数FirstFitBack，将物品分派到各个箱子。对于使用FFD策略的程序，只
需将源程序稍作修改，即在调用FirstFitBack前按递减顺序对物品进行排序。

对于FirstFitBack函数，选手i代表箱子i当前的容量，所有箱子容量初始化为c。该
函数假定，当比赛开始时左边选手是赢者，除非右边选手比较大。

具体代码见firstfit.cpp

②用相邻匹配法求解箱子装载问题：
Next Fit策略中，开始将物品1放入箱子1，对于其余物品，则从最后使用的箱子的
下一个箱子开始。比如箱子1~b正在使用，则可认为这些箱子排列成环状：i!=b时，
i的下一个箱子为i+1；i=b时，i的下一个箱子为箱子1。若上一个物品放入了箱子j
，则从箱子j的下一个箱子开始不断查找后续箱子，直到找到具有足够空间的箱子或
者又回到箱子j。若没有找到合适的，则启用一新箱子。