C++でキース数（Keith Number）を判定するプログラムの作成方法

はじめに

このチュートリアルでは、与えられた整数がキース数（Keith Number）であるかどうかを判定するプログラムをC++で作成します。

キース数とは？

キース数とは、その数自身の各桁の数字から生成される数列の中に、元の数が現れるような特別な数のことです。数列の最初の項は数nの各桁の数字とし、それ以降の項は直前のd項（dは桁数）の合計として再帰的に計算されます。

例えば「14」の場合を見てみましょう。初期項は 1, 4 です。次の項は 1+4=5、続いて 4+5=9、そして 5+9=14 となります。数列の中に元の数「14」が現れたため、14はキース数です。

アルゴリズムの手順

1. 判定対象となる数nを初期化します。
2. 数列を格納するための空のベクター（vector）を用意します。
3. 桁数を数えながら、各桁の数字をベクターに追加します。
4. ベクター内の桁の並びを逆順にします。
5. 次の項を保持する変数を0で初期化します。
6. 次の項がn未満である間、以下の処理を繰り返します。
   • 直近のd個の項を合計して、次の項を求めます。
   • 求めた次の項をベクターに追加します。
7. ループ終了時の次の項がnと一致すればtrue、一致しなければfalseを返します。

サンプルコード

それでは、実際のコードを見てみましょう。

#include<bits/stdc++.h>
using namespace std;
bool isKeithNumber(int n) {
    vector<int> elements;
    int temp = n, digitsCount = 0;
    while (temp > 0) {
        elements.push_back(temp % 10);
        temp = temp / 10;
        digitsCount++;
    }
    reverse(elements.begin(), elements.end());
    int nextElement = 0, i = digitsCount;
    while (nextElement < n) {
        nextElement = 0;
        for (int j = 1; j <= digitsCount; j++) {
            nextElement += elements[i - j];
        }
        elements.push_back(nextElement);
        i++;
    }
    return nextElement == n;
}
int main() {
    isKeithNumber(43) ? cout << "Yes" << endl : cout << "No" << endl;
    isKeithNumber(14) ? cout << "Yes" << endl : cout << "No" << endl;
    isKeithNumber(197) ? cout << "Yes" << endl : cout << "No" << endl;
    return 0;
}

実行結果

上記のコードを実行すると、以下の出力が得られます。

No
Yes
Yes

43はキース数ではありませんが、14と197はキース数であることが確認できます。実際、197の場合は 1, 9, 7 → 17 → 33 → 57 → 107 → 197 と続き、数列の中に197が現れます。

まとめ

このチュートリアルでは、キース数の定義と、C++を使った判定アルゴリズムの実装方法を学びました。桁ごとの数字から数列を生成し、元の数が現れるかどうかを確認するというシンプルなアプローチで実装できます。チュートリアルについて質問がある場合は、コメント欄でお気軽にお知らせください。