找出所有满足条件的正整数序列 - C++ 代码实现 - 常规

找出所有满足条件的正整数序列 - C++ 代码实现

题目描述

要求找到一个正整数序列，满足序列中所有的数不超过 n，序列长度为 m，且除了第一个数外，所有的数都能被前一个数整除（即是前一个数的倍数）。

我们想要知道这样的序列都有哪些，输出所有满足要求的序列。

输入

第一行，两个正整数 n，m。

输出

按字典序从小到大，每行输出一个满足要求的序列，数与数之间用空格分隔。

样例输入

4 3

样例输出

提示

【样例说明】以下 13 个数列满足条件 1,1,1；1,1,2；1,1,3；1,1,4；1,2,2；1,2,4；1,3,3；1,4,4；2,2,2；2,2,4；2,4,4；3,3,3；4,4,4。
说明/提示 1≤n≤40；1≤m≤20

C++ 代码内容

#include<iostream>
using namespace std;

int n, m;
int a[25];

void dfs(int k) {
    if (k > m) {
        for (int i = 1; i <= m; i++) {
            cout << a[i] << " ";
        }
        cout << endl;
        return;
    }
    for (int i = a[k-1]; i <= n; i++) {
        a[k] = i;
        dfs(k + 1);
    }
}

int main() {
    cin >> n >> m;
    a[0] = 1;
    dfs(1);
    return 0;
}

代码解析

代码使用深度优先搜索算法来枚举所有可能的序列。

dfs(int k) 函数 该函数负责递归地搜索所有可能的序列。参数 k 代表当前正在处理的序列中的第 k 个数字。
if (k > m) 判断 当 k 大于 m 时，表示已经找到了一个完整的序列，此时输出该序列。
for (int i = a[k-1]; i <= n; i++) 循环 该循环枚举所有可能的第 k 个数字，并保证该数字能够被前一个数字整除。
a[k] = i; dfs(k + 1); 将当前枚举的数字 i 赋值给 a[k]，然后递归调用 dfs(k + 1) 函数来处理下一个数字。

使用方法

将代码保存为 .cpp 文件，例如 sequence.cpp。
使用 C++ 编译器编译代码，例如 g++ sequence.cpp -o sequence。
运行编译后的可执行文件，例如 ./sequence。
输入两个正整数 n 和 m，程序会输出所有满足条件的序列。