《算法设计与分析.习题.ppt》由会员分享，可在线阅读，更多相关《算法设计与分析.习题.ppt（40页珍藏版）》请在三一办公上搜索。
1、算法设计与分析习题课,复杂性分析,几种基本结构的算法时间频度,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;jn;j+)S();,T(n)=n=O(n),T(n)=n2=O(n2),T(n)=n(n+1)/2=O(n2),复杂性分析,3n+1猜想请分析此算法的计算时间下界。,while(n1)if(n%2)=1)n=3*n+1;else n=n/2;,递归算法的时间分析,代入法迭代法生成函数法a0+a1+a2+.+an=?,递归算法的时间分析,递归算法的
2、时间分析,递归算法的时间分析,递归算法的非递归化,树的最优着色问题,给一棵树上的每个结点逐一着色，每个结点都有自己的权值，对结点着色的代价为着色的顺序乘以结点的权值。着色的规则为：当一个结点的父结点着色后，该结点才允许被着色。求对一棵树进行着色的最小代价。,树的最优着色问题,1*1+1*2+4*3+2*4+2*5=33,树的最优着色问题,分析问题是求解最优着色顺序。着色顺序的每个局部都是一个子序列。可以证明：权值最大的结点必紧随其父结点之后被着色。,金币阵列问题,有mn(m100，n100)枚金币在桌面上排成一个m行n列的金币阵列。每一枚金币或正面朝上，或背面朝上。用数字表示金币状态，0表示金
3、币正面朝上，1表示金币背面朝上。金币阵列游戏的规则是：(1)每次可将任一行金币翻过来放在原来的位置上；(2)每次可任选2列，交换这2列金币的位置。对给定金币阵列的初始状态和目标状态，请设计算法按金币游戏规则，将金币阵列从初始状态变换到目标状态所需的最少变换次数。,金币阵列问题,半数集问题,给定一个自然数n，由n开始可以依次产生半数集set(n)中的数如下。（1）nset(n)；（2）在n的左边加上一个自然数，但该自然数不能超过最近添加的数的一半；（3）按此规则进行处理，直到不能再添加自然数为止。例如，set(6)=6,16,26,126,36,136。半数集set(6)中有6个元素。对于给定的
4、自然数n，n24，计算半数集set(n)中的元素个数。,半数集问题,盒子里的气球,在一个长方体盒子里，有N（N6）个点。在其中任何一个点上放一个很小的气球，那么这个气球会一直膨胀，直到接触到其他气球或盒子的边界。必须等一个气球扩展完毕才能扩展下一个气球。问按照怎样的顺序在这N个点上放置气球，才使放置完毕后所有气球占据的总体积最大。,i,j,闭区间覆盖问题,设x1,x2,xn是实直线上的n个点。用固定长度的闭区间覆盖这n个点，至少需要多少个这样的固定长度闭区间?,分解式问题,对一个大于1的正整数n，可以分解为n=x1*x2*xm，例如，当n=12时，共有8种不同的分解式：12=1212=6*21
5、2=4*312=3*412=3*2*212=2*612=2*3*212=2*2*3请编写算法计算给定的正整数n共有多少种不同的分解式。,编辑距离问题,设A和B是2个字符串。要用最少的字符操作将字符串A转换为字符串B。这里所说的字符操作包括(1)删除一个字符；(2)插入一个字符；(3)将一个字符改为另一个字符。将字符串A变换为字符串B所用的最少字符操作数称为字符串A到B的编辑距离，记为d(A,B)。试设计一个有效算法，对任给的2个字符串A和B，计算出它们的编辑距离d(A,B)。,A=abcd,B=def,A=abc,A=abf,A=aef,A=def,d(A,B)=4,编辑距离问题,设:A=(A
6、1,A2,An)B=(B1,B2,Bm),若An=Bm，则d(A1.n,B1.m)=d(A1.n-1,B1.m-1),否则，可以通过三种操作将A变换为B：1、变换An为Bm；2、删除An；3、插入An+1=Bm；,Ackermann函数问题,找钱问题,设某币值系统为(c0,c1,.ck)，c1,k1，要用最少的币数找出n元钱，能否用贪心算法求解？,若采用贪心法求解，即先尽量找最大可用面值的货币。设最大可用面值为ct，即：ctnct+1，tk或ctn，t=k。设从c0到ct，各种面值的货币各找了ai个，即：a0c0+a1c1+.+atct=n，求解目标为ai最少。,贪心选择性质：所做的贪心选择为
7、：atctn(at+1)ct即：a0c0+a1c1+.+at-1ct-1ct不难证明：aic，则上式成立。,最优子结构性质：做出贪心选择atct后，应使剩余的部分a0+a1+.+at-1达到最少。,程序存储问题,设有n个程序1,2,n 要存放在长度为L的磁带上。程序i存放在磁带上的长度是li，1in。程序存储问题要求确定这n 个程序在磁带上的一个存储方案，使得能够在磁带上存储尽可能多的程序。,程序存储问题,磁带,P1,P3,P5,P7,P9,P2,P4,P6,P8,P10,P6,P1,P3,P10,P5,P2,P8,问题可形式化为：,删数问题,给定n 位正整数a，去掉其中任意kn 个数字后，剩
8、下的数字按原次序排列组成一个新的正整数。对于给定的n位正整数a 和正整数k，设计一个算法找出剩下数字组成的新数最小的删数方案。例如，n=178543，k=4，则结果为13。,删数问题,方法一：12354,可证明，删除Xi是可得到的最小的数。,重复以上过程k次，得到结果。,由以上性质易知，不须重新从头开始搜索。,删数问题,方法二：,可以证明，在前k+1个数中，必有数被保留，且前k+1个数中的最小值前面的数应删去。,石子合并问题,在一个操场的四周摆放着n 堆石子。现要将石子有次序地合并成一堆。规定每次只能选2 堆石子合并成新的一堆，合并的费用为新的一堆的石子数。试设计一个算法，计算出将n堆石子合并
9、成一堆的最小总费用。,数列极差问题,对由N(N2000)个正数组成的一个数列，进行如下操作：每一次删去其中2 个数设为a和b，然后在数列中加入一个数a*b+1，如此下去直至只剩下一个数。在所有按这种操作方式最后得到的数中，最大的数记为max，最小的数记为min，则该数列的极差M 定义为M=max-min。例如，若数列为(1,2,3)，则极差为10-8=2。,数列极差问题,可证明：每次删去数列中的两个最小的数，最后结果最大；每次删去数列中的两个最大的数，最后结果最小。,当n=3时，设a(a*c+1)*b+1(b*c+1)*a+1,数列极差问题,设对n-1，贪心策略成立，即：对于x1,x2,x3,
10、.,xn(x1x2.xn)这n个数，对于其中任意选择的n-1个数均可以通过贪心策略得到其相应选择的n-1个数的最优解。,设x1,x2.xi-1,xi+1xn对应的最优解为Mi，只要证明max(Mi*xi+1)=Mn*xn+1即可。,数列极差问题,Mi*xi+1=(x1x2+1)x3+1).+1)xi-1+1)xi+1+1).+1)xn+1)xi+1=x1x2x3xn+x3x4x5xn+x4x5x6.xn+.+(xi+1xi+2xn+.+xn+1)xi+1,Mi+1xi+1+1=(x1x2+1)x3+1).+1)xi-1+1)xi+1)xi+2+1).+1)xn+1)xi+1=x1x2x3xn+
11、x3x4x5xn+x4x5x6xn+.+xixi+1xi+2xn+(xi+2xi+3xn+.+xn+1)xi+1+1,易证：Mi+1xi+1+1Mixi+1,数字三角形问题,给定一个由n行数字组成的数字三角形如下图所示。试设计一个算法，计算出从三角形的顶至底的一条路径，使该路径经过的数字总和最大。,整数变换问题,整数变换问题。关于整数i的变换f和g定义如下：f(i)=3i；g(i)=i/2。试设计一个算法，对于给定的2个整数n和m，用最少的f和g变换次数将n变换为m。例如，可以将整数15 用4 次变换将它变换为整数4：4=gfgg(15)。,整数变换问题,最长递增子序列问题,给定正整数序列x1,x2,xn。计算其最长递增子序列的长度s。例如，若序列为(3,6,2,5)，则s=2。,设mi表示以Xi为结尾的最大递增子序列的长度。,则：mi=1+max0,mk|xkxi,1ki,最优服务次序问题,设有n 个顾客同时等待一项服务。顾客i需要的服务时间为ti，1in，应如何安排n 个顾客的服务次序才能使平均等待时间达到最小？平均等待时间是n 个顾客等待服务时间的总和除以n。,最小重量机器设计问题,设某一机器由n个部件组成，每一种部件都可以从m个不同的供应商处购得。设计算法，给出总价格不超过c的最小重量机器设计。,
