下载文档原格式
《算法设计与分析》实验报告实验一递归与分治策略应用基础学号：**************姓名：*************班级：*************日期：2014-2015学年第1学期第九周一、实验目的1、理解递归的概念和分治法的基本思想2、了解适用递归与分治策略的问题类型，并能设计相应的分治策略算法3、掌握递归与分治算法时间空间复杂度分析，以及问题复杂性分析方法二、实验内容任务：以下题目要求应用递归与分治策略设计解决方案，本次实验成绩按百分制计，完成各小题的得分如下，每小题要求算法描述准确且程序运行正确。
1、求n个元素的全排。
（30分）2、解决一个2k*2k的特殊棋牌上的L型骨牌覆盖问题。
（30分）3、设有n=2k个运动员要进行网球循环赛。
设计一个满足要求的比赛日程表。
（40分）提交结果：算法设计分析思路、源代码及其分析说明和测试运行报告。
三、设计分析四、算法描述及程序五、测试与分析六、实验总结与体会#include "iostream"using namespace std;#define N 100void Perm(int* list, int k, int m){if (k == m){for (int i=0; i<m; i++)cout << list[i] << " ";cout << endl;return;}else{for (int i=m; i<k; i++){swap(list[m], list[i]);Perm(list, k, m+1);swap(list[m], list[i]);}}}void swap(int a,int b){int temp;temp=a;a=b;b=temp;}int main(){int i,n;int a[N];cout<<"请输入排列数据总个数：";cin>>n;cout<<"请输入数据：";for(i=0;i<n;i++){cin>>a[i];}cout<<"该数据的全排列："<<endl;Perm(a,n,0);return 0;}《算法设计与分析》实验报告实验二递归与分治策略应用提高学号：**************姓名：*************班级：*************日期：2014-2015学年第1学期一、实验目的1、深入理解递归的概念和分治法的基本思想2、正确使用递归与分治策略设计相应的问题的算法3、掌握递归与分治算法时间空间复杂度分析，以及问题复杂性分析方法二、实验内容任务：从以下题目中任选一题完成，要求应用递归与分治策略设计解决方案。
算法设计与分析黄丽韵版（1）用计算机求解问题的步骤：1、问题分析2、数学模型建立3、算法设计与选择4、算法指标5、算法分析6、算法实现7、程序调试8、结果整理文档编制（2）算法定义：算法是指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过程（3）算法的三要素1、操作2、控制结构3、数据结构算法具有以下5个属性：有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。
确定性：算法中每一条指令必须有确切的含义。
不存在二义性。
只有一个入口和一个出可行性：一个算法是可行的就是算法描述的操作是可以通过已经实现的基本运算执行有限次来实现的。
输入：一个算法有零个或多个输入，这些输入取自于某个特定对象的集合。
输出：一个算法有一个或多个输出，这些输出同输入有着某些特定关系的量。
算法设计的质量指标：正确性：算法应满足具体问题的需求；可读性：算法应该好读，以有利于读者对程序的理解：健壮性：算法应具有容错处理，当输入为非法数据时，算法应对其作出反应，而不是产生莫名其妙的输出结果。
效率与存储量需求：效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。
一般这两者与问题的规模有关。
经常采用的算法主要有迭代法、分而治之法、贪婪法、动态规划法、回溯法、分支限界法迭代法也称“辗转法”，是一种不断用变量的旧值递推出新值的解决问题的方法。
迭代法也称“辗转法”，是一种不断用变量的旧值递推出新值的解决问题的方利用迭代算法解决问题，需要做好以下三个方面的工作：一、确定迭代模型。
在可以用迭代算法解决的问题中，至少存在一个直接或间接地不断由旧值递推出新值的变量，这个变量就是迭代变量。
二、建立迭代关系式。
所谓迭代关系式，指如何从变量的前一个值推出其下一个值的公式（或关系）。
迭代关系式的建立是解决迭代问题的关键，通常可以使用递推或倒推的方法来完成。
三、对迭代过程进行控制。
在什么时候结束迭代过程？这是编写迭代程序必须考虑的问题。
算法设计与分析(第2版)-王红梅-胡明-习题答案习题11. 图论诞生于七桥问题。
出生于瑞士的伟大数学家欧拉（Leonhard Euler ，1707—1783）提出并解决了该问题。
七桥问题是这样描述的：一个人是否能在一次步行中穿越哥尼斯堡（现在叫加里宁格勒，在波罗的海南岸）城中全部的七座桥后回到起点，且每座桥只经过一次，图 1.7是这条河以及河上的两个岛和七座桥的草图。
请将该问题的数据模型抽象出来，并判断此问题是否有解。
七桥问题属于一笔画问题。
输入：一个起点输出：相同的点1， 一次步行2， 经过七座桥，且每次只经历过一次3， 回到起点该问题无解：能一笔画的图形只有两类：一类是所有的点都是偶点。
另一类是只有二个奇点的图形。
2．在欧几里德提出的欧几里德算法中（即最初的欧几里德算法）用的不是除法而是减法。
请用伪代码描述这个版本的欧几里德算法1.r=m-n2.循环直到r=02.1 m=n图1.7 七桥问题2.2 n=r2.3 r=m-n3 输出m3．设计算法求数组中相差最小的两个元素（称为最接近数）的差。
要求分别给出伪代码和C++描述。
//采用分治法//对数组先进行快速排序//在依次比较相邻的差#include <iostream>using namespace std;int partions(int b[],int low,int high){int prvotkey=b[low];b[0]=b[low];while (low<high){while (low<high&&b[high]>=prvotkey)--high;b[low]=b[high];while (low<high&&b[low]<=prvotkey)++low;b[high]=b[low];}b[low]=b[0];return low;}void qsort(int l[],int low,int high){int prvotloc;if(low<high){prvotloc=partions(l,low,high); //将第一次排序的结果作为枢轴qsort(l,low,prvotloc-1); //递归调用排序由low 到prvotloc-1qsort(l,prvotloc+1,high); //递归调用排序由 prvotloc+1到 high}}void quicksort(int l[],int n){qsort(l,1,n); //第一个作为枢轴，从第一个排到第n个}int main(){int a[11]={0,2,32,43,23,45,36,57,14,27,39};int value=0;//将最小差的值赋值给valuefor (int b=1;b<11;b++)cout<<a[b]<<' ';cout<<endl;quicksort(a,11);for(int i=0;i!=9;++i){if( (a[i+1]-a[i])<=(a[i+2]-a[i+1]) )value=a[i+1]-a[i];elsevalue=a[i+2]-a[i+1];}cout<<value<<endl;return 0;}4．设数组a[n]中的元素均不相等，设计算法找出a[n]中一个既不是最大也不是最小的元素，并说明最坏情况下的比较次数。
算法设计与分析算法设计是计算机科学重要的研究方向之一。
其核心目的是在给定的计算机问题下，设计出一种能够高效完成任务的算法。
在算法设计的过程中，需要考虑多种因素，如算法的正确性、可理解性、可维护性、可移植性以及算法的时间和空间复杂度等。
常用的算法设计策略包括贪心算法、动态规划算法、回溯算法、分治算法等多种。
算法的正确性是算法设计的首要考虑因素之一。
如果一个算法不能够正确地解决问题，那么它的时间复杂度和空间复杂度再低也没有用处。
一般来说，算法的正确性可以通过数学证明来进行验证。
根据不同的算法类型，其正确性验证需要应用不同的证明方法。
时间复杂度和空间复杂度也是算法设计的关键考虑因素。
通常，一个算法的时间复杂度越低，运行时间就越短。
同样地，一个算法的空间复杂度越低，需要占用的内存就越少。
时间复杂度和空间复杂度之间通常是矛盾的，因此需要在两者之间做出权衡。
常用的算法比较基准是时间复杂度，时间复杂度大致可以分为常数阶、对数阶、线性阶、平方阶、立方阶等多个级别，并且可能还存在更高阶的时间复杂度。
在算法设计之后，需要进行算法的分析。
算法分析通常包括平均时间复杂度、最坏时间复杂度和最好时间复杂度的分析。
平均时间复杂度指的是在一组随机输入下的平均运行时间，通常是指输入数据分布的随机分布；最坏时间复杂度指的是运行时间的上界，通常是指特殊的输入情况时，算法运行时间达到最大值；最好时间复杂度指的是算法在最理想情况下的运行时间，通常指输入数据已经有序的情况下的运行时间。
除此之外，尚有许多其他因素需要考虑，例如算法的可扩展性、可移植性、可维护性、可复用性等。
其中的可扩展性指的是算法能够处理的数据规模的大小，通常需要根据不同的数据规模进行不同的优化；可移植性指的是算法能够运行在不同的计算机体系结构之上；可维护性指的是算法在输出结果有问题时，能够容易地找到错误所在并进行修改；可复用性指的是算法能够被其他程序员或其他算法模块所复用。
常用算法设计方法要使计算机能完成人们预定的工作，首先必须为如何完成预定的工作设计一个算法，然后再根据算法编写程序。
计算机程序要对问题的每个对象和处理规则给出正确详尽的描述，其中程序的数据结构和变量用来描述问题的对象，程序结构、函数和语句用来描述问题的算法。
算法数据结构是程序的两个重要方面。
算法是问题求解过程的精确描述，一个算法由有限条可完全机械地执行的、有确定结果的指令组成。
指令正确地描述了要完成的任务和它们被执行的顺序。
计算机按算法指令所描述的顺序执行算法的指令能在有限的步骤内终止，或终止于给出问题的解，或终止于指出问题对此输入数据无解。
通常求解一个问题可能会有多种算法可供选择，选择的主要标准是算法的正确性和可靠性，简单性和易理解性。
其次是算法所需要的存储空间少和执行更快等。
算法设计是一件非常困难的工作，经常采用的算法设计技术主要有迭代法、穷举搜索法、递推法、贪婪法、回溯法、分治法、动态规划法等等。
另外，为了更简洁的形式设计和藐视算法，在算法设计时又常常采用递归技术，用递归描述算法。
一、迭代法迭代法是用于求方程或方程组近似根的一种常用的算法设计方法。
设方程为f(x)=0，用某种数学方法导出等价的形式x=g(x)，然后按以下步骤执行：（1）选一个方程的近似根，赋给变量x0；（2）将x0的值保存于变量x1，然后计算g(x1)，并将结果存于变量x0；（3）当x0与x1的差的绝对值还小于指定的精度要求时，重复步骤（2）的计算。
若方程有根，并且用上述方法计算出来的近似根序列收敛，则按上述方法求得的x0就认为是方程的根。
上述算法用C程序的形式表示为：【算法】迭代法求方程的根{ x0=初始近似根；do {x1=x0；x0=g(x1)；/*按特定的方程计算新的近似根*/} while ( fabs(x0-x1)>Epsilon)；printf(“方程的近似根是%f\n”，x0)；}迭代算法也常用于求方程组的根，令X=（x0，x1，…，x n-1）设方程组为：x i=g i(X) (I=0，1，…，n-1)则求方程组根的迭代算法可描述如下：【算法】迭代法求方程组的根{ for (i=0;i<n;i++)x[i]=初始近似根;do {for (i=0;i<n;i++)y[i]=x[i];for (i=0;i<n;i++)x[i]=gi(X);for (delta=0.0,i=0;i<n;i++)if (fabs(y[i]-x[i])>delta) delta=fabs(y[i]-x[i])；} while (delta>Epsilon)；for (i=0;i<n;i++)printf(“变量x[%d]的近似根是%f”，I，x[i])；printf(“\n”)；}具体使用迭代法求根时应注意以下两种可能发生的情况：（1）如果方程无解，算法求出的近似根序列就不会收敛，迭代过程会变成死循环，因此在使用迭代算法前应先考察方程是否有解，并在程序中对迭代的次数给予限制；（2）方程虽然有解，但迭代公式选择不当，或迭代的初始近似根选择不合理，也会导致迭代失败。
《算法分析与设计》作业（一）本课程作业由两部分组成。
第一部分为“客观题部分”，由15个选择题组成，每题1分，共15分。
第二部分为“主观题部分”，由简答题和论述题组成，共15分。
作业总分30分，将作为平时成绩记入课程总成绩。
客观题部分：一、选择题（每题1分，共15题）1、递归算法：（C ）A、直接调用自身B、间接调用自身C、直接或间接调用自身D、不调用自身2、分治法的基本思想是将一个规模为n的问题分解为k个规模较小的字问题，这些子问题：（D ）A、相互独立B、与原问题相同C、相互依赖D、相互独立且与原问题相同3、备忘录方法的递归方式是：（C ）A、自顶向下B、自底向上C、和动态规划算法相同D、非递归的4、回溯法的求解目标是找出解空间中满足约束条件的：（A ）A、所有解B、一些解C、极大解D、极小解5、贪心算法和动态规划算法共有特点是：（ A ）A、最优子结构B、重叠子问题C、贪心选择D、形函数6、哈夫曼编码是：（B）A、定长编码B、变长编码C、随机编码D、定长或变长编码7、多机调度的贪心策略是：（A）A、最长处理时间作业优先B、最短处理时间作业优先C、随机调度D、最优调度8、程序可以不满足如下性质：（D ）A、零个或多个外部输入B、至少一个输出C、指令的确定性D、指令的有限性9、用分治法设计出的程序一般是：（A ）A、递归算法B、动态规划算法C、贪心算法D、回溯法10、采用动态规划算法分解得到的子问题：（ C ）A、相互独立B、与原问题相同C、相互依赖D、相互独立且与原问题相同11、回溯法搜索解空间的方法是：（A ）A、深度优先B、广度优先C、最小耗费优先D、随机搜索12、拉斯维加斯算法的一个显著特征是它所做的随机选性决策有可能导致算法：（ C ）A、所需时间变化B、一定找到解C、找不到所需的解D、性能变差13、贪心算法能得到：（C ）A、全局最优解B、0-1背包问题的解C、背包问题的解D、无解14、能求解单源最短路径问题的算法是：（A ）A、分支限界法B、动态规划C、线形规划D、蒙特卡罗算法15、快速排序算法和线性时间选择算法的随机化版本是：（ A ）A、舍伍德算法B、蒙特卡罗算法C、拉斯维加斯算法D、数值随机化算法主观题部分：二、写出下列程序的答案（每题2.5分，共2题）1、请写出批处理作业调度的回溯算法。
一、计算题或者简答题1. 有一些区间段(0,3), (1,4), (3,5), (6,8),(7,9)，给出个数最多的一组相容的区间段（两个区间相容当且仅当两个区间的交集为空）。
2. 如下可满足问题（SAT）是否有解，若有解该如何给变量赋值：3. 求如下有向图中的一个最长路径，要求给出路径和路径长度的值。
4.智能计算，并行计算概念二、将下列函数按照渐进增长率由大到小进行排列，并给出你的判断依据：三、有一堆货物需要被运走，现在有三种运货车：推车的容量最小，小货车的容量是推车容量的2倍，大货车的容量是两辆小货车的容量加上一辆推车的容量。
假设以上三种车的数量都非常多。
现在要求你设计一种方案派出最少辆车将货物全搬走，其中除了推车以外其它三种车都必须装满才能发车。
为这个问题设计一个算法，并证明该算法的正确性。
提示：贪心算法四、求如下图中s和t间的最小割。
五、对某个输入为n的问题有如下四个分而治之算法：算法1将该问题分成2个子问题，子问题大小为n/3，将子问题的解合并得到上一级问题的解需要O(n)时间；算法2将该问题分成3个子问题，子问题大小为n/2，将子问题的解合并得到上一级问题的解需要O(n)时间；算法3第 1 页共2 页六、为最大独立集问题建立一个整数规划模型。
七、一个图中的一组边集A满足如下性质则称A为一个独立匹配：A中任何两条边都没有公共顶点，任意两个来自A中两条不同边的顶点之间都不存在一条边。
证明求一个图中最大独立匹配（含有最多条边的独立匹配）是NP 难的。
（提示：可以考虑利用最大独立集问题来构造归约）八、子集和问题定义如下：输入为一个有n个正整数的集合A和一个正整数k，问是否存在A的一个子集合其中所有元素之和正好等于k。
为子集和问题设计一个动态规划算法，并用你的算法对如下实例进行求解（要求画出表格）：A={2,3,7,8,9}，k=18.九、叙述带权重的点覆盖问题（Weighted Vertex Cover Problem）的竞价法（PricingMethod），并证明这个算法是个2倍近似算法。
《算法设计与分析》试卷1一、多项选择题（每空2分, 共20分）:1.以下关于算法设计问题的叙述中正确的是__________。
A.计算机与数值问题的求解——方程式求根、插值问题、数值积分、函数逼近等有关B.利用计算机无法解决非数值问题C.计算机在解决分类、语言翻译、图形识别、解决高等代数和组合分析等方面的数学问题、定理证明、公式推导乃至日常生活中各种过程的模拟等问题中, 主要进行的是判断、比较, 而不是算术运算D、算法设计与分析主要研究对象是非数值问题, 当然也包含某些数值问题2.算法的特征包括_________。
A.有穷性B、确定性C.输入和输出D.能行性或可行性3、以下描述是有关算法设计的基本步骤:①问题的陈述②算法分析③模型的拟制④算法的实现⑤算法的详细设计⑥文档的编制, 应与其它环节交织在一起其中正确的顺序是__________。
A.①②③④⑤⑥B.①③⑤②④⑥C.②④①③⑤⑥D.⑥①③⑤②④4.以下说法正确的是__________。
A.数学归纳法可以证明算法终止性B.良序原则是证明算法的正确性的有力工具C. x = 小于或等于x的最大整数（x的低限）D. x = 小于或等于x的最大整数（x的高限）5、汉诺塔（Hanoi）问题中令h（n）为从A移动n个金片到C上所用的次数, 则递归方程为__________, 其初始条件为__________, 将n个金片从A柱移到C柱上的移动次数是__________；设菲波那契（Fibonacci）数列中Fn为第n个月时兔子的对数, 则有递归方程为__________, 其中F1=F2=__________。
A.Fn=Fn-1+Fn-2 B、h（n）= 2h（n-1）+1C.1 D、h（1）= 1E、h（n）=2n-1F、06.在一个有向连通图中（如下图所示）, 找出点A到点B的一条最短路为____ ______。
A.最短路: 1→3→5→8→10, 耗费: 20B、最短路：1→4→6→9→10, 耗费：16C.最短路: 1→4→6→9, 耗费: 12D.最短路: 4→6→9→10, 耗费: 13二、填空（每空2分, 共20分）:1.快速排序法的基本思想是重新排列关键字, 把一个文件分成两个文件, 使得第一个文件中所有元素均小于第二个文件中的元素；然后再对两个子文件进行同样的处理。
算法设计与分析报告第一点：算法设计的重要性与挑战算法设计是计算机科学和信息技术领域中至关重要的一个环节。
在现代社会，算法设计不仅广泛应用于数据处理、人工智能、网络搜索、金融分析等领域，而且对于提高生产效率、优化资源配置、提升用户体验等方面也具有重大的意义。
然而，算法设计同样面临着诸多挑战，这些挑战来自于算法效率、可扩展性、安全性、以及与硬件的协同等多个方面。
在算法设计中，我们需要关注算法的复杂度分析，包括时间复杂度和空间复杂度。
复杂度分析能够帮助我们理解算法的性能瓶颈，并在众多的算法选择中做出合理的决策。
高效算法的开发和应用，对于提升系统的处理能力、缩短计算时间、降低资源消耗等方面都有直接的积极影响。
同时，随着大数据时代的到来，算法设计需要面对的数据规模和复杂性也在不断增加。
如何在保证算法正确性的基础上，提高算法的执行效率，是算法设计师们必须考虑的问题。
此外，对于算法的可扩展性设计也是必不可少的，这要求算法能够在不同规模的数据集上都能保持良好的性能。
安全性和隐私保护也是当前算法设计中不可忽视的一环。
特别是在涉及用户敏感信息的处理过程中，如何保证数据的安全性和用户隐私不被泄露，是算法设计必须考虑的重要问题。
在这方面，加密算法、匿名化处理技术以及安全多方计算等技术的应用显得尤为重要。
最后，算法与硬件的协同优化也是当前研究的热点之一。
随着处理器架构的不断进化，比如众核处理器、GPU等，算法设计需要更加注重与这些硬件特性之间的匹配，以实现更高的计算性能。
第二点：算法分析的方法与技术算法分析是评估和比较算法性能的重要手段，它包括理论分析和实验分析两个方面。
理论分析主要通过数学模型和逻辑推理来预测算法的执行效率，而实验分析则通过在实际运行环境中执行算法来验证理论分析的结果，并进一步探究算法的性能。
在理论分析中，常用的方法有渐进分析、上下界分析、以及概率分析等。
渐进分析是通过考察算法执行次数的函数来估计其时间复杂度，这种分析方法在大多数情况下能够提供足够的信息来判断算法的效率。
东北大学继续教育学院算法设计与分析（一）复习题一、选择题1.算法的复杂性是（）的度量，是评价算法优劣的重要依据。
A.时间效率B.算法效率C.空间效率D.输出效率2.衡量一个算法好坏的标准是（）。
A.运行速度快B.占用空间少C.时间复杂度低D.代码短3.算法分析的两个主要方面是（）。
A.空间复杂度和时间复杂度B.正确性和简单性C.可读性D.程序复杂度4.计算机算法指的是（）。
A.计算方法B.排序方法C.解决问题的方法和过程D.调度方法5.多阶段决策问题就是要在可以选择的那些策略中间选取一个（）策略使在预定的标准下达到最好的效果。
A.最优B.最差C.平衡D.任意6.下列关于算法的说法中正确的有（）个。
(1)求解某一类问题的算法是唯一的;(2)算法必须在有限步操作后停止;(3)算法的每一步操作是明确的,不能有歧义或含义模糊;(4)算法执行后一定产生确定的结果。
7.( )是指算法执行时所需计算机资源的多少,包括运行时间和存储空间两个方面的要求。
A.正确性B.可读性C.效率D.健壮性8.对于简单的输入,输出和赋值语句,执行时间为（）。
(1) (n) (n*n) D.都不对9.算法点的空间复杂度是指（）。
A.算法在执行过程中所需的计算机存储空间B.算法所处理的数据量C.算法程序中的语句或指令的条数D.算法在执行过程中所需要的临时工作单元数10.算法点的时间复杂度是指（）。
A.算法的执行时间B.算法所处理的数据量C.算法程序中的语句或指令的条数D.算法在执行过程中所需要的基本运算次数11.下列哪一种算法不是随机化算法（）。
A.遗传算法B.模拟退火算法C.动态规划算法D.模特卡罗算法12.下面不是动态规划算法基本步骤的是（）。
A.找出最优解的性质B.构造最优解C.算出最优解D.定义最优解13.下列是动态规划算法基本要素的是（）。
A.定义最优解B.构造最优解C.算出最优解D.子问题重叠性质14.采用广度优先策略搜索的算法是（）。
