NOIP基础算法-贪心和分治pascal.ppt
《NOIP基础算法-贪心和分治pascal.ppt》由会员分享,可在线阅读,更多相关《NOIP基础算法-贪心和分治pascal.ppt(98页珍藏版)》请在三一办公上搜索。
1、NOIP基础算法分治与贪心,巴蜀中学 黄新军,第五部分 分治策略,一、分治思想,分治(divide-and-conquer)就是“分而治之”的意思,其实质就是将原问题分成n个规模较小而结构与原问题相似的子问题;然后递归地解这些子问题,最后合并其结果就得到原问题的解。,二、分治法的适用条件,能使用分治法解决的问题,它们一般具备以下几个特征:该问题可以分解成若干相互独立、规模较小的相同子问题;子问题缩小到一定的程度就能轻易得到解;子问题的解合并后,能得到原问题的解;分治法在信息学竞赛中应用非常广泛,使用分治策略能生成一些常用的算法和数据结构,如快排、最优二叉树、线段树等;还可以直接使用分治策略,解
2、决一些规模很大、无法直接下手的问题。,三、分治的三步骤,分解:将要解决的问题分解成若干个规模较小的同类子问题;解决:当子问题划分得足够小时,求解出子问题的解。合并:将子问题的解逐层合并成原问题的解。,分治算法设计过程图,由分治法所得到的子问题与原问题具有相同的类型。如果得到的子问题相对来说还太大,则可反复使用分治策略将这些子问题分成更小的同类型子问题,直至产生出不用进一步细分就可求解的子问题。分治求解可用一个递归过程来表示。要使分治算法效率高,关键在于如何分割?一般地,出于一种平衡原则,总是把大问题分成K个规模尽可能相等的子问题,但也有例外,如求表的最大最小元问题的算法,当n6时,等分定量成两
3、个规模为3的子表L1和L2不是最佳分割。一般来讲,都是2分为主。,四、分治的框架结构,procedure DIVIDE()begin if(问题不可分)then/解决 begin 直接求解;返回问题的解;end else begin 对原问题进行分治;/分解 递归对每一个分治的部分求解;归并整个问题,得出全问题的解;/合并 endend;,五、分治的典型应用,1、求最大值和最小值2、非线性方程求根3、二分查找4、归并排序5、快速幂6、求解线性递推关系7、棋盘覆盖问题8、循环日程表问题9、寻找最近点对,1、求最大值和最小值,例题1:给n个实数,求它们之中最大值和最小值,要求比较次数尽量小。,分析
4、:假设数据个数为n,存放在数组a1.n中。可以直接进行比较:minn:=a1;maxx:=a1;for i:=2 to n do if aimaxx then maxx:=ai;else if aiminn then minn:=ai;使用这一算法,比较次数为2(n-1)。若n=10,则比较18次。,用分治法解决这个问题就是把集合a分成a1,a2两个子集,每个子集有n/2个元素,应用递归结构找出两个子集的最大元和最小元,比较得到的两个最大元和最小元即可得到整个集合a中的最大元和最小元。划分:把n个数均分为两半。即:划分点为d=(r1+r2)/2,两个区间为r1,d和d+1,r2。递归求解:求左
5、半的最小值min1 和最大值max1以及右半最小值min2和最大值max2。合并:所有数的最大值为maxx,最小值为minn。,procedure pd(r1,r2:integer;var maxx,minn:integer)begin var max1,min1,max2,min2,d:integer;if r1=r2 then begin maxx:=xr1;minn:=xr1;end else if r2=r1+1 then begin if xr2xr1 then begin maxx:=xr2;minn:=xr1;end else begin maxx:=xr1;minn:=xr2;
6、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 min1min2 then minn:=min1;else minn:=min2;endend,2、非线性方程求根,例题2:一元三次方程的解【题目描述】有形如:ax3+bx2+cx+d=0这样的一个一元三次方程。给出该方程中各项的系数(a,b,c,d均为实数),并约定该方程存在三个不同实根(根的范围在-100至100之间),且根与根之差的绝对值=1。要求由小到
7、大依次在同一行输出这三个实根(根与根之间留有空格),并精确到小数点后4位。【文件输入】输入仅一行,有四个数,依次为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位,枚举算法时间复杂度将达不到要求。直接使用求根公式,极为复杂。加上本题的提示给我们以启迪:采用二分法逐渐缩小根的范围,从而得到根的某
8、精度的数值,分析,A.当已知区间(a,b)内有一个根时;用二分法求根,若区间(a,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)0,根在(a+b)/2,b)中,对此区间重复该过程。执行完毕,就可以得到精确到0.0001的根。,分析,B、求方程的所有三个实根所有的根的范围都在-100至100之间,且根与根之差的绝对值=1。因此可知:在-100,-99、-99,-98、99,100、100,100这201个区间内,每个区间内至多只能有一个根。即:除区间100,100
9、外,其余区间a,a+1,只有当f(a)=0或f(a)f(a+1)0时,方程在此区间内才有解。若f(a)=0,解即为a;若f(a)f(a+1)0,则可以利用A中所述的二分法迅速出找出解。如此可求出方程的所有的解。,核心参考代码,procedure divide(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-x11)then divide(x1,x0);if(y0*y21)then divide(x0,x2);End;,3、归并排序,归并排序的
10、基本思想:归并排序充分应用分治算法的策略,通过二分的思想,将n个数最终分成n个单独的有序数列,每个数列中仅有一个数字;再将相邻的两列数据合并成一个有序数列;再重复上面的合并操作,直到合成一个有序数列。按照分治三步法来说,归并过程为:(1)划分:把序列分成元素个数相等的两半;(2)递归求解:把两半分别排序;(3)合并:把两个有序表合成一个有序表;,分析,显然,前两部分是很容易完成的,关键在于如何把两个有序表合成一个。每次只需要把两个序列中当前的最小元素加以比较,删除较小元素并加入合并后的新表。,核心参考代码,procedure MergeSort(left,right:integer)/归并排序
11、begin if left=right then exit;/只有一个元素 mid:=(left+right)div 2;/找中间位 MergeSort(left,mid);/对左边归并 MergeSort(mid+1,right);/对右边归并 i:=left;j:=mid+1,p:=left;/合并左右 while(iaj)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=
12、right)do begin tempp:=aj;inc(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=n=30000。,朴素算法,在看完试题以后,我们不难想到一个非常简单的算法穷举算法,即对数组中任意的两个元素进行判断,看它们是不是构成“逆序对”,因此这种算法的时间复杂度为O(N2)。C:=0;for i:=1 to n-1
13、do for j:=i+1 to n do if aiaj 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,mid,ed)其中F(st,mid,ed)表示一个数取自ast,mid,令一个数取自amid+1,ed的逆序对数目。,和归并排序一样,划分和递归求解都好办,关键在于合并:如何求出i在左边,而j在右边的逆序对数目呢?统计的常见技巧是“分类”。我们按照j的不同把这些“跨越两边”的逆序对进行分类:
14、只要对于右边的每个j,统计左边比它大的元素个数f(j),则所有f(j)之和便是答案。幸运的是,归并排序可以帮助我们“顺便”完成f(j)的计算:由于合并操作是从小到大进行排序的,当右边的aj复制到T中时,左边还没有来得及复制到T的那些数就是左边所有比aj大的数。此时累加器中加上左边元素个数mid-i+1即可。即把“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);end,4、二分查找,【问题描述】给出从小到大排列的n个不同数a1
15、an,试判断元素x是否出现在表中。,方法1:顺序查找。方法是一个个寻找,时间复杂度为O(n)。这个方法并没有用到“n个数从小到大排列”这一个关键条件,因而时间效率低下。,方法2:二分查找,只需要比较log2n个元素。假设需要在aLar中查找元素x。划分:检查某个元素am(Lx,那么元素只可能在aLam-1中;如果amx,那么元素只可能在am+1ar中。合并:不需要合并。,方法1:二分查找的递归实现,function bsh(L,r,x:integer):integer;Begin var m:integer;if Lr exit(-1);m:=(L+r)div 2;if am=x bsh:=m
16、;else if amx then bsh:=bsh(L,m-1,x);else bsh:=bsh(m+1,r,x);End;,方法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】二分查找求下界,即第一次出现的位置 function Erfen(L,r,x:integer):integer;begin var mid:integer;while(Lr)do begin mid:=(L
17、+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。,【变形】查找等值点,【问题描述】n个不同整数从小到大排序后放在数组A1An中,是否存在i,使得Ai=i?若存在,试找到此点。,5、快速幂,【问题描述】计算an%k,n=109。,方法1:朴素算法。每次乘以a,时间复杂度O(n)。function power
18、(a,n:integer):integer;begin var x:integer;x:=1;for i:=1 to n do x:=x*a;power:=x;end;,方法2:分治算法,划分:如果n是偶数,考虑x=n div 2,否则考虑x=(n-1)div 2递归求解:计算ax。合并:如果n是偶数,则an=(ax)2,否则an=(ax)2*a,方法2:分治算法,根据这个方法很容易写出程序:function power(a,n:integer):integer;Begin if n=0 begin power:=1;exit;end else if n mod 2=1 then/n为奇数的情
19、况 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:用二进制实现快速幂计算,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 t
20、hen s:=(a mod k)*s)mod k;/如果是奇数,就多乘a end;writeln(s);/输出ab mod k,6、求解线性递推关系,【例题】Fibonacci数【题目描述】Fibonacci数列定义为:fi=fi-2+fi-1(i2),其中f1=1,f2=1。现在请你求Fibonacci数列的第n项。【文件输入】输入文件只有一行为一个整数n(1=n=231-1)。【文件输出】输出文件只有一行为一个整数,表示Fibonacci数列的第n项mod 32768的值。【样例输入】4【样例输出】3【数据范围】对于20%的数据,1=n=1000 对于40%的数据,1=n=10000000
21、 对于100%的数据,1=n=231-1,朴素算法,肯定超时,procedure Fib(n:integer)Begin var i:integer;f0:=0;f1:=1;for i:=2 to n do fi:=fi-1+fi-2;End;,先复习矩阵乘法两个2*2矩阵相乘的公式为,可用倍增法在O(logn)时间内求出幂(忽略高精度),扩展练习:,若fi=fi-1+fi-2+fi-3,如何计算求出fn,7、棋盘覆盖问题,分析,8、循环日程表问题,【例题】比赛安排【问题描述】设有2n(n=6)个球队进行单循环比赛,计划在2n-1天内完成,每个队每天进行一场比赛。设计一个比赛的安排,使在2n-
22、1天内每个队都与不同的对手比赛。例如n=2时的比赛安排为:队 1 2 3 4 比赛 1-2 3-4 第一天 1-3 2-4 第二天 1-4 2-3 第三天【文件输入】一个整数n。【文件输出】输出比赛安排表。【样例输入】2【样例输出】1-2 3-4 1-3 2-4 1-4 2-3,初看此题,感觉无法下手,因为没有任何直接可用的算法和数据结构。仔细分析,可以发现,将问题进行分解,能找出规律。当n=1时,共有2个球队参赛,一天就可以比完。当n=2时,共有4个球队,需比赛3天。从2个球队的比赛安排表中可以看出,左上角与右下角对称,左下角与右上角对称,左下角的值是由左上角值加n得到的。,read(n);
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- NOIP 基础 算法 贪心 分治 pascal
链接地址:https://www.31ppt.com/p-5441527.html