算法设计与分析练习题

1、算法设计与分析练习题1. 仅使用、和o的定义，证明下列各式成立。1) 5n2 6n = (n2)2) n!= (nn)ni=03) 2n22n + nlogn =(n22n)ni=04) i2 = (n3)n2n（n ）2n5) i3 = (n4)6) + 6 * 2n =7) n3 + 106n2 =(n3)8) 6n3/(logn + 1) =(n3)9) n1.001 + nlogn =(n1.001)10) nk+ nklogn =(nk+)，k0，02. 采用定理2.2、2.4和2.6，证明第1题的所有式子成立。3. 证明以下等式不成立。1) 10n2+9=(n)2) n2logn=

2、(n2)3) n2/logn =(n2)4) n32n+6n23n=(n32n)n4. 证明当且仅当 lim f(n)/g(n)=0时，f(n)=o(g(n)。5. 下面哪些规则是正确的？为什么？1) f(n)=(F(n)，g(n)=(G(n) f(n)/g(n)=(F(n)/G(n)2) f(n)=(F(n)，g(n)=(G(n) f(n)/g(n)=(F(n)/G(n)3) f(n)=(F(n)，g(n)=(G(n) f(n)/g(n)=(F(n)/G(n)4) f(n)=(F(n)，g(n)=(G(n) f(n)/g(n)=(F(n)/G(n)5) f(n)=(F(n)，g(n)=(G(

3、n) f(n)/g(n)=(F(n)/G(n)6) f(n)=(F(n)，g(n)=(G(n) f(n)/g(n)=(F(n)/G(n)7) f(n)=(F(n)，g(n)=(G(n) f(n)/g(n)=(F(n)/G(n)8) f(n)=(F(n)，g(n)=(G(n) f(n)/g(n)=(F(n)/G(n)9) f(n)=(F(n)，g(n)=(G(n) f(n)/g(n)=(F(n)/G(n)6 计算以下函数的渐进复杂性，设计一个频率表加以说明。1).SelectionSort(a,int n)语句s/e频率总步数Void SelectionSort(elemTyoe a,int n

4、) /及时终止的选择排序bool Sorted = false;for(int size = n;!sorted&&(size>1);size-)int pos = 0;sorted = true;for(int i=1;i<size;i+)/找最大元素if(apos<=ai) pos = i;else sorted = false;/未按序排列Swap(apos,asize-1);总计2).InsertionSort(a,int n)语句s/e频率总步数Void InsertionSort(elemTyoe a,int n) /及时终止的选择排序for(in

5、t i=1;i<n;i+)/将ai插入到a0,i-1中elemTyoe t = ai;int j;for(j=i-1;j>=0 && t<aj;j-)/找t的位置aj+1=aj;aj+1=t;总计3).BubbleSort(a,int n)语句s/e频率总步数bool Bubble(elemTyoe a,int n) /把a0:n-1中的最大元素冒泡至最后bool swapped = false; /尚未发生交换 for(int i = 0; i<n-1;i+) if(ai>ai+1) Swap(ai,ai+1);swapped = true; /

6、发生了交换;return swapped;void BubbleSort(elemTyoe a,int n) /及时终止的冒泡排序算法for(int i = n; i>1 && Bubble(a,i);i-);总计4) 判断下列算法的渐进时间复杂度Status CharLoopCheck() InitStack(S);InitQueue(Q);C=getchar(); /读取一个字符。或者从文件上读入；或者从键盘上读入。While(c!=) Push(S,c);EnQueue(Q,c);C=getchar();/whilewhile(!empty(s) pop(s,x);

7、Dequeue(Q,y);if(x!=y) return Error;whileif(!empty(s) | !empty(Q) return Error;else return ok/ CharLoopCheck7. 某算法的计算时间可用下面的递推关系式描述。试采用迭代的方式求解该关系式，并用大写表示解(要求给出详细的推导过程)。a n=1，a为常数 T(n)=2T(n/2) + c*n n>1，c为常数8. 折半查找过程的判定树上，定义根结点到每个内部结点(查找成功的结点)的路径长度之和为内部路径长度，记为I；定义根结点到每个外部结点(查找不成功的结点)的路径长度之和外部路径长度，记

8、为E。试证明：具有n个内部结点的这样的判定树，满足E = I + 2n 。 9.已知f(n)=(log2n)，求证：f(n)=(logkn)，k1。10. 根据大写、小写o的定义，计算给定函数的渐进表示。请大家熟练掌握大写、小写o定义，并加以灵活应用。n2 ，n为正奇数 令f(n)=n3 ，n为正偶数例如， 则，根据定义有：f(n)= (?)，f(n)= (?)。11. 阅读下面的算法，并回答给定的问题。注意，行号是为了说明问题而设置，它不属于算法本身。void ABC(A，n) /A(0:n)是一个一维数组，共有n个可比较值大小的元素；/且A(0)未存放元素；变量x是与A(i)同类型的数据元

9、素。1 int i, j；2 for(j=2；j<=n；j+) 3 i=j-l；4 A0=Aj；5 while(A0<Ai) 6 x=Ai+1；7 Ai+1=Ai；8 Ai=x；9 i=i-1；10 ；/while11 Ai+1= A0；12 ；/for13 /ABC问题： 第4行的A(0)的作用是什么？利用A(0)对算法有何影响？ 整个算法的功能是什么？ 程序中变量x是否可省，为什么？ 给出while语句的最少执行次数的示例（列出数组A的数据元素例子）12. 作业中的相关习题要掌握（各种概念题、分析算法题及证明题等）。算法题分为阅读程序并解释程序的功能、根据题意编写算法、根据题意

10、完成算法等几种类型。内容分布在分治法、贪婪法及动态规划法等典型问题中。回溯法也非常有用，请大家注意掌握。13.下面的算法是依据分治策略设计出来的，仔细阅读该算法回答下列问题(行号是为了说明问题而设置，它不属于算法本身)。行号 Void ABC(int w，int n，int &p，int &q) 1 /w0:n-1中存放了n个整数。p,q是用于返回结果的两个变量2 if(n<1) return false； 3 if(n=1) p = q = 0；return true； 4 int s；5 if(n2) p = q = 0；s = 1；6 else 7 if(w0>

11、;=w1) p = 1；q = 0；8 else p = 0；q = 1；9 s = 2；10 ；11 for(i=s；i<n；i+=2) 12 if(wi>wi+1) if(wi>wq) q=i；if(wi+1<wp) p=i+1；13 elseif(wi+1>wq) q=i+1；if(wi<wp) p=i；14 ；/for15 return true；16 /ABC问题： 算法完成什么样的功能？当返回true时，p,q的返回值分别是什么？ 算法中哪个语句是出于对算法健壮性的考虑而设置的？ 对不同的n，讨论算法的比较次数。14.依据贪婪法求解问题的思想，编

12、写一个求解下列问题的算法。 设某币种有面额为25分、10分、5分、1分的四种硬币，1元钱等于100分。当希望找给顾客小于1元钱的零钱时，如何选择硬币种类才能够使得找给顾客的硬币数量最少。假设各种面额硬币的数量足够多。利用已经给出的部分代码，写出该问题的完整C语言算法。同时，假设需要找给顾客67分钱，请依据你的算法，给出找零钱的方案。main()int a3=25,10,5,1； / a0:3存放硬币的不同面额int b4； / b0:3存放对应硬币的数量(按面额由大到小)int s； / 存放零钱总数int i； / 循环控制变量printf(“请输入零钱总数：”)；scanf(“%d”,&a

13、mp;s)；/输入零钱总数，然后在下面补充必要代码，完成整个算法for(i=0；i<4；i+) printf(“面额为%d的硬币需要%d枚 n”，ai，bi)；/main 15. 依据所给的算法思路，在划线处填写适当的语句以完成整个算法。问题：求已知两字符序列A和B的最长公共字符子序列。定义：1. 从给定的字符序列中随意地(不一定是连续的一段)去掉若干字符(可能一个也不去掉)后形成的字符序列为给定字符序列的子序列。例如，令X=FEGDAADWS，Y=FEAD，则Y是X的一个子序列。2. 若Z既是字符序列A的子序列，又是字符序列B的子序列，则称Z是A和B的公共子序列。算法描述如下：设Aa0

14、,a1,am-1， Bb0,b1,bn-1，Zz0,z1,zk-1是A、B的最长公共子序列，则有如下性质： 如果am-1=bn-1，则zk-lam-1bn-1，且z0,z1,zk-2是a0,a1,am-2和b0,b1,bn-2的一个最长公共子序列； 如果am-1bn-1，则若zk-1am-1，蕴含z0,z1,zk-1是a0,a1,am-2和b0,b1,bn-1的一个最长公共子序列； 如果am-1bn-1，则若zk-1bn-1，蕴含z0,z1,zk-1是a0,a1,am-1和b0,b1,bn-2的一个最长公共子序列；即，在找A和B的公共子序列时，如有am-1=bn-1，则进一步解决一个子问题，即

15、找a0,a1,am-2和b0,b1,bn-2的一个最长公共子序列；如果am-1bn-1，则要解决两个子问题，即找出a0,a1,am-2和b0,b1,bn-1的一个最长公共子序列，和找出a0,a1,am-1和b0,b1,bn-2的一个最长公共子序列，再取两者中的较长者作为A和B的最长公共子序列。设cij为序列a0,a1,ai-1和b0,b1,bj-1的最长公共子序列的长度，则cij 计算的递归定义如下： cij=0，如果i=0，或j0； cij=ci-1j-11，如果i,j>0，且ai-1=bj-1； cij=maxcij-1,ci-1j，如果i,j>0，且ai-1bj-1。依据上述

16、思路的算法如下：# include<stdio.h># include<string.h># define n 100 /假设串的最大长度为100char an，bn，strn；int lcs_len(char *a，char *b，int cnn)int mstrlen(a)，nstrlen(b)，i，j；for(i0；i<=m；i+) ci00；for(j1；j<=n；j+) A ； /最长公共子序列的长度初始化for(i1；i<=m；i+)for(j1；j<=n；j+)if(ai-1=bj-l) cij = ci-1j-1+l；else i

17、f(ci-1j >= cij-1)cij = B ；else cij = cij-1；return C ；/返回最长公共子序列的长度char *build-lcs(char s,char *a,char *b)int k，i=strlen(a)，j=strlen(b)，cnn；k = lcs_len(a，b， D )；sk = 0；while(k>0)if(cij=ci-1j) i-；else if(cij=cij-1) E ；else s-k = ai-1；i-；j-；return s ；void main()printf(“Enter two string(<d)！n”，

18、 n)；scanf(“ss”，a，b)；printf(“LCS=sn”，build_lcs(str，a，b)；nnn16. 试证明，对于函数f(n)和g(n)，若lim g(n)/f(n)存在，则f(n)(g(n)当且仅当存在确定的常数c，有lim g(n)/f(n)c。 17. 证明：如果一个算法在平均情况下的计算时间复杂度为(g(n)，则该算法在最坏情况下所需的时间是(g(n)。18.证明：n!=(nn) 19. 用贪婪法解装箱问题。装箱问题可简述如下：设有编号为1，n的n种物品，体积分别为v1，v2，vn。将这n种物品装到容量都为V的若干箱子里。约定这n种物品的体积均不超过V，即对于1i

19、n，有0<viV。不同的装箱方案所需要的箱子数目可能不同，装箱问题要求使装尽这n种物品的箱子数要少。设n件物品的体积已按从大到小排好序，即有：v1v2vn。装箱算法简单描述如下： 输入箱子的容积；输入物品种数n；按体积从大到小顺序，输入各物品的体积；预置已用箱子链为空；预置已用箱子计数器box_count为0；for(i=1；i<=n；i+) /物品i按以下步骤装箱从已用的第一只箱子开始，顺序寻找能放入物品i的箱子j；if(已用箱子都不能再放物品i) 另用一只箱子，并将物品i放入该箱子；box_count+；else 将物品i放入箱子j；以下程序是按照以上算法编写的，请在划线的空白

20、处填入适当的语句以完成该程序，并举例说明该算法未必能够找到最优解。#include<stdio.h>#include<stdlib.h>typedef struct ele /物品结构信息int vno ； /物品号struct ele *link； /另一物品的指针ele；typedef struct hnode int remainder； /箱子尚剩空间ele *head； /箱内物品链的头结点指针struct hnode *next /箱子链的后继箱子指针hnode；void main() int n，i，box_count，box_volume，*a；hnod

21、e *box_h，*box_t，*j；ele *p，*q；printf(“输入箱子容积n”)；scanf(“%d”，&box_volume)；printf(“输入物品种数n”)；scanf(“%d”，&n)；a=(int )malloc(sizeof(int)*n)； /存储物品体积信息的数组printf(“请按体积从大到小顺序输入各物品的体积：”)；for(i=1；i<=n；i+) scanf(“%d”，ai)；box_h = box_t = null； /预置已用箱子链为空。/box_h 指向已用箱子链的第一个结点，/box_t则指向已用箱子链的最后一个结点。box_

22、count = 0； /预置已用箱子计数器box_count为0for(i=1；i<=n；i+) /物品i按以下步骤装箱。/从第一只箱子开始顺序寻找能放入物品i的箱子jp=(ele *)malloc(sizeof(ele)； /生成一个物品结点存放物品ipvno=i；for(j=box_h；j!=null；j=jnext) /j是已经放了某些物品的箱子号。if( ) break； /找还可装物品i的箱子jif(j=null) /所有已用的箱子中都不能放物品ij=( hnode *)malloc(sizeof(hnode)； /生成一个新的箱子结点jjremainder= ； /修改箱子j

23、的剩余容量jhead=null；jnext = null；if(box_h=null) box_h = box_t = j； /尚没有已经使用的箱子else ； /将箱子j加入到已用箱子链中box_count+；else ； /将物品i放入箱子jfor(q=jhead；q!=null && qlink!=null；q=qlink)；if(q=null) /新启用的箱子plink=jhead；jhead=p； /p结点是箱子结点j中的第一个物品结点else plink=null；qlink=p； /将p结点插入到箱子结点j的物品链中的最后/for/输出使用的箱子数及每个箱子中的全

24、部物品与剩余容量printf(“共使用%d只箱子。”，box_count)；printf(“各箱子装物品情况如下：”)；for(j=box_h，i=1；j!=null；j=jnext，i+) /第i只箱子情况 printf(“第%2d只箱子，还剩余容积%4d，所装物品有:n”，i，jremainder)； for(p=jhead；p!=null；p=plink) printf(“%4d”，pvno)； /输出物品的编号printf(“n”)；remainderheadnextbox_hremainderheadnextremainderheadnextvnolinkvnolinkvnolink

25、box_tvnolinkvnolinkvnolink所确定的数据结构如下:20.用回溯法求8-皇后问题的算法描述如下： n=8； m=0； /从空配置开始 good=1； /空配置中皇后不相互捕捉do /循环找解if(good)if(m=n) /找到了一个解输出解；回溯，改变上一个m的选值，形成下一个候选解； else 扩展当前候选解至下一列，修改m的值；else回溯，改变上一个m的选值，形成下一个候选解；good = 检查当前候选解的合理性；while(m!0)；为了程序实现方便，约定第i行上的皇后的编号为i(1i8)。可以引入一个一维数组col作为该问题的数据结构。colj表示在棋盘第j列

26、、colj行上有一个皇后，该皇后也确定了两条斜线上有皇后。为了使程序在找到全部解后能够回溯到最初位置，设定col0=0。当回溯到第0列时，说明程序已经求得全部解或无解，结束程序的执行。为了使程序在检查皇后配置的合理性方面简易方便，引入以下三个工作数组：数组a，ak表示第k行上还没有皇后；数组b，bt表示第k条右高左低的斜线上没有皇后，k=行号+列号，且同一右高左低的斜线上的方格，它们的行号与列号之和均相同；数组c，ct表示第k条左高右低的斜线上没有皇后，k=n+列号-行号，且同一左高右低的斜线上的方格，它们的行号与列号之差均相同。初始时，所有的行和斜线上均没有皇后，从第1列的第1行开始配置第1

27、个皇后。假设已经在第m列、colm行上放置了一个合理的皇后，即在数组a，b，c中为第m列、colm行的位置设定有皇后标志。下一步准备考察在第m+1列放置皇后。当从第m列回溯到m-1列(为该列重新配置皇后)时，应清除数组a，b，c中已经设置的关于第m-1列、第colm-1行有皇后的标志。一个皇后在m列，colm行的方格内的配置是合理的，等价于数组a，b，c中的对应分量都为1。详细程序如下，请在划线的空白处填入适当的语句以完成该程序。#include<stdio.h>#include<stdlib.h>#define maxn 8int n，m，good；int colma

28、xn+1，amaxn+1；int b2*maxn+1，c2*maxn+1；void main() int j；char awn；int n=8；for(j=0；j<=n；j+) aj=1； /初始化数组afor(j=0；j<=2*n；j+) bj=cj=1； /初始化数组b和cm=l； col1=1； ok=1； col0=0；while(m!=0) /循环找解if(good) if( ) /找到一个解printf(“列t行”)；for(j=1; j<=n; j+)printf(“%3dt%dn”，j，colj)；printf(“Enter a character(Q/q f

29、or exit)!n”)；scanf(“%c”，&awn)；if(awn=Q|awn=q) exit(0)；while(colm=n) /当最后一行已经合理地配置了皇后时，/改变上1列的配置，求更多的解m-； /回溯 ； /清除关于第m列，第colm行的有皇后标志/whilecolm+； /调整第m列的皇后配置，在当前行的下1行上配置皇后else /在第m列，colm行位置设定有皇后标志a colm = b m+colm = c n+m-colm = 0；col+m=1； /尝试第m+1列，从第1行开始配置else /配置没有成功，回溯调整while(colm=n) /回溯m-； ；/

30、清除关于第m列，第colm行的有皇后标志。colm+； /调整第m列的皇后配置，在当前行的下1行上配置皇后good = a colm && && ；/while21.找出从自然数1，2，n中任取r个数的所有组合。例如n=5，r=3，所有组合为：1 2 31 2 41 2 51 3 41 3 51 4 52 3 42 3 52 4 53 4 5采用回溯法找问题的解，将找到的组合以从小到大顺序存于a0，a1，ar-1中，组合的元素满足以下性质：(1) ai+1>ai，即后一个数字比前数字一个大；(2) ai-i<=n-r+1。按回溯算法思想，找解过程可以

31、叙述如下：首先放弃组合数个数为r的条件，候选组合从只有一个数字1开始。因该候选解满足除问题规模之外的全部条件，扩大其规模，并使其满足上述条件(1)，候选组合改为1，2。继续这一过程，得到候选组合1，2，3。该候选解满足包括问题规模在内的全部要求，因而是一个解。在该解基础上，选下一个候选解，因a2上的3调整为4，以及以后再调整为5，都满足问题的全部要求，得到解1，2，4和1，2，5。由于对5不能再作调整，就要从a2回溯至a1，这时的a1=2，可以调整为3，并向前试探，得到解1，3，4。重复上述向前试探和向后回溯，直至要从a0再回溯时，说明已找完问题的全部解。按上述思想写成程序如下：#includ

32、e<stdio.h>#define MAXN 100int aMAXN；void comb_back(int m，int r) int i，j；i=0；ai=1；doif( ) /还可以向前试探if(i=r-l) /已找到一个组合fot(j=0；j<r；j+) printf(“%4d”，aj)；printf(“n”)； ； /找下一个组合continue ； ； /向前试探ai=ai-1+1；else /回溯if(i=0) return； /已找完了全部 ； /继续找下一个解while(1)；void main() comb_back(5，3)；填写空白处的语句,完成该算法。

33、22.马的遍历问题。在 8×8方格的棋盘上，从任意指定的方格出发，为马寻找一条走遍棋盘每一格并且只经过一次的一条路径。马在某个方格，可以在一步内到达的不同位置最多有8个，如图9.4所示。如用二维数组board表示棋盘，其元素记录马经过该位置时的步骤号。另对马的8种可能走法(称为着法)设定一个顺序，如当前位置在棋盘的(i,j)方格，下一个可能位置依次为(i+2,j+1)，(i+1,j+2)，(i-1,j+2)，(i-2,j+1)，(i-2,j-l)，(i-1,i-2)，(i+1,j-2)，(i+2,j-l)，实际可以走的位置尽限于还未走过的和不越出棋盘边界的那些位置。为便于程序统一处理

34、，可引人两个数组，分别存储各种可能走法对当前位置的纵横增量。4352马6170图 马走一步着法示意图用贪婪法求解该问题的方法：选择下一出口的贪婪标准是在那些允许走的位置中，选择出口最少的那个位置。如马的当前位置(i,j)只有三个出口，它们是位置(i+2,j+l)，(i-2,j+l)和(i-1,j-2)，如分别走到这些位置，这三个位置又分别会有不同的出口，假定这三个位置的出口个数分别为4，2，3，则程序就选择出口位置(i-2,j+l)。由于程序采用的是一种贪婪法，整个找解过程是一直向前，没有回溯，所以能非常快地找到解。但是，对于某些开始位置，实际上有解，而该算法不能找到解。对于找不到解的情况，程

35、序只要改变8种可能出口的选择顺序，就能找到解。改变出口选择顺序，就是改变有相同出口时的选择标准。以下程序考虑到这种情况，引入变量start，用于控制8种可能着法的选择顺序。开始时为0，当不能找到解时，就让start增l，重新找解。按照这种思想解8马问题的算法如下：#include<stdo.h>int deltai=(2，1，-1，-2，-2，-l，1，2)；int deltaj=(1，2，2，l，-1，-2，-2，-1)；int board88；int exitn( int i，int j，int s，int a ) /求(i,j)的出口数，和各出口号存于a中，s是顺序选择着法的

36、开始序号int i1，j1，k，count；for(count=k=0 ；k<8；k+) i1 = i + deftai(s+k) % 8；j1 = j + deftaj(s+k) % 8；if(i1>=0 && i1<8 && j1>=0 && j1<8 && boardi1j1=0)acount+=(s+k) % 8；/forreturn count；/forint next(int i，int j，int s) /选下一出口，S是顺序选择着法的开始序号 int m，k，kk，min，a8，b8，

37、temp；m = exitn(i，j，s，a)； /确定(i,j)的出口个数if(m=0) return -1； /没有出口for(min=9，k=0；k<m；k+) /逐一考察各出口，出口数一定小于9temp=exitn(i+deltaiak，j+deltajak，s，b)；if(temp<min) /找出有最少出口数的出口 ； /记录最小的出口数kkak；return kk； /返回选中的着法void main() int sx，sy，i，j，step，no，start；for(sx=0；sx<8；sx+)for(sy=0；sy<8；sy+) start = 0 /

38、从0号着法开始顺序检查do for(i=0；i<8；i+)for(j=0；j<8；j+) ； /清棋盘boardsxsy=1；i=sx；j=sy；for(step=2；step<=64；step+) if(no=)=-1) break；/找出口不成功i+=deftaino； /前进一步j+=deftajno；boardij=step；if( ) break； /找到一个解start+； /最先检查的着法序号增1while(step<=64)；for(i0；i<8；i+) for(j=0；j<8；j+) printf(“%4d”，boardij)；prlntf

39、(“nn”)；scanf(“%*c”)； /键人回车，找下一个起点的解填写上述算法的空白处，完成整个算法。23. 设有n(=2k)位选手参加网球循环赛，循环赛共进行n-1天，每位选手要与其他n-l位选手赛一场，且每位选手每天赛一场，不能轮空。试按此要求用分治法为比赛安排日程。为了从2m-1位选手的比赛日程表，导出2m位选手的比赛日程表，假定只有8位选手(见图9.5)，若1至4号选手之间的比赛日程填在日程表的左上角(4行3列)，5至8号选手之间的比赛日程可填在日程表的左下角(4行3列)，而左下角的内容可由左上角对应项加上数4得到。至此，剩下的右上角(4行4列)是为编号小的1至4号选手与编号大的5至8号选手之间的比赛安排日程。如在第4天，让1至4号选手分别与5至8号选手比赛。以后各天，依次由前一天的日程安排，让5至8号选手循环轮转即可。最后，参照右上角得到右下角的比赛日程，如下图所示。由以上分析，不难得到为2m位选手安排比