算法设计与分析.习题

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

1、《算法设计与分析》习题课复杂性分析几种基本结构的算法时间频度for(inti=0;i1){if((n%2)==1)n=3*n+1;elsen=n/2;}递归算法的时间分析代入法迭代

2、法生成函数法a0+a1+a2+..+an=?递归算法的时间分析递归算法的时间分析递归算法的时间分析递归算法的非递归化树的最优着色问题给一棵树上的每个结点逐一着色，每个结点都有自己的权值，对结点着色的代价为着色的顺序乘以结点的权值。着色的规则为：当一个结点的父结点着色后，该结点才允许被着色。求对一棵树进行着色的最小代价。树的最优着色问题12345C1=1C3=1C5=4C2=2C4=2Figure-1.Atreewithfivenodes1*1+1*2+4*3+2*4+2*5=33树的最优着色问题分析问题是求解最优着色

3、顺序。着色顺序的每个局部都是一个子序列。可以证明：权值最大的结点必紧随其父结点之后被着色。金币阵列问题有m×n(m≤100，n≤100)枚金币在桌面上排成一个m行n列的金币阵列。每一枚金币或正面朝上，或背面朝上。用数字表示金币状态，0表示金币正面朝上，1表示金币背面朝上。金币阵列游戏的规则是：(1)每次可将任一行金币翻过来放在原来的位置上；(2)每次可任选2列，交换这2列金币的位置。对给定金币阵列的初始状态和目标状态，请设计算法按金币游戏规则，将金币阵列从初始状态变换到目标状态所需的最少变换次数。金币阵列问题0110

4、01100001110110000011010111011001010001110101000101011011011001100010001110000011010111半数集问题给定一个自然数n，由n开始可以依次产生半数集set(n)中的数如下。（1）n∈set(n)；（2）在n的左边加上一个自然数，但该自然数不能超过最近添加的数的一半；（3）按此规则进行处理，直到不能再添加自然数为止。例如，set(6)={6,16,26,126,36,136}。半数集set(6)中有6个元素。对于给定的自然数n，n<24

5、，计算半数集set(n)中的元素个数。半数集问题105432121211111盒子里的气球在一个长方体盒子里，有N（N≤6）个点。在其中任何一个点上放一个很小的气球，那么这个气球会一直膨胀，直到接触到其他气球或盒子的边界。必须等一个气球扩展完毕才能扩展下一个气球。问按照怎样的顺序在这N个点上放置气球，才使放置完毕后所有气球占据的总体积最大。ij闭区间覆盖问题设x1,x2,……,xn是实直线上的n个点。用固定长度的闭区间覆盖这n个点，至少需要多少个这样的固定长度闭区间?X1X2X3X4X5X6X7X8X9X1X2X3X

6、4X5X6X7X8X9分解式问题对一个大于1的正整数n，可以分解为n=x1*x2*…*xm，例如，当n=12时，共有8种不同的分解式：12=1212=6*212=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到

7、B的编辑距离，记为d(A,B)。试设计一个有效算法，对任给的2个字符串A和B，计算出它们的编辑距离d(A,B)。A=abcdB=defA=abcA=abfA=aefA=defd(A,B)=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：1、变换An为Bm；2、删除An；3、插入An+1=Bm；Ackermann函数问题找钱问题设某币值系统为(c0,c1,..ck)，c>1,k

8、≥1，要用最少的币数找出n元钱，能否用贪心算法求解？若采用贪心法求解，即先尽量找最大可用面值的货币。设最大可用面值为ct，即：ct≤n