123 好数 - 算法题解及C++代码

123 好数 - 算法题解及 C++ 代码

题目描述

一个数中如果如果不含连续的'12', 连续的'23', 连续的'31', 就称作'123'好数. 那么, 在由123构成的n位数中, 第k个'123'好数是什么?

输入

一行, 两个正整数n,k, 用空格分隔

输出

一行, 输出由123构成的n位数中, 第k个'123'好数.

样例输入

6 14

样例输出

113322

提示

【说明提示】 1≤n≤20 k不超过满足条件的'123'好数个数

C++ 代码

#include <iostream>
#include <vector>
using namespace std;

// 判断一个数是否为'123'好数
bool isGoodNumber(int num) {
    string str = to_string(num);
    for (int i = 2; i < str.length(); i++) {
        if (str[i] == '3' && str[i-1] == '2' && str[i-2] == '1') {
            return false;
        }
    }
    return true;
}

// 生成由123构成的n位数
void generateNumbers(vector<int>& numbers, int n, int num) {
    if (num > n) {
        numbers.push_back(num);
        return;
    }
    generateNumbers(numbers, n, num * 10 + 1);
    generateNumbers(numbers, n, num * 10 + 2);
    generateNumbers(numbers, n, num * 10 + 3);
}

int main() {
    int n, k;
    cin >> n >> k;
    
    vector<int> numbers;
    generateNumbers(numbers, n, 0);
    
    int count = 0;
    for (int num : numbers) {
        if (isGoodNumber(num)) {
            count++;
            if (count == k) {
                cout << num << endl;
                break;
            }
        }
    }
    
    return 0;
}

代码解析

1. isGoodNumber(int num) 函数用于判断一个数是否为'123'好数。
2. generateNumbers(vector<int>& numbers, int n, int num) 函数用于生成由123构成的n位数。
3. main() 函数中，首先读取输入的n和k，然后调用generateNumbers()函数生成所有由123构成的n位数。
4. 遍历生成的数字，调用isGoodNumber()函数判断是否为'123'好数，并计数。
5. 当计数器达到k时，输出当前数字并结束程序。

总结

本篇文章详细介绍了如何解决“123 好数”问题，并提供了完整的C++代码实现。希望本文能帮助读者更好地理解算法思路，并提高编程能力。