《NOIP基础算法——贪心和分治pascal说课材料》由会员分享，可在线阅读，更多相关《NOIP基础算法——贪心和分治pascal说课材料（98页珍藏版）》请在金锄头文库上搜索。
1、单击此处编辑母版标题样式单击此处编辑母版副标题样式*1NOIP基础算法分治与贪心 巴蜀中学 黄新军第五部分 分治策略一、分治思想 分治(divide-and-conquer)就是“分而治之”的意思，其实质就是将原问题分成n个规模较小而结构与原问题相似的子问题；然后递归地解这些子问题，最后合并其结果就得到原问题的解。三、分治的三步骤 分解：将要解决的问题分解成若干个规模较小的同类子问题； 解决：当子问题划分得足够小时，求解出子问题的解。 合并：将子问题的解逐层合并成原问题的解。分治算法设计过程图 由分治法所得到的子问题与原问题具有相同的类型。如果得到的子问题相对来说还太大，则可反复使用分治策略将
2、这些子问题分成更小的同类型子问题，直至产生出不用进一步细分就可求解的子问题。分治求解可用一个递归过程来表示。 要使分治算法效率高，关键在于如何分割？一般地，出于一种平衡原则，总是把大问题分成K个规模尽可能相等的子问题，但也有例外，如求表的最大最小元问题的算法，当n6时，等分定量成两个规模为3的子表L1和L2不是最佳分割。一般来讲，都是2分为主。四、分治的框架结构procedure DIVIDE()begin if(问题不可分)then/解决 begin 直接求解； 返回问题的解； end else begin 对原问题进行分治；/分解 递归对每一个分治的部分求解; 归并整个问题，得出全问题的解
3、;/合并 endend;五、分治的典型应用五、分治的典型应用 1 1、求最大值和最小值、求最大值和最小值 2 2、非线性方程求根、非线性方程求根 3 3、二分查找、二分查找 4 4、归并排序、归并排序 5 5、快速幂、快速幂 6 6、求解线性递推关系、求解线性递推关系 7 7、棋盘覆盖问题、棋盘覆盖问题 8 8、循环日程表问题、循环日程表问题 9 9、寻找最近点对、寻找最近点对1 1、求最大值和最小值、求最大值和最小值 例题1：给n个实数，求它们之中最大值和最小值，要求比较次数尽量小。分析：假设数据个数为n,存放在数组a1.n中。可以直接进行比较： minn:=a1;maxx:=a1; for
4、 i:=2 to n do if aimaxx then maxx:=ai; else if aixr1 then begin maxx:=xr2;minn:=xr1;end else begin maxx:=xr1;minn:=xr2;end end else begin d:=(r1+r2)/2; pd(r1,d,max1,min1); pd(d+1,r2,max2,min2); if max1max2 then maxx:=max1;else maxx:=max2; if min1=1。要求由小到大依次在同一行输出这三个实根(根与根之间留有空格)，并精确到小数点后4位。【文件输入】输入仅
5、一行，有四个数，依次为a、b、c、d【文件输出】输出也只有一行，即三个根(从小到大输出)【样例输入】1 -5 -4 20【样例输入】-2.00 2.00 5.00分析分析 如果精确到小数点后两位，可用简单枚举法：将x从-100.00 到100.00（步长0.01）逐一枚举，得到20000个 f(x)，取其值与0最接近的三个f(x)，对应的x即为答案。而题目已改成精度为小数点后4位，枚举算法时间复杂度将达不到要求。 直接使用求根公式，极为复杂。加上本题的提示给我们以启迪：采用二分法逐渐缩小根的范围，从而得到根的某精度的数值分析分析A.当已知区间(a,b)内有一个根时； 用二分法求根，若区间(a,
6、b)内有根，则必有f(a)*f(b)b或f(a+b)/2)=0，则可确定根为(a+b)/2并退出过程； (2).若f(a)*f(a+b)/2)0,则必然有f(a+b)/2)*f(b)=1。因此可知：在-100,-99、-99,-98、99，100、100，100这201个区间内，每个区间内至多只能有一个根。即：除区间100，100外，其余区间a,a+1，只有当f(a)=0或f(a)f(a+1)0时，方程在此区间内才有解。若f(a)=0 ，解即为a；若f(a)f(a+1)0 ，则可以利用A中所述的二分法迅速出找出解。如此可求出方程的所有的解。核心参考代码核心参考代码procedure divid
7、e(x1,x2:double)Begin var x0,y0,y1,y2:double; x0:=(x1+x2)div 2; y1:=cal(x1);y2:=cal(x2);y0:=cal(x0); if(x2-x10.00001 and y1*y20)then begin write(x2+x1)div 2:0:4);exit;end if(y1*y01)then divide(x1,x0); if(y0*y21)then divide(x0,x2);End;3 3、归并排序、归并排序 归并排序的基本思想：归并排序充分应用分治算法的策略，通过二分的思想，将n个数最终分成n个单独的有序数列，每
8、个数列中仅有一个数字；再将相邻的两列数据合并成一个有序数列；再重复上面的合并操作，直到合成一个有序数列。按照分治三步法来说， 归并过程为： （1）划分：把序列分成元素个数相等的两半； （2）递归求解：把两半分别排序； （3）合并：把两个有序表合成一个有序表；分析 显然，前两部分是很容易完成的，关键在于如何把两个有序表合成一个。每次只需要把两个序列中当前的最小元素加以比较，删除较小元素并加入合并后的新表。核心参考代码核心参考代码procedure MergeSort(left,right:integer)/归并排序begin if left=right then exit; /只有一个元素 mi
9、d:=(left+right)div 2; /找中间位 MergeSort(left,mid); /对左边归并 MergeSort(mid+1,right); /对右边归并 i:=left;j:=mid+1,p:=left; /合并左右 while(i=mid and jaj)then begin tempp:=aj;inc(p);inc(j);end else begin tempp:=ai;inc(p);inc(i);end while(i=mid)do begin tempp:=ai;inc(p);inc(i);end while(j=right)do begin tempp:=aj;i
10、nc(p);inc(i);end for i:=left to right do ai:=tempi; End;【变形1】逆序对数目 例题3：求“逆序对”。 给定一整数数组A=(A1,A2,An), 若iAj,则就为一个逆序对。例如数组（3，1，4，5，2）的逆序对有,。问题是，输入n和A数组，统计逆序对数目。 数据范围：1=naj then c:=c+1; 时间效率不尽如人意. 问题出现在哪里呢？分治算法：分治算法：采用二分法求解:记数列ast,ed的逆序对数目为d(st,ed); mid=(st+ed)/2,则有： d(st,ed)=d(st,mid)+d(mid+1,ed)+F(st,m
11、id,ed) 其中F(st,mid,ed)表示一个数取自ast,mid,令一个数取自amid+1,ed的逆序对数目。 和归并排序一样，划分和递归求解都好办，关键在于合并：如何求出i在左边，而j在右边的逆序对数目呢？统计的常见技巧是“分类”。我们按照j的不同把这些“跨越两边”的逆序对进行分类：只要对于右边的每个j，统计左边比它大的元素个数f(j)，则所有f(j)之和便是答案。 幸运的是，归并排序可以帮助我们“顺便”完成f(j)的计算：由于合并操作是从小到大进行排序的，当右边的aj复制到T中时，左边还没有来得及复制到T的那些数就是左边所有比aj大的数。此时累加器中加上左边元素个数mid-i+1即可
12、。 即把“if(aiaj)then begin tempp:=aj;inc(p);inc(j);end 改为“if(aiaj)then begin tot:=tot+mid-i+1;tempp:=aj;inc(p);inc(j);end4 4、二分查找、二分查找 【问题描述】给出从小到大排列的n个不同数a1an，试判断元素x是否出现在表中。 方法1：顺序查找。方法是一个个寻找，时间复杂度为O(n)。这个方法并没有用到“n个数从小到大排列”这一个关键条件，因而时间效率低下。方法方法2 2：二分查找：二分查找 只需要比较log2n个元素。假设需要在aLar中查找元素x。 划分：检查某个元素am(L
13、=mx，那么元素只可能在aLam-1中； 如果amr exit(-1); m:=(L+r)div 2; if am=x bsh:=m; else if amx then bsh:=bsh(L,m-1,x); else bsh:= bsh(m+1,r,x);End;方法方法2 2：二分查找的非递归实现：二分查找的非递归实现： function bsh(L,r,x:integer):integer; Begin var m:integer; while(Lx then r:=m-1 else L:=m+1; end bsh:=-1; /查找不成功End;【扩展扩展1 1】二分查找求下界，即第一次出
14、现的位置二分查找求下界，即第一次出现的位置 function Erfen(L,r,x:integer):integer; begin var mid:integer; while(Lr)do begin mid:=(L+r)div 2; if x=amid then r:=mid else L:=mid+1; end; Erfen:= L; end;【扩展2】二分查找求上界，即最后一次出现位置的后一个位置例题：奇怪的函数 【问题描述】使得xx达到或超过n位数字的最小正整数x是多少？ 【文件输入】输入一个正整数n。 【文件输出】输出使得xx达到n位数字的最小正整数x。【变形】查找等值点 【问题描
15、述】n个不同整数从小到大排序后放在数组A1An中，是否存在i，使得Ai=i？若存在，试找到此点。5 5、快速幂、快速幂 【问题描述】计算an %k ，n=109。方法1：朴素算法。每次乘以a，时间复杂度O(n)。 function power(a,n:integer):integer; begin var x:integer; x:=1; for i:=1 to n do x:=x*a; power:=x; end;方法方法2 2：分治算法：分治算法 划分：如果n是偶数，考虑x=n div 2， 否则考虑x=(n-1) div 2递归求解：计算ax。合并：如果n是偶数，则an=(ax)2，否则
16、an=(ax)2*a方法方法2 2：分治算法：分治算法 根据这个方法很容易写出程序：function power(a,n:integer):integer;Begin if n=0 begin power:=1;exit;end else if n mod 2=1 then /n为奇数的情况 begin x:=power(a,(n-1)div 2); power:=(x*x)mod k*a)mod k; end else begin /n为偶数的情况 x:=power(a,n div 2); power:=x*x mod k; end;End;方法方法3 3：用二进制实现快速幂计算：用二进制实现快速幂计算 read(a,b,k);/输入三个数 t:=b; while t0 do begin inc(len);clen:=t mod 2;t:=t div 2;end;/转为二进制 s:=1; for i:=len downto 1 do /用二分法实现ab mod k begin s:=s*s mod k; if ci=1 then s:=(a mod k)*s)mod k;/如果是奇数
