算法设计与分析习题课.pptx

算法设计与分析习题课复杂性分析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=?递归算法的时间分析递归算法的时间分析递归算法的时间分析递归算法的非递归化树的最优着色问题n给一棵树上的每个结点逐一着色，每个结点都有自己的权值，对结点着色的代价为着色的顺序乘以结点的权值。着色的规则为：当一个结点的父结点着色后，该结点才允许被着色。n求对一棵树进行着色的最小代价。树的最优着色问题12345C1=1C3=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对给定金币阵列的初始状态和目标状态，请设计算法按金币游戏规则，将金币阵列从初始状态变换到目标状态所需的最少变换次数。金币阵列问题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对于给定的自然数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，则上式成立。，则上式成立。最优子结构性质：最优子结构性质：做出贪心选择做出贪心选择atct后，应使剩余的部分后，应使剩余的部分a0+a1+.+at-1达到最少。达到最少。程序存储问题n设有n个程序1,2,n 要存放在长度为L的磁带上。程序i存放在磁带上的长度是li，1in。n程序存储问题要求确定这n 个程序在磁带上的一个存储方案，使得能够在磁带上存储尽可能多的程序。程序存储问题磁带P1P3P5P7P9P2P4P6P8P10P6P1P3P10P5P2P8问题可形式化为：删数问题n给定n 位正整数a，去掉其中任意kn 个数字后，剩下的数字按原次序排列组成一个新的正整数。对于给定的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堆石子合并成一堆的最小总费用。数列极差问题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(x1x2.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。计算其最长递增子序列的长度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