C++で偶数の位と奇数の位の合計の絶対差が1となるn桁の数をすべて出力する方法

問題の概要

この問題では、整数 n が与えられ、「偶数の位にある桁の合計」と「奇数の位にある桁の合計」の絶対差が 1 となるすべての n 桁の数を出力することが求められます。なお、数を生成する際に先頭の 0 は考慮しません（先頭が 0 のものは n 桁の数として扱いません）。

ここでいう絶対差とは、2つの値の差の絶対値（常に正の値）を意味します。

具体例を使って、問題を理解しましょう。

入力: n = 2
出力: 10 12 21 23 32 34 43 45 54 56 65 67 76 78 87 89 98
説明: 出力の中の数を例にとると、
54 の場合 → 偶数の位 − 奇数の位 = 5 − 4 = 1
89 の場合 → 8 − 9 = −1、|−1| = 1 となり条件を満たします。

解決のアプローチ

この問題を解くには、差が 1 または −1 となるすべての n 桁の数を見つける必要があります。そのために有効なのが、ある一つの桁の値を固定し、その桁が偶数の位か奇数の位かに応じて、残りの桁の値を再帰的に決定していくという方法です。これにより、条件（絶対差が 1）を満たす数だけを効率的に生成できます。

実装例

以下のプログラムは、この解法を実際に実装したものです。

#include <iostream>
using namespace std;
void printNumber(int n, char* out, int index, int evenSum, int oddSum){
    if (index > n)
        return;
    if (index == n){
        if (abs(evenSum - oddSum) == 1) {
            out[index] = ' ';
            cout << out << " ";
        }
        return;
    }
    if (index & 1) {
        for (int i = 0; i <= 9; i++) {
            out[index] = i + '0';
            printNumber(n, out, index + 1, evenSum, oddSum + i);
        }
    } else {
        for (int i = 0; i <= 9; i++) {
            out[index] = i + '0';
            printNumber(n, out, index + 1, evenSum + i, oddSum);
        }
    }
}
int findNumberWithDifferenceOne(int n) {
    char out[n + 1];
    int index = 0;
    int evenSum = 0, oddSum = 0;
    for (int i = 1; i <= 9; i++) {
        out[index] = i + '0';
        printNumber(n, out, index + 1, evenSum + i, oddSum);
    }
}
int main() {
    int n = 3;
    cout<<n<<" digit numbers with absolute difference 1 : \n";
    findNumberWithDifferenceOne(n);
    return 0;
}

出力結果

3 digit number with absolute difference 1 −
100 111 120 122 131 133 142 144 153 155 164 166 175 177 186 188 
197 199 210 221 230 232 241 243 252 254 263 265 274 276 285 287 
296 298 320 331 340 342 351 353 362 364 373 375 384 386 395 397 
430 441 450 452 461 463 472 474 483 485 494 496 540 551 560 562 
571 573 582 584 593 595 650 661 670 672 681 683 692 694 760 771 
780 782 791 793 870 881 890 892 980 991

まとめ

このように、再帰を活用して各桁の値を順番に決定していくことで、偶数の位と奇数の位の合計の絶対差が 1 となる n 桁の数をすべて効率よく出力できます。実装のポイントは、先頭の桁を 1〜9 の範囲で設定し、それ以降の桁については 0〜9 の範囲で値を試しながら、偶数の位か奇数の位かに応じて合計を更新していく点です。