那些空号检测网站是怎么做的,高唐网站,网站运营现状,近期发生的新闻最近读了一本算法书#xff0c;书中提到了深度优先算法#xff0c;于是我就整理了一下。 引入小题#xff1a; 解决方案#xff1a;这里先使用最简单最常用的穷举法时行求解。#xff08;此代码中的book数组起到了标记的作用#xff0c;可以参考桶装法排序了解标记的好处…最近读了一本算法书书中提到了深度优先算法于是我就整理了一下。 引入小题 解决方案这里先使用最简单最常用的穷举法时行求解。此代码中的book数组起到了标记的作用可以参考桶装法排序了解标记的好处和作用 #include stdio.hint main(){//因为要填写9个数字所以这里用数组a存放9次数字的变量方便在book标记数组内操作 int a[10], book[10];int i, sum, total 0;for(a[1] 1; a[1] 9; a[1] )for(a[2] 1; a[2] 9; a[2] )for(a[3] 1; a[3] 9; a[3] )for(a[4] 1; a[4] 9; a[4] )for(a[5] 1; a[5] 9; a[5] )for(a[6] 1; a[6] 9; a[6] )for(a[7] 1; a[7] 9; a[7] )for(a[8] 1; a[8] 9; a[8] )for(a[9] 1; a[9] 9; a[9] ){//初始book标记数组 for(i 1; i 9; i){book[i] 0;}//将获得的序列标记一下方便判断是否全为不一样的数字for(i 1; i 9; i) {book[a[i]] 1;}//用于判断是否为9个不同的数字 sum 0;for(i 1; i 9; i){if(book[i] 1) sum ;}if(sum 9 a[1] * 100 a[2] * 10 a[3] a[4] * 100 a[5] * 10 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]);}}printf(共有%d个这样的数\n, total / 2); return 0;
}初入DFS小题
给出n组成n位的全排序。1 n
解决方案如果已知n的话可以在程序里面写入n个for循环来得出需要的结果但是这个n是在程序运行时给出的所以这里需要用递归实现。 #include stdio.h
#include stdlib.hint *box, *book, n;void dfs(int step){int i;if(step n 1){for( i 1; i n; i ){printf(%d, box[i]); }printf(\n);return;}for(i 1; i n; i){if(book[i] 0){box[step] i;book[i] 1;dfs(step 1);book[i] 0;}}
}int main(){ int i;scanf(%d, n);//因为此处下标要从1开始所以数组要加1 box (int *)malloc(sizeof(int) * (n 1));book (int *)malloc(sizeof(int) * (n 1));//初始book标记数组for(i 1; i n; i) book[i] 0;dfs(1);return 0;
}
涉及算法可以把DFS归结为如下模型 void dfs(int step) {判断边界 越界返回 尝试每一种可能 for(i 0; i n; i) {处理继续下一步 dfs(step 1) 处理 }
}重试第一题
可使用DFS算法来编写这个题运行效率能提高10倍当然这个算法效率也不高。#include stdio.h
#include stdlib.hint *box, *book, n 9, total 0;void dfs(int step){int i;if(step n){if(box[0] * 100 box[1] * 10 box[2] box[3] * 100 box[4] * 10 box[5] box[6] * 100 box[7] * 10 box[8]){total ;printf(%d%d%d %d%d%d %d%d%d\n, box[0], box[1], box[2], box[3], box[4], box[5], box[6], box[7], box[8]);}return;}for(i 1; i n; i){if(book[i-1] 0){box[step] i;book[i-1] 1;dfs(step 1);book[i-1] 0;}}
}int main(){ int i;scanf(%d, n);//因为此处下标要从1开始所以数组要加1 box (int *)malloc(sizeof(int) * (n));book (int *)malloc(sizeof(int) * (n));//初始book标记数组for(i 0; i n; i) book[i] 0;dfs(0);printf(共有%d个, total / 2); return 0;
}
再来一题
有一天小哈一个去玩迷宫。但是方向感很不好的小哈很快就迷路了。小哼得知后便立即去解救无助的小哈。小哼当然是有备而来已经弄清楚了迷宫地图现在小哼要以最快速度去解救小哈。问题就此开始了…… 迷宫由n行m列的单元格组成每个单元格要么是空地要么是障碍物。你的任务是帮助小哼找到一条从迷宫的起点到小哈所在位置的最短路径注意障碍物是不能走的当然也不能走到迷宫之外。n和m都小于等于100。 输入格式第一行有两个数N M。N表示迷宫的行M表示迷宫的列。接来下来N行M列为迷宫0表示空地1表示障碍物。最后一行4个数前两个数为迷宫入口的x和y坐标。后两个为小哈的x和y坐标。
样例 #include stdio.h
#include stdlib.h
#include string.hint **map, **book, min 999999;
int p, q, M, N; //终点 void dfs(int x, int y, int step){int i, cX, cY;//方向数组int next[4][2] {{0, 1}, //右 {1, 0}, //下 {0, -1}, //左 {-1, 0} //上};//边界条件 if( x p y q) {if(step min) min step;return;}//遍历条件(四个方向)for(i 0; i 4; i){cX x next[i][0];cY y next[i][1];//越界 不操作 if(cX 0 || cY 0 || cX N - 1 || cY M - 1) continue;if(book[cX][cY] 0 map[cX][cY] 0){//标记此地点已走过 book[cX][cY] 1;dfs(cX, cY, step 1);book[cX][cY] 0; } }return;
}int main(){ int startX, startY;int i, j;scanf(%d %d, N, M); map (int **)malloc(sizeof(int *) * N);book (int **)malloc(sizeof(int *) * N);for(i 0; i N; i){map[i] (int *)malloc(sizeof(int) * M);book[i] (int *)malloc(sizeof(int) * M);}for(i 0; i N; i)for(j 0; j M; j)book[i][j] 0;for(i 0; i N; i){for(j 0; j M; j){scanf(%d, map[i][j]);}} scanf(%d %d %d %d, startX, startY, p, q);startX--;startY--;p--;q--;book[startX][startY] 1;dfs(startX, startY, 0);if(min 999999){printf(No Way!);}else{printf(%d, min); }return 0;
}可见此算法效率并不高。BFS算法处理明显提高时间复杂度但空间复杂度提升 #include stdio.hstruct Node{int x;int y;int s;
};int main(){int startX, startY, n, m, p, q, tX, tY, head 1, tail 1, flag 0;int i, j;int a[101][101] {0}, book[101][101] {0},next[4][2]{{0, 1}, //右 {1, 0}, //下 {0, -1}, //左 {-1, 0} //上 };struct Node que[100000];//接收初值 scanf(%d %d, n, m);for(i 1; i n; i){for(j 1; j m; j){scanf(%d, a[i][j]);}}scanf(%d %d %d %d, startX, startY, p, q);que[tail].x startX;que[tail].y startY;que[tail].s 0;book[startX][startY] 1;tail ;while(head tail){for(i 0; i 4; i ){tX que[head].x next[i][0];tY que[head].y next[i][1];if(tX 1 || tX n || tY 1 || tY m){continue;}if(a[tX][tY] 0 book[tX][tY] 0){que[tail].x tX;que[tail].y tY;que[tail].s que[head].s 1;book[tX][tY] 1;tail ;if(tX p tY q){flag 1;}}}if(flag 1) break;head ;}if(flag 1){printf(%d, que[tail - 1].s);}else{printf(No Way!);}return 0;
} 博客名称王乐平博客 博客地址http://blog.lepingde.com CSDN博客地址http://blog.csdn.net/lecepin
