天秤を用いた重いボールの特定クイズ

こんにちは。ゆうせいです。

突然ですが、クイズです。

プログラミングやシステム設計において、効率的な手順を考えることは非常に重要です。今回は、限られた道具で目的のものを探し出すアルゴリズムの考え方を、クイズ形式で解説します。

新人エンジニアの皆さんは、まず自分の頭で手順を組み立ててみてください。

クイズの回答と最小回数

同じサイズのゴルフボールが8つあり、そのうち1つだけが重いとき、天秤を使って重いボールを確実に特定するために必要な最小回数は、2回です。

8つのうちから1つを探す際、1つずつ重さを量る方法では最大で7回必要になる可能性がありますが、アルゴリズムの工夫によって回数を大幅に減らすことができます。

効率的な探索の考え方

この問題を解く鍵は、対象を3つのグループに分けることです。これをプログラミングの分野では分割統治法と呼びます。

1回目の計測

まず、8つのボールを、3つ、3つ、2つの3グループに分けます。

1. 天秤の両皿に3つずつボールを乗せます。
2. 天秤が釣り合った場合：残された2つのグループの中に重いボールがあります。
3. 天秤がどちらかに傾いた場合：下がった方の皿にある3つのボールの中に重いボールがあります。

この1回目の操作で、重いボールが含まれる候補を「2個」または「3個」に絞り込むことができます。

2回目の計測

次に、絞り込まれた候補の中から重いボールを特定します。

ケースA：候補が2個の場合 天秤の両皿に1個ずつ乗せます。下がった方が重いボールです。

ケースB：候補が3個の場合 3個のうち2個を選んで両皿に乗せます。

1. 釣り合えば、乗せなかった残りの1個が重いボールです。
2. 傾けば、下がった方の皿のボールが重いボールです。

このように、どのようなパターンでも2回の計測で確実に特定が可能です。

アルゴリズムの専門解説：分割統治法

今回の解法で用いた考え方は、専門用語で分割統治法（Divide and Conquer）といいます。これは、大きな問題を小さな問題に分割して、それぞれを解決することで全体の答えを導き出す手法です。

高校の授業に例えると、辞書で単語を引くときの動作に似ています。辞書の真ん中あたりを開き、探している単語が前か後ろかを確認して、調べる範囲を半分、さらに半分と狭めていく「二分探索」もこの仲間です。今回の天秤の例では、1回の操作で範囲を3分の1に絞り込んでいるため、より効率的な分割が行われています。

手法のメリットとデメリット

このアルゴリズムを実務に適用する際の特性を整理します。

メリット 処理回数の劇的な削減が可能です。対象の数が100個、1000個と増えた場合でも、単純な比較に比べて計算量を抑えられるため、システム全体のパフォーマンス向上に直結します。

デメリット 対象を分割するための論理的な設計が必要です。単に順番に調べる方法に比べて、実装や手順の組み立てが複雑になる傾向があります。また、対象が極めて少ない場合は、分割の手間がメリットを上回ることがあります。

まとめ：次なる学習のステップ

アルゴリズムの基礎である効率的な探索について理解を深めることができました。今後の学習ステップは以下の通りです。

1. データの個数がさらに増えた場合（例：27個、81個）に必要な回数を、今回の3分割の考え方を用いて計算してみてください。
2. プログラミング言語を用いて、二分探索（バイナリサーチ）のアルゴリズムを実際にコードで記述してください。
3. 計算の効率を示す指標である計算量（O記法）について学び、なぜ分割が効率的なのかを数理的に理解してください。

これらのステップを順に踏むことで、より高度なシステム設計能力が身につきます。

セイ・コンサルティング・グループでは新人エンジニア研修のアシスタント講師を募集しています。

投稿者プロフィール

山崎講師代表取締役

セイ・コンサルティング・グループ株式会社代表取締役。
岐阜県出身。
2000年創業、2004年会社設立。
IT企業向け人材育成研修歴業界歴20年以上。
すべての無駄を省いた費用対効果の高い「筋肉質」な研修を提供します！
この記事に間違い等ありましたらぜひお知らせください。

学生時代は趣味と実益を兼ねてリゾートバイトにいそしむ。長野県白馬村に始まり、志賀高原でのスキーインストラクター、沖縄石垣島、北海道トマム。高じてオーストラリアのゴールドコーストでツアーガイドなど。現在は野菜作りにはまっている。

最新の投稿

• 新人エンジニア研修講師2026年4月8日状態遷移で解くリソースの組み合わせ問題
• 新人エンジニア研修講師2026年4月8日剰余演算によるグループ化と周期性 「100日後の曜日」
• 新人エンジニア研修講師2026年4月8日植木算から学ぶ境界値とオフセットの考え方
• 新人エンジニア研修講師2026年4月8日クリティカルパスの最適化：吊り橋のパズルとリソース管理