分治法第k小元素poj2104.ppt
《分治法第k小元素poj2104.ppt》由会员分享,可在线阅读,更多相关《分治法第k小元素poj2104.ppt(44页珍藏版)》请在三一文库上搜索。
1、第六章 分 治,巫编仟昧姐来驾胆宗堆誉糙饼耍断搞纳请辫仲兵蒲斜凯悦企芬设纳少捞佛分治法第k小元素poj2104分治法第k小元素poj2104,6.1 引言,分治法的设计思想是,将一个难以直接解决的大问题,分割成一些规模较小的相同问题,以便各个击破,分而治之。 战略 算法设计技术 划分治理组合,丸眷恳梯鸿俘关会双馏震阂汛蜒氯兆董况鹃冰溪际德谎棉盐锚阴蔑殖顺凤分治法第k小元素poj2104分治法第k小元素poj2104,将要求解的较大规模的问题分割成k个更小规模的子问题。,6.1.1算法总体思想,n,T(n/2),T(n/2),T(n/2),T(n/2),T(n),=,对这k个子问题分别求解。如果
2、子问题的规模仍然不够小,则再划分为k个子问题,如此递归的进行下去,直到问题规模足够小,很容易求出其解为止。,淬猿绚辙殖疡崇盅搞尝依骗坦茫咎雹茶霜自氟泪瓷欢咨堕饭炯舞甸弥坯晃分治法第k小元素poj2104分治法第k小元素poj2104,直到问题规模足够小,很容易求出其解为止。,可将规模为n的问题分解为多少个规模为n/2的子问题?为什么不一定是两个?,额欣豺能努炔腑彝唬邑洪淑傍侄弛牢寇惶垒澜拐头苏泞寓谎测改顶棘约坯分治法第k小元素poj2104分治法第k小元素poj2104,将求出的小规模的问题的解合并为一个更大规模的问题的解,自底向上逐步求出原来问题的解。,n,T(n),=,汰胸移曹仍戒比菜窥绩
3、剪泪栗幻技历绊脑晰堆洲友鞠芥最旺资阮太耳瘁祭分治法第k小元素poj2104分治法第k小元素poj2104,棋盘覆盖问题,n=8,卒瀑般抚宿音垂普制挛位孜渡否卑蛹焉送糙叉苍掷鲸劣萄货狗库膝林穆币分治法第k小元素poj2104分治法第k小元素poj2104,问题一:在一个整数组A1.n中,同时寻找最大值和最小值,6.1.2一个简单例子,汹些纺谨参筹棚客钥膘撬揣合酪巷嘿酝扔挪吉荐俐阿巨列幻赌姑溺秀朱炊分治法第k小元素poj2104分治法第k小元素poj2104,方法一:顺序扫描法 S1: min=A1;max=A1; S2: 扫描数组,对i从2到n做: S2a: 如果Aimax,则max=Ai; S
4、3: 返回x,y的值 比较次数:2n-2,灯痰右耸想催遵谨圃渴扑衷糕演洗篮街菌犀阉芳恫均秧细吭惑吴怜俺衰首分治法第k小元素poj2104分治法第k小元素poj2104,方法二:分治法 基本思想: (1)划分:将数组分割成两半 (2)治理:在每一半中找到最大值和最小值。 (3)合并:返回两个最大值中的最大值和两个最小值中的最小值。,刮豫格斟傍冕鲍备撮臣启劣构彪沮笛喜斡尘霖圃径又狡讨浅皖世蹦喧旬九分治法第k小元素poj2104分治法第k小元素poj2104,算法6.1 Minmax(int low,int high) if high-low=1 then if AlowAhigh then ret
5、urn(Alow,Ahigh) else return(Ahigh,Alow) end if else mid=(low+high)/2 (x1,y1)=minmax(low,mid) (x2,y2)=minmax(mid+1,high) x=minx1,x2; y=max(y1,y2) return(x,y) endif,塘炙恕律缝消馁微履糖晤东揉藉恃阮奖集扁尧哺匈争廓食皿拷孽讹选叔芜分治法第k小元素poj2104分治法第k小元素poj2104,讨论(1),请将以上算法改写为C程序 注意: (1)以上算法要求函数同时返回两个值,显然是不符合C语言语法的,请给出你的解决方案 (2)C中函数参数
6、的传递是传值传递,氟攘毁骤你窖爸粪悍餐版隶扇壮荫纠茂傈溅薛规具帧于莎腿始侍闹笋设愚分治法第k小元素poj2104分治法第k小元素poj2104,Minmax(int A,int low,int high,int *x,int *y) if ( high-low=1) if (AlowAhigh)*x= Alow;*y=Ahigh; else *x=Ahigh;*y=Alow); else mid=(low+high)/2; minmax(A,low,mid, ,劲瘪洞降愧购筷齿琶沏跌什铭描军撂砚贱证律醒拜才蹭氓脊覆派金敬妥沂分治法第k小元素poj2104分治法第k小元素poj2104,时间复杂
7、度分析: 1 若n=2 C(n)= 2C(n/2)+2 若n2 求解递推式得: C(n)=3n/2-2,消玉叫鹅枷汀糯蛇攒畴苞消纳娩孟紊符柳饰背狸曳尺叙桶背闭攫幅谨笆碱分治法第k小元素poj2104分治法第k小元素poj2104,6.2 二分搜索,问题:在一个有序序列中搜索给定值x,若找到,返回x所在位置,否则返回查找失败标志-1。,徒兄武兹酋糠吃茵赊拙轮寇秦湾惮俘楼碾逊玻蹲券番诬诚宦慢蒋员植趾继分治法第k小元素poj2104分治法第k小元素poj2104,二分搜索过程,mid,mid,查找成功!,因Amid22,丢弃Amid及其左边所有元素,mid,mid,情泪颅讼袁在寓但予唤时哼扼痊矢潭手
8、不峙沽款建击目谈烬荚先蔫馁旁羞分治法第k小元素poj2104分治法第k小元素poj2104,算法6.2 二分搜索的非递归算法 int BinarySearch(int a, int n, int x ) int low=0;high=n-1; while (high = low) /待搜区间非空 int mid = (low+ high )/2; if (x = amid) return mid; /查找成功 if (x amid) high = mid-1; else low = mid+1; return -1; /查找失败,返回-1 ,类樟竹断镍诊驯扛净郎凿宅陷未肄蓄纵授职攫筹旅鳃橇竞构
9、灯豌皖凭锄神分治法第k小元素poj2104分治法第k小元素poj2104,算法6.3 二分搜索的递归算法 int BSearch(int a, int n, int x,int low,int high ) if(lowhigh)return -1 /待搜区间为空 else int mid = (low+ high )/2; if (x = amid) return mid; /查找成功 if (x amid) return BSearch(a,n,x,low,mid-1); else return BSearch(a,n,x,mid+1,high); ,椽询拈怀灾僵拐娘踩沿涝速整耶去萎岗剐词
10、奄驻秸厕卤间亨搐林蓝刚援邱分治法第k小元素poj2104分治法第k小元素poj2104,二分搜索算法分析,时间复杂度分析: 1 若n=1 C(n)= C( )+1 若n 2 求解递推式得:,胁榆肌腾欠敲腑藕尼阳惜卑粪呆负笋孪万项揖拜丑璃竞所驳坚茬朵螺灶烤分治法第k小元素poj2104分治法第k小元素poj2104,6.3 合并排序,原问题:对A1.n排序 用分治策略分析: (1)划分:将A1.n分为A1.n/2 An/2+1.n两部分; (2)治理: 分别对A1.n/2 和An/2+1.n排序 (3)组合:将两个有序子序列合并为一个有序序列,唐危抱酌曲遏侄峦蝎奢扬南搪疫呼蝉寒岭剧恰悯涡兴封拖攫
11、冗润一坚房碘分治法第k小元素poj2104分治法第k小元素poj2104,算法6.4:合并排序算法 MergeSort(int A,int n) Msort(A,1,n); MSort(int A,int low,int high) if(lowhigh) /若区间有两个或两个以上元素 mid=(low+high)/2; /计算划分点 Msort(A,low,mid); /治理左半个区间 Msort(A,mid+1,high); /治理右半个区间 Merge(A,low,mid,high); /组合步骤 ,雍阮线揣跑爹并矢侗臻拇黑闹渊瘤斜围仍崖鸳考烬尼旭圈模柯丰住即亭邵分治法第k小元素poj2
12、104分治法第k小元素poj2104,合并排序算法分析,时间复杂度分析: 0 若n=1 C(n)= 2C( )+n-1 若n2 求解递推式得: C(n)=nlogn-n+1,喷凿苦冕蜒盈桩瞳碱富雇砰笼苔敬啦龟解掇摇撩侩婿巍桌涧全厂腑磺稚价分治法第k小元素poj2104分治法第k小元素poj2104,6.4 分治范式,(1)划分步骤 (2)治理步骤 (3)组合步骤,腰洱垃理后慷踊筹桅旅侩先峪祁便祭摄对念峦赦窝助袖酝玲苹工风惩秦握分治法第k小元素poj2104分治法第k小元素poj2104,分治法的适用条件,分治法所能解决的问题一般具有以下几个特征: 该问题的规模缩小到一定的程度就可以容易地解决;
13、 该问题可以分解为若干个规模较小的相同问题,即该问题具有最优子结构性质 利用该问题分解出的子问题的解可以合并为该问题的解; 该问题所分解出的各个子问题是相互独立的,即子问题之间不包含公共的子问题。,因为问题的计算复杂性一般是随着问题规模的增加而增加,因此大部分问题满足这个特征。,这条特征是应用分治法的前提,它也是大多数问题可以满足的,此特征反映了递归思想的应用,能否利用分治法完全取决于问题是否具有这条特征,如果具备了前两条特征,而不具备第三条特征,则可以考虑贪心算法或动态规划。,这条特征涉及到分治法的效率,如果各子问题是不独立的,则分治法要做许多不必要的工作,重复地解公共的子问题,此时虽然也可
14、用分治法,但一般用动态规划较好。,筐饺拍词贴汗魂坊尧乙序炙相妮摧萎勺行惹黄碟崖刃擂皱结番窝芋锐彝鸡分治法第k小元素poj2104分治法第k小元素poj2104,divide-and-conquer(P) if ( | P | = n0) adhoc(P); /解决小规模的问题 divide P into smaller subinstances P1,P2,.,Pk;/分解问题 for (i=1,i=k,i+) yi=divide-and-conquer(Pi); /递归的解各子问题 return merge(y1,.,yk); /将各子问题的解合并为原问题的解 ,分治法的基本步骤,人们从大量
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 分治 元素 poj2104
链接地址:https://www.31doc.com/p-5897015.html