算法分析与设计实验报告
算法分析与设计实验报告
目录
实验一：递归与分治 (1)
二分查找
归并排序
快速排序
实验二：回溯算法 (8)
0—1背包
实验三：动态规划 (12)
矩阵连乘最少乘法数
实验一：递归与分治
一、实验目的
理解递归算法的思想和递归程序的执行过程，并能熟练编写递归程序。
掌握分治算法的思想，对给定的问题能设计出分治算法予以解决。
二、实验内容
1．二分查找
在对线性表的操作中，经常需要查找某一个元素在线性表中的位置。此问题的输入是待查元素x和线性表L，输出为x在L中的位置或者x不在L中的信息。
2．合并排序
3．快速排序
对本实验中的问题，设计出算法并编程实现。
实验总结及思考
三、实验过程
1.二分查找
算法：BinSearch(aArray[0,1……n-1],key)
low<---0;
right<---n-1;
while low<=right do
m<---(low+(right-low))/2;
if key>aArray[mid]
l<---mid+1;
if key r<---mid-1; if key=aArray[mid] return mid; 代码： #include using namespace std; void Binary(int aArray[],int key,int length) //二分查找 { int mid,low,high; mid=low=0; high=length-1; while(low<=high) { mid = low + ((high - low)/2); //使用(low + high) / 2 会有整数溢出的问题 if(low<0||high>=length||high - low==0){ cout<<"元素不存在，查找失败"< } if(key>aArray[mid]) //key在右边 { low=mid+1; } else if(key { high=mid-1; } else { cout<<"查找成功，元素的位置是:"< break; } } } int main() { int length = 0; int key = 0; cout<<"请输入数组的长度："< cin >> length; int* aArray = new int[length]; cout<<"请输入数组："< for (int i = 0; i < length; i++) { cin >> aArray[i]; } cout<<"请输入待查找的数字："< cin >> key; Binary(aArray,key,length); delete aArray; //释放空间 return 0; } 二分查找的平均时间复杂度为O(logn) 最坏情况下的时间复杂度O(n) 运行截图： 2.合并排序 基本操作如下: （1）分解:将n 个元素分成各含n/2 个元素的子序列 （2）解决:用合并排序法对两个子序列递归地排序 （3）合并:合并两个已排好序的子序列得到排序结果在对子序列排序时，其长度为1 时递归结束。单个元素被视为是已排好序的。 算法： MergeSort(A[0…n-1]) if n>1 copy A[0…n/2-1]toB[0…n/2-1] copy A[n/2…n-1]toC[0…n/2-1] MergeSort(B[0…n/2-1]) MergeSort(C[0…n/2-1]) Merge(B,C,A) Merge(B[0…p-1],C[0…q-1],A[0…P+q-1]) i<---0;j<---0;k<---0 while i if B[i]<=C[j] A[k]<---B[i];i<---i+1; else A[k]<---C[j];j<---j+1; k<---k+1; if i=p copyC[j…q-1]toA[k…p+q-1] else copyB[i…q-1]toA[k…p+q-1] 代码： #include using namespace std; void Merge(int *a, int p, int q, int r)//把数组a[]分成L[]，R[]，再排序合并成a[] { int n1 = q-p+1; int n2 = r-q; int *L = new int[n1+1]; int *R = new int[n2+1]; int i, j, k; for (i=0; i L[i] = a[p+i]; } for (j=0; j R[j] = a[q+j+1]; } L[n1] = 10000000; R[n2] = 10000000; for (i=0,j=0,k=p;k<=r;k++) { if (L[i]<=R[j]) { a[k] = L[i]; i++; }else{ a[k] = R[j]; j++; } } delete []L; delete []R; } void MergeSort(int *a, int p, int r)//递归调用 { if (p { int q = (p+r)/2; MergeSort(a, p, q); MergeSort(a, q+1, r); Merge(a, p, q, r); } } int main() { int j = 0; cout<<"请输入数组的长度："< cin >> j; int* aArray = new int[j]; cout<<"请输入原始数组："< for (int i = 0;i < j;i++) { cin >> aArray[i]; } MergeSort(aArray,0,j-1); cout<<"排序后的数组："< for (int i = 0;i < j;i++) { cout < } delete aArray;//释放空间 system("pause"); return 0; } 归并排序的平均时间复杂度：O(logn) 运行截图： 3.快速排序 实现快速排序的分治过程如下: （1）分解:数组A[p..r]被划分为两个(可能空)子数组A[p..q-1]和A[q+1..r], 使得A[p..q-1]中的每个元素都小于等于A(q),而且，小于等于A[q+1..r]中的元素。下标q 也在这个划分过程中进行计算。 （2）解决:通过递归调用快速排序，对子数组A[p..q-1]和A[q+1..r]排序 （3）合并:因为两个子数组是就地排序的，将它们的合并不需要操作，整个数组A[p..r]已排序。 代码： #include using namespace std; void quickSort(int s[], int l, int r) { if (l { int i = l, j = r; int x = s[l];//找一个基准数 while (i < j) { while(i < j && s[j]>= x) // 从右向左找第一个小于x的数 j--; if(i < j) s[i++] = s[j]; while(i < j && s[i]< x) // 从左向右找第一个大于等于x的数 i++; if(i < j) s[j--] = s[i]; } s[i] = x; quickSort(s, l, i - 1); // 递归调用 quickSort(s, i + 1, r); } } int main() { int j = 0; cout<<"请输入数组的长度："< cin >> j; int* aArray = new int[j]; cout<<"请输入原始数组："< for (int i = 0;i < j;i++) { cin >> aArray[i]; } quickSort(aArray,0,j-1); cout<<"排序后的数组："< for (int i = 0;i < j;i++) { cout < } delete aArray; system("pause"); return 0; } 快排的平均时间复杂度O(nlogn) 最坏情况下的时间复杂度为O（n^2) 运行截图： 实验二：回溯算法 一、实验目的 熟练掌握回溯算法 二、基本思想 回溯法在问题的解空间树中，按深度优先搜索策略，从根结点出发搜索解空间树，算法搜索至解空间树的任意一点时，先判断该结点是否满足约束，如果不满足，则跳过该节点为根的子树的搜索，逐层向其祖先节点搜索，否则，进入该子树，继续按照深度优先策略搜索。 三、实验内容：回溯算法的几种形式 1.用回溯算法搜索子集树的一般模式 void search(int m) { if(m>n) //递归结束条件 output(); //相应的处理(输出结果) else { a[m]=0; //设置状态：0表示不要该物品 search(m+1); //递归搜索：继续确定下一个物品 a[m]=1; //设置状态：1表示要该物品 search(m+1); //递归搜索：继续确定下一个物品 } } 2.用回溯算法搜索子集树的一般模式 void search(int m) { if(m>n) //递归结束条件 output(); //相应的处理(输出结果) else for(i=m;i<=n;i++) { swap(m,i); //交换a[m]和a[i] if() if(canplace(m)) //如果m处可放置 search(m+1); //搜索下一层 swpa(m,i); //交换a[m]和a[i](换回来) } } 四、回溯算法解决0-1背包问题 在0 / 1背包问题中，需对容量为c 的背包进行装载。从n 个物品中选取装入背包的物品，每件物品i 的重量为wi ，价值为pi 。对于可行的背包装载，背包中物品的总重量不能超过背包的容量，最佳装载是指所装入的物品价值最高。 0代表不装进背包，1代表装进背包，对树进行深度优先搜索，判断是否为可行解，若为可行解且放进去之后最大价值大于当前最大价值则修改当前最大价值和背包余量。（没有进行减支） 代码： #include void readdata(); void search(int); void checkmax(); void printresult(); int c=35, n=10; //c:背包容量；n：物品数 int w[10], v[10]; //w[i]、v[i]:第i件物品的重量和价值 int a[10], max; //a数组存放当前解各物品选取情况；max：记录最大价值 //a[i]=0表示不选第i件物品，a[i]=1表示选第i件物品int main() { readdata(); //读入数据 search(0); //递归搜索 printresult(); } void search(int m) { if(m>=n) checkmax(); //检查当前解是否是可行解，若是则把它的价值与max比较else { a[m] = 1; //不选第m件物品 search(m+1); //递归搜索下一件物品 a[m] = 0; search(m+1); } } void checkmax() { int i, weight=0, value=0; for(i = 0;i { if(a[i]==1) //如果选取了该物品 { weight = weight + w[i]; //累加重量 value = value + v[i]; //累加价值 } } if(weight<=c) //若为可行解 if(value>max) //且价值大于max max = value; //替换max } void readdata() { int i; for(i=0;i printf("请输入第%d个物品的重量和价值\n",i+1); scanf("%d %d",&w[i],&v[i]); //读入第i件物品重量和价值} } void printresult() { printf("背包可以装的最大价值为%d",max); } 运行截图： 实验三：动态规划 一、实验目的 理解动态规划的基本思想，理解动态规划算法的两个基本要素最优子结构性质和子问题的重叠性质。熟练掌握典型的动态规划问题。掌握动态规划思想分析问题的一般方法，对较简单的问题能正确分析，设计出动态规划算法，并能快速编程实现。 二、动态规划的基本思想 对于一个多阶段过程问题，是否可以分段实现最优决策，信赖于该问题是否有最优子结构性质，能否采用动态规划的方法，还要看该问题的子问题是否具有重叠性质。 最优子结构性质:原问题的最优解包含了其子问题的最优解 子问题的重叠性质:每次产生的子问题并不总是新问题，有些子问题被反复计算多次。问题的最优子结构性质和子问题重叠性质是采用动态规划算法的两个基本要素 动态规划一般方法 1.找出最优解的性质，并刻画其结构特征 2.递归地定义最优值(写出动态规划方程) 3.以自底向上的方式计算出最优值 三、用动态规划法计算矩阵连乘需要的最少乘法次数 在科学计算中经常要计算矩阵的乘积。矩阵A 和B 可乘的条件是矩阵A 的列数等于矩阵B 的行数。若A 是一个p×q 的矩阵，B 是一个q×r 的矩阵，则其乘积C=AB 是一个p×r 的矩阵。由该公式知计算C=AB 总共需要pqr 次的数乘。其标准计算公式为： 现在的问题是，给定n 个矩阵{A1,A2,…,An}。其中Ai 与Ai+1是可乘的，i=1,2,…,n -1。要求计算出这n 个矩阵的连乘积A1A2…An 。 递归公式：?????<+++==-<≤j i p p p j k m k i m j i j i m j k i j k i }]][1[]][[{min 0]][[1 代码： #include int n; //矩阵个数(0~100) int p[101]; //矩阵维数(n+1) void Matrix_mult() { int Arr[101][101],temp;//(Arr[0][0]不用)Arr[i][j]存放从矩阵i到矩阵j的最小矩阵乘法数 int i,j,k; int d; //矩阵间隔d for(i=1;i<=n;i++) Arr[i][i]=0;//第i个矩阵到第i个矩阵乘法数为0 for(d=1;d<=n-1;d++)//矩阵间隔r//矩阵链长度d+1 { for(i=1;i<=n-d;i++)//i=1..~n-d { j=i+d; //i~i+d构成长度为r+1的矩阵链 Arr[i][j]=0+Arr[i+1][j]+p[i-1]*p[i]*p[j]; //截断位置为i for(k=i+1;k { temp=Arr[i][k]+Arr[k+1][j]+p[i-1]*p[k]*p[j]; if(temp Arr[i][j]=temp; //获得从矩阵i到矩阵j的最小矩阵乘法数} } } printf("输入的%d个矩阵相乘的最少乘法数为：",n); printf("%d\n",Arr[1][n]); //从第1个矩阵到第n个矩阵最小乘法数} int main() { int i; printf("请输入矩阵的个数\n"); scanf("%d",&n);//矩阵个数(0~10) int b[100][2]; printf("请输入n个矩阵的行数和列数\n"); for( i=0;i { scanf("%d",&b[i][0]);//第i个矩阵的行数 scanf("%d",&b[i][1]);//第i个矩阵的列数 } for(i=0;i p[i]=b[i][0];//存放所有矩阵维数（测例中的1,2,3...10,11） p[n]=b[n-1][1];//最后一个矩阵的列数 Matrix_mult(); return 0; } 算法设计与分析考试题 及答案 Company number：【WTUT-WT88Y-W8BBGB-BWYTT-19998】 一、填空题（20分） 1.一个算法就是一个有穷规则的集合，其中之规则规定了解决某一特殊类型问题的一系列运算，此外，算法还应具有以下五个重要特性:确定性 有穷性 可行性 0个或多个输入 一个或多个输出 2.算法的复杂性有时间复杂性 空间复杂性之分，衡量一个算法好坏的标准是 时间复杂度高低 3.某一问题可用动态规划算法求解的显着特征是 该问题具有最优子结构性质 4.若序列X={B,C,A,D,B,C,D}，Y={A,C,B,A,B,D,C,D}，请给出序列X 和Y 的一个最长公共子序列{BABCD}或{CABCD}或{CADCD ｝ 5.用回溯法解问题时，应明确定义问题的解空间，问题的解空间至少应包含一个（最优）解 6.动态规划算法的基本思想是将待求解问题分解成若干_子问题 ，先求解_子问题 ，然后从这些子问题 的解得到原问题的解。 7.以深度优先方式系统搜索问题解的算法称为回溯法 背包问题的回溯算法所需的计算时间为o(n*2n ) ,用动态规划算法所需的计算时间为o(min{nc,2n }) 9.动态规划算法的两个基本要素是最优子结构 _和重叠子问题 10.二分搜索算法是利用动态规划法实现的算法。 二、综合题（50分） 1.写出设计动态规划算法的主要步骤。 ①问题具有最优子结构性质；②构造最优值的递归关系表达式； ③最优值的算法描述；④构造最优解； 2. 流水作业调度问题的johnson 算法的思想。 ①令N 1={i|a i =b i }；②将N 1中作业按a i 的非减序排序得到N 1’，将N 2中作业按b i 的非增序排序得到N 2’；③N 1’中作业接N 2’中作业就构成了满足Johnson 法则的最优调度。 3. 若n=4，在机器M1和M2上加工作业i 所需的时间分别为a i 和b i ，且 (a 1,a 2,a 3,a 4)=(4,5,12,10)，(b 1,b 2,b 3,b 4)=(8,2,15,9)求4个作业的最优调度方案，并计算最优值。 步骤为：N1={1，3}，N2={2，4}； N 1’={1，3}， N 2’={4，2}； 最优值为：38 4. 使用回溯法解0/1背包问题：n=3，C=9，V={6,10,3}，W={3,4,4},其解空间有长度为3的0-1向量组成，要求用一棵完全二叉树表示其解空间（从根出发，左1右0），并画出其解空间树，计算其最优值及最优解。 解空间为{(0,0,0),(0,1,0),(0,0,1),(1,0,0),(0,1,1),(1,0,1), (1,1,0),(1,1,1)}。 解空间树为： 该问题的最优值为：16 最优解为：（1，1，0） 5. 设S=｛X 1，X 2，···，X n ｝是严格递增的有序集，利用二叉树的结点来存储S 中的元素，在表示S 的二叉搜索树中搜索一个元素X ，返回的结果有两种情形，（1）在二叉搜索树的内结点中找到X=X i ，其概率为b i 。（2）在二叉搜索树的叶结点中确定X ∈（X i ，X i+1），其概率为a i 。在表示S 的二叉搜索树T 中，设存储元素X i 的结点深度为C i ；叶结点（X i ，X i+1）的结点深度为d i ，则二叉搜索树T 的平均路长p 为多少假设二叉搜索树T[i][j]=｛X i ，X i+1，···，X j ｝最优值为m[i][j]，W[i][j]= a i-1+b i +···+b j +a j ，则m[i][j](1<=i<=j<=n)递归关系表达式为什么 .二叉树T 的平均路长P=∑=+n i 1 Ci)(1*bi +∑=n j 0 dj *aj 西南交通大学2015 — 2016学年第(一)学期考试试卷 课程代码 3244152课程名称 算法分析与设计 考试时间 120分钟 阅卷教师签字： __________________________________ 填空题(每空1分，共15分) 1、 程序是 (1) 用某种程序设计语言的具体实现。 2、 矩阵连乘问题的算法可由 (2) 设计实现。 3、 从分治法的一般设计模式可以看出，用它设计出的程序一般是 (3) 4、 大整数乘积算法是用 (4) 来设计的。 5、 贪心算法总是做出在当前看来 (5) 的选择。也就是说贪心算法并不从整体最优 考虑，它所做出的选择只是在某种意义上的 (6) o 6、 回溯法是一种既带有 (7) 又带有 (8) 的搜索算法。 7、 平衡二叉树对于查找算法而言是一种变治策略，属于变治思想中的 (9) 类型 8、 在忽略常数因子的情况下，0、门和0三个符号中， (10) 提供了算法运行时 间的一个上界。 9、 算法的“确定性”指的是组成算法的每条 (11) 是清晰的，无歧义的。 10、 冋题的(12) 是该冋题可用动态规划算法或贪心算法求解的关键特征。 11、 算法就是一组有穷 (13)，它们规定了解决某一特定类型问题的 (14) o 12、 变治思想有三种主要的类型：实例化简，改变表现， (15) o 、 ___________________________________________________________________________________ L 线订装封密 线订装封密 、 __________________ 二 线订装封密 级班 选择题(每题2分，共20 分) 《算法分析与设计》实验指导书本书是为配合《算法分析与设计实验教学大纲》而编写的上机指导，其目的是使学生消化理论知识，加深对讲授容的理解，尤其是一些算法的实现及其应用，培养学生独立编程和调试程序的能力，使学生对算法的分析与设计有更深刻的认识。 上机实验一般应包括以下几个步骤： （1）、准备好上机所需的程序。手编程序应书写整齐，并经人工检查无误后才能上机。（2）、上机输入和调试自己所编的程序。一人一组，独立上机调试，上机时出现的问题，最好独立解决。 （3）、上机结束后，整理出实验报告。 实验报告应包括： 1）问题分析 2）算法描述 3）运行结果、 4）算法性能分析。 实验一 实验名称：贪心算法应用及设计 实验学时：6学时 实验类型：验证 实验目的： 1.理解贪心算法的基本思想 2.掌握利用贪心算法求解问题的求解步骤 实验容 1.活动选择问题（2学时） 问题描述： 设有11个会议等待安排，用贪心法找出满足目标要求的会议集合，这些会议按结束时间的非减序排列如下表。 实验实现提示： １)数据结构设计： 将会议开始时间存储在数组B中，结束时间存储在数组E中，数组下标为会议的代码。结果存储在数组A中，其元素A[i]==true，表示会议i被选中。 ２）算法： void GreedySelect(int n, struct time B[], struct time E[], bool A[]) { int i,j; A[1]=true; j=1; i=2; while( i<=n) if (B[i]>=E[j]) { A[i]=true; j=i;} else A[i]=false; } 思考题：证明所得的解是最优解？ 2.单源点最短路径问题。（2学时） 问题描述 如图所示的有向带权图中，求源点0到其余顶点的最短路径及最短路径长度。并对算法进行性能分析。 实现提示 1）数据结构设计： 将图存储在邻接矩阵C中，结点个数为n，源点编号为u, 源点u到其余顶点的最短路径长度存储在dist[],最短路径存储在p[]。 2) 算法 void Dijkstra(int C[n][n], int n,int u,float dist[],int p[]) { bool s[n]; for( int i=1; i<=n; i++) { dist[i]=C[u][i]; s[i]=false; if (dist[i]=∞) p[i]=-1; else p[i]=u; } p[u]=-1; s[u]=true; for( i=1; i<=n; i++) { int temp= ∞; int t=u; for( int j=1;j<=n;j++) 算法设计与分析 学院：计算机科学与技术 学号：129074106 姓名：张淼淼 2014 11 14 1、 当问题规模100 N 时，快速排序和插入排序各需多少时间？写清机器配置，列出五种 快速排序所需时间(ms) 插入排序所需时间（ms ） 两者相差多少 N=100 0.00600 0.019000 -0.013000 N=1000 0.074000 0.724000 -0.650000 N=10000 0.032000 64.657000 -64.625000 N=100000 13.300000 50.900000 -37.600000 N=1000000 53.500000 117.700000 -64.200000 Window 7 32位 Cpu ：Inter(R) Core(TM) i3-2120 cpu@3.30GHz AMD Radeon HD 6450 Graphics 程序： #include int b[1000000]; void QuickSort(int low ,int high) { long i,j; int x; i=low; j=high; x=a[i]; while(i 1.一个算法就是一个有穷规则的集合，其中之规则规定了解决某一特殊类型问题的一系列运算，此外，算法还应具有以下五个重要特性:_________,________,________,__________,__________。 2.算法的复杂性有_____________和___________之分，衡量一个算法 好坏的标准是______________________。 3.某一问题可用动态规划算法求解的显著特征是 ____________________________________。 4.若序列X={B,C,A,D,B,C,D}，Y={A,C,B,A,B,D,C,D}，请给出序列X 和Y的一个最长公共子序列_____________________________。 5.用回溯法解问题时，应明确定义问题的解空间，问题的解空间至少应包含___________。 6.动态规划算法的基本思想是将待求解问题分解成若干____________，先求解___________，然后从这些____________的解得到原问题的解。 7.以深度优先方式系统搜索问题解的算法称为_____________。 8.0-1背包问题的回溯算法所需的计算时间为_____________,用动态规划算法所需的计算时间为____________。 9.动态规划算法的两个基本要素是___________和___________。 10.二分搜索算法是利用_______________实现的算法。 二、综合题（50分） 1.写出设计动态规划算法的主要步骤。 2.流水作业调度问题的johnson算法的思想。 《算法分析与设计》试卷(A) （时间90分钟满分100分） 一、填空题（30分,每题2分）。 1．最长公共子序列算法利用的算法是（ B ）。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法2．在对问题的解空间树进行搜索的方法中,一个活结点最多有一次机会成为活结点的是( B ). A.回溯法 B.分支限界法 C.回溯法和分支限界法 D.回溯法求解子集树问题 3．实现最大子段和利用的算法是（ B ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法4．.广度优先是（ A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法5．衡量一个算法好坏的标准是（ C ）。 A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短 6．Strassen矩阵乘法是利用（ A）实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 7. 使用分治法求解不需要满足的条件是（ A ）。 A 子问题必须是一样的 B 子问题不能够重复 C 子问题的解可以合并 D 原问题和子问题使用相同的方法解 8．用动态规划算法解决最大字段和问题，其时间复杂性为( B ). A.logn B.n C.n2 D.nlogn 9.解决活动安排问题，最好用（ B ）算法 A.分治 B.贪心 C.动态规划 D.穷举 10.下面哪种函数是回溯法中为避免无效搜索采取的策略（ B ） A．递归函数 B.剪枝函数C。随机数函数 D.搜索函数11. 从活结点表中选择下一个扩展结点的不同方式将导致不同的分支限界法,以下除( C )之外都是最常见的方式. A.队列式分支限界法 B.优先队列式分支限界法 C.栈式分支限界法 D.FIFO分支限界法 12. .回溯算法和分支限界法的问题的解空间树不会是( D ). A.有序树 B.子集树 C.排列树 D.无序树 13.优先队列式分支限界法选取扩展结点的原则是（ C ）。 A、先进先出 B、后进先出 C、结点的优先级 D、随机14．下面是贪心算法的基本要素的是（ C ）。 A、重叠子问题 B、构造最优解 C、贪心选择性质 D、定义最优解15．回溯法在解空间树T上的搜索方式是( A ). A.深度优先 B.广度优先 C.最小耗费优先 D.活结点优先 二、填空题（20分,每空1分）。 1.算法由若干条指令组成的又穷序列，且满足输入、输出、 确定性和有限性四个特性。 2.分支限界法的两种搜索方式有队列式(FIFO)分支限界法、优先队列式分支限界法，用一个队列来存储结点的表叫活节点表。 算法设计与分析实验报告 贪心算法 班级：2013156 学号：201315614 姓名：张春阳哈夫曼编码 代码 #include printf("\n"); for(i=0;i 算法设计与分析 实 验 报 告 班级： 姓名： 学号： (备注：共给出5个参考实验案例，根据学号尾数做对应的实验，即如尾号为1，则模仿案例实验123；尾号2，则模仿案例实验234；尾号3，即345；尾号4，同1.) 目录 实验一分治与递归 (1) 1、基本递归算法 (1) 2、棋盘覆盖问题 (2) 3、二分搜索 (3) 4、实验小结 (5) 实验二动态规划算法 (5) 1、最长公共子序列问题 (5) 2、最大子段和问题 (7) 3、实验小结 (8) 实验三贪心算法 (8) 1、多机调度问题 (8) 2、用贪心算法求解最小生成树 (10) 3、实验小结 (12) 实验四回溯算法和分支限界法 (12) 1、符号三角形问题 (12) 2、0—1背包问题 (14) 3、实验小结 (18) 实验五多种排序算法效率比较 1、算法：起泡排序、选择排序、插入排序、shell排序，归并排序、快速排序等 (19) 2、实验小结 (18) P art1：课程设计过程 设计选题--→题目分析---→系统设计--→系统实现--→结果分析---→撰写报告 P art2：课程设计撰写的主要规范 1.题目分析：主要阐述学生对题目的分析结果，包括题目描述、 分析得出的有关模型、相关定义及假设； 2.总体设计：系统的基本组成部分，各部分所完成的功能及相互 关系； 3.数据结构设计：主要功能模块所需的数据结构，集中在逻辑设 计上； 4.算法设计：在数据结构基础上，完成算法设计； 5.物理实现：主要有数据结构的物理存储，算法的物理实现，系 统相关的实现。具体在重要结果的截图，测试案例的结果数据，核心算法的实现结果等； 6.结果分析：对第五步的分析，包括定性分析和定量分析，正确 性分析，功能结构分析，复杂性分析等； 7.结论：学生需对自己的课程设计进行总结，给出评价，并写出 设计体会； 8.附录：带有注释的源代码，系统使用说明等； 9.参考文献：列出在撰写过程中所需要用到的参考文献。 一．填空题(每空 2 分，共30分) 1．算法的时间复杂性指算法中的执行次数。 2．在忽略常数因子的情况下，O、和三个符号中，提供了算法运行时间的一个上界。 3．设D n表示大小为n的输入集合，t(I)表示输入为I时算法的运算时间, p(I)表示输入 I 出现的概率，则算法的平均情况下时间复杂性A(n)= 。 4．分治算法的时间复杂性常常满足如下形式的递归方程： f (n) d , n n0 f(n) af(n/c) g(n) , n n0 其中，g(n)表示。 5. 分治算法的基本步骤包括。6．回溯算法的基本思想是。 7．动态规划和分治法在分解子问题方面的不同点是。 8．贪心算法中每次做出的贪心选择都是最优选择。 9．PQ 式的分支限界法中，对于活结点表中的结点，其下界函数值越小，优先级 10．选择排序、插入排序和归并排序算法中，算法是分治算法。 11．随机算法的一个基本特征是对于同一组输入，不同的运行可能得到的结果。12. 对于下面的确定性快速排序算法，只要在步骤3 前加入随机 化步骤，就可得到一个随机化快速排序算法，该随机化步骤的功能是。 算法QUICKSORT 输入：n 个元素的数组A[1..n] 。 输出：按非降序排列的数组 A 中的元素 1. quicksort(1, n) end QUICKSORT ＿ ＿ 过程 quicksort(A, low, high) ＿ ＿ // 对 A[low..high] 中的元素按非降序排序。 ＿ 号 学 2. if low 内部资料，转载请注明出处，谢谢合作。 算法设计与分析试卷(A 卷) 一、 选择题 （ 选择1-4个正确的答案, 每题2分，共20分） （1）计算机算法的正确描述是： A ．一个算法是求特定问题的运算序列。 B ．算法是一个有穷规则的集合，其中之规则规定了一个解决某一特定类型的问题的运算序列。 C ．算法是一个对任一有效输入能够停机的图灵机。 D ．一个算法，它是满足5 个特性的程序，这5个特性是：有限性、确定性、能 行性、有0个或多个输入且有1个或多个输出。 （2）影响程序执行时间的因素有哪些？ A ．算法设计的策略 B ．问题的规模 C ．编译程序产生的机器代码质量 D ．计算机执行指令的速度 （3）用数量级形式表示的算法执行时间称为算法的 A ．时间复杂度 B ．空间复杂度 C ．处理器复杂度 D ．通信复杂度 （4）时间复杂性为多项式界的算法有： A ．快速排序算法 B ．n-后问题 C ．计算π值 D ．prim 算法 （5）对于并行算法与串行算法的关系，正确的理解是： A ．高效的串行算法不一定是能导出高效的并行算法 B ．高效的串行算法不一定隐含并行性 C ．串行算法经适当的改造有些可以变化成并行算法 D. 用串行方法设计和实现的并行算法未必有效 （6）衡量近似算法性能的重要标准有： A ．算法复杂度 B ．问题复杂度 C ．解的最优近似度 D ．算法的策略 （7）分治法的适用条件是，所解决的问题一般具有这些特征： A ．该问题的规模缩小到一定的程度就可以容易地解决； B ．该问题可以分解为若干个规模较小的相同问题； C ．利用该问题分解出的子问题的解可以合并为该问题的解 D ．该问题所分解出的各个子问题是相互独立的。 （8）具有最优子结构的算法有： A ．概率算法 B ．回溯法 C ．分支限界法 D ．动态规划法 （9）下列哪些问题是典型的NP 完全问题： A ．排序问题 B ．n-后问题 C ．m-着色问题 D ．旅行商问题 （10）适于递归实现的算法有： A ．并行算法 B ．近似算法 C ．分治法 D ．回溯法 二、算法分析题（每小题5分，共10分） （11）用展开法求解递推关系： （12）分析当输入数据已经有序时快速排序算法的不足，提出算法的改进方案。 ???>+-==1 1)1(211)(n n T n n T 湖南科技学院二○年学期期末考试 信息与计算科学专业年级《算法设计与分析》试题 考试类型:开卷试卷类型:C卷考试时量:1２０分钟 题号一二三四五总分统分人 得分 阅卷人 复查人 一、填空题(每小题3 分，共计30 分) １、用O、Ω与θ表示函数f与g之间得关系＿__________＿__＿_＿_＿＿_＿__＿___＿＿。 2、算法得时间复杂性为,则算法得时间复杂性得阶为_＿__＿＿____＿_＿_＿____＿＿_＿__＿。 3、快速排序算法得性能取决于_＿_____＿_______＿__＿__＿_＿___＿__。 4、算法就是__＿_＿______＿＿_＿＿__＿________＿___＿___＿___＿___＿_＿_＿_＿＿_＿__。 5、在对问题得解空间树进行搜索得方法中,一个活结点最多有一次机会成为活结点得就是＿_______＿__＿____________＿。 6、在算法得三种情况下得复杂性中,可操作性最好且最有实际价值得就是__＿_＿情况下得时间复杂性。 7、大Ω符号用来描述增长率得下限,这个下限得阶越__＿________,结果就越有价值。。 8、_＿_＿__＿_＿____＿________＿_____就是问题能用动态规划算法求解得前提。 9、贪心选择性质就是指_＿____________＿______＿_＿__＿__＿______＿________________＿__＿_____＿____＿____＿_＿______＿__＿__＿___＿_＿__＿___＿_＿＿＿________＿__。 1０、回溯法在问题得解空间树中,按______＿＿＿_＿__＿策略,从根结点出发搜索解空间树。 二、简答题(每小题10分,共计3０分) １、试述回溯法得基本思想及用回溯法解题得步骤。 2、有８个作业{１,２,…,8}要在由2台机器M1与Ｍ２组成得流水线上完成加工。每个作业加工得顺序都就是先在M1上加工,然后在M2上加工。M１与M2加工作业ｉ所需得时间分别为: M１10 2 8 12 6 ９４14 《计算机算法设计与分析》实验指导书（第一版） 前言 计算机算法分析与设计是面向设计的，它是计算机科学的核心。无论是计算机系统、系统软件和解决计算机的各种应用问题都可归结为算法的设计。通过本课程的学习，使学生掌握计算机领域中许多常用的非数值的算法描述：分治法、贪心法、动态规划、回溯法、分枝限界等算法，并掌握算法分析的方法，从而把学生的分析问题和解决问题能力提高到理论的高度。 前期课程为程序设计语言、数据结构、高等数学，即学生应该具备一门高级语言程序设计编程基础，学习基本的数据结构知识，还要求学生掌握较好的数学基础。 开发环境不限，本书采用C/C++语言的集成开发环境等。 实验完成后书写实验报告，包含实验问题、基本思想、关键算法流程图、测试数据及运行结果（截图）、调试心得和源程序。 总实验学时为16学时。 目录 预备实验验证算法的方法 (4) 实验目的： (4) 实验课时： (4) 实验原理： (4) 实验题目： (6) 基本题： (6) 提高题： (6) 实验一递归与分治 (7) 实验目的： (7) 实验课时： (7) 实验原理： (7) 实验题目： (7) 基本题： (7) 提高题： (8) 思考问题： (8) 实验二动态规划算法 (9) 实验目的： (9) 实验课时： (9) 实验原理： (9) 实验题目： (9) 基本题： (9) 提高题： (10) 思考问题： (10) 实验三贪心选择算法 (11) 实验目的： (11) 实验课时： (11) 实验原理： (11) 实验题目： (11) 基本题： (11) 提高题： (12) 思考问题： (12) 实验四回溯算法 (13) 实验目的： (13) 实验课时： (13) 实验原理： (13) 实验题目： (14) 基本题： (14) 提高题： (14) 思考问题： (14) 算法分析与设计复习题及答案一、单选题 1．D 2．B 3．C 4．D 5．D 6．D 7．C 8．D 9．B 10．C 11．D 12．B 13．D 14．C 15．C 16．D 17．D 18．D 19．D 20．C 1．与算法英文单词algorithm具有相同来源的单词是（）。 A logarithm B algiros C arithmos D algebra 2．根据执行算法的计算机指令体系结构，算法可以分为（）。 Ａ精确算法与近似算法Ｂ串行算法语并行算法 Ｃ稳定算法与不稳定算法Ｄ３２位算法与６４位算法 3．具有１0个节点的完全二叉树的高度是（）。 Ａ６Ｂ５Ｃ3Ｄ 2 4．下列函数关系随着输入量增大增加最快的是（）。 Ａlog2n B n2 C 2n D n! 5．下列程序段的S执行的次数为( )。 for i ←0 to n-1 do for j ←0 to i-1 do s //某种基本操作 A.n2 B n2/2 C n*(n+1) D n(n+1)/2 6．Fibonacci数列的第十项为( )。 A 3 B 13 C 21 D 34 7．4个盘子的汉诺塔，至少要执行移动操作的次数为( )。 A 11次 B 13次 C 15次 D 17次 8．下列序列不是堆的是（）。 A 99，85，98，77，80，60，82，40，22，10，66 B 99，98，85，82，80，77，66，60，40，22，10 C 10，22，40，60，66，77，80，82，85，98，99 D 99，85，40，77，80，60，66，98，82，10，22 9．Strassen矩阵乘法的算法复杂度为（）。 ＡΘ(n3)ＢΘ(n2.807) ＣΘ(n2) ＤΘ(n) 10．集合A的幂集是（）。 A．A中所有元素的集合 B. A的子集合 C． A 的所有子集合的集合 D. 空集 11．与算法英文单词algorithm具有相同来源的单词是（）。 A logarithm B algiros C arithmos D algebra 12．从排序过程是否完全在内存中显示，排序问题可以分为（）。 Ａ稳定排序与不稳定排序Ｂ内排序与外排序 Ｃ直接排序与间接排序Ｄ主排序与辅助排序 13．下列（）不是衡量算法的标准。 Ａ时间效率Ｂ空间效率 Ｃ问题难度Ｄ适应能力 14．对于根树，出度为零的节点为（）。 Ａ０节点Ｂ根节点Ｃ叶节点Ｄ分支节点 15．对完全二叉树自顶向下，从左向右给节点编号，节点编号为１0的父节点编号为（）。 Ａ０Ｂ２Ｃ４Ｄ６ 16．下列程序段的算法时间的复杂度为（）。 for i ←0 to n do for j ←0 to m do 《算法分析与设计》实验指导书 《算法分析与设计》课程是计算机专业的一门必修课程。开设算法分析与设计实验，目的就是为了使学生消化理论知识，加深对讲授内容的理解，尤其是一些算法的实现及其应用，培养学生独立编程和调试程序的能力，使学生对算法的分析与设计有更深刻的认识。 《算法分析与设计》课程实验的目的：是为了使学生在课程学习的同时，通过实验环境中的实际操作，对部分算法的具体应用有一个初步的了解，使学生加深了解和更好地掌握《算法分析与设计》课程教学大纲要求的内容。 《算法分析与设计》课程实验的注意事项：在《算法分析与设计》的课程实验过程中，要求学生做到： (1)预习实验指导书有关部分，认真做好实验内容的准备，就实验可能出 现的情况提前作出思考和分析。 (2)认真书写实验报告。实验报告包括实验目的和要求，实验情况及其分 析。 (3)遵守机房纪律，服从辅导教师指挥，爱护实验设备。 (4)实验课程不迟到。如有事不能出席，所缺实验一般不补。 《算法分析与设计》课程实验的验收：实验的验收将分为两个部分。第一部分是上机操作，包括检查程序运行和即时提问。第二部分是提交电子的实验报告。 实验一算法实现一 一、实验目的与要求 熟悉C/C++语言的集成开发环境； 通过本实验加深对分治法、贪心算法的理解。 二、实验内容: 掌握分治法、贪心算法的概念和基本思想，并结合具体的问题学习如何用相应策略进行求解的方法。 三、实验题 1. 【伪造硬币问题】给你一个装有n个硬币的袋子。n个硬币中有一个是伪造的。你的 任务是找出这个伪造的硬币。为了帮助你完成这一任务，将提供一台可用来比较两组硬币重量的仪器，利用这台仪器，可以知道两组硬币的重量是否相同。试用分治法的思想写出解决问题的算法，并计算其时间复杂度。 2.【找零钱问题】一个小孩买了价值为33美分的糖，并将1美元的钱交给售货员。售 货员希望用数目最少的硬币找给小孩。假设提供了数目有限的面值为25美分、10美分、5美分、及1美分的硬币。给出一种找零钱的贪心算法。 a)实验步骤 理解算法思想和问题要求； 编程实现题目要求； 上机输入和调试自己所编的程序； 验证分析实验结果； 整理出实验报告。 四、实验程序 五、实验结果 六、实验分析 《算法分析与设计》期末试题及参考答案 一、简要回答下列问题： 1.算法重要特性是什么？ 1.确定性、可行性、输入、输出、有穷性 2. 2.算法分析的目的是什么？ 2.分析算法占用计算机资源的情况，对算法做出比较和评价，设计出额更好的算法。 3. 3.算法的时间复杂性与问题的什么因素相关？ 3. 算法的时间复杂性与问题的规模相关，是问题大小n的函数。 4.算法的渐进时间复杂性的含义？ 4．当问题的规模n趋向无穷大时，影响算法效率的重要因素是T(n)的数量级，而其他因素仅是使时间复杂度相差常数倍，因此可以用T(n)的数量级(阶)评价算法。时间复杂度T(n)的数量级(阶)称为渐进时间复杂性。 5.最坏情况下的时间复杂性和平均时间复杂性有什么不同？ 5. 最坏情况下的时间复杂性和平均时间复杂性考察的是n固定时，不同输入实例下的 算法所耗时间。最坏情况下的时间复杂性取的输入实例中最大的时间复杂度： W(n) = max{ T(n，I) } , I∈Dn 平均时间复杂性是所有输入实例的处理时间与各自概率的乘积和： A(n) =∑P(I)T(n，I) I∈Dn 6.简述二分检索（折半查找）算法的基本过程。 6. 设输入是一个按非降次序排列的元素表A[i：j] 和x，选取A[(i+j)/2]与x比较， 如果A[(i+j)/2]=x，则返回(i+j)/2，如果A[(i+j)/2] 算法设计与分析实验报告 教师： 学号： 姓名： 实验一：串匹配问题 实验目的：(1) 深刻理解并掌握蛮力法的设计思想; (2) 提高应用蛮力法设计算法的技能; (3) 理解这样一个观点: 用蛮力法设计的算法, 一般来说, 经过适度的努力后, 都可以对算法的第一个版本进行一定程度的改良, 改进其时间性能。 三、实验要求：( 1) 实现BF 算法; (2 ) 实现BF 算法的改进算法: KMP 算法和BM 算法; (3 ) 对上述 3 个算法进行时间复杂性分析, 并设计实验程序验证 分析结果。 #include "stdio.h" #include "conio.h" #include 实验一、归并排序及各种排序算法性能比较 一、实验实习目的及要求 了解归并排序等各种排序算法，并能独立在计算机上实现，同时并能够计算它们的时间复杂度，并用计算机来验证。 二、实验实习设备（环境）及要求（软硬件条件） 计算机eclipse软件，执行环境JavaSE-1.8. 三、实验实习项目、内容与步骤(注意是主要关键步骤，适当文字+代码+截图说明) 项目：对10 4 6 3 8 2 5 7进行从小到大排序，采用几种排序方法，并统计这几种方法的运行时间，与归并排序比较。 内容及步骤： (1)归并排序：将序列每次分成两组，再进行合并，直到递归完成； 1、递归调用mergeSort对数组排序 2、merge将两个有序数组合并为一个有序数组 3、主函数调用mergeSort对数组排序 4、统计时间 (2) 选择排序：每次选择一个当前最小的并和当前的相对的第一个元素交换，直到最后 只有一个元素时结束；也可选择当前最大的并与当前的相对的最后一个 元素交换，直到最后只有一个元素时结束。 1、数组长度为n，需要选择n-1次；每次选择完成后，将数组中的最大值与最后一 个元素互换，调用java.util包中Arrays类。 2、主函数调用ChooseSort对数组排序。 3、统计运行时间。 (3)插入排序：从第二个元素开始，每次插入一个到当前有序序列中，使得有序，当 所有的元素插入完毕时，就排好序了； 1、从第二个元素开始，与之前序列比较，插入到合适的位置。 2、主函数调用sort对数组排序。 3、统计运行时间 (4) 快速排序：每次选择一个中间元素，并进行交换，使得中间元素的左边比它小，右 边比它大，然后对左右两边进行递归； 1、选取一个基准位，从右边向左边看，找比基准位小的元素，再从左边向右边看， 找比基准位大的元素，若两者均存在则交换；若两者相遇，则相遇元素与基准位元素交换，然后递归排序左右半数组。 一、选择题 1．一个.java文件中可以有（）个public类。 A．一个B．两个C．多个D．零个 2．一个算法应该是（） A．程序B．问题求解步骤的描述 C．要满足五个基本特性D．A和C 3．用计算机无法解决“打印所有素数”的问题，其原因是解决该问题的算法违背了算法特征中的（）A．唯一性B．有穷性C．有0个或多个输入D．有输出 4．某校有6位学生参加学生会主席竞选，得票数依次为130，20，98，15，67，3。若采用冒泡排序算法对其进行排序，则完成第二遍时的结果是（） A．3，15，130，20，98，67B．3，15，20，130，98，67 C．3，15，20，67，130，98 D．3，15，20，67，98，130 5．下列关于算法的描述，正确的是（） A．一个算法的执行步骤可以是无限的B．一个完整的算法必须有输出 C．算法只能用流程图表示D．一个完整的算法至少有一个输入 6．Java Application源程序的主类是指包含有（）方法的类。 A、main方法 B、toString方法 C、init方法 D、actionPerfromed方法 7．找出满足各位数字之和等于5的所有三位数可采用的算法思路是（） A．分治法B．减治法C．蛮力法D．变治法 8．在编写Java Application程序时，若需要使用到标准输入输出语句，必须在程序的开头写上( )语句。 A、import java.awt.* ; B、import java.applet.Applet ; C、import java.io.* ; D、import java.awt.Graphics ; 9．计算某球队平均年龄的部分算法流程图如图所示，其中：c用来记录已输入球员的人数，sum用来计算有效数据之和，d用来存储从键盘输入的球员年龄值，输入0时表示输入结束。 计算机算法设计与分析实验报告 目录 实验一 (1) [实验题目] (1) [问题描述] (1) [算法设计] (1) [算法分析] (1) [源代码] (1) [运行结果] (2) 实验二 (2) [实验题目] (2) [问题描述] (2) [算法设计] (2) [算法分析] (2) [源代码] (2) [运行结果] (4) 实验三 (5) [实验题目] (5) [问题描述] (5) [算法设计] (5) [算法分析] (5) [源代码] (5) [运行结果] (6) 实验一 [实验题目] 2-7集合划分问题 [问题描述] n个元素的集合{1，2，…，n}可以划分为若干非空子集。例如，当n=4时，集合{1，2，3，4}可以划分为15个不同的非空子集。 [算法设计] 给定正整数n，计算出n个元素的集合{1，2，…，n}可以划分为多少个不同的非空子集。 [算法分析] 本算法实现采用分治法思想，F(n,m)=F(n-1,m-1)+m*F(n-1,m)。假设将m个元素分解到n 个集合中，首先考虑将(m – (n - 1))个元素分到第一个集合中，将余下的(n - 1)个元素分别分配到余下的(n - 1)个集合中，然后再考虑将(m – (n - 2))个元素分配到第一个集合中，将余下的(n - 2)个元素分别分配到余下的(n - 1)集合中，依此类推，直到后面的有一个集合中的元素个数比第一个集合中的元素个数多为止。 [源代码] #include 算法设计与分析考试题及答案
2015年算法分析与设计期末考试试卷B卷
算法分析与设计实验指导书
算法分析与设计实验报告
算法设计与分析考试题及答案
算法分析与设计试卷
算法设计与分析实验报告贪心算法
计算机算法设计与分析
(完整版)算法设计与分析期末考试卷及答案a
算法设计与分析试卷(2010)
算法设计与分析试卷及答案
《算法分析与设计》实验指导书
算法分析与设计复习题及答案
算法分析与设计实验指导书
《算法分析与设计》期末试题及参考答案
算法设计与分析实验报告
算法分析与设计实验报告
《算法分析与设计》期末复习题
算法分析与设计实验报告
相关文档
- 算法设计与分析期末考试复习题
- 算法设计与分析期末试题考试版
- 《算法分析与设计》期末考试复习题纲(完整版)
- 《算法分析与设计》期末复习题[1]
- 算法设计与分析期末试题_考试版
- 《算法设计与分析》历年期末试题整理_含答案_
- 算法设计与分析期末试题
- 算法设计与分析(期末总复习)
- 算法设计与分析期末试卷A卷
- 算法设计与分析 期末试卷 A卷 完整含答案
- 算法设计分析期末考试试卷
- 《算法分析与设计》期末考试复习题纲(完整版)
- 算法设计与分析期末备考知识点总结.pdf
- 2015年算法分析与设计期末考试试卷B卷
- 算法设计与分析考试题目及答案
- 《算法分析与设计》期末复习题
- 《算法分析与设计》期末考试复习题纲(完整版)
- 《算法设计与分析》历年期末试题整理(含答案)
- 2019年算法分析与设计期末考试试卷B卷
- 计算机算法设计与分析期末考试复习题