In Tất Cả Số N Chữ Số Có Hiệu Tuyệt Đối Giữa Tổng Chữ Số Chẵn Lẻ Bằng 1 Trong C++

Trong bài toán này, chúng ta được cho số nguyên n, in tất cả số N chữ số sao cho hiệu tuyệt đối giữa tổng chữ số ở vị trí chẵn và lẻ là 1. Số 0 dẫn đầu không được phép.

Hiệu tuyệt đối là hiệu giữa hai số lấy giá trị tuyệt đối (giá trị dương).

Ví dụ để hiểu vấn đề:

Đầu vào: n = 2 → Đầu ra: 10 12 21 23 32 34 43 45 54 56 65 67 76 78 87 89 98
Giải thích: Với 54, chữ số chẵn - chữ số lẻ = 5 - 4 = 1. Với 89: 8 - 9 = -1, |-1| = 1.

Để giải quyết, ta tìm tất cả số N chữ số có hiệu 1 hoặc -1. Cố định vị trí chữ số với mọi giá trị, dựa trên vị trí chẵn/lẻ, gọi đệ quy cho các vị trí khác sao cho điều kiện thỏa mãn.

Ví Dụ

Chương trình minh họa giải pháp:

#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 << " chữ số với hiệu tuyệt đối 1:\n";
    findNumberWithDifferenceOne(n);
    return 0;
}

Đầu Ra

3 chữ số với hiệu tuyệt đối 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