第一步排列组合子集

最终作品第一步:写出 perm、comb、subs 的递归部分,输出三个个数(1、2、3 全排列 / 1、2、3、4 取 2 / 1、2、3 子集)。 (本题用 g++ -std=c++17 -O0 编译。)

开始练习 →

第二步把路径记对

写出撤销写全、存内容的 perm,输出解的个数和第一个解。 (本题用 g++ -std=c++17 -O0 编译。)

开始练习 →

第三步剪枝且证明没剪错

写出 naive 和 pruned(1 到 5 排一排、挨着的不能是连号),输出不剪枝结点数 / 剪枝结点数 / 结果一致或结果不一致。 (本题用 g++ -std=c++17 -O0 编译。)

开始练习 →

第四步 N 皇后

写出 queen_ok 和 queens_dfs,把 n = 4、5、6、7 各跑一遍,四个解数拼起来输出。 (本题用 g++ -std=c++17 -O0 编译。)

开始练习 →

交付回溯加剪枝验收

这是这条路线的最终作品。模板里已经有全部函数的框架和验收用的 main,补全几个关键的递归函数,一次验完五条:1、2、3 全排列 6 个、子集 8 个;第一个排列是 1,2,3;漏了 pop_back 的版本只有 1 个解;剪枝前后解数相同

开始练习 →

限时题靠什么过

N 皇后 n = 12 时不剪枝根本跑不完,能在限时内跑完的关键是【0】。

开始练习 →

写组合枚举

场景:实验机上 ~/work/bt/comb.cpp 读入 n 和 k,要按字典序输出从 1..n 里取 k 个的全部组合,每行一个,数之间一个空格。comb_dfs 还没写。 任务:补全 comb_dfs。make 编译,./comb &

开始练习 →

十二皇后要剪枝

场景:~/work/bt/queens.cpp 数 n 皇后的解数:它把每一行的列号全排好,排满之后才检查斜线。n 小的时候对,n = 12 就跑不完。 任务:改写 queens.cpp,放之前就检查列和两条斜线,让 n = 12 在 2

开始练习 →

修好忘了撤销的标记

场景:~/work/bt/perm.cpp 读入 n,按字典序输出 1..n 的全部排列。可它只输出了第一个。 任务:找到回溯里漏掉的那一步恢复现场并修好。make 编译后用 sample.txt 自测;check 会用随机的 n 对拍。

开始练习 →

修好重复输出的子集

场景:~/work/bt/subsets.cpp 读入一组可能有重复的数,要输出所有不重复的子集。可它输出了好几个一模一样的子集。 任务:修好去重的判断,让每个子集只出现一次、顺序不变。make 编译后用 sample.txt 自测;che

开始练习 →