下载文档原格式
算法分析与设计（答案）一：二分查找的递归实现算法import java.util.Arrays;import java.util.Scanner;public class BinSearch {public static int binsearch(int []a,int start,int stop,int b) {if(start>stop)return -1;int i=(start+stop)/2;if(a[i]==b)return i;if(a[i]>b)return binsearch(a,start,i-1,b);return binsearch(a,i+1,stop,b);}/***@param args*/public static void main(String[] args) {// TODO Auto-generated method stubScanner sc=new Scanner(System.in);System.out.println("输入数组长度");int n=sc.nextInt();int a[]=new int [n];System.out.println("输入数组元素");for(int i=0;i<n;i++){a[i]=sc.nextInt();}Arrays.sort(a);System.out.println("排序后的数组为");for(int i=0;i<a.length;i++){System.out.print(a[i]+" ");}System.out.println();System.out.println("输入要查找的数");int b=sc.nextInt();int x=binsearch(a,0,n-1,b);if(x==-1){System.out.println(b+"不在数组中，请输入另一个数");b=sc.nextInt();x=binsearch(a,0,n-1,b);}System.out.println(b+"在数组中的第"+(x+1)+"个位置");}}二：Ackerman函数的递归实现算法//Ackerman函数import java.util.Scanner;public class L {private static int Ackerman(int n,int m){int a,b;if(n==1&&m==0)a=2;else if(n==0&&m>=0)a=1;else if(m==1)a=n*2;else if(m==2)a=(int)Math.pow(2, n);else if(m==0&&n>=2)a=n+2;else {b=Ackerman(n-1,m);a=Ackerman(b,m-1);}return a;}public static void main(String[] args){Scanner sc=new Scanner(System.in);System.out.println("请先输入1个大于等于0的整数：");int N1=sc.nextInt();System.out.println("请再输入1个大于等于0的整数求Ackerman函数的递归：");int N2=sc.nextInt();System.out.println("Ackerman的值是"+Ackerman(N1,N2));}}三：全排列的递归实现算法import java.util.Scanner;public class AllSort{//全排列public static void main(String[] args) {Scanner sc=new Scanner(System.in);System.out.println("输入需要全排列的元素个数");int n=(char) sc.nextInt();int buf[]=new int [n];System.out.println("请依次输入每一个元素");for(int i=0;i<n;i++){buf[i]=sc.nextInt();}perm(buf,0,buf.length-1);}public static void perm(int[] buf,int start,int end){if(start==end){//当只要求对数组中一个元素进行全排列时，只要就按该数组输出即可（特殊情况）for(int i=0;i<=end;i++){System.out.print(buf[i]);}System.out.println();}else{//多个字母全排列（普遍情况）for(int i=start;i<=end;i++){//（让指针start分别指向每一个数） int temp=buf[start];//交换数组第一个元素与后续的元素buf[start]=buf[i];buf[i]=temp;perm(buf,start+1,end);//后续元素递归全排列temp=buf[start];//将交换后的数组还原buf[start]=buf[i];buf[i]=temp;}}}}四：快速排序的递归实现算法import java.util.Scanner;public class QuickSort {public static int []a;public static void quicksort(int p,int r){if(p<r){int q=partition(p,r);quicksort(p,q-1);quicksort(q+1,r);}}public static int partition(int p,int r){int i=p,j=r+1;int x=a[p];while(true){while(a[++i]<x&&i<r);while(a[--j]>x);if(i>=j)break;int temp=a[i];a[i]=a[j];a[j]=temp;}a[p]=a[j];a[j]=x;return j;}/***@param args*/public static void main(String[] args) { // TODO Auto-generated method stubScanner sc=new Scanner(System.in);System.out.println("输入要排序的数组长度");int n=sc.nextInt();a=new int[n];System.out.println("输入"+n+"个元素");for(int i=0;i<n;i++)a[i]=sc.nextInt();quicksort(0,n-1);System.out.println("排序后的数组为");for(int j=0;j<a.length;j++)System.out.print(a[j]+" ");}}五：整数划分的递归实现算法import java.io.IOException;import java.util.*;public class ZhengshuHuafen {public static int a=0 ;public static int Devide(int input, int base, int []pData, int index){ if(input<1||base<1)return 0;if(input==1||base==1){if(input==1){pData[index] = input;print(pData, index+1);}else{for(int k=0; k<input; k++){pData[index++] = base;}print(pData,index);}return 1;}if(input==base){pData[index] = base;print(pData,index+1);int temp = Devide(input,base-1,pData,index);return 1 + temp;}if(input<base){int temp = Devide(input,input,pData,index);return temp;}else{pData[index] = base;int temp1 = Devide(input-base,base,pData,index+1); int temp2 = Devide(input,base-1,pData,index);return temp1 + temp2;}}public static void print(int []pData ,int index){String s = new String();for(int i = 0 ; i < index - 1 ; i++){System.out.print(pData[i]+"+");s += String.valueOf(pData[i]);s += "+"; }System.out.println(pData[index-1]);s += String.valueOf(pData[index-1]) +"\r\n";}public static void main(String[] args) {int n ;Scanner in = new Scanner(System.in) ;System.out.print("请输入一个整数") ;n = in.nextInt() ;System.out.println("你刚才输入的数为"+n) ;int []pdata = new int[n] ;a=Devide(n, n, pdata, 0) ;System.out.println(""+a) ;}}//请输入一个整数100//你刚才输入的数为100//190569292六：合并排序的递归实现算法import java.util.Scanner;public class mergeSort {public static int []b;public static void mergeSort1(int []a,int left,int right) {if(left<right){int i=(left+right)/2;mergeSort1(a,left,i);mergeSort1(a,i+1,right);merge(a,b,left,i,right);copy(a,b,left,right);}}public static void merge(int []c,int []d,int l,int m,int r) {int i=l;int j=m+1;int k=l;while((i<=m)&&(j<=r))if(c[i]<=c[j])d[k++]=c[i++];else d[k++]=c[j++];if(i>m)for(int q=j;q<=r;q++)d[k++]=c[q];elsefor(int q=i;q<=m;q++)d[k++]=c[q];}public static void copy (int []c,int []b,int left,int right) {for(int i=left;i<=right;i++){c[i]=b[i];}}public static void main(String[]args) {Scanner sc=new Scanner(System.in);int n=sc.nextInt();b=new int[n];int []a;a=new int [n];for(int i=0;i<n;i++){a[i]=sc.nextInt();}mergeSort.mergeSort1(a,0,n-1);for(int j=0;j<=n-1;j++)System.out.print(a[j]+" ");}}结果。
算法设计与分析基础习题1.15..证明等式gcd(m,n)=gcd(n,m mod n)对每一对正整数m,n都成立.Hint:根据除法的定义不难证明:●如果d整除u和v, 那么d一定能整除u±v;●如果d整除u,那么d也能够整除u的任何整数倍ku.对于任意一对正整数m,n,若d能整除m和n,那么d一定能整除n和r=m mod n=m-qn；显然，若d能整除n和r，也一定能整除m=r+qn和n。
数对(m,n)和(n,r)具有相同的公约数的有限非空集，其中也包括了最大公约数。
故gcd(m,n)=gcd(n,r)6.对于第一个数小于第二个数的一对数字,欧几里得算法将会如何处理?该算法在处理这种输入的过程中,上述情况最多会发生几次?Hint:对于任何形如0<=m<n的一对数字,Euclid算法在第一次叠代时交换m和n, 即gcd(m,n)=gcd(n,m)并且这种交换处理只发生一次.7.a.对于所有1≤m,n≤10的输入, Euclid算法最少要做几次除法?(1次)b. 对于所有1≤m,n≤10的输入, Euclid算法最多要做几次除法?(5次)gcd(5,8)习题1.21.(农夫过河)P—农夫W—狼G—山羊C—白菜2.(过桥问题)1,2,5,10---分别代表4个人, f—手电筒4. 对于任意实系数a,b,c, 某个算法能求方程ax^2+bx+c=0的实根,写出上述算法的伪代码(可以假设sqrt(x)是求平方根的函数)算法Quadratic(a,b,c)//求方程ax^2+bx+c=0的实根的算法//输入:实系数a,b,c//输出:实根或者无解信息If a≠0D←b*b-4*a*cIf D>0temp←2*ax1←(-b+sqrt(D))/tempx2←(-b-sqrt(D))/tempreturn x1,x2else if D=0 return –b/(2*a)else return “no real roots”else //a=0if b≠0 return –c/belse //a=b=0if c=0 return “no real numbers”else return “no real roots”5.描述将十进制整数表达为二进制整数的标准算法a.用文字描述b.用伪代码描述解答：a.将十进制整数转换为二进制整数的算法输入：一个正整数n输出：正整数n相应的二进制数第一步：用n除以2，余数赋给Ki(i=0,1,2...)，商赋给n第二步：如果n=0，则到第三步，否则重复第一步第三步：将Ki按照i从高到低的顺序输出b.伪代码算法DectoBin(n)//将十进制整数n转换为二进制整数的算法//输入：正整数n//输出：该正整数相应的二进制数，该数存放于数组Bin[1...n]中i=1while n!=0 do {Bin[i]=n%2;n=(int)n/2;i++;}while i!=0 do{print Bin[i];i--;}9.考虑下面这个算法,它求的是数组中大小相差最小的两个元素的差.(算法略) 对这个算法做尽可能多的改进.算法MinDistance(A[0..n-1])//输入:数组A[0..n-1]//输出:the smallest distance d between two of its elements习题1.31.考虑这样一个排序算法,该算法对于待排序的数组中的每一个元素,计算比它小的元素个数,然后利用这个信息,将各个元素放到有序数组的相应位置上去.a.应用该算法对列表‖60,35,81,98,14,47‖排序b.该算法稳定吗?c.该算法在位吗?解:a. 该算法对列表‖60,35,81,98,14,47‖排序的过程如下所示:b.该算法不稳定.比如对列表‖2,2*‖排序c.该算法不在位.额外空间for S and Count[] 4.(古老的七桥问题)习题1.41.请分别描述一下应该如何实现下列对数组的操作,使得操作时间不依赖数组的长度. a.删除数组的第i 个元素(1<=i<=n)b.删除有序数组的第i 个元素(依然有序) hints:a. Replace the i th element with the last element and decrease the array size of 1b. Replace the ith element with a special symbol that cannot be a value of the array ’s element(e.g., 0 for an array of positive numbers ) to mark the i th position is empty. (―lazy deletion ‖)第2章 习题2.17.对下列断言进行证明:(如果是错误的,请举例) a. 如果t(n )∈O(g(n),则g(n)∈Ω(t(n)) b.α>0时,Θ(αg(n))= Θ(g(n)) 解:a. 这个断言是正确的。
院系：计算机科学学院专业：年级：课程名称：算法设计与分析基础班号：组号：指导教师：年月日实验结果及分析1.求最大数2.递归法与迭代法性能比较递归迭代3.改进算法1.利用公式法对第n项Fibonacci数求解时可能会得出错误结果。
主要原因是由于double类型的精度还不够，所以程序算出来的结果会有误差，要把公式展开计算。
2.由于递归调用栈是一个费时的过程，通过递归法和迭代法的比较表明，虽然递归算法的代码更精简更有可读性，但是执行速度无法满足大数问题的求解。
3.在当前计算机的空间较大的情况下，在一些速度较慢的问题中，空间换时间是一个比较周全的策略。
实验原理（算法基本思想）定义：若A=(a ij), B=(b ij)是n×n的方阵，则对i,j=1,2,…n，定义乘积C=A⋅B 中的元素c ij为：1.分块解法通常的做法是将矩阵进行分块相乘，如下图所示：二．Strassen解法分治法思想将问题实例划分为同一问题的几个较小的实例。
对这些较小实例求解，通常使用递归方法，但在问题规模足够小时，也会使用另一种算法。
如果有必要，合并这些问题的解，以得到原始问题的解。
求解矩阵相乘的DAC算法，使用了strassen算法。
DAC（A[]，B[]，n）{If n=2 使用7次乘法的方法求得解ElseDivide（A）//把A分成4块Divide（B）//把B分成4块调用7次strassen算法求得解的4块合并这4块得到解并返回}伪代码Serial_StrassenMultiply(A, B, C) {T1 = A0 + A3;T2 = B0 + B3;StrassenMultiply(T1, T2, M1);T1 = A2 + A3;StrassenMultiply(T1, B0, M2);T1 = (B1 - B3);StrassenMultiply (A0, T1, M3);T1 = B2 - B0;StrassenMultiply(A3, T1, M4);T1 = A0 + A1;StrassenMultiply(T1, B3, M5);T1 = A2 – A0;T2 = B0 + B1;StrassenMultiply(T1, T2, M6);T1 = A1 – A3;T2 = B2 + B3;StrassenMultiply(T1, T2, M7);C0 = M1 + M4 - M5 + M7C1 = M3 + M5C2 = M2 + M4C3 = M1 - M2 + M3 + M6}实验结果及分析时间复杂度1.分块相乘总共用了8次乘法，因而需要Θ(n log28)即Θ(n3)的时间复杂度。
《算法及其分析》课后选择题答案及详解第1 章——概论1.下列关于算法的说法中正确的有（）。
Ⅰ.求解某一类问题的算法是唯一的Ⅱ.算法必须在有限步操作之后停止Ⅲ.算法的每一步操作必须是明确的，不能有歧义或含义模糊Ⅳ.算法执行后一定产生确定的结果A.1个B.2个C.3个D.4个2.T(n)表示当输入规模为n时的算法效率，以下算法效率最优的是（）。
A.T(n)=T(n-1)+1，T(1)=1B.T(n)=2nC.T(n)= T(n/2)+1，T(1)=1D.T(n)=3nlog2n答案解析：1.答：由于算法具有有穷性、确定性和输出性，因而Ⅱ、Ⅲ、Ⅳ正确，而解决某一类问题的算法不一定是唯一的。
答案为C。
2.答：选项A的时间复杂度为O(n)。
选项B的时间复杂度为O(n)。
选项C 的时间复杂度为O(log2n)。
选项D的时间复杂度为O(nlog2n)。
答案为C。
第3 章─分治法1.分治法的设计思想是将一个难以直接解决的大问题分割成规模较小的子问题，分别解决子问题，最后将子问题的解组合起来形成原问题的解。
这要求原问题和子问题（）。
A.问题规模相同，问题性质相同B.问题规模相同，问题性质不同C.问题规模不同，问题性质相同D.问题规模不同，问题性质不同2.在寻找n个元素中第k小元素问题中，如快速排序算法思想，运用分治算法对n个元素进行划分，如何选择划分基准？下面（）答案解释最合理。
A.随机选择一个元素作为划分基准B.取子序列的第一个元素作为划分基准C.用中位数的中位数方法寻找划分基准D.以上皆可行。
但不同方法，算法复杂度上界可能不同3.对于下列二分查找算法，以下正确的是（）。
A.intbinarySearch(inta[],intn,int x){intlow=0,high=n-1;while(low<=high){intmid=(low+high)/2;if(x==a[mid])returnmid;if(x>a[mid])low=mid;elsehigh=mid;}return –1;}B.intbinarySearch(inta[],intn,int x) { intlow=0,high=n-1;while(low+1!=high){intmid=(low+high)/2;if(x>=a[mid])low=mid;elsehigh=mid;}if(x==a[low])returnlow;elsereturn –1;}C.intbinarySearch(inta[],intn,intx) { intlow=0,high=n-1;while(low<high-1){intmid=(low+high)/2;if(x<a[mid])high=mid;elselow=mid;}if(x==a[low])returnlow;elsereturn –1;}D.intbinarySearch(inta[],intn,int x) {if(n>0&&x>=a[0]){intlow= 0,high=n-1;while(low<high){intmid=(low+high+1)/2;if(x<a[mid])high=mid-1;elselow=mid;}if(x==a[low])returnlow;}return –1;}答案解析：1.答：C。
《算法设计与分析》实验报告实验三回溯法3.迷宫问题一天Luna在森林里探险的时候不小心走入了一个迷宫，迷宫可以看成是由n * n的格点组成，每个格点只有2种状态，. 和#，前者表示可以通行后者表示不能通行。
同时当Luna处在某个格点时，她只能移动到东南西北(或者说上下左右)四个方向之一的相邻格点上，Luna想要从点A走到点B（不能走出迷宫）。
如果起点或者终点有一个不能通行(为#)，则看成无法办到。
[输入]第1行是测试数据的组数k，后面跟着k组输入。
每组测试数据的第1行是一个正整数n (1 <= n <= 100)，表示迷宫的规模是n * n 的。
接下来是一个n * n的矩阵，矩阵中的元素为. 或者#。
再接下来一行是4个整数ha, la, hb, lb，描述A处在第ha行, 第la列，B处在第hb 行, 第lb列。
注意到ha, la, hb, lb全部是从0开始计数的。
1.八皇后问题1.1解题思路八皇后问题的解法，很简单的解法。
通过回溯实现枚举。
对于当前行，尝试是否可在当前列放置皇后，然后进入下一行的尝试，同时尝试完毕以后，要将当前行回复（回溯），来进行下一次尝试。
到达最后一行的时候，即递归结束条件，打印结果即可。
1.2程序运行情况1.3所有的皇后解见附录。
（毕竟92个解...）1.4程序源码（含注释）2. 24点问题2.1 解题思路这题虽然使用dfs很简单，但是有一点思维在里面。
我很惭愧，自己没有想出来怎么如意的独立AC此题。
遇到的最大的问题——如何插入括号？枚举插入、和运算符一同排列都不靠谱。
解决方法是：用同等的办法转化。
每一次从待组合的是数字中，任取两个数，随机用运算符计算完毕后，再放回去。
下一次计算，再次重复这个过程，可以等价为有括号的运算方式了。
遇到第二个问题——如何实现这种“任取两个数”的选择方式。
这里就直接体现出了我个人能力的不足。
居然没想到。
尝试使用STL的set，但是没成功。
计算机算法设计与分析实验指导书本书是为配合《算法分析与设计实验教学大纲》而编写的上机指导，其目的是使学生消化理论知识，加深对讲授内容的理解，尤其是一些算法的实现及其应用，培养学生独立编程和调试程序的能力，使学生对算法的分析与设计有更深刻的认识。
上机实验一般应包括以下几个步骤：（1）准备好上机所需的程序。
手编程序应书写整齐，并经人工检查无误后才能上机。
（2）上机输入和调试自己所编的程序。
一人一组，独立上机调试，上机时出现的问题，最好独立解决。
（3）上机结束后，整理出实验报告。
实验报告应包括：题目、程序清单、运行结果、对运行情况所作的分析。
本书共分阶段6个实验，其具体要求和步骤如下：实验一分治算法（2学时）一、实验目的与要求1、熟悉二分搜索算法；2、初步掌握分治算法；二、实验题设a[0:n-1]是一个已排好序的数组。
请改写二分搜索算法，使得当搜索元素x不在数组中时，返回小于x的最大元素的位置i和大于x的最小元素位置j。
当搜索元素在数组中时，i和j相同，均为x在数组中的位置。
三、实验提示用i，j做参数，且采用传递引用或指针的形式带回值。
bool BinarySearch(int a[],int n,int x,int& i,int& j){int left=0;int right=n-1;while(left<right){int mid=(left+right)/2;if(x==a[mid]){i=j=mid;return true;}if(x>a[mid])left=mid+1;elseright=mid-1;}i=right;j=left;return false;}实验二动态规划算法（2学时）一、实验目的与要求1、熟悉最长公共子序列问题的算法；2、初步掌握动态规划算法；二、实验题若给定序列X={x1,x2,…,xm}，则另一序列Z={z1,z2,…,zk}，是X的子序列是指存在一个严格递增下标序列{i1,i2,…,ik}使得对于所有j=1,2,…,k有：zj=xij。
《算法分析与设计》练习题一答案1.程序书写格式应该遵循哪四个原则？参考答案：（1）正确使用缩进：一定要有缩进，否则代码的层次不明显。
（2）在一行内只写一条语句。
（3）, '}'位置不可随意放置。
（4）变量和运算符之间最好加1个空格2.什么是算法？参考答案：用计算机解决问题的过程可以分成三个阶段：分析问题、设计算法和实现算法。
算法可以理解为冇基本运算及规定的运算顺序所构成的完整的解题步骤，它是求解问题类的、机械的、统一的方法，它由有限多个步骤组成，对于问题类屮每个给定的具体问题，机械地执行这些步骤就可以得到问题的解答。
或者看成按照要求设计好的有限的确切的计算序列，并且这样的步骤和序列可以解决一类问题。
3.什么是线性结构？什么是非线性结构？参考答案：线性结构：数据逻辑结构屮的一类。
它的特征是若结构为非空集，则该结构有且只有一个开始结点和一个终端结点，并且所冇结点都冇R只冇一个直接前趋和一个直接后继。
线性表就是一个典型的线性结构。
栈、队列、串等都是线性结构。
非线性结构：数据逻辑结构中的另一大类，它的逻辑特征是一个结点可能有多个直接而趋和直接后继。
数组、广义表、树和图等数据结构都是非线性结构。
4.已知二叉树后序遍丿力序列是DABEC,屮序遍丿力序列是DEBAC,则前序遍历序列是什么？参考答案：前序遍历序列是CEDBA5.什么是数制？参考答案：数制是人们利用符号进行计数的一种科学方法。
数制也称计数制，是用一组固定的符号和统一的规则來表示数值的方法。
6.如果将十进制数106转换为八进制数，结果是多少？参考答案：1527.请问查找算法的效率用什么进行度量？参考答案：平均查找长度ASL：在查找其关键字等于给定值的过程小，需要和给定值进行比较的关键字个数的期望值称为查找成功吋的平均查找长度。
AS厶=£皿/=1其屮，n是结点的个数；是杳找第i个结点的概率,是找到第i个结点所需要的比较次数。
算法设计与分析报告学生姓名学号专业班级指导教师完成时间目录一、课程内容 (3)二、算法分析 (3)1、分治法 (3)（1)分治法核心思想 (3)（2）MaxMin算法分析 (3)2、动态规划 (4)（1）动态规划核心思想 (4)（2）矩阵连乘算法分析 (5)3、贪心法 (5)(1）贪心法核心思想 (5)（2）背包问题算法分析 (6)（3）装载问题算法分析 (7)4、回溯法 (7)（1）回溯法核心思想 (7)（2)N皇后问题非递归算法分析 (7)(3）N皇后问题递归算法分析 (8)三、例子说明 (9)1、MaxMin问题 (9)2、矩阵连乘 (10)3、背包问题 (10)4、最优装载 (10)5、N皇后问题(非递归） (11)6、N皇后问题(递归) (11)四、心得体会 (12)五、算法对应的例子代码 (12)1、求最大值最小值 (12)2、矩阵连乘问题 (13)3、背包问题 (15)4、装载问题 (17)5、N皇后问题(非递归） (19)6、N皇后问题(递归） (20)一、课程内容1、分治法,求最大值最小值，maxmin算法；2、动态规划，矩阵连乘，求最少连乘次数；3、贪心法，1）背包问题，2）装载问题；4、回溯法，N皇后问题的循环结构算法和递归结构算法。
二、算法分析1、分治法（1）分治法核心思想当要求解一个输入规模为n,且n的取值相当大的问题时，直接求解往往是非常困难的。
如果问题可以将n个输入分成k个不同子集合，得到k个不同的可独立求解的子问题，其中1<k≤n, 而且子问题与原问题性质相同,原问题的解可由这些子问题的解合并得出。
那末，这类问题可以用分治法求解。
分治法的核心技术1)子问题的划分技术.2）递归技术。
反复使用分治策略将这些子问题分成更小的同类型子问题，直至产生出不用进一步细分就可求解的子问题。
3)合并技术.（2）MaxMin算法分析问题：在含有n个不同元素的集合中同时找出它的最大和最小元素。
《算法分析与设计》作业（一）本课程作业由两部分组成。
第一部分为“客观题部分”，由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.简述算法和程序的区别。
算法:是指解决问题的一种方法或一个过程。
算法是若干指令的有穷序列，程序：是算法用某种程序设计语言的具体实现。
程序可以不满足算法的性质(4)。
例如:操作系统，是一个在无限循环中执行的程序，因而不是一个算法。
操作系统的各种任务可看成是单独的问题，每一个问题由操作系统中的一个子程序通过特定的算法来实现。
该子程序得到输出结果后便终止。
2.一个算法应有哪些主要特征？满足如下性质：(1)输入：有外部提供的量作为算法的输入。
(2)输出：算法产生至少一个量作为输出。
(3)确定性：组成算法的每条指令是清晰，无歧义的。
(4)有限性：算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的。
3.简述动态规划算法和贪心算法的基本要素。
动态规划算法的基本要素：最优子结构：矩阵连乘计算次序问题的最优解包含着其子问题的最优解。
这种性质称为最优子结构性质。
在分析问题的最优子结构性质时，所用的方法具有普遍性：首先假设由问题的最优解导出的子问题的解不是最优的，然后再设法说明在这个假设下可构造出比原问题最优解更好的解，从而导致矛盾。
利用问题的最优子结构性质，以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。
最优子结构是问题能用动态规划算法求解的前提。
重叠子问题：递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。
这种性质称为子问题的重叠性质。
动态规划算法，对每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此子问题时，只是简单地用常数时间查看一下结果。
通常不同的子问题个数随问题的大小呈多项式增长。
因此用动态规划算法只需要多项式时间，从而获得较高的解题效率贪心算法的基本要素：贪心选择性质：所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。
这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。
动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。
实验一分治与递归（4学时）一、实验目的与要求1、熟悉C/C++语言的集成开发环境；2、通过本实验加深对递归过程的理解二、实验内容掌握递归算法的概念和基本思想，分析并掌握“整数划分”问题的递归算法。
三、实验题任意输入一个整数，输出结果能够用递归方法实现整数的划分。
四、程序代码五、实验结果首先按照提示输入数字：按回车键，得到此数划分的个数：此时您可以接着计算另一个数的划分个数：若要退出，请输入一个小于等于零的数：六、结果分析及程序功能经过和其它同学的实验数据对比，初步认定此程序基本正确，然而不足之处是只能得到划分的个数，而不能列出每个划分的详细情况。
一、实验目的与要求1、掌握棋盘覆盖问题的算法；2、初步掌握分治算法二、实验题盘覆盖问题：在一个2k×2k个方格组成的棋盘中，恰有一个方格与其它方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。
在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。
三、程序代码四、实验结果按照提示输入特殊方格的行号和列号（起始行列号为0）：按回车键，得到一个矩阵，数字相同区域为一个L型骨牌覆盖：五、结果分析及程序功能得到的16*16棋盘覆盖结果正确，此程序的不足之处：只能设定特殊方格的行列号，而不能设定棋盘的大小。
实验二动态规划算法(4学时)一、实验目的与要求1、熟悉最长公共子序列问题的算法；2、初步掌握动态规划算法；二、实验题若给定序列X={x1,x2,…,xm}，则另一序列Z={z1,z2,…,zk}，是X的子序列是指存在一个严格递增下标序列{i1,i2,…,ik}使得对于所有j=1,2,…,k有：zj=xij。
例如，序列Z={B，C，D，B}是序列X={A，B，C，B，D，A，B}的子序列，相应的递增下标序列为{2，3，5，7}。
给定2个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。
《算法设计与分析》作业作业四+五回溯法+分支限界法1. 二元最大连通块搜索因为下了场大雨，青蛙王子高兴坏了，它有机会重新划定自己的王国范围。
在下图中，空白区域表示积水的地方，青蛙王子需要找到一块最大的连续积水区域（上下或左右相连）作为自己的新领地。
2. 三元最大连通块搜索小明在玩一种消除游戏。
游戏中有一个长方形的区域，被RGB(红绿蓝)三种颜色的小球充满。
要求每次找出当前最大连通区域（上下左右相邻同种颜色即可算作连通），进行消除。
####.######.######.#####the ans is 712 8..#......##....#.#....#..###.#......#.....##.#...#....#..##..#.####..#......#......#......#.....the ans is 181.3 程序运行情况1.4 程序源码（含注释）#include"bits/stdc++.h"using namespace std;#define inf 999//代码下标从0始，输入时.为可走，#为不可走int n,m;//行、列int ans,now;//最大连通数，当前搜索时连通数char e[inf][inf];//地图int book[inf][inf];//标记地图int pos[4][2]={-1,0,1,0,0,1,0,-1};//方位，上下右左void read()//输入数据{printf("input the row and the column of the map:"); scanf("%d%d",&n,&m);printf("now input the map:\n");for(int i=0;i<n;i++)scanf("%s",e[i]);2.4 程序源码（含注释）#include"bits/stdc++.h"using namespace std;#define inf 999//代码下标从0始int n,m;//行、列int ans,now;//最大连通数，当前搜索时连通数int ans_x,ans_y;//最大连通对应的字符char e[inf][inf];//地图int book[inf][inf];//标记地图int pos[4][2]={-1,0,1,0,0,1,0,-1};//方位，上下右左void read()//输入数据{printf("input the row and the column of the map:");scanf("%d%d",&n,&m);printf("now input the map:\n");for(int i=0;i<n;i++)scanf("%s",e[i]);。
合肥师范学院实验报告册2016/ 2017 学年第 1 学期系别计算机学院实验课程算法设计与分析专业软件工程班级一班姓名杨文皇学号1310421071指导教师程敏实验一：分治算法一、实验目的1、理解分治策略的基本思想；2、掌握用分治法解决问题的一般技巧。
二、实验内容利用分治算法在含有n个不同元素的数组a[n]中同时找出它的最大的两个元素和最小的两个元素，编写出完整的算法，并分析算法的时间复杂度。
三、实验源程序。
1、算法设计思想利用分治法思想，n个不同元素的数组不断进行划分，化为若干个个子问题，其与原问题形式相；解决子问题规模较小而容易解决则直接解决：即当n的规模为只有一个或两个，三个或四个；否则再继续直至更小的子问题：即当n的规模大于四时。
将已求得的各个子问题的解，逐步合并原问题的解：即将左右两边求得的子问题进行比较，在四个数据中的得到两个最大（最小）值。
为了简化空间，采用了对每一个小规模问题的排序，以及合并原问题时，对四个数据进行排序，获得当前或合并的最大（最小）值2、算法实现#include<iostream>using namespace std;int a[10]={4,5,6,2,3,9,8,13,1};int b[4];int sort(int i,int j){int temp,k;for(;i<j;i++){for(k=i;k<j;k++)if(a[k]>a[k+1]){temp=a[k];a[k]=a[k+1];a[k+1]=temp;}}return 0;}int sort1(int lmin1,int lmin2,int rmin1,int rmin2){int i,j,temp;b[0]=lmin1;b[1]=lmin2;b[2]=rmin1;b[3]=rmin2;for(i=0;i<=1;i++)for(j=i;j<=3;j++){if(b[i]>b[j]){temp=b[i];b[i]=b[j];b[j]=temp;}}return 0;}int maxmin(int i,int j,int &fmin1,int &fmin2,int &fmax1,int &fmax2) {int mid;int lmin1,lmin2,lmax1,lmax2;int rmin1,rmin2,rmax1,rmax2;if(i==j || i==j-1){sort(i,j);fmin1=a[i];fmin2=a[i];fmax1=a[j];fmax2=a[j];}elseif(i==j-2 || i==j-3){sort(i,j);fmin1=a[i];fmin2=a[i+1];fmax1=a[j-1];fmax2=a[j];}else{mid=(i+j)/2;maxmin(i,mid,lmin1,lmin2,lmax1,lmax2);maxmin(mid+1,j,rmin1,rmin2,rmax1,rmax2);sort1(lmin1,lmin2,rmin1,rmin2);fmin1=b[0];fmin2=b[1];sort1(lmax1,lmax2,rmax1,rmax2);fmax1=b[2];fmax2=b[3];}return 0;}int main(){int fmin1,fmin2,fmax1,fmax2;int i;maxmin(0,8,fmin1,fmin2,fmax1,fmax2);cout<<endl;cout<<"该组数据为:";for(i=0;i<=8;i++)cout<<a[i]<<" ";cout<<endl<<endl<<"最小值是:"<<fmin1<<"，第二小值是:"<<fmin2<<endl;cout<<endl<<"第二大值是:"<<fmax1<<",最大值是:"<<fmax2<<endl<<endl;return 0;}3、程序结果4、算法分析用T（n）元素表示数，则导出的递推关系式是：在理想的情况下，即每一小规模的子问题中的数据都是递增序列，则:当n<=4时，T（n）=1; 当n>4时，T（n）= T（n/2）+ T（n/2）(均向下取整);在非理想情况下，即每一小规模的子问题中的数据都是递减序列，则：当n=1时，T（n）=1；当n=2时，T（n）=2；当n=3时，T（n）=3；当n=4时，T（n）=6；当n>4时，T（n）= T（n/2）+ T（n/2）(均向下取整)+12。
算法分析与设计教程习题解答第1章 算法引论1. 解：算法是一组有穷的规则，它规定了解决某一特定类型问题的一系列计算方法。
频率计数是指计算机执行程序中的某一条语句的执行次数。
多项式时间算法是指可用多项式函数对某算法进行计算时间限界的算法。
指数时间算法是指某算法的计算时间只能使用指数函数限界的算法。
2. 解：算法分析的目的是使算法设计者知道为完成一项任务所设计的算法的优劣，进而促使人们想方设法地设计出一些效率更高效的算法，以便达到少花钱、多办事、办好事的经济效果。
3. 解：事前分析是指求出某个算法的一个时间限界函数（它是一些有关参数的函数）；事后测试指收集计算机对于某个算法的执行时间和占用空间的统计资料。
4. 解：评价一个算法应从事前分析和事后测试这两个阶段进行，事前分析主要应从时间复杂度和空间复杂度这两个维度进行分析；事后测试主要应对所评价的算法作时空性能分布图。
5. 解：①n=11； ②n=12； ③n=982； ④n=39。
第2章 递归算法与分治算法1． 解：递归算法是将归纳法的思想应用于算法设计之中，递归算法充分地利用了计算机系统内部机能，自动实现调用过程中对于相关且必要的信息的保存与恢复；分治算法是把一个问题划分为一个或多个子问题，每个子问题与原问题具有完全相同的解决思路，进而可以按照递归的思路进行求解。
2． 解：通过分治算法的一般设计步骤进行说明。
3． 解：int fibonacci(int n) {if(n<=1) return 1;return fibonacci(n-1)+fibonacci(n-2); }4. 解：void hanoi(int n,int a,int b,int c) {if(n>0) {hanoi(n-1,a,c,b); move(a,b);hanoi(n-1,c,b,a); } } 5. 解：①22*2)(--=n n f n② )log *()(n n n f O =6． 解：算法略。
