C++の基数変換法を使って数値がkの冪乗かどうかを判定する方法

はじめに

この記事では、ある数値と値 k が与えられたとき、その数値が k の冪乗であるかどうかを「基数変換法(底の変換)」を用いて判定するC++プログラムを紹介します。

例として、数値が 27、k = 3 のケースを考えてみましょう。27 を 3 進法で表すと「1000」になります。このように基数変換を行った結果、「1」がちょうど1回だけ現れ、それ以外の桁がすべて「0」であれば、その数値は k の冪乗であると判断できます。

アルゴリズムの手順

この問題は、以下の手順に従って解くことができます。

• フラグ(flag)を false として初期化する
• number > 0 の間、手順3〜6を繰り返す
• digit := number mod k を計算する(k進法での現在の桁を取得)
• digit > 1 の場合は false を返す
• digit が 1 の場合、flag がすでに true であれば false を返し、そうでなければ flag := true とする
• number := number / k として更新する
• ループを抜けたら true を返す

このアルゴリズムの計算量は O(log_k n) であり、非常に効率的です。

サンプルコード(C++)

#include <iostream>
#include <cmath>
using namespace std;
bool isPowerOfK(int num, int k) {
    bool flag = false;
    while (num > 0) {
        int digit = num % k; // k進法での現在の桁を取得
        if (digit > 1) // 桁が0でも1でもない場合、kの冪乗ではない
        return false;
        if (digit == 1) {
            if (flag)
                return false;
            flag = true;
        }
        num /= k;
    }
    return true;
}
int main() {
    int number = 27, K = 3;
    if(isPowerOfK(number, K)){
        cout << number << " is power of " << K;
    } else {
        cout << number << " is not power of " << K;
    }
}

実行結果

27 is power of 3

コードの解説

isPowerOfK 関数では、数値を k で割りながら各桁を順番に調べていきます。途中で「1」以外の非ゼロの桁が見つかった時点で、その数値は k の冪乗ではないと即座に判定できます。また、「1」が2回以上現れた場合も冪乗ではないため、flag 変数によって「1」の出現を管理しています。

上記の例では、27 を 3 進法で表すと「1000」となり、「1」が1回だけ出現するため、27 は 3 の冪乗(3³)であると正しく判定されています。