私は12の比較で中央値を見つけることができます。しかし、比較の最小数とその方法を知りたいです。
2153 次
3 に答える
9
Donald Knuthは、 The Art ofComputerProgrammingのVolumeIIIに「Minimum-ComparisonSelection」に関する章を持っています。
Knuthは、「[最小数の比較で選択する]一般的な方法はまだ明らかではありません」と述べていますが、最小に近いいくつかの一般的な方法を示しています。
表5.3.3–1を見ると、V₄（7）= 10（つまり、最大10の比較を使用して7つの項目の中で4番目に大きい項目を見つけることができます）とアルゴリズム（「試行錯誤によって手動で見つけられた」）がわかります。 "）は、5.3.3–10を実行するためのソリューションで与えられます。
于 2010-11-11T12:32:42.070 に答える
1
並列比較を許可する場合（最新のCPUはおそらくこれを実行します）、ソーティングネットワークを使用して6つのステップで問題を解決できます。
于 2010-11-11T23:38:16.480 に答える
0
（7s）の場合、飛行ロボットを見つけたときに正しい軌道に乗っていることがわかります（ハッセ図）。10コンプを検証する主なケースは2つあります。他の場合は限界に近づいていません。（7s）は、Eのゼブラパズルのような完璧なパズルに近いです。それほど難しくはありませんが、十分に難しいので、訓練を受けた人だけが最初にそれをクラックします。
これで、（4s、3）も7つの数字で、（7s）と等しくなります。ここでは、数値の1つが3回繰り返されると仮定します（多重度3）。答え（最適な三元樹の高さ）はわかりません。それを見つけに行きなさい！
于 2019-05-08T03:12:01.357 に答える