zhangjinxuan 发表于 2022-10-23 10:43:44

如何用非递归形式做出回溯类型的题？

比如说全排列，正常情况我们是这么做的：
#include <cstdio>
using namespace std;

int n, res;
bool u;

void dfs(int c) {
        if (c == n + 1) {
                for (int i = 1; i <= n; ++i) {
                        printf("%d ", res);
                }
                puts("");
                return;
        }
        for (int i = 1; i <= n; ++i) {
                if (!u) {
                        u = 1;
                        res = i;
                        dfs(c + 1);
                        u = 0;
                }
        }
}

int main() {
        scanf("%d", &n);
        dfs(1);
}

但我该怎么样把这段代码写为非递归的形式呢？

柿子饼同学 发表于 2022-10-23 11:47:13

本帖最后由 柿子饼同学 于 2022-10-23 11:49 编辑

next_permutation() 实现是就不是递归 , 可以直接用
开个玩笑
看看这个 : https://blog.csdn.net/wzh1378008099/article/details/108196039?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522166649692416782412538235%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=166649692416782412538235&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~sobaiduend~default-1-108196039-null-null.142^v59^new_blog_pos_by_title,201^v3^add_ask&utm_term=%E5%85%A8%E6%8E%92%E5%88%97%E4%B8%8D%E7%94%A8%E9%80%92%E5%BD%92&spm=1018.2226.3001.4187

zhangjinxuan 发表于 2022-10-23 12:16:37

柿子饼同学 发表于 2022-10-23 11:47
next_permutation() 实现是就不是递归 , 可以直接用
开个玩笑
看看这个 : https://blog.csdn.net/wzh1378 ...

好，我研究研究，刚刚打比赛

柿子饼同学 发表于 2022-10-23 12:39:56

zhangjinxuan 发表于 2022-10-23 12:16
好，我研究研究，刚刚打比赛

哈? 洛谷月赛?

zhangjinxuan 发表于 2022-10-23 12:41:52

柿子饼同学 发表于 2022-10-23 12:39
哈? 洛谷月赛?

yes

柿子饼同学 发表于 2022-10-23 12:47:28

zhangjinxuan 发表于 2022-10-23 12:41
yes

你做了多少题啊
我今天上午有课,写了前两题 120 ...

zhangjinxuan 发表于 2022-10-23 13:04:47

柿子饼同学 发表于 2022-10-23 12:47
你做了多少题啊
我今天上午有课,写了前两题 120 ...

前两题190，总分210

zhangjinxuan 发表于 2022-10-23 13:05:42

柿子饼同学 发表于 2022-10-23 12:47
你做了多少题啊
我今天上午有课,写了前两题 120 ...

现在帮弟弟做作业，暂时不聊了
页: [1]
查看完整版本: 如何用非递归形式做出回溯类型的题？