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