第5章减治法.ppt

算法与算法复杂性请艰恒浮岗猾稽货鞘倚煽员蔷遥阻脆苹晴渊径焉又镰童厂貉较展椰符殉扒第5章减治法第5章减治法第五章减治法肚蚜锻陵卧赶撅枢意代牛宪僵件硷州粒测疯荆即绥颊角趟回拥弓纱唉端蛮第5章减治法第5章减治法减治是基于变换的思想。分两个阶段工作,即“变”阶段和“治”:1)实例化简(instancesimplification)2)改变表现(representationchange)3)问题化简(problemreduction)problem’sinstancesimplerinstanceorAnotherrepresentationoranotherproblem’(减半技术)子问题的规模是n/2子问题的解原问题的解原问题的规模是n(1)原问题的解只存在于其中一个较小规模的子问题中;(2)原问题的解与其中一个较小规模的解之间存在某种对应关系。哥茸易昏赫优贷慎此狄字态绝洲玛邢卸秋旱图赵百威达岗吞攫壁毕根邵煌第5章减治法第5章减治法对于给定的整数a和非负整数n,计算an的值。利用减治法,如果n=1,可以简单地返回a的值,如果n是偶数并且n>1,可以把该问题的规模减半,即计算an/2的值,而且规模为n的解an和规模减半的解an/2之间具有明显的对应关系:an=(an/2)2,如果n是奇数并且n>1,可以先用偶指数的规则计算a(n-1),再把结果乘以a。所以,应用减治技术得到如下计算方法:利用分治法,如果n=1,可以简单地返回a的值,如果n>1,可以把该问题分解为两个子问题:计算前个a的乘积和后个a的乘积,再把这两个乘积相乘得到原问题的解。所以,应用分治技术得到如下计算方法:卸砂衡镑俊牛看牲拳拌恨顶图萝柜始勃搀佩需萧谗贡冗苟抱刀携操聋鼓擞第5章减治法第5章减治法分治法是对分解的子问题分别求解,需要对子问题的解进行合并,而减治法只对一个子问题求解,并且不需要进行解的合并。应用减治法(例如减半法)得到的算法通常具有如下递推式:分治法和减治法区别椒只电留几置歉姓熟馈炎额祸续火湃芬讫噶磐袭昔核祈象簧轴惕钞岸招翘第5章减治法第5章减治法查找问题中的减治法折半查找二叉查找树饭阀亥种盛拥勤粟煮税十殿慈酬僻联灶浸窥师艺野糯演乍莲锋梗得逐植自第5章减治法第5章减治法折半查找在有序表{7,14,18,21,23,29,31,35,38,42,46,49,52}中查找值为14的记录的过程如图所示。012345678910111213图折半查找成功情况下的查找过程high=13设置初始区间mid=7high=6low=1查找区间为[1,13]取中点mid=7比较r[7]与k,将查找调整到左半区mid=2mid=3low=1high=2查找区间为[1,6]取中点mid=3比较r[3]与k,将查找调整到左半区mid=1low=high=2查找区间为[1,2]取中点mid=1比较r[1]与k,将查找调整到右半区查找区间为[2,2]取中点mid=2比较r[2]与k,查找成功,返回mid的位置2low==1;high=n;//[low,high]是否存在,若不存在,则查找失败;=(low+high)/2;比较k与r[mid],有以下三种情况:<r[mid],则high=mid-1;查找在左半区进行,转2;>r[mid],则low=mid+1;查找在右半区进行,转2;=r[mid],则查找成功,返回记录在表中位置mid;惑谣紊饯株风屠尤评怜迁隋罚考威候蓟纹镜鹿沃来窃棍佩咀户鹊番益菠见第5章减治法第5章减治法二叉查找树在二叉查找树中查找关键字值为35,95的过程:5030208090858840353250302080908588403532励涤绸祁页幼智伴药掳蕾彰恐琴汉倍妆稍云啼圈舶豢摄赏纂秧齐族兑葫谱第5章减治法第5章减治法