做游戏网站用什么系统做,钟表商城网站建设方案,制作网页代码大全,南京网站设计培训【导航】 上一篇文章 → 《【算法】蓝桥杯dfs深度优先搜索之凑算式总结》 为了重申感谢之意#xff0c;再次声明下文的大部分灵感均来自于【CSDN】梅森上校《JAVA版本#xff1a;DFS算法题解两个例子#xff08;走迷宫和求排列组合数#xff09;》 强烈大家去上面那篇文… 【导航】 上一篇文章 → 《【算法】蓝桥杯dfs深度优先搜索之凑算式总结》 为了重申感谢之意再次声明下文的大部分灵感均来自于【CSDN】梅森上校《JAVA版本DFS算法题解两个例子走迷宫和求排列组合数》 强烈大家去上面那篇文章看看写的很好。 下面我会列出蓝桥杯第六届B组省赛第7题、第七届第5题、第八届第4题共3道题。 因为他们都是排列组合。 【第一道题】 这道题可以强制转为昨天的“凑算式”类型。 首先强调一下题意总共13种牌A到K每种可以选0到4张总共选出13张两个13如果简单表示的话就是2 13其中13也可以用大写的字母B表示隐晦的透露了这道题的内涵。 如果你还能想起来昨天“凑算式”的思路的话那么上来第一件事肯定就是设置一个数组了 下图是我昨天在最后一题做的总结对于这道题来说也适合。 第一件事显然这个数组的长度为13因为我们要存13种牌数组中只存0到4之间的数。 public static int[] a new int[13]; 第二件事这里不涉及到数字重用与否略过。 第三件事定义dfs方法还是和昨天一样就传一个index参数 public static void dfs(int index) 第四件事写递归结束条件这里就是index 13越界代表A到K我们已经取完了接下来就是要统计一下总数是不是13张。如果是的话就算一种count。 // 递归结束条件
if(index 13) { int sum 0; for(int i : a) { sum i; } if(sum 13) { count; } return; //递归结束一定要有return啊没有return不叫递归结束 } 第五件事还未凑齐深搜。a[]数组总共13个位置每个位置是0到4中的一个数。代码如下: // 搜索
for(int i0; i4; i) { a[index] i; dfs(index1); } 【完整代码】 1 public class 牌型种数dfs {2 public static int count 0 ;3 public static int[] a new int[13];4 public static void dfs(int index) {5 if(index 13) {6 int sum 0;7 for(int i : a) {8 sum i;9 }
10 if(sum 13) {
11 count;
12 }
13 return;
14 }
15 // 搜索
16 for(int i0; i4; i) {
17 a[index] i;
18 dfs(index1);
19 }
20 }
21
22 public static void main(String[] args) {
23 dfs(0);
24 System.out.println(count); // 答案是: 3598180
25 }
26
27 } 其实我的这种解法关键就在于对数组的使用是否熟练用13个位置代表13个种类每个位置只能填0到4最后数组凑填满后统计一下每个位置之和是否是13。 如果你每天吃饭、睡觉、聊天都是讨论的和数组呀dfs呀相关的再加上看我写的文章照着代码敲敲那么用不了1天准能掌握这种套路。 这篇文章的标题是关于排列组合的之所以开个新坑就是想告诉大家虽然我总结的步骤对大多数dfs类型的题有用但是不要局限以为只有那样的模式才算是dfs。 比如同样是这道题同样是dfs算法但是代码却不一样。下面的代码参考自【CSDN】h1021456873《蓝桥杯 牌型种数 (暴力||dfs)》 1 public static int count 0 ;2 public static void dfs(int type, int sum) {3 // 结束条件4 if(type 13) { // A到K 13类5 if(sum 13) { // 要凑够13张6 count;7 }8 return;9 }
10 // 搜索
11 for(int i0; i4; i) {
12 dfs(type1, sumi); // 此解法的关键就在于sumi 而不是sum1
13 }
14 }
15
16 public static void main(String[] args) {
17 dfs(0,0);
18 System.out.println(count);
19 } 可以看到这个dfs方法传入了两个参数上面的代码没有像我那样使用数组如果看懂我的代码这个也挺好理解的。 之所以要说上面的代码是要引出来下面这道题 【第二道题】 这是一道填空题给出的代码如下其中的注释是我添加的 1 public class 抽签dfs {2 3 public static void f(int[] a, int k, int n, String s) {4 // 结束条件5 if (k a.length) {6 if (n 0)7 System.out.println(s);8 return;9 }
10 // 搜索
11 String s2 s;
12 for (int i 0; i a[k]; i) {
13 _________________________// 填空位置
14 s2 (char) (k A);
15 }
16 }
17
18 public static void main(String[] args) {
19 int[] a { 4, 2, 2, 1, 1, 3 };
20 f(a, 0, 5, );
21 }
22 } 我还清楚的记得我第一次做这道题当时我还不知道什么是dfs深度优先搜索压根没看出来这代码什么意思只是觉得应该递归。经过上篇文章的磨练现在可以一眼看出这就是dfs的代码套路只不过他传的参数有点多4个。 这道题13分这种填空题一定不能莽撞他给出了程序代码自己填上答案之后可以结合题意验证一下比如这道题他有说明总共会输出101行结果这就是一个检验条件。 我第一次做的时候完全是蒙的答案如下: f(a, k, n, s2); //错误示例 正确答案 f(a, k 1, n - i, s2); 很显然我当时没有搞懂dfs的搜索代码即下列代码 for (int i 0; i a[k]; i) { _________________________// 填空位置 s2 (char) (k A); } 既然他在main方法中调用了dfs算法参数n传入的是5那么就代表观察团的总人数要求是5人这里的for循环进行搜索一但选中 i 个人那么接下来只能选 n - i 个人所以参数应该是n - i而不是n 还有一点就是对于深搜这种下一个情况是k1而不能用k或k。原因是数组会越界至于为什么会越界我自己分析了一下没搞懂。最后就硬记住了这就是套路请按套路出牌。 说实话这道题如果不是填空题而是一道大题尽管我自认为理解了dfs算法但还是写不对代码。还是要多理解理解这道题。 【第三道题】 这篇文章的最后一道题 先说明这道题到底怎么解其实我也不知道在这里写它的原因是看到了下面这篇文章不过作者说的答案216作者明知11112233和33221111是同一种知道去重却没说出来12233111 和 11133221这样之类的也是同一种因此对于他的答案我不敢苟同。【CSDN】sangjinchao《第八届蓝桥杯JAVAB组第四题》 不过就11112233全排列这一单纯的知识点我是很感兴趣的。 下面我想讨论一下使用dfs算法就给定数字全排列问题比如上面的数字四个1两个2两个3进行全排列我使用了标记法写的代码如下 1 public class 全排列dfs {2 3 public static int[] a new int[] { 1, 1, 1, 1, 2, 2, 3, 3 };4 public static int[] visited new int[8];5 public static int[] result new int[8];6 public static void dfs(int index) {7 // 结束条件8 if (index 8) {9 for (int i : result) {
10 System.out.print(i);
11 }
12 System.out.println();
13 return;
14 }
15 // 搜索
16 for(int i0; i8; i) {
17 if(visited[i]0) {
18 visited[i] 1;
19 result[index] a[i];
20 dfs(index1);
21 visited[i] 0;
22 }
23 }
24 }
25
26 public static void main(String[] args) {
27 dfs(0);
28 }
29
30 } 不过有些情况11112233和33221111还有11221133和33112211这类的都算重复的所以需要去掉。目前我给出一个不太成熟的代码只能想到这里了如果有谁有优化的代码一定要给我打call告诉我 1 public class 全排列dfs逆置去重 {2 3 public static int[] a new int[] { 1, 1, 1, 1, 2, 2, 3, 3 };4 public static int[] visited new int[8];5 public static int[] result new int[8];6 public static int[] res new int[33221112];7 public static int count 0;8 public static void dfs(int index) {9 // 结束条件
10 if (index 8) {
11 String s ;
12 String rev ;
13 StringBuilder sb new StringBuilder();
14 for (int i : result) {
15 sb.append(i);
16 }
17 s sb.toString();
18 rev sb.reverse().toString(); // 逆置
19 if(res[Integer.parseInt(rev)] 0) {// 去重
20 res[Integer.parseInt(s)] 1;
21 System.out.println(s);
22 count;
23 }
24 return;
25 }
26 // 搜索
27 for(int i0; i8; i) {
28 if(visited[i]0) {
29 visited[i] 1;
30 result[index] a[i];
31 dfs(index1);
32 visited[i] 0;
33 }
34 }
35 }
36
37 public static void main(String[] args) {
38 dfs(0);
39 System.out.println(count);
40 }
41
42 } 这篇文章到这里就该结束了我的初衷就是想告诉大家dfs不仅仅是我在上篇文章里面写的那篇只能计算“凑算式”dfs身为一种暴力破解方法有很多种变形还需要大家多加练习。 有些人会担心都这个时候了复习蓝桥杯迟吗送你一句话Latter Better Than Never 上一篇文章 → 《【算法】蓝桥杯dfs深度优先搜索之凑算式总结》 下一篇文章预计会在周五更新 → 《【算法】蓝桥杯dfs深度优先搜索之图连通总结》 参考文章 【CSDN】h1021456873《蓝桥杯 牌型种数 (暴力||dfs)》 【CSDN】豌豆苞谷《2017 第八届蓝桥杯 魔方状态》 【CSDN】sangjinchao《第八届蓝桥杯JAVAB组第四题》 转载于:https://www.cnblogs.com/littlecurl/p/10575638.html
