今回はプログラミングのための
脳を鍛えるトレーニングとして
天秤問題をやっていきます。
解説動画はこちら
さて天秤問題ですが、簡単なクイズです。
2問を用意しています。
問題1
8個の同じサイズのボール
7つは同じ重さですが1つだけ重いものが
混じっています。
秤を2回だけ使って重いボールを見つけるには
どうすれば良いでしょう?
割と簡単な問題で良くいろんな企業の試験に出ていたりします。
考えたい方はここで止まって考えてみましょう。
秤を効率よく使って最小回数で答えを見つける
コレは最適解を考える問題でもあり
出来るようになるといろんな場面で役立ちます。
問題1の解答
さて解答は以下のように考えます。
1回目は3,3,2でボールを分けて
3,3を乗せて測ります。
結果は
・釣り合う
・上下動
の2通りになります。
2回目：1回目が上下動した場合
下がった方に答えがあるので
下がった方の3つのボールのうち1,1で秤に乗せて測り
釣り合えば残ったボール
下がった場合はその下がったボールが答えになります。
2回目：1回目が釣り合った場合
3,3で釣り合ったら、残る2つの中に答えがあります。
残りを1,1で秤に乗せて計って下がった方が答えになります。
まとめるとこうなります。
1問目は比較的考えるのが楽ですねーー
問題2
13個の同じサイズのボール
12つは同じ重さですが1つだけ
重さが違うものが混じっています。重いか軽いかは分かりません。
秤を3回だけ使って重いボールを見つけるにはどうすれば良いでしょう?
今度は13個にボールが増えてしかも重いか軽いかも分かりませんので
少し難しいかもしれないですね。
考えたい方はここで止めて考えてみましょう。
解説はこの下です。
問題2の解答
まず最初はボールをどう分けて測るかです。
4,4,5に分ける事として4,4を秤に乗せて測ります。
結果は
・釣り合う
・上下動
の2通りになります。
2回目：1回目が釣り合った場合
4,4は同じ重さなのでこの8個はセーフ
残る5個の中に答えがあります。
残る5個のうちの3つを選んで秤に乗せ
セーフの中から3つを乗せて測ります。
結果は
・釣り合う
・上下動
の2通りになります。
3回目:1回目に釣り合い、2回目も釣り合った場合
残る2つの中に答えがあるので
そのうちの1つを秤に乗せセーフの中から1つを乗せて測ります。
釣り合った場合は残った一つ
上下動した場合は、セーフでない物が答えになります。
3回目：1回目に釣り合い、2回目上下動した場合
選んだ3つの中に答えがあります。
その3つのうち1,1を選んで秤に乗せ測ります。
釣り合った場合は残った一つが答え。
上下動した場合は2回目の結果と合わせて考えます。
2回目にその3つが上がった場合は
軽い物が混じっているので3回目に上がった方が答えです。
2回目にその3つが下がった場合は
重い物が混じっているので3回目に下がった方が答えです。
2回目：1回目に釣り合わなかった場合
4,4で釣り合わなかった場合は
その8つの中に答えがあり測らなかった5つはセーフです。
この8個を2群に分ける事にして測っていきます。
便宜上1回目に測った物をABCD - EFGH として
ABE - CDF を秤に乗せて測りGHを残します。
この2回目の測り方の結果は
・釣り合う
・上下動
の2通りになります。
3回目：1回目上下動して、2回目釣り合った場合
この2回目が釣り合ったら残ったGHの中に答えがあるので
Gとセーフから1つを選んで測ります。
釣り合えば残りのHが答え
上下動したらGのボールが答えになります。
3回目：1回目上下動して、2回目上下動した場合
1,2回目とも上下動した場合は
2回目に測ったこの6個の中に答えがあることになります。
1,2回目で測った際のパターンとしては
4通りあることになります。
ここからは1,2回のパターンごとに3回目を考えることになります。
4パターンの結果はこうなります。
まとめるとこうなります。
測りの結果は「釣り合う」か「上下動」するので
そのパターンごとに全通りを考えれば良いでしょうね。
さて、天秤問題はいかがでしたでしょうか?
たまにはこういうクイズも良いですよね。
またお会いしましょう。
それでは。
作者の情報
乙pyのHP：
http://www.otupy.net/
Youtube：
https://www.youtube.com/channel/UCaT7xpeq8n1G_HcJKKSOXMw
Twitter：
https://twitter.com/otupython