算法设计与分析习题课课件.ppt

1、算法设计与分析习题课复杂性分析n几种基本结构的算法时间频度for(int i=0;in;i+)S();for(int i=0;in;i+)for(int j=0;jn;j+)S();for(int i=0;in;i+)for(int j=i;j1)if(n%2)=1)n=3*n+1;else n=n/2;递归算法的时间分析n代入法n迭代法n生成函数法na0+a1+a2+.+an=?nkka0101:nnnkknfafaf即记0)(:nnnzfzg定义生成函数1101)(:nnnnnnzfazfazgza则010)()1(nnnnzzfzgaz递归算法的时间分析111)(lim:0axaxaxn

2、iin由zznn110azBzAazzzg11)1)(1(1)(aaBaA1,11:由待定系数法可求得递归算法的时间分析000)(11,11:)(limnnnnniinazazzzax 得又由0)()(nnnzaBAzg111111aaaaaaaBAfnnnn递归算法的时间分析递归算法的非递归化1,1),1()1,(11),(nmnmfnmfmnnmnmf树的最优着色问题n给一棵树上的每个结点逐一着色，每个结点都有自己的权值，对结点着色的代价为着色的顺序乘以结点的权值。着色的规则为：当一个结点的父结点着色后，该结点才允许被着色。n求对一棵树进行着色的最小代价。树的最优着色问题12345C1=1

3、C3=1C5=4C2=2C4=2Figure-1.A tree with five nodes1*1+1*2+4*3+2*4+2*5=33树的最优着色问题n分析n问题是求解最优着色顺序。n着色顺序的每个局部都是一个子序列。n可以证明：权值最大的结点必紧随其父结点之后被着色。金币阵列问题n有mn(m100，n100)枚金币在桌面上排成一个m行n列的金币阵列。每一枚金币或正面朝上，或背面朝上。用数字表示金币状态，0表示金币正面朝上，1表示金币背面朝上。n金币阵列游戏的规则是：n(1)每次可将任一行金币翻过来放在原来的位置上；n(2)每次可任选2列，交换这2列金币的位置。n对给定金币阵列的初始状态和

4、目标状态，请设计算法按金币游戏规则，将金币阵列从初始状态变换到目标状态所需的最少变换次数。金币阵列问题011001100001110110000011010111011001010001110101000101011011011001100010001110000011010111半数集问题n给定一个自然数n，由n开始可以依次产生半数集set(n)中的数如下。（1）nset(n)；（2）在n的左边加上一个自然数，但该自然数不能超过最近添加的数的一半；（3）按此规则进行处理，直到不能再添加自然数为止。n例如，set(6)=6,16,26,126,36,136。半数集set(6)中有6个元素。n对

5、于给定的自然数n，n1,k1，要用最少的币数找出n元钱，能否用贪心算法求解？若采用贪心法求解，即先尽量找最大可用面值的货币。若采用贪心法求解，即先尽量找最大可用面值的货币。设最大可用面值为设最大可用面值为ct，即：，即：ctnct+1，tk或或ctn，t=k。设从设从c0到到ct，各种面值的货币各找了，各种面值的货币各找了ai个，即：个，即：a0c0+a1c1+.+atct=n，求解目标为，求解目标为ai最少。最少。贪心选择性质：贪心选择性质：所做的贪心选择为：所做的贪心选择为：atctn(at+1)ct即：即：a0c0+a1c1+.+at-1ct-1ct不难证明：不难证明：aic，则上式成立

6、。，则上式成立。最优子结构性质：最优子结构性质：做出贪心选择做出贪心选择atct后，应使剩余的部分后，应使剩余的部分a0+a1+.+at-1达到最少。达到最少。程序存储问题n设有n个程序1,2,n 要存放在长度为L的磁带上。程序i存放在磁带上的长度是li，1in。n程序存储问题要求确定这n 个程序在磁带上的一个存储方案，使得能够在磁带上存储尽可能多的程序。程序存储问题磁带P1P3P5P7P9P2P4P6P8P10P6P1P3P10P5P2P8LxLxxxniiiiinii11,10max或问题可形式化为：删数问题n给定n 位正整数a，去掉其中任意kn 个数字后，剩下的数字按原次序排列组成一个新

7、的正整数。对于给定的n位正整数a 和正整数k，设计一个算法找出剩下数字组成的新数最小的删数方案。n例如，n=178543，k=4，则结果为13。删数问题方法一：1235 54可证明，删除Xi是可得到的最小的数。重复以上过程k次，得到结果。由以上性质易知，不须重新从头开始搜索。删数问题方法二：可以证明，在前k+1个数中，必有数被保留，且前k+1个数中的最小值前面的数应删去。01.i.kk+1.n-1min石子合并问题n在一个操场的四周摆放着n 堆石子。现要将石子有次序地合并成一堆。规定每次只能选2 堆石子合并成新的一堆，合并的费用为新的一堆的石子数。试设计一个算法，计算出将n堆石子合并成一堆的最

8、小总费用。数列极差问题n对由N(N2000)个正数组成的一个数列，进行如下操作：每一次删去其中2 个数设为a和b，然后在数列中加入一个数a*b+1，如此下去直至只剩下一个数。在所有按这种操作方式最后得到的数中，最大的数记为max，最小的数记为min，则该数列的极差M 定义为M=max-min。n例如，若数列为(1,2,3)，则极差为10-8=2。数列极差问题n可证明：n每次删去数列中的两个最小的数，最后结果最大；n每次删去数列中的两个最大的数，最后结果最小。当n=3时，设ab(a*c+1)*b+1(b*c+1)*a+1数列极差问题设对n-1，贪心策略成立，即：对于x1,x2,x3,.,xn(x

9、1x2.Mixi+1数字三角形问题n给定一个由n行数字组成的数字三角形如下图所示。试设计一个算法，计算出从三角形的顶至底的一条路径，使该路径经过的数字总和最大。73 88 1 02 7 4 44 5 2 6 5整数变换问题n整数变换问题。关于整数i的变换f和g定义如下：f(i)=3i；g(i)=i/2。n试设计一个算法，对于给定的2个整数n和m，用最少的f和g变换次数将n变换为m。n例如，可以将整数15 用4 次变换将它变换为整数4：4=gfgg(15)。整数变换问题15745321221359110631166674054最长递增子序列问题n给定正整数序列x1,x2,xn。计算其最长递增子序

10、列的长度s。n例如，若序列为(3,6,2,5)，则s=2。设mi表示以Xi为结尾的最大递增子序列的长度。则：mi=1+max0,mk|xkxi,1ki最优服务次序问题n设有n 个顾客同时等待一项服务。顾客i需要的服务时间为ti，1in，应如何安排n 个顾客的服务次序才能使平均等待时间达到最小？平均等待时间是n 个顾客等待服务时间的总和除以n。最小重量机器设计问题n设某一机器由n个部件组成，每一种部件都可以从m个不同的供应商处购得。n设计算法，给出总价格不超过c的最小重量机器设计。供应一供应二供应三零件一零件二零件三1,12,23,33,32,21,12,22,22,2各选一种组成一台机器 c,w c,w c,w