基础算法(枚举 贪心 分治策略).ppt

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * procedure arrangment(K,N:integer); {从K号运动员起的共N员运动员单循环比赛日程表的过程} begin if n=2 then {处理只有2名运动员的情况，递归终止条件} begin A[K,0]:=K;A[K,1]:=K+1; A[K+1,0]:=K+1; A[K+1,1]:=K; end else begin arrangment(K,N div 2); arrangment(K + N div 2,N div 2); {递归分解原问题与求解子问题} for I:=K to K +(N div 2) –1 do {合并子问题的解,构造原问题的解A[I,J]} for J:=(N div 2) to N-1 do A[I,J]:=A[I+(N div 2),J-(N div 2)]; for I:=K+(N div 2) to K +N –1 do for J:=(N div 2) to N-1 do A[I,J]:=A[I-(N div 2),J-(N div 2)]; end; end; 分治的应用举例 例题5：求“逆序对”。 给定一整数数组A=(A1,A2,…An), 若ij且AiAj,则I,j就为一个逆序对。例如数组（3，1，4，5，2）的逆序对有3,1,3,2,4,2,5,2。问题是，输入n和A数组，统计逆序对数目。 1=n=30000。 分析 原始的解决方案（双重循环） C:=0; For i:=1 to n -1 do for j:=i+1 to n do if a[i]a[j] then c:=c+1; 时间复杂度为O(n2) 分析 采用二分法求解: 记数列a[st,ed]的逆序对数目为D(st,ed);mid=[(st+ed)/2],则有： D(st,ed)=D(st,mid)+D(mid+1,ed)+F(st.mid,ed). 其中F(st,mid,ed)表示一个数取自A[st,mid],令一个数取自A[mid+1,ed]的逆序对数目。 分析 若要求计算d值的同时数列A已排序，设I,j指针分别已排序的A[st,med)和A(mid+1,ed)中的一个元素，若满足： A[mid+1],…A[j-1]均小于A[i],但A[j]A[i] 则j-mid-1必须计入F，顺序移动I,j指针即可完成合并。 * * * * * * * * * * * * * * * * * * * * * * * * * * * 归纳策略的应用 上述算法从数学意义上来说，是一定可以出得出正确解的。但是该算法疏漏了一个重要条件 ── 1≤k≤109 。如果K值超过105，上述算法不可能在限定的15秒内出解。 归纳策略的应用 【分析】方法二 分析小数据会发现：m,n是Fibonacci数列的相邻两项。 因为： （n 2－mn－m2）2 ＝1 故： （ m2 + mn－ n 2 ）2 ＝1 又： m 2＋mn－n2＝(m＋n)2－mn－2n2 ＝(m＋n)2－(m＋n)n－n2 故： （m2＋mn－n2）2＝[(m＋n)2－(m＋n)n－n2]2 即： （n2－mn－m2）2＝[(m＋n)2－(m＋n)n－n2]2 归纳策略的应用 【分析】由上述数学变换式可以得出，如果m和n为一组满足条件①和条件②的解，设n’＝m＋n，m ’＝n那么n’，m ’也是一组满足条件①和条件②的一组解。 将所有满足条件①和条件②的m和n 按递增顺序排成一个Fibomacci数列 ｛1，1，2，3，5，8，……｝ 数列中小于k的最大两个相邻数即为试题所要求的一组m和n。 算法：利用Fibomacci数列顺推m,n，求出在条件范围内的m,n最大值，此时m2＋n2的值最大。 归纳策略的应用 例题4：“王”棋子遍历问题。 题目大意：在n×n格（2＜＝n=20）棋盘上的任一格子中放置一个棋子，棋子每次只能往其上、下、左、右相邻方格移动一步，求一种遍历方法，使得棋子走n2-1