0

stackoverflow で重複した質問を確認しました。これは近いかもしれません：必要なテニスの試合数を見つけてください

これはAmazonのインタビューの質問です. 「p」プレイヤーの場合、クリティカル パスでの Θ(log p) 操作がこれに対する正しい答えであるかどうかを知りたい (トーナメント バリア アルゴリズムと同じ -> John Mellor-Crummey)。

たとえば、1、2、3、4 の 4 人のプレーヤーがいるとします。次の間で試合をスケジュールできます。

 1)  Between (1 & 2)

 2)  Between (3 & 4) 

 3) organize the third match between winners of these two matches.

同様に、5 人 (奇数) のプレイヤーの場合、以下の間で試合をスケジュールできます。

 1) (1 & 2) and (3 & 4) 

 2) Winner from (1&2) OR winner from (3&4) against 5

 3) Winner between winner of not chosen group and winner from previous match

.

4

1 に答える 1

4

すべての試合で1人のプレイヤーが排除されます。p人のプレイヤーから1人のプレイヤーに減らすには、p-1試合が必要です。

最大数の試合を同時にスケジュールしている場合、プレーヤーは一度に1つの試合にしか参加できないという制約があり、多くのラウンドが必要なことを知りたい場合、つまり、ceiling（log p）です。

于 2013-03-16T18:00:17.217 に答える