|
uchinyan |
|
はい，こんにちは。さて，今回の問題は．．．
うーむ，今回も前回みたいなことはないだろうな，とちょっとおっかなびっくり，という感じで解きました。 しかも，最初はどう考えたらいいか手がかりがピンと来なかったのですが，最も重い重りならバイナリサーチだよな，と気付き， その後は比較的容易に解けました。こんな感じで。 ２番目に重い重りを見つけるわけですが，そのためには，まず，基準となる最も重い重りを見つける必要があります。 まず，16 個を適当に 2 個ずつの 8 組に分け，各組で重さを比較し，重い方の 8 個を選びます。これには 8 回。 次に，選んだ 8 個を適当に 2 個ずつの 4 組に分け，各組で重さを比較し，重い方の 4 個を選びます。これには 4 回。 さらに，選んだ 4 個を適当に 2 個ずつの 2 組に分けま，各組で重さを比較し，重い方の 2 個を選びます。これには 2 回。 そして，選んだ 2 個の重さを比較し，重い方の 1 個を選びます。これには 1 回。 この最後に残ったものは，常に重い方同士を比較してきたので，最初の 16 個の中で最も重い重りです。 ここまでで，8 + 4 + 2 + 1 = 15 回。 求める重りは２番目に重い重りなので，この最も重い重りと比較して軽かった 4 個の中にあるはずです。 何故ならば，これら 4 個以外の重りはこれら 4 個のいずれかと比較してより軽かったからです。 そこで，これら 4 個の中で最も重い重りを見つければ，それが２番目に重い重りになります。 これは同様にして，2 + 1 = 3 回。 結局，２番目に重い重りを見つけるには，15 + 3 = 18 回，が必要です。 ．．．と思いますが。最小性は大丈夫なのかな。 多分，最初に書いたように，２番目に重い重りを見つけるには基準となる最も重い重りを見つける必要があると思うので， 大丈夫だろうと思うのですが。 |
|
ネコの住む家
10月9日（木） 17:34:39
42511 |