文档介绍：枚举算法2
第三讲
（遍历算法）
（回溯算法之一）
如果可能解，不完美（不连续或离散）怎么办？
把各种可能的情况都考虑到，并对全部可能结果逐一进行判断，过滤掉那些不符合要求的，保留符合要求的结果，这种方法叫枚举算法
一般思路：
步骤一：确定可能解的范围；
步骤二：根据各种约束条件，对每一个可能解进行判断
CA(255860045)
1
中国古代《孙子算经》共三卷，成书大约在公元5世纪。 “鸡兔同笼”问题：
今有雉兔同笼，上有三十五头，下有九十四足，问雉兔各几何？
分析：
则：x+y=35
2*x+4*y=94
可能的解：
X: 0-35
Y: 0-23
约束条件
设x，y分别为鸡、兔的个数
可能的解
2
建立一个循环, 可能的解如下：
x<=35
Y
N
开始
x ←0
x ←x+1
结束
2x+4y=94？
N
y ←35-x
Y
正确解
x
Y=35-x
0
35
1
34
2
33
…
…
35
0
3
x<=35
Y
N
开始
x ←0
x ←x+1
结束
2x+4y=94？
N
y ←35-x
Y
正确解
S1]x从0到35，每次递增1。对每个x执行如下操作
][头]y=35-x
][腿]如果2x+4y=94,则x，y为正确解。
4
又后一例：
我国古代数学家张丘建在《算经》中提出了著名的百鸡百钱问题
“鸡翁一值钱5，
鸡母一值钱3，
鸡雏三值钱1”
现有100钱，欲买100只鸡，问：鸡翁、鸡母、鸡雏各买几只？
分析：
设x，y，z分别为买的鸡翁、鸡母、鸡雏的个数
则：x+y+z=100
5*x+3*y+z/3=100
可能的解
X: 0-20
Y: 0-33
Z: 100-x-y
和：效率和逻辑的折中
5
建立一个双重循环, 可能的解如下：
x<=20
Y
N
开始
x ←0
x ←x+1
结束
y<=33
N
y ←y+1
y ←0
Y
判断可能的解
是否是真正的解
x
y
z
0
0
100
0
1
99
0
2
98
…
…
…
0
33
67
1
0
99
…
…
…
20
33
47
6
检验可能的解是否真正的解
判断：5*x+3*y+z/3=100
若是，x,y,z就是一个真正的解
算法：
←0
s2.
←x+1
<=20 ,则转2
y←0
s3.
←y+1
<=33,转3；否则7
z←100-x-y
+3y+z/3=100,则输出x,y,z;
否则转5
百鸡
百钱
如何提高效率？
S1]x从0到20，每次递增1,对每个x执行如下子操作。
]y从0到33，每次子递增1，对每个y执行如下操作。
]z=100-x-y
]如果5x+3y+z/3=100，则输出x,y,z
7
作业1：百马百瓦
有一百匹马，分三种：大马，中马，小马。有一百块同样的瓦。一匹大马驼3块瓦，一匹中马驼1块瓦，三匹小马合驼1块瓦。这一百匹马，正好驼一百块瓦。问：大马，中马，小马各多少匹？请列出所有可能的方案。
8
素数判断
任意给一个正整数n，
判断其是否为素数
素数（质数）：只能被1或本身整除。如2，3,5,7
解题空间：
2~n-1
优化为：2~
排除条件：
是否整除
9
素数判断
任意给一个正整数n，
判断其是否为素数
素数（质数）：只能被1或本身整除。如2，3,4
解题空间：
2~n-1
优化为：2~
排除条件：
是否整除
S1] isPrime=true
S2]i从2到根下n，对每个i执行如下操作
]如果n能整除i，
]isPrime=false
]转s3
S3]如果isPrime=true，是素数；否则不是素数
10