C言語の練習問題としてよく出題される「Hit and Blow（ヒット＆ブロー）」では、ヒットとブローの定義がやや直感と異なるため、実装時に混乱が生じやすいポイントがあります。特に「重複数字がある場合のブローの数え方」で、問題文の例と自分のプログラム結果が一致しないケースがよく発生します。本記事では、そのズレの原因と正しい考え方について整理して解説します。
Hit and Blowの基本ルールのおさらい
Hit and Blowは、4桁の数字などを対象にした数当てゲームです。
同じ位置に同じ数字があれば「ヒット」、位置が違っていて同じ数字があれば「ブロー」としてカウントします。
ただし、重要なのは「各桁は一度だけ使用される」という制約です。
ブローのカウントでよくある誤解
ブローを単純に「一致する数字の総数」として考えると、実装結果と問題例が一致しないことがあります。
これはヒットとブローの優先順位と、1つの数字を複数回カウントしないルールが原因です。
そのため、単純な重複カウントでは正しく判定できません。
問題の例「1112 vs 1221」の正しい考え方
正解「1112」と予想「1221」を比較すると、数字の一致数だけを見ると4つすべて一致しているように見えます。
しかしヒットを先に確定させると、位置一致が1つ発生し、その分を除外してブローを計算する必要があります。
結果としてヒット1・ブロー2となるのが問題文の意図です。
なぜ「1ヒット3ブロー」にならないのか
「1ヒット3ブロー」としてしまう実装は、同じ数字を複数回カウントしている可能性があります。
例えば「1」が複数回一致する場合でも、使用済みの数字を再利用してしまうと過剰カウントになります。
このため、配列管理やフラグ管理で「使用済み管理」が必要になります。
C言語での正しい実装アプローチ
一般的な実装では、まずヒットを判定し、その後に残りの数字でブローを判定します。
具体的には、正解と予想の各桁をチェックし、使用済みフラグを立てながら比較する方法が安全です。
この手順により重複カウントを防ぐことができます。
配列を使った安全な判定方法
0〜9の出現回数を配列で管理する方法もよく使われます。
正解と予想の数字をそれぞれカウントし、最小値をブローとして扱うことで正確に計算できます。
この方法はバグが少なく実装もシンプルです。
まとめ｜例は正しく、実装側のカウント方法がポイント
問題文の「1ヒット2ブロー」という結果は、ヒット優先・使用済み管理というルールに基づいた正しい結果です。
一方で「1ヒット3ブロー」になる場合は、ブローの重複カウントが発生している可能性があります。
ヒット＆ブローは単純な一致問題ではなく、状態管理が重要なアルゴリズム問題です。
コメント