大连 祥云 网站优化,服务公司沈傲芳,领地网做网站咋加文章,专业建网站价格博主联系方式#xff1a; QQ:1540984562 QQ交流群#xff1a;892023501 群里会有往届的smarters和电赛选手#xff0c;群里也会不时分享一些有用的资料#xff0c;有问题可以在群里多问问。 目录1、穷举法2、贪心算法3、递归与分治算法4、回溯算法5、数值概率算法1、穷举法… 博主联系方式 QQ:1540984562 QQ交流群892023501 群里会有往届的smarters和电赛选手群里也会不时分享一些有用的资料有问题可以在群里多问问。 目录1、穷举法2、贪心算法3、递归与分治算法4、回溯算法5、数值概率算法1、穷举法
基本思想
在可能的解空间中穷举出每一种可能的解并对每一个可能解进行判断从中筛选出问题的答案。
关键步骤划定问题的解空间并在该解空间中一一枚举每一种可能的解。
注意点
1、解空间的划定必须保证覆盖问题的全部解只有问题的解集属于解空间集合才能使用穷举法求解。
2、解空间集合以及问题的解集一定是离散的集合。即可列的、有限的
例1寻找给定区间的素数
分析最简便的方法就是穷举法在1-100中对每个整数进行判断。
code:
#includeiostream
#include stdio.h
#include stdlib.h
#include malloc.h
#include conio.h
int IsPrime(int n)
{//判断n是否为素数如果是返回1如果不是返回0int i;for (i2;in;i){if (n % i 0) return 0;}return 1;
}
void GetPrime(int low, int high)
{//寻找【low,high】之间的素数int i;for (ilow;ihigh;i){if (IsPrime(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;
} 例2TOM的借书方案
TOM共有5本新书要借给A、B、C三个同学每人只能借1本书则TOM可以有多少种借书方法
分析设5本书的序号为{1,2,3,4,5}每个同学借的书范围限定于此。方案总数不可能超过5 * 5 * 5125种。由于1本书一次只能借给1位同学因此在每一种借书方案中元素有重复的排列组合一定不会是问题的解。所以可以描述如下
//测试函数
int main()
{int i, j, k;int print_times 0;printf(有如下的几种方案:\n);for(i1;i5;i)for(j1;j5;j)for(k1;k5;k)if (i ! j j ! k i ! k){print_times;printf( (%d,%d,%d) ,i,j,k); //输出借书方案if (print_times % 10 0) printf(\n);}_getche();return 0;
}效果
2、贪心算法
贪心算法不从整体最优上加以考虑所做的仅是在某种意义上的局部最优解。而局部最优解叠加到一起便是该问题整体上的最优解或者近似最优解。
严格意义上讲要使用贪心算法求解问题该问题应当具备如下性质
1、贪心选择性质指求解的问题的整体最优解可以通过一系列的局部最优解得到。所谓局部最优解就是指在当前的状态下做出的最好的选择。
2、最优子结构性质
一个问题的最优解包含着它的子问题的最优解
例题1最优装船问题
有一批集装箱要装入一个载重量为C的货船中每个集装箱的质量由用户自己输入指定在货船的装载体积不限制的前提下如何装载集装箱才能尽可能多地将集装箱装入货船中
算法设计
1、数组w[]存放每个集装箱的质量
2、数组x[]存放每个集装箱的取舍状态
3、变量c存放货船的剩余载重量初始值为C
4、为了使装载可能多的集装箱每次都选出数组w[]中当前w[i]值最小的集装箱并将x[i]置1同时cc-w[i]
5、循环执行4操作直道w[i]c,表明货船装货已经达到最大载重量输出x[]中所有x[i]1的下标i
代码描述
#includeiostream
#include stdio.h
#include stdlib.h
#include malloc.h
#include conio.hvoid swap(int a, int b)
{//方法一 int tmp 0;tmp b;b a;a tmp;//方法二 //a ab; //b a-b; //a a -b; //方法三 //a ^ b ^ a ^ b; //方法四 //a ab-(ba);
}
void sort(int w[], int t[], int n)
{int i, j;//动态开辟一个临时数组存放w[]中的内容,用于排序int* w_tmp (int*)malloc(sizeof(int) * n);for (i 0;i n;i)t[i] i; //初始化t[]for (i 0;i n;i)w_tmp[i] w[i]; //复制数组w[]到w_tmp[]中//将w_tmp[]与t[]共同排序当w_tmp实现从小到大排列后t[]中存放的就是w_tmp[]元素在w[]中对应的下标for (i 0;i n - 1;i)for (j 0;j n - i - 1;j)if (w_tmp[j] w_tmp[j 1]){swap(w_tmp[j], w_tmp[j 1]);swap(t[j], t[j 1]);}
}
//输入 x[]集装箱取舍状态 w[]每个集装箱的质量 c船的剩余载重量 n一共几个货物
void Loading(int x[],int w[],int c,int n)
{int i, s 0;//动态开辟出一个临时数组存放w[]的下标,如果t[i],t[j],ij,则有w[t[i]] w[t[j]];int* t (int*)malloc(sizeof(int)*n); sort(w, t, n); //排序用数组t[]存放w[]的下标for (i 0;i n;i)x[i] 0; //初始化取舍状态数组for (i 0;i n w[t[i]] c;i){x[t[i]] 1;c c - w[t[i]];}
}
//t存放数组w[]的下标使得如果ij,则w[t[i]]w[t[j]]
//例如w[3]{5,3,2} 则t[3]{2,1,0},即将w[]从小到大排序然后记录下w[i]的原本下标i在新的顺序中的位置。
//原本5,3,2三个元素排列顺序为:5,3,2,对应下标0,1,2从小到大排之后5,3,2三个元素排列顺序为2,3,5下标对应原来的(2,1,0)int main()
{int x[5], w[5], c, i;printf(输入船最大载重量:\n);scanf(%d,c);printf(输入5个载货箱的重量\n);for (i 0;i 5;i)scanf(%d,w[i]);//进行最优装载Loading(x,w,c,5);printf(这些箱子将被装入:\n);for (i 0;i 5;i){if (x[i] 1) printf(BOX:%d ,i);}_getche();return 0;
}3、递归与分治算法
基本思想
将规模较大的问题分割为规模较小的同类问题然后将这些子问题逐个加以解决最终也就将整个大的问题解决了。
分治思想举例折半查找就是利用序列之间元素的顺序关系不断缩小问题的规模每次都将问题缩小为原来的1/2采用顺序的方法查找需要O(n),而折半只需要O(long2n)
递归思想:一种直接或间接地调用原算法本身的一种算法。
设计递归算法需要注意的几点
1、每个递归函数都必须有一个非递归定义得初始值作为递归结束标志或递归结束的出口
2、递归算法的运行较低时间和空间复杂度都比较高对于一些对时间和空间要求较高的程序建议使用非递归算法设计。
例题
1、计算整数的划分数
将一个正整数n表示为一系列的正整数之和
nn1n2n3n4;(n1n2n3nk1,k1)
被称为正整数n的一次划分。一个正整数n可能存在不同的划分例如正整数6的全部的划分为;
66
651
642、6411
633、6321、63111
6222、62211、621111
6111111
正整数n的不同的划分的个数被称为该正整数n的划分数。
编写一个程序计算输入的正整数n的划分数
分析设标记p(n,m)表示正整数n的所有不同的划分中最大加数不大于m的划分个数。例如P(6,2)4因为在正整数6的全部划分中最大加数不大于2的只有6222、62211、621111
6111111四个划分。
建立如下4个递归关系
1、P(n,1) 1.n1
任何正整数n的划分中加数不大于1的划分有且仅有1种即n111…1n个1
2、P(n,m)P(n,n),mn
最大加数等于n不存在最大加数大于n的情况
3、P(n,n)P(n,n-1)1
最大加数为n的划分只有1种即nn因此最大加数不大于n的划分数就是P(n,n-1)1
4、P(n,m)P(n,m-1)P(n-m,m),nm1
正整数n的最大加数不大于m的划分数n的最大加数不大于m-1的划分数n的最大加数为m的划分数
例 根据这四个式子书写code:
int P(int n, int m)
{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;
}2、递归折半查找
原本的折半查找code:
int bin_search(keytype key[], int n, keytype k)
{int low 0, high n - 1, mid;while (low high){mid (low high) / 2;if (key[mid] k)return mid;if (k key[mid])low mid 1; //在后半序列中查找elsehigh mid - 1;}return -1; //查找失败返回-1
}修改为递归形式
typedef int keytype;
int bin_search(keytype key[], int low,int high,keytype k)
{int mid;if (low high) return -1;else{mid (lowhigh) / 2;if (key[mid] k)return mid;else if (k key[mid])return bin_search(key, mid 1,high,k);elsereturn 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 10;i)printf(%d ,A[i]);printf(\n输入待查找的元素\n);scanf(%d,n);addr bin_search(A,0,9,n);if (addr ! -1){printf(%d 下标为%d,n,addr);}else{printf(元素不在序列中);}_getche();return 0;
}4、回溯算法
基本思想
在包含问题的所有解的解空间中按照深度优先搜索的策略从根结点出发深度探索解空间树。当探索到某一结点时要先判断该结点是否包含问题的解如果包含就从该结点出发继续探索下去如果该结点不包含问题的解那就说明以该结点为根结点的子树一定不包含问题的最终解因此要跳过对以该结点为根的子树的系统探索逐层向其祖先结点回溯。这个过程叫做解空间树的“剪枝”操作。
如果应用回溯法求解问题的所有解要回溯到解空间树的树根这样才能保证根结点的所有子树都被探索到才结束。如果只要求得问题的一个解那么在探索解空间树时只要搜索到问题的一个解就可以结束了。
1、四皇后问题求解
问题描述求解如何在一个NxN的棋盘上无冲突地摆放N个皇后棋子在任意一个皇后所在位置的水平、数值、以及45度斜线上都不能出现其他皇后的棋子否则视为冲突。
以四皇后问题为例构建出一棵空间树通过探索这棵解空间树可以得到四皇后的一个解或者几个解。 根结点派生出4个子结点每个结点都示意出前两个皇后可能摆放的位置。每个结点又可以派生出4个子结点每个结点都示意出前3个皇后可能摆放的位置整个解空间树为一棵4叉的满树共包含4x4x44x44185个结点.
应用回溯法解决问题从根结点出发深度优先搜索整个解空间树。当访问到根结点的第一个孩子时观察结点如果该结点不包含问题的解那么由该结点作为根结点派生出来的子树中也肯定不会包含四皇后问题的解停止向下搜索回溯到根结点继续太多根结点的下一个孩子结点。这就是”剪枝“操作可以减少搜索的次数
在解决出四皇后问题时并不一定要真的构建出这样的一棵解空间树它完全可以通过一个递归回溯来模拟。所谓解空间树只是一个逻辑上的抽象。当然也可以用树结构真实地创建出一棵解空间树不过比较浪费空间资源。
#includeiostream
#include stdio.h
#include stdlib.h
#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 4;t)if (Q[s][t] 1 t ! j) return 0; //判断是否在同一行for (t j, s 0;s 4;s)if (Q[s][t] 1 s ! i) return 0; //判断是否在在同一列for (s i - 1, t j - 1;s 0 t 0;s--, t--)if (Q[s][t] 1) return 0; //判断是否在左上方for (s i 1, t j 1;s 4 t 4;s, t)if (Q[s][t] 1) return 0; //判断是否在右下方for (s i - 1, t j 1;s 0 t 4;s--, t)if (Q[s][t] 1) return 0; //判断是否在右上方for (s i 1, t j - 1;s 4 t 0;s, t--)if (Q[s][t] 1) return 0; //判断是否在左下方//否则返回1return 1;
}//输入参数: j:二维数组Q的列号(0-3),最开始调用时j0,表明第一个皇后摆放在棋盘上的第一列。(*Q)[4]指向二维数组每一行的指针
//中间变量i二维数组Q的行号(0-3),通过对变量i的4次循环可以分别探索四皇后问题的4棵解空间树(以Q[0][0]、Q[1][0]、Q[2][0]、Q[3][0]为解空间树的根结点)
//当j4时表明Q第0-3列都已经放置好棋子了说明此时得到了一个四皇后的解因此程序返回上一层
void FourQueen(int j, int(*Q)[4])
{int i, k;//如果得到一个解if (j 4){//打印出结果for (i 0;i 4;i){for (k 0;k 4;k)printf(%d , Q[i][k]);printf(\n);}printf(\n);//解个数1//返回到上一级_getche();count;return;}//否则for (i 0;i 4;i){if (IsCorrect(i, j, Q)) //如果Q[i][j]可以放置皇后表明这一列不需要再探索了{Q[i][j] 1;FourQueen(j1,Q); //探索下一列递归深度优先搜索//Q[i][j]0以便循环试探Q[i1][j](下一行是否可以摆放皇后因为如果这一行如果没有找到解需要清除这一行痕迹然后到下一行继续探索Q[i][j] 0;}}
}
//测试函数
int main()
{int Q[4][4];int i, j;//初始化数组Qfor (i 0;i 4;i)for (j 0;j 4;j)\Q[i][j] 0;FourQueen(0,Q); //执行四皇后求解printf(四皇后解法有%d种\n,count);_getche();
}效果 2、上楼梯问题
已知楼梯有20阶上楼可以一步上1阶也可以一步上2阶。编写一个程序计算共有多少种不同的上楼梯方法。
分析采用递归回溯用一棵空间二叉树描述 从根结点出发向下搜索每经过一个结点则表示这一步登上的台阶数。每次都将访问结点中的数字相加记录为当前已经走过的台阶数当这个数字等于20就表示寻找出了一种上楼梯的方案。那么该结点以下的结点也就没必要再访问了而是向其父结点回溯并继续探索下一分支。
代码
#includeiostream
#include stdio.h
#include stdlib.h
#include malloc.h
#include conio.h#define MAX_STEPS 20 //定义20个台阶的楼梯
int Steps[MAX_STEPS] { 0 }; //Steps[i]等于1或者等于2记录第i步登上的台阶数
int cnt 0; //记录上楼梯的方案的数目void Upstairs(int footstep,int count,int step)
{//footsetp:当前要登的台阶数、count已经走过的阶数、step:走过的步数int i;if (count footstep MAX_STEPS){//得到一种上楼梯方案Steps[step] footstep;cnt; //方案数1//打印出方案for (i 0;i step;i){printf(%d ,Steps[i]);}printf(\n);//返回到父结点不必再向下搜索}else if (count footstep MAX_STEPS){//超过了楼梯的阶数不必再向下搜索返回到父结点return;}else{//Steps[step] footstep; //记录当前上楼梯的台阶数step; //步数1count 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();
}效果
5、数值概率算法
概率算法允许在执行过程中随机地选择下一步的计算步骤因此使用概率算法有时会大大降低复杂度提高算法的效率但有时也可能得不到问题的全部答案。
概率算法可以分为4类
1、数值概率算法
2、蒙特卡洛算法
3、拉斯维加斯算法
4、舍伍德算法
这里只介绍最基础的数值概率算法。
数值概率算法常用于解决数值计算的问题。应用数值概率算法往往只能得到问题的近似解并且该近似解的精度一般随着计算时间的增加而不断提高。
例:f(x)1-x^2;计算定积分:
该积分的几何意义如下: 如果随机地向图中虚线与x,y坐标轴所围成的正方形中投点那么根据几何概率知识可知随机点落入阴影区域的概率即为阴影部分的面积与虚线与x,y轴所围成的正方形的面积之比。
所以只要求出随机点落入阴影区域的概率的概率就求出了定积分的近似值。
算法描述
#includeiostream
#include stdio.h
#include stdlib.h
#include malloc.h
#include conio.h
#include time.hdouble Darts(int n) //n为试验投点的个数决定了计算概率的精度
{double x, y;time_t t;int i, count 0;srand((unsigned)time(t));for (i 0;i n;i){//随机初始化投点的坐标x rand() % 100 / 100.0;y rand() % 100 / 100.0;if (y 1 - pow(x, 2))count; //如果随机点落入阴影区域则用count记录个数}return (double)count / (double)n; //返回概率
}
//测试函数
int main()
{int n;char c;printf(请输入试验精度(越大精度越好):\n);scanf(%d, n);printf(结果为\n);printf(%f\n, Darts(n));_getche();return 0;
}
