2算法基本工具.ppt

:以不变应万变;两种思路:循环、递归。(运行机制、复杂度分析)(循环)/递归比较21循环设计要点循环控制-熟悉;设计要点:“自顶向下”的设计方法由具体到抽象设计循环结构注意算法的效率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。(注:本题限定因数不包括这个数本身)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是“完数”;判断是否是完数的方法是“不变”,被判断的数是“万变”。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])}61循环设计要点-,其“不变”不易抽象;1621073131**********n=:根据参数n打印具有下面规律的图形,如,当n=4时,图形如下:1528631097471循环设计要点-**********问题分析:容易发现图形中数据排列的规律。另一种思路先用一个数组按此顺序存储数据, 再正常输出;**********可不可以从1—最大数,通过循环,直接输出?printf是按照从左至右、从上至下的顺序;若想直接输出,只有找出公式,循环计算得到序列:1-\n-5-2-\n-8-6-3-\n-10-9-7-,也要用循环,如何循环?又要回到找规律公式的路上吗?斜着能循环吗?让循环泼辣一点。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]91循环设计要点-(){inti,j,a[100][100],n,k;input(n);k=1;for(i=1;i<=n;i=i+1)for(j=1;j<=n+1-i;j=j+1){a[i-1+j][j]=k;k=k+1;}for(i=1;i<=n;i=i+1){print(“换行符”);for(j=1;j<=i;j=j+1)print(a[i][j]);}}斜行i取值(1~n)列j取值(1~n+1-i)1528631097410