深圳网站建设价格多少,vi企业形象设计公司,龙岗网站建设公司哪家好,查看网站开发语言方法代码思路是受一个洛谷题解里面大佬的启发。应该算是一个dfs和回溯的入门题目#xff0c;很好的入门题目了下面我会先给我原题解思路我想可以很快了解这个思路。下面是我自己根据力扣大佬写的。
我会进行详细讲解并配上图辅助理解大家请往下看
#includeiostream
#inc… 代码思路是受一个洛谷题解里面大佬的启发。应该算是一个dfs和回溯的入门题目很好的入门题目了下面我会先给我原题解思路我想可以很快了解这个思路。下面是我自己根据力扣大佬写的。
我会进行详细讲解并配上图辅助理解大家请往下看
#includeiostream
#includeiomanip
using namespace std;
int n,k;
int a[100], b[100];
void print(int n)
{for (int i 1; i n; i) {cout setw(5) a[i];}cout endl;return;
}
void dfs(int k) {if (k n) {print(n);return;}for (int i 1; i n; i) {if (!b[i]) {b[i] 1;a[k 1] i;dfs(k 1);b[i] 0;}}
}
int main()
{cin n;dfs(0);return 0;
} 这是原题解的原代码 #includebits/stdc.h
using namespace std;
int n,pd[100],used[100];//pd是判断是否用过这个数
void print()//输出函数
{int i;for(i1;in;i)printf(%5d,used[i]);//保留五位常宽coutendl;
}
void dfs(int k)//深搜函数当前是第k格
{int i;if(kn) //填满了的时候{print();//输出当前解return;}for(i1;in;i)//1-n循环填数{if(!pd[i])//如果当前数没有用过{pd[i]1;//标记一下used[k1]i;//把这个数填入数组dfs(k1);//填下一个pd[i]0;//回溯}}
}
int main()
{cinn;dfs(0);//注意这里是从第0格开始的return 0;
}
我一开始卡住的点是这里也是代码最最最核心的地方。我非常迷糊这里面有回溯
pd[i]0;//回溯
然后又是for循环之后又是dfsk1很明显这是递归。我不知道程序运行的顺序是什么给我绕懵逼了昨天晚上想了一晚上。咪咪咪咪咪。
for(i1;in;i)//1-n循环填数{if(!pd[i])//如果当前数没有用过{pd[i]1;//标记一下used[k1]i;//把这个数填入数组dfs(k1);//填下一个pd[i]0;//回溯}}
}重点思路总结递归这个顺序比for循环的优先级高。通过dfs不断增加就是层数增加并且在dfsk1同时进行了标记和used【K1】计入数组避免重复和数组填入类似剪枝和遍历并且到达最大层数时返回并print输入结果之后回溯dfs应为刚开始不是加到最大层数吗执行完后返回当初的dfs2这里回溯其实是函数递归调用继续循环。直到遍历所有。很巧妙会用就行。
思路来源和思考过程
刚开始我困惑于递归这个顺序和for循环的优先级。
我用gtp作图然后又去北理工acmb站视频看了看。之后就是递归就是递推加回溯但是这个应该是计算机原理导致的。理解的话就是机器就是这样运作的有什么调用帧啥玩意的。
如果打比方就是你可以想一想这个猴子偷桃问题原题就是有10天每天吃二分之一1真能吃啊问原来多少桃子。你把递归式子列出来然后计算机就会一个递推形容一下你能知道我在说什么就行到第1天吧好像是然后在回溯一直回溯然后算出结果。
其实讲到这里会的早就能听懂了。然后为了更直观大家理解我放几个图大家自行观看哈。 上面这个照片大家主要看图还有上面那几段话我觉得很好嗯说的就很好 上面这个图看看图就行我截的片段 下面的两个图是gpt辅助理解的流程大家可自行阅读理解 import pandas as pd# Data for each step of dfs for n 3
data [{Step: dfs(0), k: 0, used: [None, None, None], pd: [0, 0, 0], Action: Start dfs(0)},{Step: dfs(0), k: 0, used: [1, None, None], pd: [1, 0, 0], Action: i1, place 1, recurse dfs(1)},{Step: dfs(1), k: 1, used: [1, 2, None], pd: [1, 1, 0], Action: i2, place 2, recurse dfs(2)},{Step: dfs(2), k: 2, used: [1, 2, 3], pd: [1, 1, 1], Action: i3, place 3, recurse dfs(3)},{Step: dfs(3), k: 3, used: [1, 2, 3], pd: [1, 1, 1], Action: Print {1, 2, 3}, backtrack to dfs(2)},{Step: dfs(2), k: 2, used: [1, 2, None], pd: [1, 1, 0], Action: Unmark i3, backtrack to dfs(1)},{Step: dfs(1), k: 1, used: [1, None, None], pd: [1, 0, 0], Action: Unmark i2, try i3},{Step: dfs(1), k: 1, used: [1, 3, None], pd: [1, 0, 1], Action: i3, place 3, recurse dfs(2)},{Step: dfs(2), k: 2, used: [1, 3, 2], pd: [1, 1, 1], Action: i2, place 2, recurse dfs(3)},{Step: dfs(3), k: 3, used: [1, 3, 2], pd: [1, 1, 1], Action: Print {1, 3, 2}, backtrack to dfs(2)},{Step: dfs(2), k: 2, used: [1, 3, None], pd: [1, 0, 1], Action: Unmark i2, backtrack to dfs(1)},{Step: dfs(1), k: 1, used: [1, None, None], pd: [1, 0, 0], Action: Unmark i3, backtrack to dfs(0)},{Step: dfs(0), k: 0, used: [None, None, None], pd: [0, 0, 0], Action: Unmark i1, try i2},{Step: dfs(0), k: 0, used: [2, None, None], pd: [0, 1, 0], Action: i2, place 2, recurse dfs(1)},{Step: dfs(1), k: 1, used: [2, 1, None], pd: [1, 1, 0], Action: i1, place 1, recurse dfs(2)},{Step: dfs(2), k: 2, used: [2, 1, 3], pd: [1, 1, 1], Action: i3, place 3, recurse dfs(3)},{Step: dfs(3), k: 3, used: [2, 1, 3], pd: [1, 1, 1], Action: Print {2, 1, 3}, backtrack to dfs(2)},{Step: dfs(2), k: 2, used: [2, 1, None], pd: [1, 1, 0], Action: Unmark i3, backtrack to dfs(1)},{Step: dfs(1), k: 1, used: [2, None, None], pd: [0, 1, 0], Action: Unmark i1, try i3},{Step: dfs(1), k: 1, used: [2, 3, None], pd: [0, 1, 1], Action: i3, place 3, recurse dfs(2)},{Step: dfs(2), k: 2, used: [2, 3, 1], pd: [1, 1, 1], Action: i1, place 1, recurse dfs(3)},{Step: dfs(3), k: 3, used: [2, 3, 1], pd: [1, 1, 1], Action: Print {2, 3, 1}, backtrack to dfs(2)},{Step: dfs(2), k: 2, used: [2, 3, None], pd: [0, 1, 1], Action: Unmark i1, backtrack to dfs(1)},{Step: dfs(1), k: 1, used: [2, None, None], pd: [0, 1, 0], Action: Unmark i3, backtrack to dfs(0)},{Step: dfs(0), k: 0, used: [None, None, None], pd: [0, 0, 0], Action: Unmark i2, try i3},{Step: dfs(0), k: 0, used: [3, None, None], pd: [0, 0, 1], Action: i3, place 3, recurse dfs(1)},{Step: dfs(1), k: 1, used: [3, 1, None], pd: [1, 0, 1], Action: i1, place 1, recurse dfs(2)},{Step: dfs(2), k: 2, used: [3, 1, 2], pd: [1, 1, 1], Action: i2, place 2, recurse dfs(3)},{Step: dfs(3), k: 3, used: [3, 1, 2], pd: [1, 1, 1], Action: Print {3, 1, 2}, backtrack to dfs(2)},{Step: dfs(2), k: 2, used: [3, 1, None], pd: [1, 0, 1], Action: Unmark i2, backtrack to dfs(1)},{Step: dfs(1), k: 1, used: [3, None, None], pd: [0, 0, 1], Action: Unmark i1, try i2},{Step: dfs(1), k: 1, used: [3, 2, None], pd: [0, 1, 1], Action: i2, place 2, recurse dfs(2)},{Step: dfs(2), k: 2感谢观看谢谢谢谢么么么么~
