基于01计数递推规则递归生成第n个字符串的C++实现方法

DevOps 小满

2026-10-6

校招字符串递推题C++实现方案

前置规则梳理

初始两个字符串的1、0计数：
- 第1个字符串s1 = "11100"：1的个数为3，0的个数为2
- 第2个字符串s2 = "1111000"：1的个数为4，0的个数为3
n≥3时的递推规则：
- 第n个字符串的1个数 = 第n-1个字符串的1个数 + 2 * 第n-2个字符串的0个数
- 第n个字符串的0个数 = 2 * 第n-1个字符串的0个数 + 2 * 第n-2个字符串的1个数
输出规则：参考前两个字符串的格式，所有1在前、所有0在后拼接为最终字符串

注意：递推数值增长速度极快，n超过20后会超出int存储范围，代码中使用long long类型存储计数，如需支持更大的n可替换为大数实现

完整实现代码

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

int main() {
    int n;
    cin >> n;
    // 直接返回初始的两个字符串结果
    if (n == 1) {
        cout << "11100" << endl;
        return 0;
    }
    if (n == 2) {
        cout << "1111000" << endl;
        return 0;
    }
    // 滚动变量存储前两项的计数，节省空间
    long long prev2_one = 3, prev2_zero = 2; // 对应n-2位置的计数，初始为n=1的数值
    long long prev1_one = 4, prev1_zero = 3; // 对应n-1位置的计数，初始为n=2的数值
    long long curr_one, curr_zero;
    for (int i = 3; i <= n; ++i) {
        curr_one = prev1_one + 2 * prev2_zero;
        curr_zero = 2 * prev1_zero + 2 * prev2_one;
        // 更新滚动变量
        prev2_one = prev1_one;
        prev2_zero = prev1_zero;
        prev1_one = curr_one;
        prev1_zero = curr_zero;
    }
    // 拼接输出字符串
    string res;
    res.append(prev1_one, '1');
    res.append(prev1_zero, '0');
    cout << res << endl;
    return 0;
}