C++で数値を最小個数の疑似2進数の合計として表現する方法

疑似2進数とは

疑似2進数(pseudo-binary number)とは、0と1という2進数の数字のみで構成される数値のことです。例として、00、11、10、100、111、1011などが挙げられます。

このチュートリアルでは、ある数値Nをできるだけ少ない個数の疑似2進数の合計として表現する方法を解説します。

以下に、数値を疑似2進数の合計として表した具体例を示します。

入力 : 23
出力 : 11 + 11 + 1
説明 : 23 = 11 + 11 + 1、つまり疑似2進数(11、11、1)の合計は23になります。

入力 : 50
出力 : 10 + 10 + 10 + 10 + 10

解法のアプローチ

Nを表現するための最小個数の疑似2進数を見つけるための、効果的なアプローチを以下に示します。

• 数値Xを作成し、Nの各桁の値に応じてXの対応する桁を1または0に更新します。

• Nの各桁を確認します。

  • その桁が0の場合、Xの対応する桁を0にします。

  • 0以外の場合、Xの対応する桁を1にします。

  • 例えば、N = 32 の場合、X = 11 となります。

• こうして得られたXは、1つの疑似2進数です。

• NからXを減算し、Nが0になるまで手順1を繰り返します。

C++による実装例

上記アプローチのC++コード

#include<iostream>
using namespace std;
int main(){
    int N = 51;
    // Nが0になるまで疑似2進数を求め続けます。
    cout << "pseudo-binary representation of " << N << " is: ";
    while (N > 0){
        // Nの各桁に応じて0と1で構成されるXを求めます。
        int temp = N;
        int X = 0, bit = 1;
        // tempの各桁がゼロかどうかを確認します。
        while (temp!=0){
            int last_dig = temp % 10;
            temp = temp / 10;
            if (last_dig != 0)
                X += bit;
            bit *= 10;
        }
        // 疑似2進数を1つ出力します。
        cout << X << " ";
        // NからXを引いて更新します。
        N = N - X;
    }
    return 0;
}

実行結果

pseudo-binary representation of 51 is: 11 10 10 10 10

コードの解説

• 外側のwhileループでは、Nを受け取り、各桁の数字を取り出してXを求めます。

• 変数tempにNの値をコピーし、内側のループでtempの各桁を確認しながら、変数Xの対応する桁を更新していきます。

• Xの値を出力します。これが1つの疑似2進数に相当します。

• NからXを減算して更新し、Nが0になるまで外側のループを繰り返します。

まとめ

このチュートリアルでは、数値を最小個数の疑似2進数の合計として表現する方法について解説しました。すべての疑似2進数を効率的に見つけるアプローチと、そのC++実装コードを紹介しました。なお、ここで紹介したロジックは、C、Java、Pythonなど他のプログラミング言語でも同様に実装できます。本チュートリアルが皆さんのお役に立てば幸いです。