基本算法
c
枚举算法:一一列举问题所有可能的解,并在逐一列举的过程中,检验每个可能解是否是问题的真正解。
【例5】.求1-1000中,能被3整除的数。
【例6】.找出1-1000中所有能被7和11整除的数。
【例7】.涂抹单据。5位数的编号缺连续二位。
【例8】.判断一个正整数是否质数。
【例9】.输出1000以内的素数。
【例10】.找水仙花数。
【例11】.鸡兔同笼问题。
【例12】.百鸡百钱问题。
c
【例5】.求1-1000中,能被3整除的数。
开始
结束
T
F
i=1
i<=1000
i=i+1
i mod 3=0
T
F
输出 i
i mod 3=0
T
F
输出 i
检验
检验:
枚举时注意:
不遗漏,不重复,
且可能的解有限。
c
【例5】.求1-1000中,能被3整除的数。
在枚举算法中往往把问题分解成二部分:
1)一一列举:
这是一个循环结构。要考虑的问题是如何设置循环变量、初值、终值和递增值。循环变量是否参与检验。
2)检验:
一般是一个分支结构。要考虑的问题是检验的对象是谁?逻辑判断后的二个结果该如何处理?
分析出以上二个核心问题后,再合成:要注意循环变量与判断对象是否是同一个变量。
该算法的输入和输出处理:大部分情况下是利用循环变量来代替。判断的一个分支中实现的。
c
【例6】.找出1-1000中所有能被7和11整除的数。
开始
结束
T
F
i=1
i<=1000
i=i+1
i mod 3=0
T
F
输出 i
i mod 7=0 and
i mod 11=0
i mod 77=0
c
【例7】.某单据1xx47,缺千位数和百位数,但知道这个5位数是57或67的倍数,请设计一个算法,输出所有满足条件的5位数,并统计这样的数的个数。
开始
结束
T
F
i=1
i<=1000
i=i+1
i mod 3=0
T
F
输出 i
一一列举:
初值:
终值:
递增值:
i
0
99
1
检验:
n mod 57=0 or
n mod 67=0
n=10047+i*100
如何统计这样的数的个数?
j=0
开始
结束
T
F
i=0
i<100
i=i+1
T
F
输出 n
n mod 57=0 or
n mod 67=0
N=10047+i*100
j=j+1
输出个数 j
c
【例7-1】.某单据1x4x7,缺千位数和十位数,但知道这个5位数是57或67的倍数,请设计一个算法,输出所有满足条件的5位数,并统计这样的数的个数。
一一列举:
初值:
终值:
递增值:
i
0
9
1
检验:
n mod 57=0 or
n mod 67=0
n=10407+i*1000+k*10
如何统计这样的数的个数?
千位十位
k
0
9
1
开始
T
F
i=0
i<10
i=i+1
T
F
k<10
k=k+1
检验
K=0
c
【例7-1】.某单据1x4x7,缺千位数和十位数,但知道这个5位数是57或67的倍数,请设计一个算法,输出所有满足条件的5位数,并统计这样的数的个数。
j=0
开始
结束
T
F
i=0
i<10
i=i+1
T
F
输出 n
n mod 57=0 or
n mod 67=0
n=10407+i*1000+k*10
j=j+1
输出个数 j
T
F
k<10
k=k+1
检验
K=0
c
【例8】.判断一个正整数是否质数。
开始
结束
T
F
i=2
i<n
n mod i=0
T
F
一一列举:
初值:
终值:
递增值:
i
2
n-1
1
检验:
n mod i< >0
输入正整数 n
输入 n
i=i+1
i=n+1
i=n
T
F
输出“否”
输出“是”
算法实例—枚举 来自淘豆网m.daumloan.com转载请标明出处.