算法作业和期末复习题

1．给出递推公式x(n)=x(n-1)+n,x(0)=0对应的通项公式计算过程？解： X(n)-X(n-1)=nX(n-1)-X(n-2)=n-1…………X(1)-X(0)=1X(n)-X(0)=(n+1)n\2X(n)= (n+1)n\22．O、Θ、Ω之间的区别与联系O描述增长率的上限上限值越低，结果越有价值。

Θ用来表示算法的精确阶Ω描述增长率的下限下限值越高越有价值。

联系：只要当考察问题规模充分大时，算法中基本语句的执行次数在渐近意义下的阶，通常使用3种等渐近符号。

3．什么是数据结构，什么是算法，两者有什么关系？数据结构：是指相互之间存在一定关系的数据元素的集合。

算法：是对特定问题求解步骤的一种描述是指令的有限序列。

程序=算法+数据结构5．举例说明分治法、动态规划法和贪心法适用范围，及三者之间的区别。

答：分治法：适用于原问题可划分为子问题时如汉诺塔问题（循环赛，最近对，棋盘覆盖等）动态规划：当原问题可分解为子问题并且问题重叠并且具有最优子结构时可用动态规划法，如TSP问题（多端最短路径问题，0/1背包问题等）贪心：当一个问题具有最优子结构性质且具有贪心选择性时可用贪心算法，如最小生成树问题（背包问题，活动安排问题等）在分治法的基础上，满足最优子结构性质才能用动态规划，在动态规划可行的基础上满足贪心选择性才能用贪心。

6．简述分治法、贪心法、蛮力法、回溯法、减治法的设计思想。

分治：建一个难以直接解决的大问题划分成一些规模较小的子问题，以便各个击破，分而治之。

贪心把一个问题分解为一系列较简单的局部最优选择，每一步选择都是对当前解的一个扩展，直到获得问题的完整解。

（指根据当前已有信息做出选择，不从整体最优考虑，只选择局部最优蛮力：采用一定的策略将待求解问题的所有元素依次处理一次，从而找出问题的解。

回溯：只构造可能解的一部分，然后评估这个部分解，如果这个部分解有可能导致一个完全解，则对其进一步构造，否则，就不必继续构造这个解了。

减治：把一个大问题划分为若干子问题，但些子问题不需要分别求解，只需求解其中那个一个子问题。

7．举例说明分治法和减治法的在设计上区别与联系。

分治法是将一个大问题分解为若干子问题分别求解，而减治法是只求解部分子问题。

在排序问题中，分治法用用快速排序，以轴值为基准划分序列，再求每个子集递归序列，最后合并并操作。

减治法则用选择问题算法，先选定轴值并划分，比轴值小的在左侧，比轴值大的在右侧，选择问题的查找区间减少一半，划分后只需处理一个子序列。

8．简述什么是欧拉回路，TSP问题，哈密顿回路问题。

欧拉回路：图G的一个回路，若它恰它通过G 中每条边一次，则称该回路为欧拉回路。

TSP：从图的一个顶点出发，各个定点只能经历并访问一次，最后回到原点且使路径最短。

哈密顿回路：从一个城市出发，经过每一个城市恰好一次，然后回到出发城市。

1．给出应用动态规划法设计算法的一般步骤，并用动态规划法求下面多段图中从顶点0到顶点15的最短路径，写出求解过程。

解：d(0,9)=min{c01 +d(1,9) , c02+d(2,9) , c03 +d(3,9)}d(1,9)=min{c14 +d(4,9) , c15+d(5,9) }d(2,9)=min{c24 +d(4,9) , c25+d(5,9) , c26 +d(6,9)}d(3,9)=min{c35 +d(5,9) , c36+d(6,9) }d(4,9)=min{c47 +d(7,9) , c48+d(8,9) }d(5,9)=min{c57 +d(7,9) , c58+d(8,9) }d(0,9)=min{c67 +d(7,9) , c68+d(8,9) }d(7,9)= c79 =7 (7→9)d(8,9)= c89 =3(8→9)d(6,9)=min{6+7,5+3}=8(6→8)d(5,9)= min{8+7,6+3}=9(5→8)d(4,9)= min{5+7,6+3}=9(4→8)d(3,9)=min{4+9,7+8}=13(3→5)d(2,9)=min{6+9,7+9,8+8}=15(2→4)d(1,9)=min{9+9,8+9}=17(1→5)d(0,9)=min{4+17,2+15,3+13}=16(0→3)最后得最短路径为0→3→5→8→9 长度为16。

2．有4个物品，其重量分别为(4, 7, 5, 3)，物品的价值分别为(40, 42, 25, 12)，背包容量为10。

试设计3种贪心策略,并给出在每种贪心策略下背包问题的解。

重量最轻：装入143.总价值：40+12+25*3/5=67价值最大：装入1，2。

总价值：40*3/4+42=72性价比最小：装入1，2.总价值：40+6/7*42=763．给出{23 13 49 6 31 19 28}采用快速排序思想进行排序时一次划分的过程示意图。

19 13 49 6 31 23 2819 13 23 6 31 49 2819 13 6 23 31 49 281．给定数组A[n]，存储n个实数，试设计一个算法，在最坏情况下用最少比较次数找出该数组中元素的最大值和最小值，并说明采用了何种算法设计思想，其最坏比较多少次。

求数组的最大值和最小值a)问题求给定数组a[0:n-1]的最大值和最小值。

要求：最坏情况下用3n/2-2次比较b)分析分治法，把数组分成n/2组，每组2个数。

然后每组的两个数进行一次比较，确定出每组的最大数和最小数保存在数组MAX[i]和MIN[i]中，这样总共进行了n/2次比较。

最后从MAX[i]中找出最大的数MAX，从MIN[i]中找出最小的数MIN，需要2*（n/2-1）次比较。

MAX和MIN就是原来问题的解。

总比较次数为3n/2 – 2次该算法在任何情况下进行的比较次数都是3n/2 – 2,固最差情况也是3n/2 –2.c)编程实现Quoted from 求数组的最大值和最小值://two15.java//该算法在任何情况下的比较次数都是3N/2 -2。

所以在最差情况下也是3N/2 -2 import ;public class two15{public static void main(String args[]){int a[]=new int[50];//int min[]=new int[25];//int max[]=new int[25];//int n=0,i=0,k=1;String num;String aa[]=new String[50];num=JOptionPane.showInputDialog("enter the total num of the array");n=Integer.parseInt(num);//单个数不进行比较if(n!=1){for(i=0;i<n;i++){aa[i]=JOptionPane.showInputDialog("请输入数组的每个元素");a[i]=Integer.parseInt(aa[i]); }//用分治法把N个数分成2/N组每组两个进行比较，把小的放在MIN，大的放在MAX//最差情况下比较N/2次for(i=1;i<(n/2)*2;i=i+2){ if(a[i-1]<=a[i]){ min[k-1]=a[i-1];max[k-1]=a[i];k++;}else{min[k-1]=a[i];max[k-1]=a[i-1];k++;}}/*在MAX中找出最大的，在MIN中找出最小的*最差情况下比较2*（N/2-1）次*/int maxm=max[0], minm=min[0];for(k=1;k<n/2;k++){ if(max[k]>maxm) maxm=max[k];if(min[k]<minm) minm=min[k];}if(n%2!=0)//N为奇数时，还要和最后一个数比较{if(a[n-1]>maxm) maxm=a[n-1];if(a[n-1]<minm) minm=a[n-1]; }JOptionPane.showMessageDialog(null,"最大的数是"+maxm+"最小的数是"+minm,"result",RMATION_MESSAGE); } else JOptionPane.showMessageDialog(null,"一个数无须查找","警告！",RMATION_MESSAGE); }}2．描述贪心法的求解过程，给出基于最近邻点策略采用贪心法求解TSP问题伪代码，并分析该算法的时间性能。

伪代码：1.P={}; 2.V=V-{u0};u=u0;//从顶点u0出发； 3循环直到集合P 中包含n-1条边 3.1查找与顶点u邻接的最小代价边（u，v）并且v 属于集合V ；3.2 P=P+{（u， v）}；3.3 V=V—{v}； 3.4 u=v； //从顶点v出发继续求解3．设计算法实现求数组中相差最小的两个元素（称为最接近数）的差。

算法 MinDistance(A[0..n-1])//输入:数组A[0..n-1]//输出:the smallest distance d between two of its elements算法4.10——最近对问题int ClosestPoints(S) //S为平面上n个点的坐标组成的集合{ 1．if (n<2) return ∞;2．m=S中各点x坐标的中位数；3．构造S1和S2，使得S1中点的x坐标小于m，S2中点的x坐标大于m；4．d1=ClosestPoints(S1); d2=ClosestPoints(S2);5．d=min(d1, d2);6．构造P1和P2，使得P1是S1中点的x坐标与m的距离小于d的点集，P2是S2中点的x坐标与m的距离小于d的点集;7．将P1和P2中的点按y坐标升序排列；8．对P1中的每一个点p，在P2中查找与点p的y坐标小于d的点，并求出其中的最小距离d'；9．return min(d, d' )；}4．有n枚硬币，其中有一枚硬币是假币，且假币的重量较轻，通过一架天平找出假币，。

比较次数最少。

答：减治算法。

先把n枚硬币分成两组，每组有[2/n]枚硬币，如果n为奇数就留下一枚硬币，然后把两组硬币分别放到天平的两端。

如果两组硬币重量相同，那么留下的硬币就是假币；否则，用同样的方法对较轻的那组硬币进行同样处理，应为假币一定在较轻的那组里.#include <iostream>#include <cstdlib>using namespace std;int Check_out(int B[],int n);int main(){ int n,n1;cout<<"注意：\n"<<"真硬币用1表示，假硬币用0或2表示.\n";cout<<" 0表示假硬币比真硬币轻,2表示假硬币比真硬币重。