作业解答.ppt

《作业解答.ppt》由会员分享，可在线阅读，更多相关《作业解答.ppt（21页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、School of Software,YunNan University算法作业解答任课教师：何婧任课教师：何婧任课教师：何婧任课教师：何婧Email:Email:2HeJing(2011)School of Software作业作业1 1p截至日期：9月21日p上传地址：ftp:/113.55.4.20p文件名称：“学号姓名作业”pP32 1.1 1.5 1.13 1.16 1.31 p硬件厂商硬件厂商XYZ公司宣称他们最新研制的微处理器运行速度为其竞争公司宣称他们最新研制的微处理器运行速度为其竞争对手对手ABC公司同类产品的公司同类产品的100倍。对于计算复杂性分别为倍。对于计算复杂性分别

2、为n，n2，n3和和n!的各算法，若用的各算法，若用ABC公司的计算机能在公司的计算机能在1小时内解输入规模为小时内解输入规模为n的问题，那么用的问题，那么用XYZ公司的计算机在公司的计算机在1小时内分别能解输入规模为多小时内分别能解输入规模为多大的问题？大的问题？3HeJing(2008)School of Software作业作业1 11.P32 1.1 令令A1.60=11,12,70，用算法，用算法BinarySearch搜索下列搜索下列x值时执行了多少次比较运算值时执行了多少次比较运算n（a）33 （b）7 （c）70 （d）77p解：根据二分搜索思想，算法最大比较次数为解：根据二分

3、搜索思想，算法最大比较次数为具体分析：具体分析：（a）33；查找次数为：；查找次数为：6次，分别查找了次，分别查找了40，25，32，36，34，33。（b）7；查找次数为：；查找次数为：5次，分别查找了次，分别查找了40，25，17，13，11。（c）70；查找次数为：；查找次数为：6次，分别查找了次，分别查找了40，55，63，67，69，70。（d）77；查找次数为：；查找次数为：6次，分别查找了次，分别查找了40，55，63，67，69，70。4HeJing(2008)School of Software作业作业1 12.P32 1.5 ModSelectionSort解：解：（a）M

4、odSelectionSort算法赋值的最少次数为算法赋值的最少次数为0次，在要排序的数组次，在要排序的数组中的所有元素已按非降序排序的情况下达到最小值。中的所有元素已按非降序排序的情况下达到最小值。（b）ModSelectionSort算法赋值的最大次数为算法赋值的最大次数为3n(n-1)次，在要排序次，在要排序的数组中的所有元素的数组中的所有元素正好是降序排序时，需要的交换次数最多，正好是降序排序时，需要的交换次数最多，(n-1)+(n-2)+(n-3)+1=n(n-1)/2。一次交换需要三次赋值，所以赋一次交换需要三次赋值，所以赋值次数为值次数为3n(n-1)/2。5HeJing(200

5、8)School of Software作业作业1 1pP32 1.13f(n)g(n)f=O(g)f=(g)f=(g)2n3+3n100n2+2n+100FTF50n+logn10n+loglognTTT50nlogn10nloglognFTFlognlog2nTFFn!5nFTF6HeJing(2008)School of Software作业作业1 1pP32 1.16 BubbleSortp解：解：（a）元素比较最少次数是）元素比较最少次数是n-1，当输入数组是非降序排列时，执行一，当输入数组是非降序排列时，执行一遍第遍第4行语句，进行行语句，进行n-1次比较后得知后一个元素总是比前一

6、个元素次比较后得知后一个元素总是比前一个元素要大，数组已排好序，要大，数组已排好序，sorted=true，则程序结束。，则程序结束。（b）元素比较最多次数是）元素比较最多次数是n(n-1)/2，当输入数组是降序排列时，当输入数组是降序排列时，while循环执行循环执行n-1次，元素比较次数总和为：次，元素比较次数总和为：n-1+n-2+1（c）赋值主要来自于交换，元素赋值最少次数是）赋值主要来自于交换，元素赋值最少次数是0，当输入数组是非，当输入数组是非降序排列时，不需要赋值。降序排列时，不需要赋值。（d）元素赋值最多次数是）元素赋值最多次数是3n(n-1)/2，当输入数组是降序排列时，当输

7、入数组是降序排列时，每一次比较都要进行交换。每一次比较都要进行交换。（e）算法运行时间为）算法运行时间为O(n2)，(n)（f）由于算法运行时间与输入序列有关，从线性到平方排列，因此这）由于算法运行时间与输入序列有关，从线性到平方排列，因此这一算法不能用一算法不能用表示。表示。7HeJing(2008)School of Software作业作业1 1pP32 1.31 算法Count4的时间复杂度p解：解：p第第4行的行的j循环总是执行循环总是执行6次，第次，第5行行k的循环与的循环与i相关，为相关，为i2次，所以次，所以第第6行的执行次数为行的执行次数为6*12+6*22+.6*(logn

8、)2，根据，根据P49求和求和公式公式（a）第）第6步执行步执行（b）要表示算法的时间复杂性用）要表示算法的时间复杂性用更合适，因为用公式求出的值能够更合适，因为用公式求出的值能够得到算法的精确阶。得到算法的精确阶。（c c）算法的时间复杂性是）算法的时间复杂性是(log(log3 3n)n)8HeJing(2008)School of Softwarep 硬件厂商硬件厂商XYZ公司宣称他们最新研制的微处理器运行速度为公司宣称他们最新研制的微处理器运行速度为其竞争对手其竞争对手ABC公司同类产品的公司同类产品的100倍。对于计算复杂性分倍。对于计算复杂性分别为别为n，n2，n3和和n!的各算法

9、，若用的各算法，若用ABC公司的计算机能公司的计算机能在在1小时内解输入规模为小时内解输入规模为n的问题，那么用的问题，那么用XYZ公司的计算机公司的计算机在在1小时内分别能解输入规模为多大的问题？小时内分别能解输入规模为多大的问题？解：解：n=100n n12=100n2 求出求出 n1=10n n13=100n3 求出求出 n1!=100n!作业作业1 19HeJing(2008)School of Software作业作业1 1p如何仅用如何仅用7次比较完成次比较完成5个元素排序。请简要写出过程。个元素排序。请简要写出过程。p解：假设有解：假设有a,b,c,d,e五个数五个数（1）2次比

10、较次比较，得到，得到ab,cd，将元素分为，将元素分为s1=b,d,s2=a,c,e（2）b和和d进行进行1次比较次比较，若，若bd,s1=b,d,否则否则s1=d,b（3）若：）若：bd a c e /s2中的元素与中的元素与s1对应，有对应，有ab,cd（4）按分段逆序插入法：因为）按分段逆序插入法：因为ab，得到的已排序序列为，得到的已排序序列为abd（5）e与与b比较比较1次，若次，若eb，则，则e和和a比，否则比，否则e和和d比。比。2次比较次比较得到得到a,b,d,e已排序序列。已排序序列。（6）最后，因为）最后，因为cd，在当前的已排序序列中，在当前的已排序序列中，d之前最多有之

11、前最多有3个元素，个元素，最多经过最多经过2次比较次比较就能找到就能找到c的合适位置。的合适位置。（7）因此，）因此，5个元素排序，使用分段逆序插入法，无论元素如何排列，个元素排序，使用分段逆序插入法，无论元素如何排列，最多最多7次比较。次比较。10HeJing(2008)School of Software作业作业2 2p截止日期：截止日期：9月月28日日p上传地址：上传地址：ftp:/222.19.217.20p文件名称：文件名称：“学号姓名作业学号姓名作业”pP86 4.5、4.14、4.17p补充：金币问题。有补充：金币问题。有mn(M=100,n=100)枚金币在桌面上排成枚金币在桌

12、面上排成m行行n列的金币阵列。每一枚金币或正面朝上，用列的金币阵列。每一枚金币或正面朝上，用0表示，或背面朝上，用表示，或背面朝上，用1表表示。示。p游戏规则游戏规则：（：（1）每次可将一行金币翻过来放在原来的位置上。）每次可将一行金币翻过来放在原来的位置上。p （2）每次可选择任意两列，交换这两列的位置。）每次可选择任意两列，交换这两列的位置。p要求：给定金币阵列的初始状态和目标状态，编程计算按游戏规则，达到目要求：给定金币阵列的初始状态和目标状态，编程计算按游戏规则，达到目标状态所需的最少变换次数。标状态所需的最少变换次数。2023/5/17 10100011010110111101110

13、111HeJing(2008)School of Software作业作业2 2pP86 4.5 参照参照MakeHeap算法算法1.resulttrue;2.for i downto 13.if(2i+1)=n)4.if(AiA2i or AiA2i+1)5.resultfalse;break;6.endif7.else if(AiA2i)8.resultfalse;break;9.endif;10.endfor 最坏情况下执行最坏情况下执行n/2次循环，在每次循环中进行次循环，在每次循环中进行2次比较。所以算法的时间次比较。所以算法的时间复杂性是复杂性是O(n)2023/5/17 12He

14、Jing(2008)School of Software作业作业2 2pP86 4.14、4.17 参照课本参照课本HeapSort算法完成。算法完成。p算法算法HeapSortp输入：输入：n个元素的数组个元素的数组A1np输出：以非将序排列的数组输出：以非将序排列的数组A1.MakeHeap(A);2.for j n downto 23.交换交换A1和和Aj;4.Sift_down(A1j-1,1);5.Endfor2023/5/17 算法：算法：MakeHeapMakeHeap输入：输入：n n个元素的数组个元素的数组A1nA1n输出：输出：A1nA1n转换成的堆转换成的堆1.1.for

15、 for ii downto 1 downto 12.2.Sift_down(A,i);Sift_down(A,i);3.3.endforendfor13HeJing(2008)School of Software作业作业2 2p补充：金币问题。有补充：金币问题。有mn(M=100,n=100)枚金币在桌面上排成枚金币在桌面上排成m行行n列的金币阵列。每一枚金币或正面朝上，用列的金币阵列。每一枚金币或正面朝上，用0表示，或背面朝上，用表示，或背面朝上，用1表表示。示。p游戏规则游戏规则：（：（1）每次可将一行金币翻过来放在原来的位置上。）每次可将一行金币翻过来放在原来的位置上。p （2）每次可

16、选择任意两列，交换这两列的位置。）每次可选择任意两列，交换这两列的位置。p要求：给定金币阵列的初始状态和目标状态，编程计算按游戏规则，达到目要求：给定金币阵列的初始状态和目标状态，编程计算按游戏规则，达到目标状态所需的最少变换次数。（提交算法思想、源程序和可执行文件）标状态所需的最少变换次数。（提交算法思想、源程序和可执行文件）2023/5/17 10100011010110111101110114HeJing(2008)School of Software作业作业3 3p截止日期：截止日期：9月月29日日p上传地址：上传地址：ftp:/113.55.4.20p文件名称：文件名称：“学号姓名作

17、业学号姓名作业”pP99 5.4 5.14 p写出汉诺塔问题算法思想，程序实现，以及算法复杂度分写出汉诺塔问题算法思想，程序实现，以及算法复杂度分析。如果移动析。如果移动16个盘需要移动多少次。个盘需要移动多少次。p求解下列递归关系式求解下列递归关系式2023/5/17 15HeJing(2008)School of Software作业作业3 3pP99 5.4p#include p#define N 5pdouble aver(float*a,int t,int n)pp if(t!=-1)return(at/n+aver(a,t-1,n);p else return 0;pint mai

18、n(void)pp float a=7,1,3,18,15;p printf(%fn,aver(a,N-1,N);p return 0;p2023/5/17 16HeJing(2008)School of Software作业作业3 3p5.14ASelectionSortBInsertionSortCBubbleSortDBottomUpSortEHeapSortFRadixSort17HeJing(2008)School of Software作业作业3 3p作业作业:写出汉诺塔问题算法思想，程序实现，以及算法复杂度分析。写出汉诺塔问题算法思想，程序实现，以及算法复杂度分析。p算法：算法：

19、pvoid hanoi(int n,char source,char temp,char target)ppif(n=1)move(source,target);pelsepphanoi(n-1,source,target,temp);/*实现第一步实现第一步*/pmove(source,target);/*实现第二步实现第二步*/phanoi(n-1,temp,source,target);/*实现第三步实现第三步*/ppp算法复杂度：算法复杂度：递推式展开，求得递推式展开，求得2n-12023/5/17 18HeJing(2008)School of Software作业作业3 32023

20、/5/17 19HeJing(2008)School of Software作业作业3 32023/5/17 20HeJing(2008)School of Software作业作业3 32023/5/17 21HeJing(2008)School of Software 作业作业4 4p截止日期：截止日期：10月月9日日p上传地址：上传地址：ftp:/113.55.4.20p文件名称：文件名称：“学号姓名作业学号姓名作业”1.参考课本参考课本P110算法算法Select，任选一种程序设计语言，实现该，任选一种程序设计语言，实现该算法。算法。2.循环赛日程表问题循环赛日程表问题要求：写出算法思想、程序实现、以及算法复杂度分析。要求：写出算法思想、程序实现、以及算法复杂度分析。