今天上午听到，那个非常6+1的李咏先生因癌症去世
DFS算法的基本模型
深度下，不撞南墙不回头，就是一直往后找，知道没有路了，向后返回。
想起一首民谣，《可能否》--木小雅 https://music.163.com/#/song?id=569214126
现在可能也就民谣还有一些安静了，好像雷子的歌也有点厌了。
木小雅Olivia：谢谢云村pick我这块小石头，也谢谢优秀的制作团队，更谢谢来听这首歌的你。愿多年以后，你撞过的南墙，都成为坦途；你遇见过的绝望，都成为最美的盛放。
今天也要上班吗：不撞南墙不回头 不见黄河不死心。
UP：山有木兮木有枝，心悦君兮君不知。
好了话归正题。
void dfs(int step){ //1 判断达到边界了吗 //2 没有达到边界就尝试每一种方法 for(i=1;i<=n;i++){ //继续下一步 dfs(step+1); } return; }两个例题
1
#include <iostream> #include <stdio.h> #include <stdlib.h> using namespace std; int a[10],book[10],total=0; /*[][][]+[][][]==[][][] []种只能填1-9，每个数字只能使用一次 暴力枚举方法 和 DFS方法 还是9个格子，放九张牌 */ void dfs(int step){ int i; if(step == 10){//判断边界 就是所以格子都填满了 满足！？ if((a[1]+a[4])*100+(a[2]+a[5])*10+a[3]+a[6] == a[7]*100+a[8]*10+a[9]){ total++; printf("%d%d%d+%d%d%d=%d%d%d\n", a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8],a[9]); } return; } for(i=1;i<=9;i++){ if(book[i] == 0){ a[step]=i; book[i]=1; dfs(step+1); book[i]=0; } } return; } int main(){ dfs(1); printf("%d",total/2); system("pause"); return 0; }2
#include <iostream> #include <stdio.h> #include <stdlib.h> using namespace std; int a[10],book[10],n;// a[]为盒子数组 book[i]用来表示i有没有用到，n为盒子数目 //全局变量在没有赋值以前系统默认为0，而局部变量在没有赋值以前的值是不确定的，所以在声明局部变量的时候一定要初始化。 /*本题是 啊哈算法第四章 扑克牌的全排列 有N张不同的扑克牌 和 N个不同格子 最多有 N!个排列方式 对于第一个 格子有N种选择，第二个 N—1个选择，最后一个 1个 格子因为顺序，相互独立，相乘运算。 跟生物 N种氨基酸可组成N长的氨基酸链相同 */ /*0—>【1】 【2】 【3】,4{ 4 不存在} 假设有三张牌1,2,3，三个格子123 step—>一步一步向前放牌，到4的时候说明放好了一次例如 1 2 3输出 收回【3】中的牌没有其他方法， 再收回【2】中的，此时【2】处的for循环已经读过2了，所以还有一种排序， 【2】处放入 3，dfs(step+1)->【3】处还可以放入2 这样递归自己 收回【1】……………，递归给出答案 */ void dfs(int step){//深度优先搜索算法 Deep First Search int i; if(step == n+1){//step超出格子【N】范围说明完成一次排序 for(i=1;i<=n;i++){ printf("%d",a[i]); } printf("\n"); return;//返回之前最近一次调用DFS的地方， } //处于Step位置，没有达到要输出就，判断这个位置可以放入什么牌 for(i=1;i<=n;i++){ if(book[i] == 0){//for循环判断扑克牌 I是否还在手中 a[step]=i;//在放入格子 book[i]=1;//表明已经使用 dfs(step+1);//向下一格子看看，递归 book[i]=0;//完成一次就收回刚刚尝试的扑克牌，进行下一次尝试 } } return; } int main(){ scanf("%d",&n);//N个格子和扑克 dfs(1);//从第一次格子开始放 system("pause");//暂停 return 0; }
