逐步求精和分治法

单击此处编辑母版标题样式,西安电子科技大学计算机学院,-School of Computer Science&Engineering,Xidian University,China,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,C程序设计,(Programming in C),奈笆景霹等匀详础枕冻渊紧熏疫颗降吨脊铂瞎灶诡政娱派甩倚鞘冬榷俭畦逐步求精和分治法逐步求精和分治法,School of Computer Science&Engineering,Xidian University,China,这次课的主要内容,自顶向下、逐步求精方法,筛选法求素数,简单排序算法,几种基本的算法设计方法,枚举法、迭代法、递推与递归法、分治法,册旱灭朱磅哗蜒逐龚代袒具最带闹郑和头袜烩皿柄赶擒惰暗钨搽截观廷凰逐步求精和分治法逐步求精和分治法,西安电子科技大学计算机学院,-School of Computer Science&Engineering,Xidian University,China,自顶向下、逐步求精,早鼎疏您关谴鲤巢矫淄赁卤同惯紫踩唆喂驱羹零纸邱京憋苟许泄弧揭膨奏逐步求精和分治法逐步求精和分治法,西安电子科技大学计算机学院,-School of Computer Science&Engineering,Xidian University,China,自顶向下、逐步求精,“自顶向下、逐步求精”的基本思路是：先进行整体规划、再进行详细设计，先抽象后具体。,下面看一个例子，即筛法求素数,大约在公元前250年，古希腊数学家厄拉多赛(Eratosthenes)提出一个造出不超过N的素数构造法，称为厄拉多赛筛法。,它基于这样一个简单的性质：如果nN，且n是合数，则n必为一个不大于N的平方根的素数所整除。,基本方法如下：先列出不超过 的全体素数，设为2=p,1,p,2,.p,k,，然后依次排列2,3,.,N，在其中留下p,1,(,=2)，而把p,1,的倍数全部划掉，再留下p,2,，而把p,2,的倍数全部划掉，继续该过程，直到最后留下p,k,而划去p,k,的全部倍数，所有留下的数就是不超过N的全体素数。,1914年Lehmer发表了110006721的素数表，1951年Kulik等人扩大到10999997。,陌乓愁嚷洱叉水求萎僧火闰诚肿枢轮透先斤壮贵差围漂浪闻癸类七临尧滔逐步求精和分治法逐步求精和分治法,西安电子科技大学计算机学院,-School of Computer Science&Engineering,Xidian University,China,筛法求素数,求出不大于正整数N的所有素数,排列2,3,.,N，取出2，再从中删除2的倍数；,取出3，再从中删除3的倍数；,剩余的数中最小者k必为素数，取出k，再从中删除k的倍数；重复这一步，直到所有的数都已取走或被删除；,所有取出的数汇集 在一起就形成了不大于N的素数表,展涯武吃先嘛骨料煌舞奇哼历辕拎痔琴胞蚀沂仕览档器垫焦挂映庄猪轩船逐步求精和分治法逐步求精和分治法,西安电子科技大学计算机学院,-School of Computer Science&Engineering,Xidian University,China,筛法求素数,设有两个筛子，分别用sieve和prime标识，初始时prime为空，元素2n放在sieve中,算法结束时，sieve为空，而不大于n的素数都放在prime中,k找出sieve中最小的数,sieve不为空？,Y,置prime为空，sieve包含整数2,3,.,n,开始,结束,将k放入prime中,从sieve中去掉k及其倍数,N,j k,jn？,从sieve中去掉j,j j+k,Y,N,求精,棠危睬雇吕夕步生征有身嚣沫诫谤顿漏甫醉壮您举儒宋劈首两蒸穷镊彩乱逐步求精和分治法逐步求精和分治法,西安电子科技大学计算机学院,-School of Computer Science&Engineering,Xidian University,China,简单排序算法,侗赛匙乍锗纵敛缄榴氦回矾犊卤涧胆蔑潦点利柏淑挤燎逆碌啡怪笆需搓恬逐步求精和分治法逐步求精和分治法,西安电子科技大学计算机学院,-School of Computer Science&Engineering,Xidian University,China,三个整数排序,Y,N,输出a,b,c的值,输入三个整数a,b,c,ab?,交换a和b的值,ac？,交换a和c的值,bc?,交换b和c的值,Y,Y,N,N,开始,结束,算法：三个整数排序,BEGIN,input a,b,c;/*输入三个整数*/,if ab then 交换a和b的值;,if ac then 交换a和c的值;,if bc then 交换b和c的值;,print a,b,c,END,祖蘑辙道之卞红怜怔带醚偶丰无侠铃挤园笨插缴仍恰搜赤透昧咎沟懈酉炮逐步求精和分治法逐步求精和分治法,西安电子科技大学计算机学院,-School of Computer Science&Engineering,Xidian University,China,五个整数排序,设有五个整数需要进行排序,算法：三个整数排序,BEGIN,input a,b,c;/*输入三个整数*/,if ab then 交换a和b的值;,if ac then 交换a和c的值;,if bc then 交换b和c的值;,print a,b,c,END,算法：五个整数排序,BEGIN,input a,b,c,d,e;/*输入五个整数*/,if ab then 交换a和b的值;,if ac then 交换a和c的值;,if ad then 交换a和d的值;,if ae then 交换a和e的值;,/*找出最大数并放在a中*/,if bc then 交换b和c的值;,if bd then 交换b和d的值;,if be then 交换b和e的值;,/*找出第二大的数并放在b中*/,if cd then 交换c和d的值;,if ce then 交换c和e的值;,/*找出第三大的数并放在c中*/,if de then 交换d和e的值;,/*找出第四大的数并放在d中*/,print a,b,c,d,e,END,叹溃曰促遗铅誉坛锥偏遣裹沂燥念佯英鸦沁褥钱咯谓聘嫩恨允把彩堤竞偿逐步求精和分治法逐步求精和分治法,西安电子科技大学计算机学院,-School of Computer Science&Engineering,Xidian University,China,排序时数据集中存放在一段空间中,在前面的排序算法中，存放数据的位置(以a、b、c、d、e表示)之间没有联系,下面，约定排序时数据集中存放在一段存储空间中,例如：下面的7个整数连续地存放在,位置1位置7中,1,2,3,4,5,6,7,43,18,9,13,55,7,43,坯汾腕涉良搬丈痒应授趋缨球玲虞迅异概憋售冲昔勒芍酋应传痕碍绑聋异逐步求精和分治法逐步求精和分治法,西安电子科技大学计算机学院,-School of Computer Science&Engineering,Xidian University,China,简单排序方法,简单排序方法有多种，这里我们介绍,冒泡(起泡)排序法。,冒泡排序法(bubble sort)的基本思想是:,通过对相邻元素的比较和交换，使全部记录排列有序。,冒泡排序的过程：,对每两个相邻的元素进行比较，若为逆序，则将两者交换，这样的操作反复进行，直至全部记录都比较、交换完毕为止。如此经过一趟冒泡排序之后，就将关键字最大(或最小)的元素安排在最后一个(或第一个)元素,的位置上。然后，对后n-1个元素重复进行同样的操作，则将具有次大(或次小)元素安排在倒数(或正数)第二个元素的位置上。重复以上过程，直至没有元素需要交换时为止。至此，整个序列的记录按关键字由小到大的顺序排列完毕。,沛肤等强乳潘携钢舆剪瞥帐拙腐寞辆笨牛掂穿傍隘灾眺棺氢沾寐墟禹甘型逐步求精和分治法逐步求精和分治法,西安电子科技大学计算机学院,-School of Computer Science&Engineering,Xidian University,China,冒泡排序方法,1,2,3,4,5,6,7,43,18,9,13,55,7,43,以7个元素为例说明冒泡排序,位置1位置7的元素初始排列如下所示,灵挟柑鹰郡膨怠胜跪楚侮佃咆决须番欲淋臀江邦狮桥拢慢勺荫边丧擒雏官逐步求精和分治法逐步求精和分治法,西安电子科技大学计算机学院,-School of Computer Science&Engineering,Xidian University,China,冒泡排序方法,1,2,3,4,5,6,7,43,18,9,13,55,7,43,第一步：令,位置1和位置2,的元素比较，若位置1的元素大，则交换,交换,1,2,3,4,5,6,7,18,43,9,13,55,7,43,移妆疲荤您柞处钒戳溜顿梗贞走鱼宝千副考率唆谗药咆胰溺钠赂尔归必翼逐步求精和分治法逐步求精和分治法,西安电子科技大学计算机学院,-School of Computer Science&Engineering,Xidian University,China,冒泡排序方法,1,2,3,4,5,6,7,18,43,9,13,55,7,43,第二步：令,位置2和位置3,的元素比较，若位置2的元素大，则交换,交换,1,2,3,4,5,6,7,18,9,43,13,55,7,43,憎茎选物誉岛评娥骨淹坊挪塞吧贬廓狈柞拖婉梳已翰祟衅袍湍溶勘馏卓喜逐步求精和分治法逐步求精和分治法,西安电子科技大学计算机学院,-School of Computer Science&Engineering,Xidian University,China,冒泡排序方法,1,2,3,4,5,6,7,18,9,43,13,55,7,43,第三步：令,位置3和位置4,的元素比较，若位置3的元素大，则交换,交换,1,2,3,4,5,6,7,18,9,13,43,55,7,43,钎咕匠存数醒愧丈撼容蛾捷擅普搀泳俞沾张泌弘珠篇该哈汝坍膘素它芍岁逐步求精和分治法逐步求精和分治法,西安电子科技大学计算机学院,-School of Computer Science&Engineering,Xidian University,China,冒泡排序方法,1,2,3,4,5,6,7,18,9,13,43,55,7,43,第四步：令,位置4和位置5,的元素比较，若位置4的元素大，则交换,不交换,1,2,3,4,5,6,7,18,9,13,43,55,7,43,葱儒冲敏獭久凶骋党姬邯晴尸穆搜走幢师孟恍匿蹭芜撰陌惺冠摹泽阐巩烦逐步求精和分治法逐步求精和分治法,西安电子科技大学计算机学院,-School of Computer Science&Engineering,Xidian University,China,冒泡排序方法,1,2,3,4,5,6,7,18,9,13,43,55,7,43,第五步：令,位置5和位置6,的元素比较，若位置5的元素大，则交换,交换,1,2,3,4,5,6,7,18,9,13,43,7,55,43,编狠裕鞭皂圃斌座蹬岩艘滦兽蒂量幻膨霜懒肝幢派秉祝缨叙贿南哥赘邮肛逐步求精和分治法逐步求精和分治法,西安电子科技大学计算机学院,-School of Computer Science&Engineering,Xidian University,China,冒泡排序方法,1,2,3,4,5,6,7,18,9,13,43,7,55,43,第六步：令,位置6和位置7,的元素比较，若位置6的元素大，则交换,交换,1,2,3,4,5,6,7,18,9,13,43,7,43,55,最大元素被交换到最后一个位置(位置7),下一趟则需将次大元素交换到倒数第二个位置,懦鞍敷请访酪注箩爽搪纳豺静舆均揉助羽朱眩茫束狐某患氰万唱诞孝昨栏逐步求精和分治法逐步求精和