2算法基本工具.pptx

1
循环与递归
设计算法重复处理大量数据的思路:以不变应万变;
两种思路:循环、递归。
1 循环设计要点
求完数
打印数字图形
求级数
2 递归设计思路(运行机制、复杂度分析)
累加求和
3 递归设计要点
hanoi塔
4 非递归(循环)/递归比较
库文档分享
2
1 循环设计要点
循环控制-熟悉;
设计要点:
“自顶向下”的设计方法
由具体到抽象设计循环结构
注意算法的效率
库文档分享
3
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。(注:本题限定因数不包括这个数本身)
库文档分享
4
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是“完数”;
判断是否是完数的方法是“不变”,被判断的数是“万变”。
库文档分享
5
输出数据的方法是“不变”,被输出的数是“万变”。
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])
}
库文档分享
6
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
库文档分享
7
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.
为数组赋值,也要用循环,如何循环?
又要回到找规律公式的路上吗?
斜着能循环吗?让循环泼辣一点。
库文档分享
8
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斜行,对应行号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]
库文档分享
9
1 循环设计要点-
main( )
{
int i,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+