算法分析及设计习题集整理Word文档格式.docx

1、2、什么是算法？算法的特征有哪些？1）算法：指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过程。通俗讲，算法：就是解决问题的方法或过程。2）特征：1）算法有零个或多个输入；）算法有一个或多个输出； 3）确定性 ； ）有穷性3、给出算法的定义？何谓算法的复杂性？计算下例在最坏情况下的时间复杂性？j+） （1）for（i=1;i+） （2） （3） k+） （4） cij= cij+aik*bkj; （5）1）定义： 2）算法的复杂性：指的是算法在运行过程中所需要的资源（时间、空间）多少。 所需资源越多，表明算法的复杂性越高 3）该算法的主要元操作是语句5，其执行次数是n3次。 故该算

2、法的时间复杂度记为O（n3）. 4、算法A和算法B解同一问题，设算法A的时间复杂性满足递归方程，算法B的时间复杂性满足递归方程，若要使得算法A时间复杂性的阶高于算法B时间复杂性的阶，a的最大整数值可取多少？分别记算法A和算法B的时间复杂性为和，解相应的递归方程得：依题意，要求最大的整数a使得。显然，当a4时，a2写出其相应的递归算法？Int F（int n） if（n=1） return 1; else if（n=2） return 2; else return F（n-1）+ F（n-2）;2、设a,b,c是3个塔座。开始时，在塔座a上有一叠共n个圆盘，这些圆盘自下而上，由大到小地叠在一起。

3、各圆盘从小到大编号为1,2,n,现要求将塔座a上的这一叠圆盘移到塔座b上，并仍按同样顺序叠置。在移动圆盘时应遵守以下移动规则：规则1：每次只能移动1个圆盘；规则2：任何时刻都不允许将较大的圆盘压在较小的圆盘之上；规则3：在满足移动规则1和2的前提下，可将圆盘移至a,b,c中任一塔座上。写出该问题的解题步骤？第一步：将n1个盘子看成一个整体，从A移到C； 第二步：将第n个盘子移到B; 第三步：将n1个盘子看成一个整体，从C移到B；写出其相应的递归算法：void hanoi（int n, int a, int b, int c） if （n 0） hanoi（n-1, a, c, b）; move

4、（a,b）; hanoi（n-1, c, b, a）; 第二章 分治算法（2）分治算法1、在快速排序、插入排序和合并排序算法中， 插入排序 算法不是分治算法。2、合并排序算法使用的是 分治 算法设计的思想。3、二分搜索算法是利用 分治 算法思想设计的。1、适合用分治算法求解的问题具有的基本特征？1）该问题的规模缩小到一定的程度就可以容易解决;2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质； 3）该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。4）利用该问题分解出子问题解可以合并为该问题解;2、分治算法基本思想，解题步骤？三、算法设计题：1、改写

5、二分查找算法：设a1n是一个已经排好序的数组，改写二分查找算法，使得当搜索元素x不在数组中时，返回小于x的最大元素位置i，和大于x的最小元素位置j；当搜索元素x在数组中时，i和j相同，均为x在数组中的位置。 并分析其时间复杂度？int binsearch（ int an, int x ,） /x待查数据 int mid, i , j; low=1; int high=n; while（lowx） high=mid-1; /继续在左边查找 else / （amid=2）个元素的集合中寻找极大元和极小元。用分治法（二分法）可以用较少比较次数地解决上述问题：1）将数据等分为两组（两组数据可能差1），

6、目的是分别选取其中的最大（小）值。2）递归分解直到每组元素的个数2,可简单地找到最大（小）值.3）回溯时将分解的两组解大者取大，小者取小，合并为当前问题的解。 、 第三章动态规划算法1、动态规划算法中存储子问题的解是为了 避免重复求解子问题 。2、（ 最优子结构 ）是问题能用动态规划算法求解的前提。3、矩阵连乘问题的算法可由（动态规划 ）算法设计实现。1、动态规划算法基本要素的是最优子结构。2、最优子结构性质是指原问题的最优解包含其子问题的最优解。3、动态规划算法求解问题时，分解出来的子问题相互独立。 （ X）1、动态规划算法解题步骤？找出最优解的性质，并刻划其结构特征; （即原问题的最优解，

7、包含了子问题的最优解）递归地定义最优值; （即子问题具有重叠性，由子问题定义原问题）以自底向上的方式计算出最优值;根据计算最优值时得到的信息，构造最优解;2、动态规划算法基本思想？动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题；但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次；如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。3、动态规划与分治算法异同点？4、动态规划算法的基本要素？四、算法设计与计算题：1、的最长公共子序列为问：若用

8、记录序列公共子序列长度。用动态规划法求解时,计算最优值的递归公式？设计计算最优值的算法？以及构造最优解的算法？2、长江游艇俱乐部在长江上设置了n个游艇出租站1,2n.游客可在这些游艇出租站租用游艇，并在下游的任何一个游艇出租站归还游艇。游艇出租站i到游艇出租站j之间的租金为r（i，j），其中1=i=n；用动态规划法求解时,计算最优值（最少租金）的递归公式？设计计算最优值（最少租金）的算法？并分析其时间复杂度？计算最优值算法public static void matrixChain（int p, int m, int s） int n=p.length-1; for （int i = 1; i

9、 = n; i+） mii = 0; /1个站 for （int r = 2; r r+）= n - r+1; int j=i+r-1; m i j = mii + mi+1 j; s i j = i; /断点位置在i处 for （int k = i+1; k j; k+） int t = m i k + mk+1 j; if （t mij） m i j = t; s i j = k; 构造最优解算法public void traceback（ int s,int I,int j）if（i=j） return;traceback（ s, i, s i j ）;traceback（ s, s i

10、 j+1, j ）;System.out.println（“A”+ i +“，”+ s i j + “A”+ s i j+1 +“,”+ j ） /（m i, s i j ） （m s i j+1, j ）时间复杂度：O（n3）第 4 章 贪心算法1、某单位给每个职工发工资（精确到元）。为了保证不要临时兑换零钱, 且取款的张数最少，统计所需各种币值（100,50,20,10,5,2,1元共七种）的张数。贪心算法如下：void greedy_zhaoling （ float GZ, int B , int S ） /GZ应发工资 for（ j=1, j=7;j+） /贪心选择，依次给最大币种 A

11、= GZ/B j ; /A表示对应j币种张数 S j= S j +A ; /S j存放对应j币种总张数 GZ= GZ-A*B j ; print（ B i , “-”, S i ）; /输出币种和对应张数2、贪心算法的两个基本要素是（贪心选择性 ）和（ 最优子结构 ）。3、给定n种物品和一个背包。物品i的重量是Wi，其价值为Vi，背包的容量为M，应如何选择装入背包的物品，使得装入背包中物品的总价值最大。float greedy_knapsack （ float M, float w , float p , float x ） / x 背包问题最优解, w 物品重量， P 物品价值 int n=

12、w.length;float pp=0;float mmM; /pp计算当前总价值，mm背包剩余载重for（ int i=1; i+ ） float ww i= p i / w i ； /计算物品单位价值ww x i=0; /初始化Mergesort （ w , n ）; /按单位价值将物品排序， 便于贪心选择 i i+ ） /贪心选择，总是选择价值最大放入背包 if （ w i=mm ） /当前物品小于背包剩余载重 x i=1; mm= mm - w i ; pp= pp + p i ; else x i=mm/w i; pp= pp + x i*p i ; break; /i部分放入背包r

13、eturn pp;1、满足贪心选择性质必满足最优子结构性质。1、贪心算法的基本思想？2、贪心算法的基本要素？3、贪心算法与动态规划算法的异同?1、假设有7个物品，它们的重量和价值如下表所示。若这些物品均可以被分割，且背包容量M150，如果使用贪心方法求解此背包问题（背包不超载的前提下，装载的物品价值达到最大）。物品ABCDEFG重量35306050401025价值利用贪心算法求解该问题时，为了进行贪心选择，首先应该做什么？ 然后进行贪心装载，给出一种正确的物品装载顺序？并给出其最优装载方案？利用贪心思想设计该普通背包问题的贪心算法？分析其时间复杂度？ 1）依据不同的标准对这些物品进行排序，标准

14、有重量、价值、单位价值； 2）重量从小到大：FGBAEDC ,得到的贪心解为：FGBAE 全部放入,D放入20% ，得到价值为165； 价值从大到小 ：DFBEGCA ，得到的贪心解为：DFBE 全部放入,G放入80% ，得到价值为189； 单位价值从大到小 ：FBGDECA ，得到的贪心解为：FBGD 全部放入,E放入87.5% ，得到价值为190.625； 3）显然使用单位价值得出最佳转载方案。 、2、设有n个活动集合，其中每个活动都要求使用同一资源，如足球场，而在同一时间只能有一个活动使用该资源。 每个活动i都有一个要求使用该资源起始时间si和结束时间fi，且si n ） / 搜索到叶子

15、节点 sum+; /着色方案数加1 for （int i=1; system.out.print（ x i ）; /输出解,顶点i着颜色x i else / 搜索到中间节点 for（int i=1;=m; x t=i; /顶点t着颜色i=1m if（ ok（ t ） ） backtrack（t+1）;boolean ok（ int k） /当前着色顶点与以前相邻顶点是否同色 for（int j=1; j j+） if（ a k j&（ x j=x k ） ） /数组a是图的邻接矩阵 /当前顶点k到j有边：a k j，且色同：x j=x k return false; else return true;算法分析（m种颜色，n个节点） 计算限界函数，一重for循环时间复杂度：O（n）; 在最坏的情况下每一个内节点都需要判断约束，内节点个数：1+m+m2+ m3+mn-1=（mn-1）/（m-1）个；故图的m着色问题的回溯算法，时间复杂度为：O（n*mn）。第六章 分支限界算法1、按照活结点表的组织方式的不同，分支限界法