C++で1からnまでの数のうち、数字「4」を含む数を数える方法

このチュートリアルでは、1からnまでの整数の中に、数字「4」が含まれる数がいくつあるかを求めるプログラムについて解説します。

具体的には、ある数nが与えられたとき、その範囲内で「4」という桁を少なくとも1つ持つすべての数を数え上げ、その個数を出力するのが目的です。

アルゴリズムの考え方

この問題はシンプルなアプローチで解くことができます。

まず、1からnまでの各数値に対して、「4」という桁が含まれているかどうかを判定します。判定には、数値を10で割った余り（最下位の桁）を順番に確認していく方法を使います。もし余りが4であれば、その数には「4」が含まれていると判断できます。桁の確認が終わるまで、数値を10で割り続けることで、すべての桁を調べることが可能です。

次に、条件を満たす数を見つけるたびにカウントを増やし、最終的な合計を結果として返します。

実装例

以下に、C++での実装例を示します。

#include<iostream>
using namespace std;
bool has4(int x);
// 1からnまでの数のうち、4を含む数の合計を返す
int get_4(int n){
    int result = 0;
    // 各数値について判定を行う
    for (int x=1; x<=n; x++)
        result += has4(x)? 1 : 0;
    return result;
}
// 数字「4」が含まれているかどうかをチェックする
bool has4(int x) {
    while (x != 0) {
        if (x%10 == 4)
            return true;
        x = x /10;
    }
    return false;
}
int main(){
    int n = 328;
    cout << "Count of numbers from 1 to " << n
        << " that have 4 as a digit is "
        << get_4(n) << endl;
    return 0;
}

出力結果

Count of numbers from 1 to 328 that have 4 as a digit is 60

この例では、1から328までの範囲に「4」を含む数は60個存在することがわかります。

処理の流れのポイント

• has4関数：引数として受け取った数値の各桁を下の桁から順に確認し、「4」が見つかった時点でtrueを返します。最後まで見つからなければfalseを返します。
• get_4関数：1からnまでループを回し、has4関数の結果がtrueであればカウントを1ずつ加算していきます。

この方法の計算量はO(n × 桁数)となるため、nが非常に大きい場合には効率化の余地がありますが、基本的な桁操作の練習としては非常に分かりやすい実装です。