算法设计与分析期末成绩考核标准要求：算法设计与分析考试方式为小论文形式。
下面给出了小论文的参考模型和参考题目，供大家选择。
1.小作业题目（仅供参考）（题目的难易：●简单10道题★中等11道题▲复杂10道题）●最佳浏览路线问题问题描述：某旅游区的街道呈网格状，其中东西向的街道都是旅游街，南向的街道都是林荫道。
由于游客众多，旅游街被规定为单行道。
游客在旅游街上只能从西向东走，在林荫道上既可以由南向北走，也可以从北向南走。
阿隆想到这个旅游区游玩，他的好友阿福给了他一些建议，用分值表示所有旅游街相邻两个路口之间的道路浏览的必要程度，分值从-100到100的整数，所有林荫道不打分，所有分值不可能全是负值。
阿隆可以从任一路口开始浏览，在任一路口结束浏览，请写出一个算法，帮助阿隆寻找一条最佳的浏览路线，使得这条路线的所有分值总和最大。
（算法设计与分析第二版P190—11题）●问题描述：某工业生产部门根据国家计划的安排，拟将某种高效率的5台机器，分配给所属的，A，B，C个工厂，各工厂在获得这种机器后，可以为国家盈利如图表所示，问：这5台机器如何分配给各工厂，才能使得国家盈利最大？（P190-14题）●问题描述：编写算法对输入的一个整数，判断他能否被4，7，9整除，并输出一下信息之一，能同时被4，7，9整除;能被其中两个数（要指出那两个）整除能被其中一个数（要指出哪一个）整除不能被4，7，9任一个整除。
问咋样安排这6项加工任务的加工工序，使得加工工时最少？（P191-17）C的算法(P191-19).●问题描述：编写用动态规划法求组合数mn●问题描述：仿照分治算法中两个大数相乘的算法策略，完成求解两个n*n阶矩阵A和矩阵B的乘积的算法。
排序算法复杂性分析一健鹏明欢我们重承诺，本作业的容均为原创，没有任何抄袭他人成果的行为，也不存在他人代写作业和程序的行为。
引用他人成果或公开资料的部分都已经按照正确的格式在参考文献中标出。
作者签字得分统计学生填写老师填写学号工作所占比例得分分别得分健20131401鹏20131400明欢20130711摘要本文通过三种简单排序-插入、冒泡和选择排序算法并运用C++语言编程实现，以计算简单排序算法复杂度。
本文将围绕以下两个问题进行讨论分析:1）设计一个程序，程序的输入为n个（n必须要从键盘输入）0到10000的正整数（正整数可以是随机产生），输出为对这n个数进行从小到大排序后的序列。
排序方法分别使用插入排序、冒泡排序和选择排序。
一、算法复杂度1.1算法复杂性算法的复杂性是算法效率的度量，是评价算法优劣的重要依据。
一个算法的复杂性的高低体现在运行该算法所需要的计算机资源的多少上面，所需的资源越多，我们就说该算法的复杂性越高；反之，所需的资源越低，则该算法的复杂性越低。
《算法分析与设计》作业(一)本课程作业由两部分组成。
第一部分为”客观题部分”,由15个选择题组成,每题1分,共15分。
第二部分为”主观题部分”,由简答题和论述题组成,共15分。
作业总分30分,将作为平时成绩记入课程总成绩。
算法分析经典算法题第一章1.计算A+B的值：#includeintmain(){inta,b;cin>>a>>b;cout<
第二行输入n个整数。
输出最大值importjava.util.Scanner;publicclassMain{publicstaticvoidmain(String[]args)throwsException{Scannerinput=newScanner(System.in);intn=input.nextInt();intarr[]=newint[n];for(inti=0;i
网格点由整数坐标(x,y)表示。
士兵们可以沿网格边上、下、左、右移动一步，但在同一时刻任一网格点上只能有一名士兵。
按照军官的命令，士兵们要整齐地列成一个水平队列，即排列成(x,y),(x+1,y),…,(x+n-1,y)。
如何选择x和y的值才能使士兵们以最少的总移动步数排成一列。
计算使所有士兵排成一行需要的最少移动步数。
输入：第1行是士兵数n，1n10000。
接下来n行是士兵的初始位置，每行2个整数x和y，-10000《=x，y《=10000。
1.)(nT给定数组a[0:n-1],试设计一个算法,在最坏情况下用n+[logn]-2次比较找出a[0:n-1]中的元素的最大值和次大值.(算法分析与设计习题2.16)（分治法）a、算法思想用分治法求最大值和次大值首先将问题划分，即将划分成长度相等的两个序列，递归求出左边的最大值次大值，再求出右边的的最大值次大值，比较左右两边，最后得出问题的解。
//不知道为什么会-2！C、代码实现：#include
cmax=lcmax;}else{max=lmax;cmax=rmax;}elseif(rcmax>lmax){if(rmax==rcmax){max=rmax;cmax=lmax;}else{max=rmax;cmax=rcmax;}}。
最接近点对问题问题此问题分为一维，二维，三维的情况1.一维:给定直线上n个点，找其中一对点，使得在n个点组成的所有点对中，该点对间的距离最小，这个问题比较简单，是引出二维解法的一个引子，因为一维的直线上的点，相邻点的距离肯定小于相隔的点的距离，只需要考虑相邻点即可。
2.二维：给定平面上n个点，找其中一对点，使得在n个点组成的所有点对中，该点对间的距离最小，这是我们这一问题的重点3.三维：给定空间上n个点，找其中一对点，使得在n个点组成的所有点对中，该点对间的距离最小，此问题是二维的解法的复杂化，具体可以在飞机航线等问题上运用，但在此不多做介绍。
基本思想由于该问题的基本解法是去考察每个点和其他所有点的距离。
1.因二维的情况太过复杂，先考虑一维的情况中，可以用分治法对其进行分部计算：把直线分成两部分,1s2s,分别求出其最接近点的距离1d2d。
但分割开的地方的两点距离可能小于这两个值，这三个值进行比较之后，得到最后结果。
2.鉴于此，二维的也可以用此方法进行计算：把待计算的点s分成两部分1s2s，分别求出其最接近点的距离1d2d。
但1d2d最小的未必是s中的最小距离d，它有可能是1s中的一个点和2s中的一个点组成的最接近点对。
所以还要考虑1s中的所有点到2s中的每一个点的距离，一一比较之后得出一个最小值，再和1d2d比较，这就得出了最后结果。
3.接下来是具体算法实现的步骤：1.把待计算的点s分成两部分1s2s:重要的如何去划分，这里采用在二维平面上的中线（用横坐标的最小值加上最大值的平均数）来划分。
2.分别求出其最接近点的距离1d2d:这可以用一个递归来完成。
3.计算1s中的所有点到2s中的每一个点的距离：这个问题是此问题的关键。
冒泡排序：原理：将待排序的元素看作是竖着排列的“气泡”，较小的元素比较轻，从而要往上浮。
在冒泡排序算法中我们要对这个“气泡”序列处理若干遍。
所谓一遍处理，就是自底向上检查一遍这个序列，并时刻注意两个相邻的元素的顺序是否正确。
如果发现两个相邻元素的顺序不对，即“轻”的元素在下面，就交换它们的位置。
算法分析大作业动态规划方法解乘法表问题和汽车加油行驶问题目录1.动态规划解乘法表问题1.1问题描述------1.2算法设计思想------1.3设计方法------1.4源代码------1.5最终结果------2.动态规划解汽车加油行驶问题2.1问题描述------2.2算法设计思想------2.3设计方法------2.4源代码------2.5最终结果------3.总结1.动态规划解决乘法表问题1.1问题描述定义于字母表∑{a,b,c)上的乘法表如表所示：依此乘法表,对任一定义于∑上的字符串,适当加括号表达式后得到一个表达式。
例如,对于字符串x=bbbba,它的一个加括号表达式为(b(bb))(ba)。
依乘法表,该表达式的值为a。
试设计一个动态规划算法,对任一定义于∑上的字符串x=x1x2…xn，计算有多少种不同的加括号方式,使由x导出的加括号表达式的值为a。
1.2算法设计思想设常量a,b,c分别为1,2,3。
n为字符串的长度。
设字符串的第i到第j位乘积为a的加括号法有result[i][j][a]种，字符串的第i到第j位乘积为b的加括号法有result[i][j][b]种,字符串的第i到第j位乘积为c的加括号法有result[i][j][c]种。
则原问题的解是：result[i][n][a]。
设k为i到j中的某一个字符，则对于k从i到j：result[i][j][a]+=result[i][k][a]*result[k+1][j][c]+result[i][k][b]*result[k+1][j][c]+result[i][k][c]*result[k+1][j][a];result[i][j][b]+=result[i][k][a]*result[k+1][j][a]+result[i][k][a]*result[k+1][j][b]+result[i][k][b]*result[k+1][j][b];result[i][j][c]+=result[i][k][b]*result[k+1][j][a]+result[i][k][c]*result[k+1][j][b]+result[i][k][c]*result[k+1][j][c];输入：输入一个以a,b,c组成的任意一个字符串。
算法分析与设计作业一、冒泡排序1.1冒泡排序算法冒泡排序（BubbleSort）也称为沉底排序，算法的特点是从数组头部到尾部进行多次遍历，当遍历到一些数时，如果比它前面的数大就交换。
比较n个数大小，可以进行n-1次交换。
算法步骤如下：（1）比较相邻的元素，如果第一个比第二个大，就交换他们两个的位置；（2）对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后循环结束时，最大的数会移动到最后；（3）重复第一步，直到所有元素排序完成。
算法在每一轮排序后会判断是否有可以交换的数据，如果没有就表明已经全部排序完成，此时可以终止排序。
相比传统的算法，优化后的算法可以大大减少不必要的循环，提高排序的速度。
二、快速排序2.1快速排序算法快速排序（QuickSort）是一种分治策略，将大问题分解为小问题，同时在排序过程中不断的拆分问题，最终完成排序。
算法步骤如下：。
2、设计一个算法，用于在一个已排序的整数数组中查找特定元素。
3、比较贪心算法和动态规划算法的异同，并举例说明它们在实际问题中的应用。
参考答案一、冒泡排序算法的分析冒泡排序（BubbleSort）是一种简单的排序算法。
它重复地走访要排序的数列，一次比较两个数据元素，如果顺序不对则进行交换，并一直重复这样的走访操作，直到没有要交换的数据元素为止。
2、空间复杂度冒泡排序只在交换元素时使用了临时变量，空间复杂度为O(1)，是一个原地排序算法。
3、性能分析性能较好的情况：当数组规模较小且接近有序时，冒泡排序的性能相对较好。
因为在这种情况下，比较和交换的次数相对较少。
性能较差的情况：当数组规模较大且无序程度较高时，冒泡排序的性能会非常差。
例如，对于数组2,1,3,5,4，冒泡排序需要经过多次比较和交换才能将其排序为1,2,3,4,5。
而对于已经有序的数组1,2,3,4,5，冒泡排序只需要进行较少的比较操作就能确定数组已经有序。
二、在已排序数组中查找特定元素的算法设计对于在已排序的整数数组中查找特定元素，我们可以使用二分查找（BinarySearch）算法。
二分查找的基本思想是：将数组从中间分成两部分，比较目标元素与中间元素的大小，如果目标元素小于中间元素，则在左半部分继续查找；如果目标元素大于中间元素，则在右半部分继续查找；如果目标元素等于中间元素，则查找成功。
算法分析练习题（一）一、选择题1、二分搜索算法是利用（A）实现的算法。
A、分治策略B、动态规划法C、贪心法D、回溯法2、下列不是动态规划算法基本步骤的是（A）。
A、找出最优解的性质B、构造最优解C、算出最优解D、定义最优解3．下列算法中通常以自底向上的方式求解最优解的是（B）。
A、备忘录法B、动态规划法C、贪心法D、回溯法4、衡量一个算法好坏的标准是（C）。
A棋盘覆盖问题B选择问题C归并排序D0/1背包问题6.实现循环赛日程表利用的算法是（A）。
A、分治策略B、动态规划法C、贪心法D、回溯法7.备忘录方法是那种算法的变形。
（B）A、分治法B、动态规划法C、贪心法D、回溯法8．最长公共子序列算法利用的算法是（B）。
A、分支界限法B、动态规划法C、贪心法D、回溯法9．实现棋盘覆盖算法利用的算法是（A）。
A、分治法B、动态规划法C、贪心法D、回溯法10.矩阵连乘问题的算法可由（B）设计实现。
A、分支界限算法B、动态规划算法C、贪心算法D、回溯算法11、Strassen矩阵乘法是利用（A）实现的算法。
A、分治策略B、动态规划法C、贪心法D、回溯法12、使用分治法求解不需要满足的条件是（A）。
A子问题必须是一样的B子问题不能够重复C子问题的解可以合并D原问题和子问题使用相同的方法解13、下列算法中不能解决0/1背包问题的是（A）A贪心法B动态规划C回溯法D分支限界法14．实现合并排序利用的算法是（A）。
A、分治策略B、动态规划法C、贪心法D、回溯法15．下列是动态规划算法基本要素的是（D）。
A、定义最优解B、构造最优解C、算出最优解D、子问题重叠性质16．下列算法中通常以自底向下的方式求解最优解的是（B）。
算法分析期末试题集答案1.应Johnson法则的流作业调度采的算法是（D）A.贪算法B.分限界法C.分治法D.动态规划算法2.Hanoi塔问题如下图所。
现要求将塔座A上的的所有圆盘移到塔座B上，并仍按同样顺序叠置。
移动圆盘时遵守Hanoi塔问题的移动规则。
由此设计出解Hanoi塔问题的递归算法正确的为：（B）Hanoi塔3.动态规划算法的基本要素为（C）A.最优结构性质与贪选择性质B．重叠问题性质与贪选择性质C．最优结构性质与重叠问题性质D.预排序与递归调4.算法分析中，记号O表（B），记号Ω表（A），记号Θ表（D）。
A.渐进下界B.渐进上界C.紧上界D.紧渐进界E.紧下界5.以下关于渐进记号的性质是正确的有：（A）A.f(n)(g(n)),g(n)(h(n))f(n)(h(n))=Θ=Θ=ΘB.f(n)O(g(n)),g(n)O(h(n))h(n)O(f(n))===C.O(f(n))+O(g(n))=O(min{f(n),g(n)})D.f(n)O(g(n))g(n)O(f(n))==6.能采贪算法求最优解的问题，般具有的重要性质为：（A）A.最优结构性质与贪选择性质B．重叠问题性质与贪选择性质C．最优结构性质与重叠问题性质D.预排序与递归调7.回溯法在问题的解空间树中，按（D）策略，从根结点出发搜索解空间树。
A．度优先B.活结点优先C.扩展结点优先D.深度优先8.分限界法在问题的解空间树中，按（A）策略，从根结点出发搜索解空间树。
A．度优先B.活结点优先C.扩展结点优先D.深度优先9.程序块（A）是回溯法中遍历排列树的算法框架程序。
《算法分析与设计》一、解答题1.机器调度问题。
问题描述：现在有n件任务和无限多台的机器，任务可以在机器上得到处理。
例如：区间[1，4]与区间[2，4]重叠，而与[4，7]不重叠。
一个可行的任务分配是指在分配中没有两件重叠的任务分配给同一台机器。
因此，在可行的分配中每台机器在任何时刻最多只处理一个任务。
最优分配是指使用的机器最少的可行分配方案。
2.已知非齐次递归方程：f(n)bf(n1)g(n)f(0)c=-+=，其中，b、c是常数，g(n)是n的某一个函数。
则f(n)的非递归表达式为：nnnii1f(n)cbbg(i)-==+∑。
现有Hanoi塔问题的递归方程为：h(n)2h(n1)1h(1)1=-+=，求h(n)的非递归表达式。
解：利用给出的关系式，此时有：b=2,c=1,g(n)=1,从n递推到1，有：n1n1n1ii1n1n22nh(n)cbbg(i)22(22121)----=--=+=+++++=-∑3.单源最短路径的求解。
问题的描述：给定带权有向图（如下图所示）G=(V,E)，其中每条边的权是非负实数。
另外，还给定V中的一个顶点，称为源。
现在要计算从源到所有其它各顶点的最短路长度。
这里路的长度是指路上各边权之和。
这个问题通常称为单源最短路径问题。
解法：现采用Dijkstra算法计算从源顶点1到其它顶点间最短路径。
排序算法总结一、各种排序算法及程序清单插入排序(Insert_Sort)1.基本思想：每次将一个待排序的数据元素，插入到前面已经排好序的数列中的适当位置，使数列依然有序；直到待排序数据元素全部插入完为止。
2.程序清单：#include
2.程序清单：#include 哈算法分析作业Byyejinru1.给定个数组A，任务是设计个算法求得数组中的“主元素”，即在数组中个数超过数组总元素个数半的元素。 因此我们：b)递归查找两部分T1,T2的主元素m1,m2，如果：1.m1跟m2相同，则m1即为该部分的主元素。 2.否则：遍历遍T1和T2组成的部分，判断主元素是m1还是m2。 c)递归结束返回该部分的主元素。 B.O(n)算法：参考编程之美书上的算法。 我们同时删除两个不同的元素，不会改变剩下元素中的主元素。 因此我们可以每次删除两个不同的元素，直到不能删除为，剩下的元素即为主元素。 2.令I1,…,In是n个区间，其中任区间Ii=(ai,bi)，假设这些区间按照bi从到排序，每个区间有个权重vi,考虑如下两个问题：区间安排问题P1:找到最数量互不相交的区间，例如，对于四个区间I1=(1,2);I2=(2,3);I3=(1,4);I4=(4,5)，个解是{I1,I2,I4}加权任务安排问题P2:找个互不相交区间的集合，使得这些区间的权重之和最，例如I1=(1,2),v1=0.9;I2=(2,3),v2=0.5;I3=(1,4),v3=4;I4=(4,5),v4=2，解是{I3,I4}。 A、分治法B、动态规划法C、贪心法D、回溯法17、合并排序算法是利用（A）实现的算法。 A、分治策略B、动态规划法C、贪心法D、回溯法18．实现大整数的乘法是利用的算法（C）。 A、贪心法B、动态规划法C、分治策略D、回溯法19.实现最大子段和利用的算法是（B）。 A、分治策略B、动态规划法C、贪心法D、回溯法20.一个问题可用动态规划算法或贪心算法求解的关键特征是问题的（B）。 A、重叠子问题B、最优子结构性质C、贪心选择性质D、定义最优解21.实现最长公共子序列利用的算法是（B）。 2、程序是算法用某种程序设计语言的具体实现。 3、算法的“确定性”指的是组成算法的每条指令是清晰的，无歧义的。 4.矩阵连乘问题的算法可由动态规划设计实现。 5、算法是指解决问题的一种方法或一个过程。 6、从分治法的一般设计模式可以看出，用它设计出的程序一般是递归算法。 7、矩阵连乘问题的算法可由动态规划设计实现。 8.动态规划算法的基本思想是将待求解问题分解成若干子问题，先求解子问题，然后从这些子问题的解得到原问题的解。 9.算法是由若干条指令组成的有穷序列，且要满足输入、输出、确定性和有限性四条性质。 10、大整数乘积算法是用分治法来设计的。 11.快速排序算法是基于分治策略的一种排序算法。 12.动态规划算法的两个基本要素是.性质和性质。 14.快速排序算法的性能取决于划分的对称性。 15、出自于“平衡子问题”的思想，通常分治法在分割原问题，形成若干子问题时，这些子问题的规模都大致相同。 18、动态规划算法有一个变形方法备忘录方法。 这种方法不同于动态规划算法“自底向上”的填充方向，而是“自顶向下”的递归方向，为每个解过的子问题建立了备忘录以备需要时查看，同样也可避免相同子问题的重复求解。 22、直接或间接地调用自身的算法称为（递归算法）。 23、θ记号在算法复杂性的表示法中表示（渐进确界或紧致界）。 24、在分治法中，使子问题规模大致相等的做法是出自一种（平衡子问题）的思想。 25、动态规划算法适用于解（具有某种最优性质）问题。 26、最优子结构性质的含义是（问题的最优解包含其子问题的最优解）。 27、按照符号O的定义O(f)+O(g)等于O(max{f(n),g(n)})。 28、二分搜索技术是运用（分治）策略的典型例子。 29、动态规划算法中，通常不同子问题的个数随问题规模呈（多项式）级增长。 30、（最优子结构性质）和（子问题重叠性质）是采用动态规划算法的两个基本要素。 三、算法填空1.最大子段和:动态规划算法intMaxSum(intn,inta[]){intsum=0,b=0；//sum存储当前最大的b[j],b存储b[j]for(intj=1；j<=n；j++){if（b>0）b+=a[j]；elseb=a[i]；//一旦某个区段和为负，则从下一个位置累和if(b>sum)sum=b；}returnsum；}2.快速排序template 最优子结构性质是指大问题的最优解包含子问题的最优解。 动态规划方法是自底向上计算各个子问题的最优解，即先计算子问题的最优解，然后再利用子问题的最优解构造大问题的最优解，因此需要最优子结构4、设计动态规划算法的主要步骤是怎么的？请简述。 参考解答：（1）找出最优解的性质，并刻划其结构特征。 (6分)（2）递归地定义最优值。 （3）以自底向上的方式计算出最优值。 （4）根据计算最优值时得到的信息，构造最优解。 5、分治法所能解决的问题一般具有哪几个特征？请简述。 参考解答：（1）该问题的规模缩小到一定的程度就可以容易地解决；(6分)（2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质;（3）利用该问题分解出的子问题的解可以合并为该问题的解；（4）原问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。 6、算法的要特性是什么？参考解答：确定性、可实现性、输入、输出、有穷性7、算法分析的目的是什么？参考解答：分析算法占用计算机资源的情况，对算法做出比较和评价，设计出额更好的算法。 11快速排序算法最坏情况下需要多少次比较运算？参考解答：最坏情况下快速排序退化成冒泡排序，需要比较n2次。 12阐述归并排序的分治思路。 参考解答：讲数组一分为二，分别对每个集合单独排序，然后将已排序的两个序列归并成一个含n个元素的分好类的序列。 如果分割后子问题还很大，则继续分治，直到一个元素。 13快速排序的基本思想是什么。 参考解答：快速排序的基本思想是在待排序的N个记录中任意取一个记录，把该记录放在最终位置后，数据序列被此记录分成两部分。 所有关键字比该记录关键字小的放在前一部分，所有比它大的放置在后一部分，并把该记录排在这两部分的中间，这个过程称作一次快速排序。 之后重复上述过程，直到每一部分内只有一个记录为止。 14分治法的基本思想是什么？将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。 求出子问题的解，就可得到原问题的解。 即一种分目标完成程序算法，简单问题可用二分法完成。 15设计动态规划算法的主要步骤？参考解答：（1）找出最优解的性质，并刻划其结构特征。 16分治法与动态规划法的异同共同点：将待求解的问题分解成若干子问题，先求解子问题，然后再从这些子问题的解得到原问题的解。 不同点：1、适合于用动态规划法求解的问题，分解得到的各子问题往往不是相互独立的；而分治法中子问题相互独立。 17分治法所能解决的问题一般具有的几个特征？参考解答：（1）该问题的规模缩小到一定的程度就可以容易地解决；(6分)（2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质;（3）利用该问题分解出的子问题的解可以合并为该问题的解；（4）原问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。