1 算法基本工具 2 循环与递归?设计算法重复处理大量数据的思路: 以不变应万变; ?两种思路: 循环、递归。?1循环设计要点?例 求完数?例 打印数字图形?例 求级数? 2 递归设计思路(运行机制、复杂度分析) ?例 累加求和? 3 递归设计要点?例 hanoi 塔? 4 非递归(循环)/递归比较 3 1 循环设计要点?循环控制-熟悉; ?设计要点: ?“自顶向下”的设计方法?由具体到抽象设计循环结构?注意算法的效率 4 1 循环设计要点-例 ?例 编算法找出 1000 以内所有完数。?如: 28 的因子为 1、2、4、7, 14 ,而 28=1+2+4+7+14 。因此 28 是“完数”。编算法找出 1000 之内的所有完数,并按下面格式输出其因子: 28 it ’ s factors are 1 ,2,4, 7, 14 。?问题分析: ?1、这里不是要质因数,所以找到因数后也无需将其从数据中“除掉”。?2、每个因数只记一次,如 8的因数为 1,2,4而不是 1,2, 2,2,4。(注:本题限定因数不包括这个数本身) 5 1 循环设计要点-例 ?核心算法设计? 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 (i % j==0) s=s+j; ? if (s==i) i 是“完数”; 判断是否是完数的方法是“不变”, 被判断的数是“万变”。6 输出数据的方法是“不变”,被输出的数是“万变”。 1 循环设计要点-例 ?考虑到要按格式输出结果,应该开辟数组存储数据 i的所有因子,并记录其因子的个数,因此算法细化如下: ? int a[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’ s factors are : ”,1); for(j=0;j<k;j++) print( “,”,a[k]) }7 1 循环设计要点-例 ?对于不太熟悉的问题,其“不变”不易抽象; ? 1 ? 6 2 ? 10 7 3 ? 13 11 8 4 ? 15 14 12 9 5 ? n=5 ?例 编写算法:根据参数 n打印具有下面规律的图形,如, 当 n=4 时,图形如下: ? 1 ? 5 2 ? 8 6 3 ? 10 9 7 4 8 1 循环设计要点-例 ? 1 ? 5 2 ? 8 6 3 ? 10 9 7 4 ?问题分析: ?容易发现图形中数据排列的规律。?另一种思路?先用一个数组按此顺序存储数据, ?再正常输出; ? 1 ? 5 2 ? 8 6 3 ? 10 9 7 4 ?可不可以从 1—最大数,通过循环,直接输出? ? printf 是按照从左至右、从上至下的顺序;若想直接输出, 只有找出公式,循环计算得到序列: 1-\n-5-2-\n-8-6-3-\n- 10-9-7-4. ?为数组赋值,也要用循环,如何循环? ?又要回到找规律公式的路上吗? ?斜着能循环吗?让循环泼辣一点。 9 1 循环设计要点-例 ?用斜行、列描述新的循环方向。? 1 ? 5 2 ? 8 6 3 ? 10 9 7 4 ?斜[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算法基本工具 来自淘豆网www.taodocs.com转载请标明出处.