-
2021-05-20 09:12:23
本科生实验报告
课程名称:算法设计与分析
实验项目:递归和分治算法
实验地点:计算机系实验楼110
专业课:物联网1601学生。2016002105
学生姓名:于
指导员:郝晓丽
2018年5月4日
实验1递归和分治算法
1.1实验目的和要求
1.进一步熟悉C/C语言的集成开发环境;
2.通过本实验加深对递归和分治策略的理解和应用。
1.2实验课时
2小时
1.3实验原理
分而治之的思想是将一个规模为n的复杂问题的解分成几个规模小于n的子问题,然后将子问题的解组合成原问题的解。
应该注意的是分治法使用递归。分割后的每个子问题与原问题具有相同的性质,可以用相同的方法求解。最后,当子问题的规模足够小时,子问题可以直接求解,然后原问题可以反过来求解。
1.4实验主题
1.计算机主题:格雷码构造
格雷码是长度为2n的序列。序列没有相同的元素,每个元素是一个长度为n的字符串,相邻的元素正好有一位不同。尝试设计一个算法来为任何n(分而治之,减少和改变)构造相应的格雷码。
对于给定的正整数n,格雷码是满足以下条件的编码序列。
(1)该序列由2n个代码组成,每个代码是长度为n的二进制位串
(2)序列中没有相同的代码。
(3)序列中的两个相邻码正好有一个比特不同。
2.设计理念:
根据格雷码的性质和寻找他的规则,可以发现比特1是0 1。两个是00 01 11 10。三位数是000 001 011 010 110 111 101 100。这N位是前n-1位的两倍。N-1位前有0,N-2位反相后有1。
3.代码设计:
#包括
#包括
#包括
#包括
使用命名空间标准;
//找到格雷码的递归公式:G(n-1)=B(n-1) G(i)=B(i 1)异或B(I)(0my _ gray;
void get_grad(int n)
{
//cout11)
{
//cout 1 tmp;
对于(int j=0;j=0;j -)
{
字符串s=' 1
s=tmp[j];
我的毕业论文。
}
}
}
}
int main()
{
int n;
同时(cinn)
{
get _ grad(n);
对于(int I=0;I0,t=(t1,T2,TN),客户I期望的服务完成时间是di0,d=(D2 D1,dn);时间表f:AN,f(i)是客户I的开始时间。如果客户I的服务在di之前结束,则客户I的服务没有延迟,即如果在di之后结束,则服务延迟的时间等于实际完成时间f(i) ti减去服务的预期完成时间di。计划的最大延迟是所有客户延迟周期的最大值。图2显示了不同调度下的最大延迟。使用贪婪策略找到一个时间表,以最小化最大延迟。
2.设计理念:
贪婪的思想,按照自己的期限从小到大,如果期限是一样的,按照时间从小到大。然后,根据f_min(所有客户延迟时间的最大值)=max(工作[1)。《[一世》。截止日期,f _ min);找出所有客户的最大延迟时间。
3.代码设计:
//最小延迟调度问题
//输入内容包括:任务、完成任务所需时间、完成修改任务的截止时间
#包括
#包括
#包括
#包括
使用命名空间标准;
常量int maxn=1000 10
int n;
结构节点{
int id。
内部成本;
int截止日期;
}[马克斯作品】;
bool cmp(节点a,节点b)
{
如果(a .截止日期!b .截止日期)
返回a .致命工程[1]。截止日期)
f _ min=max([作品一)。花费时间-工作[i]。截止日期,f _ min);
//cout
#包括
更多相关内容 -
算法分析与设计实验报告一——分治算法
2020-07-17 22:12:59一、实验目的 了解分治策略算法思想 掌握快速排序、归并排序算法 ...三、算法思想分析 归并排序 基本思想为先将一个待排序序列分成两段大小大致相同的段,然后对这两个段同样递归地进行二分,直到不能再一、实验目的
- 了解分治策略算法思想
- 掌握快速排序、归并排序算法
- 了解其他分治问题典型算法
二、实验内容
- 编写一个简单的程序,实现归并排序。
编写一段程序,实现快速排序。 - 编写程序实现循环赛日程表。设有n=2k个运动员要进行网球循环赛。现要设计一个满足以下要求的比赛日程表:
(1)每个选手必须与其它n-1个选手各赛一次
(2)每个选手一天只能赛一场
(3)循环赛进行n-1天
三、算法思想分析
- 归并排序
基本思想为先将一个待排序序列分成两段大小大致相同的段,然后对这两个段同样递归地进行二分,直到不能再分为止,然后把足够小的相邻序列合并成有序序列(依据最优子结构且各个子问题相互独立),再上溯,合并,直到整个序列有序化。
合并时需要对两个已有序的序列合并成一个有序队列,因此在合并操作时就需要进行有序化操作,在这里因为本身子序列已经有序,所以采用设置两个子序列的首尾指针,首指针移动来比较两个子序列中的较小元素并存到新序列,直到一方首尾指针重合,再将另一个序列的剩余部分直接接到新序列即可。 - 快速排序
基本思想为通过一次排序将需要排序的序列分割成独立的两部分,首先设置一个基准数,进行一次排序后,其中一部分的所有数据比基准数小,另一部分的所有数据都比基准数大,这样基准数当前位置就是其在有序序列的位置,然后对新分出的两个序列递归地进行排序处理(由于两方互不影响,其满足最优子结构,有独立性),直到序列大小最小,这样通过一次分治的排序可以将所有元素放到有序序列的正确位置上,从而将整个序列有序化,整体是一个“挖坑填数+分治”的过程。 - 循环赛日程表
基本思想为将整个n * n表格分成n/2 * n/2的四部分,对左上角与右上角的部分递归地进行分割(独立性),直到大小为2 * 2的最小可分配部分,针对最小部分,将每个部分的左上角部分赋给右下角(在最优子结构下2 * 2的部分左上角和右上角都是一个元素),右上角部分赋给左下角,再上溯到4 * 4,重复合并操作,一直到大小为n,这样获得的表就是一个已分配好的表,其中第一列是比赛的每一方,后七列的每一列分别代表当天的对阵。
四、实验过程分析
在做本次实验的过程中,我起初对递归的理解程度不是很深,归并和快排的思想相对还好理解,实现起来也有规律可循,但当做到循环赛日程表时,发现分割从归并与快排的一维升到了二维,就在递归的设计上犯了难,通过一段时间的研究与调试,最后发现当规模没有降到最小时其实都是在进行分割,只有当规模够小之后才能简单进行合并操作,再将部分完成的矩阵升规模再合并直到完成整个矩阵。
通过分治的实验,我对分治的最优子结构性质,独立性,规模缩小策略等相关概念与思想的理解相对更加的深入,这对我在整个课程的学习中都是一个十分显著的成果,而且通过代码的实现,我对分治的基本策略与递归的结合的使用更加的娴熟了,这提高了我的编程能力。五、算法源代码及用户屏幕
1.归并排序
①代码#include<iostream> using namespace std; void merge(int array[], int left, int middle, int right) { int length = right - left + 1; //申请空间用于存储合并之后的序列 int temp[right - left + 1]; //设置标号 int begin1 = left; int end1 = middle; int begin2 = middle + 1; int end2 = right; //设置新数组的计数器 int i = 0; //比较,进入序列 while ((begin1 <= end1) && (begin2 <= end2)) { if (array[begin1] < array[begin2]) { temp[i] = array[begin1]; begin1++; i++; } else { temp[i] = array[begin2]; begin2++; i++; } } //将剩余部分直接接到最后的序列上 while (begin1 <= end1) { temp[i] = array[begin1]; begin1++; i++; } while (begin2 <= end2) { temp[i] = array[begin2]; begin2++; i++; } for (int j = 0; j < length; j++) { array[left + j] = temp[j]; } } //递归调用完成操作 void mergeSort(int data[], int left, int right) { if (left < right) { int middle = (left + right) / 2; //先分后合并 mergeSort(data, left, middle); mergeSort(data, middle + 1, right); merge(data, left, middle, right); } } int main() { int n; cout << "Please input the number of numberSet: "; cin >> n; int array[n]; cout << "Please input the number: "; for (int i = 0; i < n; i++) { cin >> array[i]; } mergeSort(array, 0, n - 1); cout << "the result is: "; for (int i = 0; i < n; i++) { cout << array[i] << " "; } system("pause"); return 0; }
②用户界面
首先输入序列中数的个数,然后输入无序序列,回车之后返回有序序列
2.快速排序
①代码#include <iostream> using namespace std; int splitArray(int data[], int left, int right) { //获取最左边的元素 int temp = data[left]; //从左向右查找小于标志位的元素,换到左边,移指针 while (left < right) { while ((left < right) && (data[right] >= temp)) { right--; } data[left] = data[right]; //从右向左查找大于标志位的元素,换到右边,移指针 while ((left < right) && (data[left] <= temp)) { left++; } data[right] = data[left]; } //将标志位填到空位 data[left] = temp; return left; } //先将标志位填好,然后左右递归调用 void quickSort(int data[], int left, int right) { if (left < right) { int middle = splitArray(data, left, right); quickSort(data, left, middle - 1); quickSort(data, middle + 1, right); } } int main() { int n; cout << "Please input the number of numberSet: "; cin >> n; int array[n]; cout << "Please input the number: "; for (int i = 0; i < n; i++) { cin >> array[i]; } quickSort(array, 0, n - 1); cout << "the result is: "; for (int i = 0; i < n; i++) { cout << array[i] << " "; } system("pause"); return 0; }
②用户界面
首先输入序列中数的个数,然后输入无序序列,回车之后返回有序序列
3.循环赛日程表
①代码#include<iostream> using namespace std; #define NUM 100 void queue(int data[NUM][NUM], int left, int right, int num) { int middle = (left + right) / 2; //将左上角送到右下角 for (int i = 0; i < num; i++) { for (int j = left; j <= middle; j++) { data[i + num][j + num] = data[i][j]; } } //将左下角送到右上角 for (int i = 0; i < num; i++) { for (int j = middle + 1; j <= right; j++) { data[i + num][j - num] = data[i][j]; } } } void queueRace(int data[NUM][NUM], int left, int right, int num) { int middle = (left + right) / 2; //当没有到临界条件(块足够小)时,递归调用 if (num > 1) { queueRace(data, left, middle, num / 2); queueRace(data, middle + 1, right, num / 2); } //合并块 queue(data, left, right, num); } int main() { int n; cout << "Please input the number of queues: "; cin >> n; cout << "The result of race is: " << endl; int data[NUM][NUM] = { 0 }; for (int i = 0; i < n; i++) { data[0][i] = i + 1; } for (int i = 1; i < n; i++) { for (int j = 0; j < n; j++) { data[i][j] = 0; } } queueRace(data, 0, n - 1, n / 2); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (j == n - 1)cout << data[i][j] << endl; else cout << data[i][j] << " "; } } system("pause"); return 0; }
②用户界面
首先输入需要比赛的队伍数(2的倍数),回车之后显示比赛日程表
-
算法设计与分析学习心得
2020-06-23 22:13:14计算机算法设计与分析主要通过介绍常见的算法设计策略及复杂性分析方法,培养学生分析问题和解决问题的能力,为开发高效的软件系统及参加相关领域的研究工作奠定坚实的基础。该课程理论与实践并重,内容具有综合性、...计算机算法设计与分析主要通过介绍常见的算法设计策略及复杂性分析方法,培养学生分析问题和解决问题的能力,为开发高效的软件系统及参加相关领域的研究工作奠定坚实的基础。该课程理论与实践并重,内容具有综合性、广泛性和系统性,是一门集应用性、创造性及实践性为一体的综合性极强的课程,通过对本课程的学习,对如下算法有了深刻的理解。
一、递归与分治策略:大整数的乘法、矩阵乘法、棋盘覆盖、合并排序、快速排序
程序直接或间接调用自身的编程技巧称为递归算法。分治法的设计思想是,将一个难以直接解决的大问题,分割成一些规模较小的相同问题,以便各个击破,分而治之。
分治法在每一层递归上都有三个步骤:分解:将原问题分解为若干个规模较小,相互独立,与原问题形式相同的子问题;解决:若子问题规模较小而容易被解决则直接解,否则递归地解各个子问题;合并:将各个子问题的解合并为原问题的解。
递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算,大大地减少了程序的代码量。递归优秀在代码简洁,但首先需要有清晰的思路理清递归的循环条件及出口。递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时,递归前进;当边界条件满足时,递归返回。
有时递归需要多次重复某一计算,可以用数组记录下需要的数据进行调用大大降低空间复杂度。在用分治法设计算法时,最好使子问题的规模大致相同。如分成大小相等的k个子问题,许多问题可以取k=2。
分治法所能解决的问题一般具有以下几个特征:
(1)该问题可以分解为若干个规模较小的相同问题,即该问题具有最优子结构性质,当一个问题的最优解包含其子问题的最优解时,称此问题具有最优子结构性质;
(2)利用该问题分解出的子问题的解可以合并为该问题的解;
(3)该问题所分解出的各个子问题是相互独立的,即子问题之间不包含公共的子子问题。
二、动态规划:最长公共子序列、凸多边形最优三角剖分、图像压缩、0-1背包问题、最优二叉搜索树
动态规划是解决多阶段决策问题的一种方法。据空间顺序或时间顺序对问题的求解划分阶段。根据题意要求,对每个阶段所做出的某种选择性操作。用数学公式描述与阶段相关的状态间的演变规律。
如果一类问题的求解过程可以分为若干个互相联系的阶段,在每一个阶段都需作出决策,并影响到下一个阶段的决策。在做每一步决策时,列出各种可能的局部解.依据某种判定条件,舍弃那些肯定不能得到最优解的局部解。以每一步都是最优的来保证全局是最优的。
动态规划与分治法所能解决问题的特征类似,主要区别在于动态规划所分解出的各个子问题不是相互独立的,即子问题之间包含公共的子子问题。
三、贪心算法:活动安排问题、装载问题、哈夫曼编码、单源最短路径、最小生成树
在求最优解问题的过程中,依据某种贪心标准,从问题的初始状态出发,直接去求每一步的最优解,通过若干次的贪心选择,最终得出整个问题的最优解,这种求解方法就是贪心算法。
利用贪心法求解的问题应具备如下2个特征:
1、贪心选择性质,指所求问题的整体最优解可以通过一系列局部最优的选择,即贪心选择来达到;
2、最优子结构性质。
四、回溯法:装载问题、n后问题、0-1背包问题、最大团问题、旅行售货员问题
以深度优先的方式系统地搜索问题的解的方法称为回溯法,分为递归回溯和迭代回溯两种。当所给的问题是从n个元素的集合S中找出满足某种性质的子集时,相应的解空间树称为子集树。当所给的问题是确定n个元素满足某种性质的排列时,相应的解空间树称为排列树。回溯算法可以很方便地遍历一个集合的所有子集或者所有排列。
在生成解空间树时,定义以下几个相关概念:活结点:如果已生成一个结点而它的所有儿子结点还没有全部生成,则这个结点叫做活结点。扩展结点:当前正在生成其儿子结点的活结点叫扩展结点(正扩展的结点)。死结点:不再进一步扩展或者其儿子结点已全部生成的结点就是死结点。
在确定了解空间的组织结构后,回溯从开始结点(根结点)出发,以深度优先的方式搜索整个解空间。这个开始结点成为一个活结点,同时成为当前的扩展结点。在当前的扩展结点,搜索向深度方向进入一个新的结点。这个新结点成为一个新的活结点,并成为当前的扩展结点。若在当前扩展结点处不能再向深度方向移动,则当前的扩展结点成为死结点,即该活结点成为死结点。此时回溯到最近的一个活结点处,并使得这个活结点成为当前的扩展结点。回溯法以这样的方式递归搜索整个解空间(树),直至满足中止条件。
在回溯法搜索解空间树时,通常采用两种策略(剪枝函数)避免无效搜索以提高回溯法的搜索效率:用约束函数在扩展结点处减去不满足约束条件的子树;用限界函数减去不能得到最优解的子树。
回溯法是一种组织搜索的一般技术,有“通用的解题法”之称,用它可以系统的搜索一个问题的所有解或任一解。有许多问题,当需要找出它的解集或者要求回答什么解是满足某些约束条件的最佳解时,往往要使用回溯法。应用回溯法求解时,需要明确定义问题的解空间,问题的解空间应至少包含问题的一个(最优)解。
五、分支界限法:单元最短路径问题、装载问题、0-1背包问题、最大团问题、旅行售货员问题
分支限界法在具体执行时,把全部可行的解空间不断分割为越来越小的子集(称为分支),并为每个子集内的解的值计算一个下界或上界(称为限界)。
分支限界法常以广度优先或以最小耗费(最大效益)优先的方式搜索问题的解空间树。在分支限界法中,每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点,就一次性产生其所有儿子结点。在这些儿子结点中,凡是界限超出已知可行解值的儿子结点被舍弃,其余儿子结点被加入活结点表中。此后,从活结点表中取下一结点成为当前扩展结点,并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。
一般情况下,分支限界法与回溯法的求解目标不同。回溯法的求解目标是找出T中满足约束条件的所有解,而分支限界法的求解目标则是找出满足约束条件的一个解,或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解,即在某种意义下的最优解。
六、结语
在动态规划算法中,每步所做的选择往往依赖于相关子问题的解,因而只有在解出相关子问题后,才能做出选择(子问题->选择->原问题)。在贪心算法中,仅在当前状态下做出最好选择,即局部最优选择,然后再去解出这个选择后产生的相应的子问题(原问题->选择->子问题)。贪心算法的每一次操作都对结果产生直接影响,而动态规划则不是。贪心算法对每个子问题的解决方案都做出选择,不能回退;动态规划则会根据以前的选择结果对当前进行选择,有回退功能。动态规划主要运用于二维或三维问题,而贪心一般是一维问题。
大多数问题动态规划都可以解决,但是太慢。因此有些问题贪心确实比动态快的多。不过相对的贪心解决问题并不如动态规划精细,得出来的不一定是最优解,只能说是相对最优,根据情况选择不同的算法解决问题才是王道。
在现实中,有很多问题往往需要我们把其所有可能穷举出来,然后从中找出满足某种要求的可能或最优的情况,从而得到整个问题的解。回溯算法就是解决这种问题的“通用算法”,有“万能算法”之称。如果一个问题可以同时用几种方法解决,贪心算法应该是最好的选择之一。
通过对课程的理论学习与实践,我掌握了许多经典的算法思想,思维创新能力和实践能力得到了有效的提高,并且一题多解的情况让我对不同的算法有了更加深刻的认识。这些知识在我今后的学习中将会得到更深层次的理解与应用。
-
算法分析与设计心得
2022-04-12 20:54:00数据结构和算法是非常难啃的东西 ,以下我会用VS2019可以编译 并且以代码和典型例子为基础 来讲解 几个典型的计算机学生应该掌握并且使用非常熟练的算法以下内容 需要大家有基本的数据结构知识, 如果学过 巩固数据...数据结构和算法是非常难啃的东西 ,以下我会用VS2019可以编译 并且以代码和典型例子为基础 来讲解 几个典型的计算机学生应该掌握并且使用非常熟练的算法以下内容 需要大家有基本的数据结构知识, 如果学过 巩固数据结构基本的一些知识
型特例)
1.贪心法【以狄杰斯特拉算法为特例】
贪心算法思想:
顾名思义,贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑,它所作出的选择只是在某种意义上的局部最优选择。当然,希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解,但对许多问题它能产生整体最优解。如单源最短路经问题,最小生成树问题等。在一些情况下,即使贪心算法不能得到整体最优解,其最终结果却是最优解的很好近似。
贪心算法的基本要素:
1.贪心选择性质。所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择,即贪心选择来达到。这是贪心算法可行的第一个基本要素,也是贪心算法与动态规划算法的主要区别。
动态规划算法通常以自底向上的方式解各子问题,而贪心算法则通常以自顶向下的方式进行,以迭代的方式作出相继的贪心选择,每作一次贪心选择就将所求问题简化为规模更小的子问题。
对于一个具体问题,要确定它是否具有贪心选择性质,必须证明每一步所作的贪心选择最终导致问题的整体最优解。
- 当一个问题的最优解包含其子问题的最优解时,称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。
贪心算法的基本思路:
从问题的某一个初始解出发逐步逼近给定的目标,以尽可能快的地求得更好的解。当达到算法中的某一步不能再继续前进时,算法停止。
该算法存在问题:
-
不能保证求得的最后解是最佳的;
-
不能用来求最大或最小解问题;
-
只能求满足某些约束条件的可行解的范围。
实现该算法的过程:
从问题的某一初始解出发;
while 能朝给定总目标前进一步 do
求出可行解的一个解元素;
由所有解元素组合成问题的一个可行解;
```cpp #include <iostream> using namespace std; #define max 10000 void yuan(int n, int** a, int m)//实现贪心法的函数 { int* b = new int[n + 1], * s = new int[n + 1];//增加一块空间,b用来存放目的节点到其它节点的最小距离,S用来标记 int i, j; for (i = 1; i <= n; i++) { b[i] = a[m][i]; s[i] = 0;//可以做假设 从第一个开始m=1 放入b数组中,此时是没有更新的距离,不是最短距离都没有标记 } s[m] = 1;//此时标记本身,自身到自身肯定是最短距离 for (int ii = 1; ii < n; ii++)//最外层循环,以节点为单位 操作每个节点 { int min = max, w = 1;//所有大于Max的值都算作 无穷大 w=1 for (int k = 1; k <= n; k++) if (min > b[k] && (!s[k])) { w = k; min = b[k]; }//求出节点1相邻的节点中最短的距离 s[w] = 1;//标记这个节点 记住已记住, 以后不再操作 for (i = 1; i <= n; i++) if (!s[i])//对没有标记的节点进行操作,更新最小值。如此循环 { if (b[i] > b[w] + a[w][i]) b[i] = b[w] + a[w][i]; } } for (j = 1; j <= n; j++) if (j != m) cout << m << "-->" << j << " : " << b[j] << endl; } int main() { int n, m, ** a, i, j; cout <<"请输入顶点数和起始的顶点号:随后输入顶点 到另几个顶点的长度(包括自身)"; while (cin >> n >> m) { a = new int* [n + 1]; for (i = 0; i <= n; i++) a[i] = new int[n + 1]; for (i = 1; i <= n; i++) for (j = 1; j <= n; j++) cin >> a[i][j]; yuan(n, a, m); } return 0; }
``
不懂的可以自己画图 然后用邻接矩阵法画出一个图,试一试;分治法(二分查找)
将整个问题分解成若干小问题后再分而治之。如果分解得到的子问题相对来说还是太大,则可反复使用分治策略将这些子问题分成更小的同类型子问题,直至产生方便求解的子问题,必要时逐步合并这些子问题的解,从而得到问题的解。
分治算法可以由递归过程来表示,因为分治法就是一种找大规模问题与小规模问题关系的方法,是递归设计的一种具体策略。步骤
1.分解
将原问题分解为若干规模较小,相互独立,与原问题相同的子问题。
2.解决
若干子问题较小而容易被解决则直接解决,否则再继续分解为更小的子问题,直到容易解决。
3.合并
将已求解的各个子问题的解,逐步合并为原问题的解。有的问题分解后不需要合并子问题的解,此时就不需要再做第3步了。多数问题需要子问题的解,按照题意使用恰当的方法合并成为整个问题的解。需要具体问题具体分析。
#include<stdio.h> float a[5]={3,6,9,2,5}; int main(){ void maxmin(int i,int j,float &fmax,float &fmin,int &count);//fmax的地址,fmin的地址 float fmax=0,fmin=0; int count=0; maxmin(0,4,fmax,fmin,count); //传递地址是为了能够把值带出来 printf("fmax=%f\nfmin=%f\ncount=%d\n",fmax,fmin,count); return 0; } void maxmin(int i,int j,float &fmax,float &fmin,int &count){ int mid; int k; float lmax,lmin,rmax,rmin; count++; //递归结束条件(子问题的解) //当分到只剩一个数 if(i==j){ fmax=a[i];fmin=a[i]; } else if(i==j-1){//(i,j为下标,在分解过程中,i总在左,j总在右 )假如只剩两个数 if(a[i]>a[j]){ fmax=a[i]; fmin=a[j]; } else if(a[j]>a[i]){ fmax=a[j]; fmin=a[i]; } } else{//其他情况(还剩很多数),则继续递归分解 mid=(i+j)/2;//继续分半 maxmin(i,mid,lmax,lmin); maxmin(mid+1,j,rmax,rmin); if(lmax>rmax) fmax=lmax; else fmax=rmax; if(lmin<rmin) fmin=rmin; else fmin=rmin; } }
动态规划法[背包问题]
以下是我综合了动态规划的特点给出的动态规划的定义:动态规划是一种多阶段决策最优解模型,一般用来求最值问题,多数情况下它可以采用自下而上的递推方式来得出每个子问题的最优解(即最优子结构),进而自然而然地得出依赖子问题的原问题的最优解。
划重点:
多阶段决策,意味着问题可以分解成子问题,子子问题,。。。,也就是说问题可以拆分成多个子问题进行求解
最优子结构,在自下而上的递推过程中,我们求得的每个子问题一定是全局最优解,既然它分解的子问题是全局最优解,那么依赖于它们解的原问题自然也是全局最优解。
自下而上,怎样才能自下而上的求出每个子问题的最优解呢,可以肯定子问题之间是有一定联系的,即迭代递推公式,也叫「状态转移方程」,要定义好这个状态转移方程, 我们就需要定义好每个子问题的状态(DP 状态),那为啥要自下而上地求解呢,因为如果采用像递归这样自顶向下的求解方式,子问题之间可能存在大量的重叠,大量地重叠子问题意味着大量地重复计算,这样时间复杂度很可能呈指数级上升(在下文中我们会看到多个这样重复的计算导致的指数级的时间复杂度),所以自下而上的求解方式可以消除重叠子问题。
简单总结一下,最优子结构,状态转移方程,重叠子问题就是动态规划的三要素,这其中定义子问题的状态与写出状态转移方程是解决动态规划最为关键的步骤,状态转移方程如果定义好了,解决动态规划就基本不是问题了。
既然我们知道动态规划的基本概念及特征,那么怎么判断题目是否可以用动态规划求解呢,其实也很简单,当问题的定义是求最值问题,且问题可以采用递归的方式,并且递归的过程中有大量重复子问题的时候,基本可以断定问题可以用动态规划求解,于是我们得出了求解动态规划基本思路如下(解题四步曲)#include<iostream> using namespace std; #include <algorithm> int main() { int w[5] = { 0 , 2 , 3 , 4 , 5 }; //商品的体积2、3、4、5 int v[5] = { 0 , 3 , 4 , 5 , 6 }; //商品的价值3、4、5、6 int bagV = 8; //背包大小 int dp[5][9] = { { 0 } }; //动态规划表 for (int i = 1; i <= 4; i++) { for (int j = 1; j <= bagV; j++) { if (j < w[i]) dp[i][j] = dp[i - 1][j]; else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]); } } //动态规划表的输出 for (int i = 0; i < 5; i++) { for (int j = 0; j < 9; j++) { cout << dp[i][j] << ' '; } cout << endl; } return 0; }
搜索法【旅行商问题】
回溯法思路的简单描述是:把问题的解空间转化成了图或者树的结构表示,然后使用深度优先搜索策略进行遍历,遍历的过程中记录和寻找所有可行解或者最优解。
基本思想类同于:
图的深度优先搜索
二叉树的后序遍历
【分支限界法:广度优先搜索 思想类同于:图的广度优先遍历 二叉树的层序遍历 】
-
详细描述
详细的描述则为:回溯法按深度优先策略搜索问题的解空间树。首先从根节点出发搜索解空间树,当算法搜索至解空间树的某一节点时,先利用剪枝函数判断该节点是否可行(即能得到问题的解)。如果不可行,则跳过对该节点为根的子树的搜索,逐层向其祖先节点回溯;否则,进入该子树,继续按深度优先策略搜索。 回溯法的基本行为是搜索,搜索过程使用剪枝函数来为了避免无效的搜索。剪枝函数包括两类:1. 使用约束函数,剪去不满足约束条件的路径;2.使用限界函数,剪去不能得到最优解的路径。 问题的关键在于如何定义问题的解空间,转化成树(即解空间树)。解空间树分为两种:子集树和排列树。两种在算法结构和思路上大体相同。
-
回溯法应用
当问题是要求满足某种性质(约束条件)的所有解或最优解时,往往使用回溯法。它有“通用解题法”之美誉。
#include<iostream> #include<algorithm> #define MAX 100 using namespace std; int n; //城市个数 int a[MAX][MAX]; //城市间距离 int x[MAX]; //记录路径 int bestx[MAX] = {0}; //记录最优路径 int bestp = 63355; //最短路径长 int cp = 0; //当前路径长 void backpack(int t){ if(t>n){ if((a[x[n]][1])&&(a[x[n]][1]+cp<bestp)){ bestp = a[x[n]][1]+cp; for(int i = 1;i<=n;i++){ bestx[i] = x[i]; } } }else{ for(int i = t;i<=n;i++){ /*约束为当前节点到下一节点的长度不为0,限界为走过的长度+当前要走的长度之和小于最优长度*/ if((a[x[t-1]][x[i]])&&(cp+a[x[t-1]][x[i]]<bestp)){ swap(x[t],x[i]); cp+=a[x[t-1]][x[t]]; backpack(t+1); cp-=a[x[t-1]][x[t]]; swap(x[t],x[i]); } } } } int main(){ cout<<"输入城市个数:"<<endl; cin>>n; //顶点数 for(int i = 1;i<=n;i++){ x[i] = i; } cout<<"输入城市之间的距离(0表示城市间不通):"<<endl; for(int i = 1;i<=n;i++){ for(int j = 1;j<=n;j++){ cin>>a[i][j]; } } backpack(2); cout<<"最少旅行费用为: "<<bestp<<endl; cout<<"旅行路径为:"<<endl; for(int i = 1;i<=n;i++){ cout<<bestx[i]<<" "; } cout<<bestx[1]; return 0; }
-
算法分析与设计-实验一 递归与分治算法设计
2020-11-09 19:58:26掌握分治算法的基本思想,掌握分治算法的设计步骤及用递归技术实现分治策略。 二、实验所用仪器及环境 Windows 7 以上操作系统,PC机,codeblocks环境 三、 实验原理: 算法总体思想:对这k个子问题分别求解。如果子... -
理工大算法设计与分析实验报告
2018-06-24 14:31:37实验一递归与分治算法1.1实验目的与要求1.进一步熟悉C / C ++语言的集成开发环境;2.通过本实验加深对递归与分治策略的理解和运用。1.2实验课时2学时1.3实验原理分治(分而治之)的思想:一个规模为Ñ的复杂问题的... -
算法设计与分析(Java实现)—— 归并排序
2022-01-25 15:47:15该算法采用经典的分治(divide-and-conquer) 策略(分治法将问题分(divide)成一些小的问题然后递归求解,而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起,即分而治之)。 二、归并排序思想 1-基本思想: ... -
算法设计与分析 实验二 分治法求解最近点对问题
2021-06-07 01:06:362、实验亮点:二、实验内容与方法三、实验步骤与过程(一)一些准备工作1、实验流程2、数据生成与去除重复点(二)暴力穷举法1、算法描述2、时间复杂度分析3、编程实现(三)分治法1、算法描述2、算法解释与正确性... -
数据结构与算法-常用排序算法分析总结
2021-01-07 22:07:29《数据结构与算法之美》关于排序的4个章节学完后,进行下总结,结合C语言glibc库中实现的qsort函数举例说明下。 常用的排序算法: 冒泡排序(时间复杂度O(n²) 原地排序 稳定排序):两层循环,内层循环执行一轮... -
算法总结与学习心得体会
2021-08-13 21:37:59一.【回溯算法】 最经典的是八皇后问题 二.【贪心算法】 第一个是活动选择问题 第二个是排队打水问题 三.【分治算法】 例子:比赛日程表 -
分治法求最近点对 (深大算法实验2)报告+代码
2020-06-27 15:35:46目录写在前面问题描述求解问题的算法原理描述分治法分治法的改进:算法核心伪代码测试流程算法测试结果及效率分析总览与对比分治法:特殊情况的测试图形演示对求解这个问题的经验总结代码最近点对图形演示 ... -
分治法循环赛实验报告
2020-05-26 19:20:26按照给出的实验算法的思路与步骤,编写程序源代码,验证该试验。 通过该实验,理解并掌握分治法的算法设计思想。 三、算法思想设计: 假设n位选手顺序编号为1,2,3…n,比赛的日程表是一个n行n-1列的表格。i行j列的... -
算法与程序设计基础略讲(附带洛谷例题)
2018-11-12 09:45:58这篇文章改编自我的选修课“算法与程序设计”课程报告,我将里面的大部分例子换成了洛谷上的例题,适合给想入门程序设计竞赛(oi,ACM)或者刚接触计算机编程不久的人看。其实我也只是一位大自然的搬运工,里面的... -
算法实验:分治法合并排序(C++)
2019-09-27 13:34:06这篇文章分两部分来写,第一部分写代码的实现过程,第二部分把实验报告从头到尾呈现出来。 我习惯调试使用的编译器是DEV C++,不是vs系列的,可能头文件上有点区别。但是下面的报告是我放到vs里面测试过的,可以... -
动态规划算法学习总结
2018-08-31 14:52:08动态规划与贪心、分治的...分治算法(Divide and conquer alalgorithm) 字面上的解释是“分而治之”,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,直到最后子问题可以简单的直接求解,原问题的解即子问... -
JAVA实验报告(运用JavaFx实现时钟动画).doc
2021-03-16 15:14:26JAVA实验报告(运用JavaFx实现时钟动画),javafx时钟,javafx动画,javafx等待动画,javafx动画效果,时钟动画,ppt时钟动画,时钟机关之星动画化,flash时钟动画,flash制作时钟动画JAVA实验报告实验二 运用JavaFx实现时钟... -
实验一 ADT描述及其实现.doc
2021-05-26 01:40:06但是容易忽略实验的总结,忽略实验报告的撰写。对于一名大学生必须严格训练分析总结能力、书面表达能力。需要逐步培养书写科学实验报告以及科技论文的能力。拿到一个题目,一般不要急于编程。... -
南方某高校离散数学实验报告
2017-11-22 22:42:48本实验的主要算法思路是将需要判断真值的合式公式分解为小的合式公式“分而治之”,以括号为划分界限,计算出括号内”小的“合式公式的真值后再对总的合式公式进行真值判断。 输入说明 输入合式公式时考虑... -
『嗨威说』算法设计与分析 - 算法第二章上机实践报告(二分查找 / 改写二分搜索算法 / 两个有序序列的中位...
2019-10-04 12:56:00本文索引目录: 一、PTA实验报告题1 :二分...二、PTA实验报告题2 :改写二分搜索算法 2.1 实践题目 2.2 问题描述 2.3 算法描述 2.4 算法时间及空间复杂度分析 三、PTA实验报告题3 :两个有序序列... -
基于JavaSpringMVC+Mybatis+Jquery高校毕业设计管理系统设计和实现
2022-02-08 09:30:04随着信息时代计算机网络技术的发展给人们带来了极大的方便,传统的毕业设计过程在很大程度上给学生、教师和管理人员带来了不便。而毕业论文对于高校学生而言是对自己在学校所学的专业知识和技能的总结,对高校的教育... -
实验 ADT描述及其实现.doc
2021-05-20 15:55:25实验 ADT描述及其实现实验一 ADT描述...但是容易忽略实验的总结,忽略实验报告的撰写。对于一名大学生必须严格训练分析总结能力、书面表达能力。需要逐步培养书写科学实验报告以及科技论文的能力。拿到一个题目,一... -
《大数据技术原理与应用》林子雨(第二版)--总结
2021-01-22 21:11:28本篇文章主要是根据书中内容,对书中的课后答案做下总结。 第一篇 大数据基础 大数据处理架构Hadoop 试述 hadoop 和谷歌的 mapreduce、gfs 等技术之间的关系 答:Hadoop 的核心是分布式文件系统 HDFS 和 MapReduce... -
吉林大学软件需求分析 Software Requirement Analysis
2022-01-27 12:09:22吉林大学软件需求分析 Software Requirement Analysis 缩写/术语 RE:Requirements Engineering 需求工程 SRS:Software Requirements Specification 软件需求规范 SRA:Software Requirements Analysis 软件需求... -
实验报告5
2021-04-19 13:49:01课程名称 《算法分析与设计》 实验日期 2021 年 4 月12 日 学生姓名 吕静怡 所在班级 计算机194 学号 2019212212145 实验名称 实验地点 同组人员 1.问题. 最近对问题要求在包含有n个点的集合S中,找出... -
【算法学习】实验 2. 基于分治法的循环日程表算法
2018-10-30 22:23:00目录 实验内容 实验目的 实验要求 实验步骤 步骤一:理解问题并给... 步骤二:算法设计,包括策略与数据结构 步骤三:描述算法,伪代码与流程图的形式 步骤四:算法正确性证明 步骤五:算法复杂性分析 ... -
Spark MLlib分布式机器学习源码分析:决策树算法
2020-03-25 09:22:29Spark是一个极为优秀的大数据框架,在大数据批处理...本文结合机器学习思想与Spark框架代码结构来实现分布式机器学习过程,希望与大家一起学习进步~ 目录 1.决策树理论 2.Spark实例 3.源码分析 本文采用的... -
Hadoop大数据技术课程总结2021-2022学年第1学期
2021-12-04 13:57:00本文为Hadoop大数据技术课程总结,包括大数据概述,HDFS,MapReduce,Yarn,Hive,Zookeeper,Flume的基本介绍,部分内容附上了可供参考的链接,希望通过本博客的学习,各位学生能有所得,欢迎留言回复问题 -
学习使用分治算法来解决邮局选址问题(Java实现)
2020-10-24 10:50:21注意:三、邮局选址问题总结算法设计思路 前言 提示:在算法的学习过程中我们会遇到各种各样的算法思想,其中最常见的就有分治算法思想,而本文的问题邮局选址问题就是基于分治思想而去实现的一个日常问题 提示:... -
机器学习之集成学习(实验记录)
2022-01-30 17:06:41集成学习实验任务一、实验目标二、实验内容三、实验任务及步骤四、实验总结 一、实验目标 了解集成学习的基本结构、训练方法、实现方法,并通过随机森林与Adaboost算法加深理解。 二、实验内容 概念 集成学习...