algorithm - 赛车拼图

Question

你能帮我解决这个我找不到好的答案的难题吗!!

有 49 辆汽车以独特的速度比赛。还有一个赛道，最多可以让 7 辆车一起比赛。我们需要找到组中第 25 快的汽车。我们没有秒表来测量时间(因此我们只能测量每辆汽车相对于比赛中其他 6 辆汽车的相对速度)。最少需要多少场比赛？

Answer 1

遵循辩证法的灵感。分成 7 个随机组，对每个组进行比赛，然后对这些组的中位数进行比赛。这辆车成为枢轴，我们已经知道它与其他 30 辆汽车的直接或间接关系(这是中位数的属性)。因此，将其与resp一起放置。其他 18 辆我们需要跑 3 场比赛，包括支点。旋转之后，我们最多需要对 33 辆汽车进行递归。继续前进。我结束了 29 场比赛。即使您假设需要完全排序(实际上不需要)，也有 17 场比赛的下限(真正的下限会更低)，远小于 29。所以我怀疑这不是正确的答案，但由于这一直缺乏任何解决方案，这里是一个次优的解决方案。如果你看一下排序网络的研究(这个问题是一次限制两辆车的比赛)，找到最佳网络是困难的，而且最佳网络只在非常小的尺寸下已知，绝对不超过 49。我不知道关于具有 7 向比较器的网络的任何研究。

也许一个例子可以提供帮助。假设按照从最慢到最快的顺序对汽车进行编号，并将它们排列在 7x7 矩阵中(任意排列，因为在我们比赛之前我们不知道速度)。

     [,1] [,2] [,3] [,4] [,5] [,6] [,7]
[1,]   34   25   45   43   26   21   13
[2,]   11   24    2   40   14   30   32
[3,]   27   19   29   42    4   17   46
[4,]   15   10   39   33    1    9    5
[5,]   28   18   41    8   23   20    6
[6,]   16    3   38    7   12   22   36
[7,]   31   44   48   35   49   37   47

然后让我们对每一列进行比赛，并根据比赛结果对它们进行排序:

     [,1] [,2] [,3] [,4] [,5] [,6] [,7]
[1,]   11    3    2    7    1    9    5
[2,]   15   10   29    8    4   17    6
[3,]   16   18   38   33   12   20   13
[4,]   27   19   39   35   14   21   32
[5,]   28   24   41   40   23   22   36
[6,]   31   25   45   42   26   30   46
[7,]   34   44   48   43   49   37   47

现在让我们比赛第 4 行(中位数)并根据结果重新排列列

     [,1] [,2] [,3] [,4] [,5] [,6] [,7]
[1,]    1    3    9   11    5    7    2
[2,]    4   10   17   15    6    8   29
[3,]   12   18   20   16   13   33   38
[4,]   14   19   21   27   32   35   39
[5,]   23   24   22   28   36   40   41
[6,]   26   25   30   31   46   42   45
[7,]   49   44   37   34   47   43   48

现在观察中位数(元素 [4,4])比上方和左侧的任何汽车都快，比下方和右侧的任何汽车慢(这是中位数的属性)。对于其他汽车(左下角和右上角)我们不知道，所以我们需要让它们与 [4,4] 比赛，一次 6 辆(3 场比赛)。现在我们观察到 26 辆汽车比 [4,4] 慢，因此中位数必须是其中之一。无需再与其他任何人比赛。现在对这 26 辆车重复该过程。