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

《算法设计与分析.习题课.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、《算法设计与分析》习题课复杂性分析几种基本结构的算法时间频度for(inti=0;i

2、set(n)中的数如下。（1）n∈set(n)；（2）在n的左边加上一个自然数，但该自然数不能超过最近添加的数的一半；（3）按此规则进行处理，直到不能再添加自然数为止。例如，set(6)={6,16,26,126,36,136}。半数集set(6)中有6个元素。对于给定的自然数n，计算半数集set(n)中的元素个数。半数集问题105432121211111闭区间覆盖问题设x1,x2,……,xn是实直线上的n个点。用固定长度的闭区间覆盖这n个点，至少需要多少个这样的固定长度闭区间?X1X2X3X4X5X6X7X8X9编辑距离问题设A和B是2个字符串

3、。要用最少的字符操作将字符串A转换为字符串B。这里所说的字符操作包括(1)删除一个字符；(2)插入一个字符；(3)将一个字符改为另一个字符。将字符串A变换为字符串B所用的最少字符操作数称为字符串A到B的编辑距离，记为d(A,B)。试设计一个有效算法，对任给的2个字符串A和B，计算出它们的编辑距离d(A,B)。例如，若A=“abcd”，B=“def”，则编辑距离为4。编辑距离问题设:A=(A1,A2,…,An)B=(B1,B2,…,Bm)若An=Bm，则d(A1..n,B1..m)=d(A1..n-1,B1..m-1)否则，可以通过三种操作将A变换为B：

4、1、变换An为Bm；2、删除An；3、插入An+1=Bm；找钱问题设某币值系统为(c0,c1,..ck)，c>1,k≥1，要用最少的币数找出n元钱，能否用贪心算法求解？若采用贪心法求解，即先尽量找最大可用面值的货币。设最大可用面值为ct，即：ct≤n

5、a1+..+at-1达到最少。程序存储问题设有n个程序{1,2,…,n}要存放在长度为L的磁带上。程序i存放在磁带上的长度是li，1≤i≤n。程序存储问题要求确定这n个程序在磁带上的一个存储方案，使得能够在磁带上存储尽可能多的程序。删数问题给定n位正整数a，去掉其中任意k≤n个数字后，剩下的数字按原次序排列组成一个新的正整数。对于给定的n位正整数a和正整数k，设计一个算法找出剩下数字组成的新数最小的删数方案。例如，n=178543，k=4，则结果为13。删数问题设X=X1X2..Xi-1XiXi+1..Xn若X1Xi+

6、1可证明，删除Xi是可得到的最小的数。石子合并问题在一个操场的四周摆放着n堆石子。现要将石子有次序地合并成一堆。规定每次只能选2堆石子合并成新的一堆，合并的费用为新的一堆的石子数。试设计一个算法，计算出将n堆石子合并成一堆的最小总费用。数列极差问题对由N(N<2000)个正数组成的一个数列，进行如下操作：每一次删去其中2个数设为a和b，然后在数列中加入一个数a*b+1，如此下去直至只剩下一个数。在所有按这种操作方式最后得到的数中，最大的数记为max，最小的数记为min，则该数列的极差M定义为M=max-min。例如，若数列为(1,2,3)，则极差为10

7、-8=2。数字三角形问题给定一个由n行数字组成的数字三角形如下图所示。试设计一个算法，计算出从三角形的顶至底的一条路径，使该路径经过的数字总和最大。738810274445265整数变换问题整数变换问题。关于整数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

8、=2。设mi表示以Xi为结尾的最大递增子序列的长度。则：mi=1+max{0,mk

9、xk