2算法基本工具.ppt

算法基本工具床俩躯衍妊俗榜***:以不变应万变;两种思路:循环、递归。(运行机制、复杂度分析)(循环)/递归比较喂钮嗣族羔诸夕浇杏湿旗解残讶叁刑妇颅的抱攒尿宫耪篙储较鳃燥妆闹洞2算法基本工具2算法基本工具21循环设计要点循环控制-熟悉;设计要点:“自顶向下”的设计方法由具体到抽象设计循环结构注意算法的效率蚁韧谴度呢拂煌柳只更与村诵附筐爬陆扮摩筑冕溺烩仕喀父境绩矿烯醉鞭2算法基本工具2算法基本工具31循环设计要点-。如:28的因子为1、2、4、7,14,而28=1+2+4+7+14。因此28是“完数”。编算法找出1000之内的所有完数,并按下面格式输出其因子:28it’sfactorsare1,2,4,7,14。问题分析:1、这里不是要质因数,所以找到因数后也无需将其从数据中“除掉”。2、每个因数只记一次,如8的因数为1,2,4而不是1,2,2,2,4。(注:本题限定因数不包括这个数本身)柴笼骡丽级么郝窿谚岳杉缀左据惑鬃黍淌贯邹删宅太校岭苟轴辩影籽介墒2算法基本工具2算法基本工具41循环设计要点-(i=0;i<n;i=i+1){ 判断i是否是完数; if是“完数”则按规则输出; }自顶向下,逐步求精判断i是否是完数for(j=2;j<i;j=j+1) 找i的因子,并累加; if累加值等于i,则i是完数;判断i是否是完数s=1; for(j=2;j<i;j=j+1) if(i%j==0) s=s+j; if(s==i)i是“完数”;判断是否是完数的方法是“不变”,被判断的数是“万变”。贵徘漱委系私抉囚戳肺设庶漾屁耸倔讼宇破舅暴伶揍竣仟窿飘刑缸倾拎铝2算法基本工具2算法基本工具5输出数据的方法是“不变”,被输出的数是“万变”。1循环设计要点-,应该开辟数组存储数据i的所有因子,并记录其因子的个数,因此算法细化如下:inta[100],s=1,k=0; for(j=2;j<i;j=j+1) if(i%j==0){ s=s+j; a[k]=j; k=k+1; }if(s==i){print(s,“it’sfactorsare:”,1);for(j=0;j<k;j++) print(“,”,a[k])}翌闰骤藉足略荐转圃秘懊荚松赛修奥色影囱差香邦斯到韧遏夫轿魔芬读钥2算法基本工具2算法基本工具61循环设计要点-,其“不变”不易抽象;1621073131**********n=:根据参数n打印具有下面规律的图形,如,当n=4时,图形如下:**********泰源办挨眠芯疚疑患苛沫惰锨桑揭噬厢簇靳浑芦恳并丹哥跪终炎辕邻饵帖2算法基本工具2算法基本工具71循环设计要点-**********问题分析:容易发现图形中数据排列的规律。另一种思路先用一个数组按此顺序存储数据, 再正常输出;**********可不可以从1—最大数,通过循环,直接输出?printf是按照从左至右、从上至下的顺序;若想直接输出,只有找出公式,循环计算得到序列:1-\n-5-2-\n-8-6-3-\n-10-9-7-,也要用循环,如何循环?又要回到找规律公式的路上吗?斜着能循环吗?让循环泼辣一点。茁倪抗沉白悠娃惕悔胸豁露已瞬倪晌朗培奶竖术遗松押锣皆冬时曰序酋牙2算法基本工具2算法基本工具81循环设计要点-、列描述新的循环方向。**********斜[1,1]—a[1,1]斜[1,2]—a[2,2]斜[1,3]—a[3,3]斜[1,4]—a[4,4]斜[2,1]—a[2,1]斜[2,2]—a[3,2]斜[2,3]—a[4,3]列号相同;行号(显然行号与列号有关)第1斜行,对应行号1—n,行号与列号j同;第2斜行,对应行号2—n,行号比列号j大1;第3斜行,对应行号3—n,行号比列号j大2;斜[3,1]—a[3,1]斜[3,2]—a[4,2]斜行i取值(1~n)列j取值(1~n+1-i)a[i-1+j][j]这样可以描述循环。但数组元素的存取还是基于“行列”,能否简单转换?关键问题:第i斜行、j列的数据对应于第几行第几列的元素?斜[4,1]—a[4,1]掌谆矗侯烛云支粕是惋僵蓟温蔚呻鹃惭梁猎渡姥墙泛葛湍繁二榜炽喷氦动2算法基本工具2算法基本工具91循环设计要点-(){inti,j,a[100][100],n,k;input(n