问题标签 [tournament]

“在 n+2k-3 个比较中找到大小为 (2^k +1) 的数组中的第三大元素。”

这是我在算法课程期末考试中遇到的一个问题，我没有得到所有的分数。经过彻底的互联网搜索，我仍然不确定正确的答案是什么。

我意识到这是第二大问题的扩展版本，但是所要求的严格比较界限使问题变得棘手。我还找到了一个数学解释来在这里找到第 K 个元素，但是这对我来说太复杂了，我无法理解。

将数组大小表示为 n = 2^k + 1。

在考试本身中，我的答案是这样的：

我们将使用锦标赛树。首先，我们遗漏了一个任意元素。
然后构建由 2^k 个元素组成的树。因此树中有 K 个级别 (log(2^k))。

找到获胜者将需要我们进行 n-2 次比较。

在输给获胜者的人中找到最大的元素。（K-1 补偿）

在输给决赛输家的人中找到最大的元素。（K-2 补偿）

我们将比较这些和我们一开始遗漏的那个。（2个补偿）

3 个中最大的是数组中的第 3 个。

比较总数：n - 2 + k - 1 + k - 2 + 2 = n + 2k - 3。

满分 25 分，我得了 10 分。

我犯了2个错误。主要的是，如果所需的元素在获胜者的子树中，我的答案将是不正确的。此外，正确答案应该是我最后比较的 3 个中的第二大。

我发现的另一个算法如下： -
构建锦标赛树并找到获胜者 (n - 2) -
通过将所有失败者与获胜者进行比较来找到第二大的。（也通过锦标赛树）（k - 1）
- 答案在于最大的输家到第二大的输家，以及在第一棵树的决赛中输掉的输家。(log(k+1) + K-1-1)

- 这个解决方案假设我们遗漏的元素不是数组中最大的。如果是，我不确定它是如何起作用的。另外，我可能没有正确理解比较次数。

我很高兴知道是否有更好的解释算法。我也很想知道是否有更多关于 L-th 大的广义的（K 被取了..）。

提前致谢， Itay

目前我正在开发一个为期 1 天的锦标赛调度应用程序。由于每年参与团队的数量都不同，我想自动化调度。

团队分为 2 组。每组进行单循环赛。我设法生成了所有要玩的游戏，但我正在为计划而苦苦挣扎。

此外，球队需要参加 3 个不同的运动项目，每个项目都有一个专门的领域。（如足球场、排球场）

给定： - 要玩的游戏 - 每项运动的场地 + 每场可用的时隙（+-15 分钟的时隙）

假设： - 时隙不受限制 - 每项运动有 1 个可用场地 - 在第一次迭代中不需要平衡时间表

问题： - 我的日程安排质量不是很好。事实上，即使有解决方案，也不是所有的时间段都被填满。我的日程安排的“密度”还取决于处理的游戏顺序。

代码片段：

谁能给我一个方法的概述，可用的算法，......？

提前致谢

在这里，我有这段代码可以按降序对诸如数组之类的锦标赛结构进行排序。它对除一个数字以外的所有数字进行排序，并始终返回-1作为排序的最低整数，我已多次阅读此代码，我似乎无法弄清楚为什么它没有正确排序，我不确定它是否只是错过了我的眼睛，或者某处有一个小错字。

我相信错误仅在于我构建锦标赛结构的功能，但是，我不太确定我是否找错了地方。

提前感谢您的任何帮助，如果我需要为此问题添加更多详细信息，请在评论中告诉我。

编辑：这是查看我收到的输出的链接。 http://imgur.com/a/KNDO8

编辑 2：如果我要使用数字 20 14 1 3 8 进行排序，它会将它们排序为20 8 1 3 -1

背景

我正处于编写“锦标赛包围”应用程序的早期阶段（C#，尽管任何面向对象的语言都适用）。这个应用程序理论上会为多种类型的锦标赛生成括号表：

• 单淘汰
• 双重淘汰
• “真秒”双淘汰
• 循环赛
• 瑞士制
• ...而且可能还有更多我以前从未听说过的东西。

对于每种类型的锦标赛，我想将“括号算法”实现为通用接口的实例。通过这种方式，我可以使系统具有可扩展性，并且将来可以轻松添加对附加括号的支持。

给定一个可变的“竞争对手”列表 - 用户可以简单地选择他们想要的括号插件和poof，生成括号！

设计挑战

我目前正在努力想象一个包围设计；接口所需的 API，以及 - 更重要的是 - 我不确定如何将括号“模型”通用和灵活地表示为数据结构。我猜是某种节点图？

理想情况下，我需要以下接口：

• 接受可变大小的竞争对手列表作为输入
• 生成一个图形（或其他）结构作为输出，表示括号的“流”。
• 图形结构需要支持某种“赢/输”API，以通过括号“推进”各种竞争对手，并随时填写。

问题

我希望我有更好的方式来表达这个问题；

• 我怎么做'dis？
• 你觉得呢？你有没有什么想法？
• 什么接口结构最有意义？
• 我如何在代码中对其进行一般建模？

我最初的鞭打

除非我在纸上写一些代码，否则这不会是 StackOverflow 问题。这是我最初的想法；

马上，我第一次尝试就发现了一些缺点；

• 我如何代表整个支架的“赢家”？
• 我如何代表从括号中“淘汰”的失败者？
• 我如何表示支架已完成/解决？已解决的括号是什么样的？
• 这个框架是否支持不属于简单“消除”模式的“奇怪”括号（例如循环赛）？

目前我实际上正在寻找一个专门针对我的问题的术语：

我创建了一个超过 4 支球队的联赛 联赛持续 3 轮（为了简单起见，编号） 比赛应从一支球队尚未交战的球队中随机分配。

我正在努力让我当前的代码在每个边缘情况下运行，所以我想查找为这种情况开发的“标准”算法，但我无法想出我正在寻找的术语。

一个时间表示例是：

在这方面我找不到任何东西，因为这似乎是一个非常非常不可能在联赛/锦标赛中使用的东西——但这是我的要求。

这是我当前创建 ONE Round 的代码。可能会发生，此代码不会在第 3 轮中为每个团队分配一个对手，因为他们可能的对手在本轮已经分配了一场比赛（测试了 6 支球队，可能在第 3 轮中发生）

对我将谷歌搜索的任何帮助将不胜感激

我正在尝试设计简单的数据库来展示某种锦标赛。所以我有一个显示“比赛”的表格（它包含两个团队的 ID），我还创建了表格“回合”（一轮包含很少的比赛）。还有我的问题。我想创建“某些东西”（表格/视图/程序/函数），这将使我能够在给定（通过参数或在选择指令中使用“where”）ID 后显示我的锦标赛排名。例如，有两支球队，甲队和乙队。在第一轮和第二轮比赛中，甲队获胜。因此，在我通过数字“1”之后，我想获得输出：

实现类似目标的最简单方法是什么？

有人可以告诉我我做错了什么吗？我已经对这个最小值和最大值查找器进行了编码，但我不断收到这个错误：“mml = getMinMax(a, low, high)”处的“StackOverflowError”。任何帮助将不胜感激。谢谢！

}

我想做一个循环赛，但有一个转折点。

周围有大量的循环实现，但到目前为止我看到的每一个都会生成一个时间表，每个人都遵循它。我的主要问题是，在比赛快结束时，选手 A 经常面对选手 B，但选手 A 知道无论结果如何，他的最终排名都是固定的，而选手 B 的排名取决于他与选手 A 的比赛换句话说，一个玩家不在乎结果，另一个在乎。这留下了令人讨厌的可能性，即 A 没有尽力而为，因此 B 可以得到比他/她在日程安排不同的情况下更高的最终分数（例如，如果 A 对 B 是锦标赛的第一场比赛） . 这是我对“坏”匹配的定义

我想知道是否有一种方法可以在循环赛的每一步计算下一组要玩的游戏，以便尽可能避免这个问题。我怀疑这并不总是可能的（10 人锦标赛，9 名非常熟练的参与者，一个非常不熟练的参与者。在 0-8 之后，如果其他人都是 5-3 或 4-4，最后一场比赛是一场“糟糕”的比赛）

我允许一条额外的信息：Elo 排名。直觉上，如果有两名选手比其他选手差很多，他们可以预期会被其他人击败，因此只有他们的正面交锋才重要。因此，避免“糟糕”比赛的唯一方法是将他们的头对头比赛放在最后。

我的衡量标准如下：提出一个循环调度程序，让 N 名玩家与他们各自的 Elo 并在每一步输出一个时间表，以便该调度程序最大化第一个“坏”比赛出现的平均时间（即：如在比赛中尽可能晚）。更简单的版本是在开始时输出一次时间表。

您可以假设玩家的成绩可以通过他们的 Elo 等级准确地表示，并且该等级是固定的和已知的。

这也将“糟糕”比赛的定义从“我确定这场比赛和任何后续比赛都不会改变我的最终排名”更改为“我有 99% 的概率知道这场比赛和任何后续比赛都不会改变我的最终排名” ”。当然99%可以改

我的意思是，结果可能是按照他们的 Elo 从 E_1 到 E_n 对所有玩家进行排序，最后一场比赛是（E_1 vs E_2）......（E_n-1 vs E_n）。但我想要一些见解

编辑 ：

澄清一下，“你可以假设玩家的成绩可以通过他们的 Elo 等级准确地表示”意味着如果等级是 R_A 和 R_B，那么 A 的胜率正是这里Elo 公式给出的

您在锦标赛中的排名仅取决于您的获胜次数

我有一个即将举行的国际足联锦标赛，我编写了一个程序来打印出可能的比赛。问题是它没有按逻辑排序，这意味着一些玩家必须连续玩 5-6 场比赛，而另一些则必须等待 6 场比赛。我想得到以下结果：

等等。这就是我目前所拥有的：

但这是打印出来的：

我使用了 Multimap，因为我需要多个具有相同值的键。

我正在查看一份过去的试卷，以备即将到来的一项考试。这是以下问题：

假设您的人口为 6。第一个解决方案的适应度，f(S1)=2；第二种解 f(S2)=4；f(S3)=8；f(S4)=16；f(S5)=19；f(S6)=27。假设您使用带有替换的锦标赛选择，锦标赛规模为 6。忽略交叉和变异，写下下一代可能的种群。

有谁知道我从哪里开始回答这个问题？我很困惑，需要一些方向。

到目前为止我有这个：

我走的是正确的路线吗？

非常感谢