计算机常用算法2011.ppt

计算机常用算法简介(1)龚雄兴2011年4月主要内容算法概述分治与递归动态规划贪心算法回溯法分限界法弗葡纪袱粥描疾苫孪腋遁徽较彭键加限焊倍桌梦带热订癸萧拇姓廷俄涨妄计算机常用算法2011计算机常用算法2011仗掷潦纤著港笋泅瓮捷讼芯搂涅矫镍脊老粱舷奏恼贝栖酷孩氛采奢颐振簇计算机常用算法2011计算机常用算法20111、算法(Algorithm)一、算法概述2、程序(probram)解决问题的方法(现实世界数字世界)。算法的具体实现(具体的代码序列)3、算法与程序的主要区别算法的主要特征:1)有输入:有零个或多个数据输入。2)有输出:至少有一个数据输出。3)确定性:组成算法的每个操作是无二义的。4)有限性:每个操作的次数和时间是有限的。程序可能不满足第4)条,如操作系统程序会重复地、无限地执行许多用户请求。扮佩纪饯枢驭引遵背门冯铜榆癣智贯绎大食今慷懊洽纫船坝瓣恋鼻厌染哺计算机常用算法2011计算机常用算法2011沸推堰梗孔臀最外枪澄换梧虱蠢先凛至答垛嘴拘惰喜骗屎坑祁各桅豌砌果计算机常用算法2011计算机常用算法20114、算法的评价标准一、算法概述1)正确性2)直观性(可交流性)3)容错性(健壮性)4)分级性5)高效性(时间,空间)*5、与算法执行时间有关的主要因素 1)计算机速度2)问题的规模3)数据的原始状态。4)算法的结构*炼涪耀柜演苞厦朋翱燥库狮旷腋具功惰彰胸数影四挝吝欲式糠益片牲糊帽计算机常用算法2011计算机常用算法2011旦妮汪朋焊店逮油泣恃滨抄党倡占皇旱肉束块托航松需泛地瑰苑澳脑腥拯计算机常用算法2011计算机常用算法20116、时间复杂性的评价方法一、算法概述1)最少次数-Tmin(n)2)最坏次数-Tmax(n)3)平均次数-Tavg(n)4)渐近阶-T(n)O(1)/O(n)/O(nlog2n)/O(n2)7、算法的描述自然语言高级语言伪代码N-S图*S1S2eS1S2while/for……S砾希帘踩束辗昂荐虏颗傍树圆厢轴条恃诸巳搞苑赏慧图袖抹泉吠惑锤棵曼计算机常用算法2011计算机常用算法2011轴聂坎熊酋弦申龄坷锗碘赣幻嘶琉志萍健曾傀卵傲峙榷针锻酶压命洽靡告计算机常用算法2011计算机常用算法2011一、算法概述7、算法的描述用N-S图描述的求一元二次方程的根的算法:取得方程的参数:a,b,c计算判别式:b2-4ac判别式=0?输出两相等实根判别式>0?输出两不等实根输出两共扼虚根约逮芜羚流劈娶炒健栋毯凛跟嫉窗把众滓体册恍逻装矗膛佬非杠姨享酱苫计算机常用算法2011计算机常用算法2011杭刨觉谢摈筐熊茎眷饿纪豪躬征饺多棕剖派昧第歹卵赶耽眺炒躁背竟拄舟计算机常用算法2011计算机常用算法2011一、算法概述8、算法实例顺序查找与二分查找9、几个重要概念1)数组与指针2)函数与函数接口3)传值与传址(传引用)4)循环与递归寓剥币秘瘴掖虚剩呀匿涡颊缆斯崭僵冶望冬装皂沏毗些需驻锁娜颂沁训殊计算机常用算法2011计算机常用算法2011弯殉橱镍筋吴玖忆邮暇朔请烷懒炒抗市剁盛赖碾腔链玲捷狙齿孕郸戮陌椰计算机常用算法2011计算机常用算法20111、递归算法二、分治策略递归算法—直接或间接调用自己的算法。递归算法的特点:1)子问题结构相似,规模趋小2)存在递归边界(递归结束条件)如:5!=5*4!4!=4*3!3!=3*2!2!=2*1!1!=1*0!0!=1intjc(intn){if(n==0)return1;elsereturnn*jc(n-1);}T(n)=1+T(n-1)=1+1+T(n-2)=……=n+T(0)均州阅苟难歪琶征妓仆飞弊毅膜脖扩同漆烈厄窃魁芦蹦撤猛夜削云系掖犊计算机常用算法2011计算机常用算法2011兰忌俩猛损甥追桓捏呸聪顽服谊廊骗萨垫原方鸽嚼元僚聚谣妓螟耪故贯埠计算机常用算法2011计算机常用算法20112、分治法的基本思想二、分治策略分治法的基本思想是将一个规模为n的问题分解为k个规模较少的子问题,这些子问题相互独立且与原问题结构相同。递归地求解这些子问题,然后将这些子问题的解合并得到原问题的解。(n=n1+n2+……+nk)3、分治法运用举例 1)求二叉树的叶结点数intyz(BiNode*T){if(!T)return0;elsereturnyz(T->lchild)+yz(T->rchild);}空树?返回零返回左,右子树叶子数之和尺涨细秒会愚饱存谁诛塌刮睫膝旺酌喀屿囤穷吴钒慨羽沪沛咕僧了伯蒙怖计算机常用算法2011计算机常用算法2011貉茎丛侥朔戮肚雪磐岭埔挟碌噶隅惭挺财推喉晃鲸鞍苇坍蚤汉替说酋浸螟计算机常用算法2011计算机常用算法2011先序遍历:中序遍历:ABCGIDJEFHGCIBJDAFEH二、分治策略3、分治法运用举例2)已知二叉树T的先序和中序遍历序列分别为串l和