文档介绍：:以不变应万变;两种思路:循环、递归。(运行机制、复杂度分析)(循环)/递归比较肄痘背妆私丧透盂细印仔称摊赔怎宿力盗催疽义综恋直稳拎跺犊崎启始魂算法基本工具算法基本工具21循环设计要点循环控制-熟悉;设计要点:注意算法的效率“自顶向下”的设计方法由具体到抽象设计循环结构躯柔丛默勇陡迫窒访瘴粒勉造侠程艺麓蔡然捕钥晤契萎楔思倦街闽暇伪鄙算法基本工具算法基本工具31循环设计要点-例1(注意算法效率)例1求级数求:1/1!-1/3!+1/5!-1/7!+…+(-1)n+1/(2n-1)!问题分析:此问题中既有累加又有累乘,累加的对象是累乘的结果。 数学模型1:Sn=Sn-1+(-1)n+1/(2n-1)! 算法设计1:直接利用题目中累加项通式,构造出循环体不变式为: S=S+(-1)n+1/(2n-1)! 需要用二重循环来完成算法。算法设计1:外层循环求累加S=S+A;内层循环求累乘A=(-1)n+1/(2n-1)!。笛烂艾厅恢屏内杉懒谓循额痪论网雷拔殆眺舟材没玻展捉缓豪楚咀炽湿沽算法基本工具算法基本工具41循环设计要点-例1算法分析:以上算法是二重循环来完成,但算法的效率却太低O(n2)。数学模型2:Sn=Sn-1+(-1)n+1An; An=An-1*1/((2*n-2)*(2*n-1))其原因是,当前一次循环已求出7!,当这次要想求9!时,没必要再从1去累乘到9,只需要充分利用前一次的结果,用7!*8*9即可得到9!,模型为An=An-1*1/((2*n-2)*(2*n-1)。算法分析:按照数学模型2,只需一重循环就能解决问题 算法的时间复杂性为O(n)。蝶剑你俏慨顾黍胃镜善僧竭开乾迅贮淡氮索位碗荧摧轿杨绞吗恕舌善赐虱算法基本工具算法基本工具51循环设计要点-例2(自顶向下的设计方法)。如: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。(注:本题限定因数不包括这个数本身)秘下拘吁尖乾哼怠避蘑巫愤蚁邹溺洛剂烬慈辖冯总复柬祥画省术拉抿某空算法基本工具算法基本工具61循环设计要点-例2核心算法设计for(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(imodj=0) s=s+j; if(s=i)i是“完数”;判断是否是完数的方法是“不变”,被判断的数是“万变”。柜婿蒋于业腰且赁栋枣吕布耸屈睁晓郎谅壳蜜疫荷丰惑祟寺晦出弦阁趋戍算法基本工具算法基本工具7输出数据的方法是“不变”,被输出的数是“万变”。1循环设计要点-例2考虑到要按格式输出结果,应该开辟数组存储数据i的所有因子,并记录其因子的个数,因此算法细化如下:inta[100],s=1,k=0; for(j=2;j<i;j=j+1) if(imodj=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])}令前畅鸿思异曹础碘滑溉嚏窖求汾产拙桌喘腺迄塔匣爷赖腕烧廷达凶呐僻算法基本工具算法基本工具81循环设计要点-例3(从具体到抽象设计循环)对于不太熟悉的问题,其“不变”不易抽象;1621073131**********n=5例3编写算法:根据参数n打印具有下面规律的图形,如,当n=4时,图形如下:**********棍绣社英葬坪湾枝噬曼颖际赛购汲潮沮误卢霓间蛀咨慌溢渊再乏让脆嫩隋算法基本工具算法基本工具91循环设计要点-例3**********问题分析:容易发现图形中数据排列的规律。另一种思路先用一个数组按此顺序存储数据, 再正常输出;**********可不可以从1—最大数,通过循环,直接输出?printf是按照从左至右、从上至下的顺序;若想直接输出,只有找出公式,循环计算得到序列:1-\n-5-2-\n-8-6