算法1_48255.doc

1算法是指解决问题的方法或过程。是一系列将问题的输入转换为输出的计算或操作步骤。2程序是算法用某种程序设计语言的具体实现 3算法一般特征：1有穷性，算法必须在执行有穷步后终止,且每一步均在有限时间内完成 2确定性，算法必须在执行有穷步后终止,且每一步均在有限时间内完成 3能行性，算法中的每个步骤是能够实现的,算法执行结果要达到预期目的 4有0个或多个输入项，至少有一个输入项 算法的三个要素算法的复杂性:算法执行所需的时间和空间的数量.显然,它与问题的规模,算法的输入数据及算法本身有关. 其中DN是规模为N的合法输入的集合；I*是DN中使T(N, I*) 达到Tmax(N)的合法输入； I~ 是中使T(N, I~ )达到Tmin(N)的合法 输入；而P(I)是在算法的应用中出现输入I的概率。 直接或间接地调用自身的算法称为递归算法。用函数自身给出定义的函数称为递归函数。 7.分治法的基本思想时将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同。递归地解这些子问题，然后将各个子问题的解合并得到原问题的解。 8.二分有哪些信誉好的足球投注网站算法的基本思想：将n个元素分成个数大致相同的两半，去a[n/2]与x比较，如果x=a[n/2],则找到x，算法终止。如果xa[n/2]，则只要在数组a的左半部继续有哪些信誉好的足球投注网站x。如果xa[n/2]，则只要在数组a的右半部继续有哪些信誉好的足球投注网站x 复杂度o(logn) 9.合并排序基本思想：将待排序元素分成大小大致相同的2个子集合，分别对2个子集合进行排序，最终将排好序的子集合合并成为所要求的排好序的集合。 10循环赛日程表：按分治策略，可以将所有的选手分为两半，n个选手的比赛日程表就可以通过为n/2个选手设计的比赛日程表来决定。递归地用这种一分为二的策略对选手进行划分，直到只剩下2个选手时，比赛日程表的制定就变得很简单。这时只要让这2个选手进行比赛就可以了。 11.最优化原理：一个最优策略的子策略，对于它的初态和终态而言也必须是最优的 12.分治法与动态规划法的）） 由0-1背包问题的最优子结构性质，可以建立计算m(i，j)的递归式如下 18贪心算法基本思想：将问题的求解过程看作是一系列选择,每次选择一个输入,每次选择都是当前状态下的最好选择(局部最优解).每作一次选择后,所求问题会简化为一个规模更小的子问题.从而通过每一步的最优解逐步达到整体的最优解。 贪心算法（自顶向下）与动态规划算法（自底向上）的主要区别：动态算法依赖于相关子问题的解，求出相关子问题后，才能做出选择。而贪心算法，仅在当前状态下做出最好选择，只依赖以往做过的选择。贪心选择性是所求问题的整体最优解可以通过一系列局部最优的选择来达到。 共同点：都具有最优子结构性质 贪心算法基本要素：1贪心选择性质：所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。2最优子结构性质：一个问题的最优解包含其子问题的最优解 单源最短路径：设置顶点集合S并不断地做贪心选择来扩充这个集合。一个顶点属于S当且仅当从源到该顶点的最短路径长度已知。开始时，S中只有源。设u是G的某一个顶点，把从源到u且中间只经过S中顶点的路称为从源到u的特殊路径，并用数组dist记录当前每个顶点所对应的最短特殊路径长度。算法每次从V-S中取出具有最短特殊路径长度的顶点u，将u添加到S中，同时对数组dist进行必要的修改。如果S包含了所有V中顶点，dist就记录了从源到所有其他顶点之间的最短路径长度。 22最小生成树： prim算法思路: 首先置S={1}, T= ? .若S是V的真子集, 就作如下的贪心选择： 选取满足条件i∈S, j∈V-S,且c[i][j]最小的边(i, j),将顶点j添加到S中边(i, j)添加到T中.这个过程一直进行到S=V时为止. T中的所有边构成G的一棵最小生成树。 void Prim(int n, Type * * c) { T= ?; S ={1}; while (S!= V) { (i, j) = i∈S且 j∈V- S的最小权边; T=TU{(i,j)}; S= S U{j}; } } Kruskal算法思路：首先将G的n个顶点看成n个孤立的连通分支, 将所有的边按权从小到大排序,然后从第一条边开始, 依边权递增的顺序查看每一条边，并按下述方法连接两个不同的连通分支：当查看到第k条边(v,w)时, 如果端点v和w分别是当前两个不同的连通分支T1, T2中的顶点时,就用边(v,w)将TI和T2连接成一个