算法设计与分析自学指导书

--1111《算法设计与分析》自学指导书习题一、填空题：20n，4n2，logn，3n，2，n2/3，n!，2n。2分治法的根本思想是将一个规模为n的问题分解为与原问题 /不一样〕的k个规模较小且 〔相互独立/相关〕的子问题。3、一个直接或间接地调用自身的算法称为 个条件，一个是要直接或间接地调用自身，另一个是必需有 。4、在一个n×n〔n=2k〕个方格组成的特别棋盘中，需要 牌完成棋盘掩盖。5在循环赛日程表问题中假设给定的运发动数则至少需要 天完成竞赛；n=2k时，则需要 天。其中，k为自然数。6、动态规划算法的主要步骤包括刻画最优解的性质和构造、递归定义最优值、了最优解的性质和构造之后，一个比较至关重要的步骤是给出最优值的递归定义，请给出下面几个问题的最优值的递归定义：矩阵连乘积问题中，A[i：j]连乘所需的最少乘法次数定义为m[i，j]〔1≤i≤j≤n，m[i，j]的初始值定义为0〔i=j，则m[i，j递归定义为：m[i，j]= c[i，j]XiYj的最长公共子序列的长c[i，j]可递归定义为：0 i0,j0c[i,j]_ _

i,j0;xyi ji,j0;xyi j7、在使用回溯法考虑求解一个具体问题时，往往需要设计出约束条件和限界条件装载问题的约束条件是 是当前最优值，cw= ，r= 。uProfitProfit，另rProfit 获得。二、求解题：1、请用快速排序法升序排序下面实例，。〔3，20，5，9，2，30，25，18，16，3〕20，请建立其。--22223法求下面网络的最短路：62 5 54 6 81 8 4 9 75 5 9 43 7 6T(1)=1，a、b、ca=b=c=1。〔1〕T(n)=aT(n-1)+bn〔2〕T(n)=aT(n/2)+bnc50-1背包问题如下：n=，c=2，P=〔1，8，15，18，12，6，W〔5，3，2，10，4，2试分别画出用回溯法或优先队列式分支限界法求解时的搜寻状况。6、有如下城市网络图：115 7 235 22 43 44 31试分别画出用回溯法或优先队列式分支限界法求解时的搜寻状况。三、证明题：1、T(n2/2r)=nT(n)+bn2〔其中r=0，T(2)=2〕则T(n)=O(n(logn)rloglogn)。2Johnson算法是满足Johnson法则的最优调度。其中：流水作业调度问题的Johnson算法是：i〔1〕令N1={i|ai<bi}，N2={i|a≥bi}；i将N1中的作业按ai非减序排序，将N2中的作业按bi非增序排列；N1中的作业接N2中的作业就构成满足Johnson法则的最优调度。满足Johnson法则的调度是最优调度，调度π满足Johnson法则，当且仅当对任意i<j，有min{b ，a }≥min{b ，a }π(i)

π(j)

π(j)

π(i)30-1背包问题中，各物品依重量递增排列时，其价值恰好依递减序排列，则用贪心算法可以找出其最优解。四、选作题：1n分钱的问题。51分四种硬币面值时，设计一个贪心n分钱，并证明算法能够产生一个最优解。〔2〕0cc>，--3333k≥1。证明在这种状况下贪心算法总能产生最优解。〔3〕给出一个贪心算法不能产生最优解的硬币面值组合。2、设G是一个有n个顶点的有向图，从顶点i动身的边的最小费用记为min(i)，证明图G 的所有前缀为x[1..i]的旅行售货员回路的费用至少为ij2

，x1

nji

minxj

3n堆石子，现要将石子有次序地合并成一堆。并分析算法的计算简单性。习题答案一、填空题1、2lognn2/320n40n22n3nn!2、一样相互独立3、递归算法初始条件或非递归定义的初始值4〔4k-1〕/3或(n2-1)/35、n2k-1n-1或k-1 6、minikj

k]m[k1,p

ppi1 k

ijc[i1,j1]1max 7、k xwCi ii1k xcii1nwiik18〔一般〕背包贪心方法或按单位重量价值降序排序后选择物品直到装满背包二、求解题1、２３３９５3025181620２３↑５９3025181620--4444↑202518163018162025↑1618↑结果：２３３５９16182025302〔动态规划算法〕 0 ijm[i,j]w minm[i,k1]m[k1,j]ij ij

ikjw aij

i1jbkki

ak的概率,其中0in且x ,x i i i1 0 n1b是xxj

j

m[1,8]=2.1,k=5,w18=1m[1,4]=0.75,k=2,w14=0.45M[1,1]=0.1 m[3,4]=0.2,k=4,w34=0.15m[3,3]=0.050e

m[6,8]=0.35,k=7,w68=0.25m[6,6]=0.05 m[8,8]=0.05b ga d f hc3〔动态规划算法〕

ijmi,j

ikjjjm,s1234567i184,15,18,1 10,2 12,3 15,5--55556,26,215,411,56,26,215,411,55,313,47,311,688,49,49,4885,584,63 84567 8最短路：1→2→5→74、a=b=c=1 TnTn1n123...nn

n12

On2 TnTnn12212k2k112n1On其中n 2 5、最优值：53，最优解：bestx=〔0，1，1，1，1，0〕6、最优值：10，最优解：bestx=〔1，2，5，4，3〕或〔1，3，4，5，2〕三、证明题1、T22T42T2b44b4……n

nT n

b nnbn...bnkbn相加，其中n22k即kloglogn=n+bnloglogn=〔bloglogn+1〕n=O〔nloglogn〕2i<j，分别证明：1〕当i,jN1时，满足Johnson不等式；2〕当i,jN2时，满足Johnson不等式；3〕当iN1,jN2时，满足Johnson不等式3、分别证明：贪心选择性质；最优子构造性质四、选作题--