常用算法总结(穷举法、贪心算法、递归与分治算法、回溯算法、数值概率算法) |
您所在的位置：网站首页 › 归纳法并生活举例说明 › 常用算法总结(穷举法、贪心算法、递归与分治算法、回溯算法、数值概率算法) |
常用算法总结(穷举法、贪心算法、递归与分治算法、回溯算法、数值概率算法)
|
博主联系方式： QQ:1540984562 QQ交流群：892023501 群里会有往届的smarters和电赛选手，群里也会不时分享一些有用的资料，有问题可以在群里多问问。 目录 1、穷举法2、贪心算法3、递归与分治算法4、回溯算法5、数值概率算法 1、穷举法基本思想： 在可能的解空间中穷举出每一种可能的解，并对每一个可能解进行判断，从中筛选出问题的答案。 关键步骤：划定问题的解空间，并在该解空间中一一枚举每一种可能的解。 注意点： 1、解空间的划定必须保证覆盖问题的全部解：只有问题的解集属于解空间集合才能使用穷举法求解。 2、解空间集合以及问题的解集一定是离散的集合。即可列的、有限的 例1：寻找给定区间的素数 分析：最简便的方法就是穷举法，在1-100中对每个整数进行判断。 code: #include #include #include #include "malloc.h" #include "conio.h" int IsPrime(int n) { //判断n是否为素数，如果是返回1，如果不是返回0 int i; for (i=2;i //寻找【low,high】之间的素数 int i; for (i=low;i printf("%d ",i); } } } //测试函数 int main() { int low, high; printf("输入搜索范围:\n"); printf("搜索起点:"); scanf("%d",&low); printf("搜索终点:"); scanf("%d", &high); printf("区域中的素数为：\n"); GetPrime(low,high); _getche(); return 0; }
例2：TOM的借书方案： TOM共有5本新书，要借给A、B、C三个同学，每人只能借1本书，则TOM可以有多少种借书方法？ 分析：设5本书的序号为{1,2,3,4,5}，每个同学借的书范围限定于此。方案总数不可能超过5 * 5 * 5=125种。由于1本书一次只能借给1位同学，因此在每一种借书方案中，元素有重复的排列组合一定不会是问题的解。所以可以描述如下： //测试函数 int main() { int i, j, k; int print_times = 0; printf("有如下的几种方案:\n"); for(i=1;i //方法一： int tmp = 0; tmp = b; b = a; a = tmp; //方法二： //a = a+b; //b = a-b; //a = a -b; //方法三： //a ^= b ^= a ^= b; //方法四： //a = a+b-(b=a); } void sort(int w[], int t[], int n) { int i, j; //动态开辟一个临时数组，存放w[]中的内容,用于排序 int* w_tmp = (int*)malloc(sizeof(int) * n); for (i = 0;i int i, s = 0; //动态开辟出一个临时数组，存放w[]的下标,如果t[i],t[j],i int x[5], w[5], c, i; printf("输入船最大载重量:\n"); scanf("%d",&c); printf("输入5个载货箱的重量：\n"); for (i = 0;i if (m == 1 || n == 1) return 1; if (m > n) return P(n,n); if (m == n) return 1 + P(n, m - 1); return P(n, m - 1) + P(n - m, m); } int main() { int n, s; printf("请输入一个整数\n"); scanf("%d",&n); s = P(n, n); printf("整数的最大划分数为 %d \n",s); _getche(); return 0; }
原本的折半查找code: int bin_search(keytype key[], int n, keytype k) { int low = 0, high = n - 1, mid; while (low int mid; if (low > high) return -1; else { mid = (low+high) / 2; if (key[mid] == k) return mid; else if (k > key[mid]) return bin_search(key, mid + 1,high,k); else return bin_search(key,low,mid-1,k); } } int main() { int n, i, addr; int A[10] = { 2,3,5,7,8,10,12,15,19,21 }; printf("初始序列为：\n"); for (i = 0;i printf("元素不在序列中"); } _getche(); return 0; }
基本思想： 在包含问题的所有解的解空间中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去；如果该结点不包含问题的解，那就说明以该结点为根结点的子树一定不包含问题的最终解，因此要跳过对以该结点为根的子树的系统探索，逐层向其祖先结点回溯。这个过程叫做解空间树的“剪枝”操作。 如果应用回溯法求解问题的所有解，要回溯到解空间树的树根，这样才能保证根结点的所有子树都被探索到才结束。如果只要求得问题的一个解，那么在探索解空间树时，只要搜索到问题的一个解就可以结束了。 1、四皇后问题求解 问题描述：求解如何在一个NxN的棋盘上无冲突地摆放N个皇后棋子，在任意一个皇后所在位置的水平、数值、以及45度斜线上都不能出现其他皇后的棋子，否则视为冲突。 以四皇后问题为例，构建出一棵空间树，通过探索这棵解空间树，可以得到四皇后的一个解或者几个解。 应用回溯法解决问题：从根结点出发，深度优先搜索整个解空间树。当访问到根结点的第一个孩子时，观察结点，如果该结点不包含问题的解，那么由该结点作为根结点派生出来的子树中也肯定不会包含四皇后问题的解，停止向下搜索，回溯到根结点，继续太多根结点的下一个孩子结点。这就是”剪枝“操作，可以减少搜索的次数 在解决出四皇后问题时，并不一定要真的构建出这样的一棵解空间树，它完全可以通过一个递归回溯来模拟。所谓解空间树只是一个逻辑上的抽象。当然也可以用树结构真实地创建出一棵解空间树，不过比较浪费空间资源。 #include #include #include #include "malloc.h" #include "conio.h" //四皇后问题求解 int count = 0; //记录四皇后问题解的个数 //判断该位置的8邻域是否存在皇后，如果有返回0 如果没有返回1 int IsCorrect(int i,int j,int (*Q)[4]) { int s, t; for (s = i, t = 0;t = 0;s--, t--) if (Q[s][t] == 1) return 0; //判断是否在左上方 for (s = i + 1, t = j + 1;s //打印出结果 for (i = 0;i if (IsCorrect(i, j, Q)) //如果Q[i][j]可以放置皇后，表明这一列不需要再探索了 { Q[i][j] = 1; FourQueen(j+1,Q); //探索下一列，递归深度优先搜索 //Q[i][j]=0，以便循环，试探Q[i+1][j](下一行）是否可以摆放皇后，因为如果这一行如果没有找到解，需要清除这一行痕迹，然后到下一行继续探索 Q[i][j] = 0; } } } //测试函数 int main() { int Q[4][4]; int i, j; //初始化数组Q for (i = 0;i //footsetp:当前要登的台阶数、count：已经走过的阶数、step:走过的步数 int i; if (count + footstep == MAX_STEPS) { //得到一种上楼梯方案 Steps[step] = footstep; cnt++; //方案数+1 //打印出方案 for (i = 0;i //超过了楼梯的阶数，不必再向下搜索，返回到父结点 return; } else { // Steps[step] = footstep; //记录当前上楼梯的台阶数 step++; //步数+1 count = count + footstep; //记录目前已经走过的台阶数 //递归探索后续的分支 Upstairs(1,count,step); //走1步的分支 Upstairs(2, count, step); //走2步的分支 } } void UpstairsALL() { Upstairs(1,0,0); //从第一步上1个台阶开始探索解空间树 Upstairs(2, 0, 0); //从第一步上2个台阶开始探索解空间树 } int main() { UpstairsALL(); printf("一共有%d种解法\n",cnt); _getche(); }效果： 概率算法允许在执行过程中随机地选择下一步的计算步骤，因此使用概率算法有时会大大降低复杂度，提高算法的效率，但有时也可能得不到问题的全部答案。 概率算法可以分为4类： 1、数值概率算法 2、蒙特卡洛算法 3、拉斯维加斯算法 4、舍伍德算法 这里只介绍最基础的数值概率算法。 数值概率算法常用于解决数值计算的问题。应用数值概率算法往往只能得到问题的近似解，并且该近似解的精度一般随着计算时间的增加而不断提高。 例:f(x)=1-x^2;计算定积分: 该积分的几何意义如下: 所以只要求出随机点落入阴影区域的概率的概率就求出了定积分的近似值。 算法描述： #include #include #include #include "malloc.h" #include "conio.h" #include "time.h" double Darts(int n) //n为试验投点的个数，决定了计算概率的精度 { double x, y; time_t t; int i, count = 0; srand((unsigned)time(&t)); for (i = 0;i int n; char c; printf("请输入试验精度(越大精度越好):\n"); scanf("%d", &n); printf("结果为：\n"); printf("%f\n", Darts(n)); _getche(); return 0; }
|
2、递归折半查找
根结点派生出4个子结点，每个结点都示意出前两个皇后可能摆放的位置。每个结点又可以派生出4个子结点，每个结点都示意出前3个皇后可能摆放的位置，整个解空间树为一棵4叉的满树，共包含4x4x4+4x4+4+1=85个结点.
如果随机地向图中虚线与x,y坐标轴所围成的正方形中投点，那么根据几何概率知识可知，随机点落入阴影区域的概率即为阴影部分的面积与虚线与x,y轴所围成的正方形的面积之比。
【本文地址】
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |