2018-水もれ-解説
- 考案国：南アフリカ共和国
- 正解
- 「4」
- 説明
- 最初は、16軒の家のどこで水漏れがおきているか分かりません。
- まず、15 個の中で真ん中の8軒目と9軒目のバルブを閉めます。メーターが動いてると1軒目〜8軒目のどこかで、メーターが止まると9軒目から16軒目のどこかで、水漏れがおきていることが分かります。つまり、水漏れがおきている可能性がある場所が16ヶ所から8ヶ所と、半分になります。
- 水漏れがおきている可能性がある場所の真ん中のバルフを閉めることで 水漏れがおきている可能性がある場所を半分にするということを繰り返すと、2回目で可能性がある場所は4ヶ所となり、3回目で2ヶ所ととなり、4回目で1ヶ所、つまり、水漏れしている場所を特定できます。
- 実際のコンピュータでは
- 上の説明のように、目的のデータや障害の箇所を探すのに、対象を半分ずつに分けて探しているデータや原因がどちらにあるかを探していく方法を、二分探索といいます。
- この問題では、原因を左から順に探していくと、最悪の場合は16回の検査が必要になってしまいます。4回で原因を特定できる二分探索のようなアルゴリズムは大量のデータを扱うときに有用です。
注があるものを除き, このサイトの内容物は
