(考研复试)计算机算法与分析笔记.doc

1：递归算法，分治法，贪心算法，动态规划，基本检索和周游方法，回溯法，并行算法。 递归2：0/1背包问题：背包最大承受重量m，现在有n个物品为质量m1,m2,m3mn，要从n个物品中挑选若干件，使放入背包的质量之和为m。（0/1的意思就是，一个物品，要么取，要么不取）一开始是mn放进容量为m的包中，如果没满，就把m1到m（n-1）放入容量为m-mn的包中，如果满了，就放弃mn，查看m（n-1）.knap（m，n），如果mn能放得进去，就进一步考虑knap（m-mn，n-1），如果mn放不进去，就考虑knap（m，n-1）2：汉诺塔问题：hanoi(n-1,one,three,two)先把n-1个盘子从1柱借助3柱移动到2柱子，move(one,three)然后把1住上还身下的第n个盘子移到3柱hanoi(n-1,two,one,three)最后把2住上的n-1块盘子借助1柱移动到3柱。3：自然数拆分：任何一个大于1的自然数都可以划分成若干个小于n的自然数之和。有n/2种拆分split（7）=1+split（6）=2+split（5）=3+split（4） 分治法4：求解一个输入规模很大的问题，直接求解很麻烦，将输入规模分成k个不同的子集合，得到k个不同可独立求解的子问题，求出这些解之后，可以找到适当的方法合并成整个问题的解。5：二分查找，二路归并，快速分类，快速排序，6：找最大和最小元素：就是把数组一分为2，选出左半边的最大值和最小值，选出右半边的最大值和最小值，然后两个最大值相比，选出最大值，然后两个最小值相比，选出最小值。maxmin（i,j,max,min）/i到j中的最大值和最小值。如果i=j，则说明max=min如果i=j-1，说明就两个数字，直接判断就是了。否则，就运行 maxmin（i，mid，max，min）和maxmin（mid=1，j，max,min）7：找出第k小的元素（并把该元素放在位置k上，并且左边的小于k，右边的大于k）：用快速分类partition（m,j），返回值是x，x是首元素被划分以后再数组中的位置，也就第x小的元素。那么再判断，如果x=k，就正确，如果x大于k，就partition(m,x)，如果x小于k，就partiotion（x+1，j）8：二次取中法：一位数组划分成多个等长的一位数组，然后分别求中间值，然后诸多中间值再求中间值。9：用二次取中法求第k小元素。先用二次取中法求得中间值，然后判断中间值是不是第k小的元素，如果不是，再对两边分别二次取中，递归。10：斯特拉森矩阵：把16*16的矩阵分块，每个矩阵里面有4个小矩阵，每个小矩阵是8*8，然后用分块矩阵相乘。 贪心算法11：现实世界中，有的问题有很多可以满足约束条件的解，这些解就叫做可行解。为了衡量这些解，我们给出目标函数，那些使目标函数取极值的可行解称之为最优解。这些问题可以用线性规划，非线性规划，动态规划等问题来解决，12：但是有些问题可以选出一种度量值，然后按照这种度量值对输入排序，然后从排序中选出最优解，这种分级处理方法就是贪心方法。13：背包问题：价值/重量 来衡量。14：带有限期的作业排序：也是先看效益值，效益值从高到低依次加入，然后判断是不是可行解。15：最优归并模式（哈夫曼树）：30 20 10 三个记录，如果先归并30和20就要移动50次，然后归并10和50移动60，一共110次。但是如果换种方法，先归并20和10，移动30次，然后归并30和30，移动60次，一共移动90次。于是就要用哈弗曼树的方法。16：最小生成树：prim方法和kruskal（克鲁斯卡尔）方法单源最短路径。 动态规划17：一个问题，活动过程可以分为若干个阶段，而且在任一阶段后的行为都仅依赖于此阶段的过程状态，与此阶段之前的过程如何达到这种状态无关，这就是多段决策过程。多段决策过程的每个阶段都可能有多重可供选择的决策，必须从中选取一种决策，一旦各个阶段的决策选定之后，就构成了解决这种问题的一个决策序列。决策序列不同导致问题结果也不同，动态规划就是要选取最优决策序列。18：最优性原理：无论过程的初始状态和初始决策是什么，其余的决策都必须相对于初始决策所产生的状态构成一个最优决策序列，这是一个递推。19：动态规划有向前处理（从最后的阶段开始，逐步向前地推的方式列出求前一阶段决策值的递推关系式）和向后处理20：多段图问题：vi中的节点j到汇点的成本=诸多l中的最小值（j到l的成本+v（i+1）中的l到汇点的成本）也就是我从重庆到江西的成本等于重庆到湖南某个市的成本加上这个市到江西的成本。比如有源点s v2 v3 v4 汇点t，向前处理法就是：先算出v4的每个点到汇点的成本，然后通过v4的每个点到汇点的成本算出v3的每个点到汇点的最小成本，依次类推。这样，v2判断的时候只需要知道v3的每个点到汇点的成本即可，与v3到v4，v4到汇点的成本不用关心。21：最优二叉排序树：定义成本概念就是成功查找和不成功查找的概率乘以权值。那么最优二叉排序树，他的两个子树也应该是最优二叉排序树。22：货郎担问题：就是求取最小成本的周游路线问题。假设是从1出发回到1，那么周游路线应该是从1