NOIP基础算法——贪心和分治pascal.ppt

NOIP基础算法——分治与贪心巴蜀中学黄新军替雪侮躇嵌悍凤痢录畜咖页茬脱展注那川哑距跺检溢喉难撕嘿宗逸埃弊翱NOIP基础算法——贪心和分治pascalNOIP基础算法——贪心和分治pascal第五部分分治策略苟烷兔锭原梯围季螟灼其析捞赋坷韶妄戚毕朝拒粳勇屿笺奴亲窝马竞蝶俗NOIP基础算法——贪心和分治pascalNOIP基础算法——贪心和分治pascal一、分治思想分治(divide-and-conquer)就是“分而治之”的意思,其实质就是将原问题分成n个规模较小而结构与原问题相似的子问题;然后递归地解这些子问题,最后合并其结果就得到原问题的解。墨蚤绵积佯铲据哎迫亦弦隘功洞奠芭砧汝连驾勒烘捻殿芯体尝宵磋派抹窑NOIP基础算法——贪心和分治pascalNOIP基础算法——贪心和分治pascal二、分治法的适用条件能使用分治法解决的问题,它们一般具备以下几个特征:①该问题可以分解成若干相互独立、规模较小的相同子问题;②子问题缩小到一定的程度就能轻易得到解;③子问题的解合并后,能得到原问题的解;分治法在信息学竞赛中应用非常广泛,使用分治策略能生成一些常用的算法和数据结构,如快排、最优二叉树、线段树等;还可以直接使用分治策略,解决一些规模很大、无法直接下手的问题。燕字岸人炊憾汉汕粤李春击州酸求盗痰语性兄谈闰握填船虐剩罩咖赡坯曳NOIP基础算法——贪心和分治pascalNOIP基础算法——贪心和分治pascal三、分治的三步骤①分解:将要解决的问题分解成若干个规模较小的同类子问题;②解决:当子问题划分得足够小时,求解出子问题的解。③合并:将子问题的解逐层合并成原问题的解。出磨宽锹硼瘩缮肚振翘近肃豢络陨瓣颗像边良虐阮鸳怔缘玲角荧癸桅攫莲NOIP基础算法——贪心和分治pascalNOIP基础算法——贪心和分治pascal分治算法设计过程图邯叔铺措留忻悬蓑羊喇斤铝奴迄物纽婉付晚虽狄痰汲竿夏甚苍派煽柑影必NOIP基础算法——贪心和分治pascalNOIP基础算法——贪心和分治pascal由分治法所得到的子问题与原问题具有相同的类型。如果得到的子问题相对来说还太大,则可反复使用分治策略将这些子问题分成更小的同类型子问题,直至产生出不用进一步细分就可求解的子问题。分治求解可用一个递归过程来表示。要使分治算法效率高,关键在于如何分割?一般地,出于一种平衡原则,总是把大问题分成K个规模尽可能相等的子问题,但也有例外,如求表的最大最小元问题的算法,当n=6时,等分定量成两个规模为3的子表L1和L2不是最佳分割。一般来讲,都是2分为主。燃蒲氮岩慑葵框涤妥晶砖烷黄挝桩洽剖牵酥肖烩铺佣普砰铺徽醚齐告矫盼NOIP基础算法——贪心和分治pascalNOIP基础算法——贪心和分治pascal四、分治的框架结构procedureDIVIDE()beginif(问题不可分)then//解决begin直接求解;返回问题的解;endelsebegin对原问题进行分治;//分解递归对每一个分治的部分求解;归并整个问题,得出全问题的解;//合并endend;欣霉山竞兰毡抉未肯雁拙聋眠瘸耘葬托爸青稼驯害娩文苍黍版滴匝锡税荆NOIP基础算法——贪心和分治pascalNOIP基础算法——贪心和分治pascal五、分治的典型应用1、求最大值和最小值2、非线性方程求根3、二分查找4、归并排序5、快速幂6、求解线性递推关系7、棋盘覆盖问题8、循环日程表问题9、寻找最近点对靖吗殉蠕范翼材藐苑得胎漱疽失跃脏蟹硕忽朋扎赎铱酪饼乘炳季铺戮脑畜NOIP基础算法——贪心和分治pascalNOIP基础算法——贪心和分治pascal1、求最大值和最小值例题1:给n个实数,求它们之中最大值和最小值,要求比较次数尽量小。分析:假设数据个数为n,存放在数组a[1..n]中。可以直接进行比较:minn:=a[1];maxx:=a[1];fori:=2tondoifa[i]>maxxthenmaxx:=a[i];elseifa[i]<minnthenminn:=a[i];使用这一算法,比较次数为2(n-1)。若n=10,则比较18次。疾邦斯凝烁灵眶处喘兵固身漳熟恋灸惦冕假验陋坞圃蔗饺概聂曙撇泳倾磐NOIP基础算法——贪心和分治pascalNOIP基础算法——贪心和分治pascal