设计思想之穷举

什么是穷举

穷举就是逐一列举问题所涉及的所有情况。
穷举法常用于解决”是否存在”和”有多少种可能”的问题。

应用穷举的示例

白鸡百钱问题

1
2
3
4
5
6
7
8
9
# 已知公鸡5元一只,母鸡3元一只,小鸡一元3只。现用100元钱买100只鸡,问:公鸡母鸡小鸡各几只?

for i in range(100):
for j in range(100):
for k in range(100):
number = i + j +k
price = i*5 + j*3 + k*(1/3)
if (number <= 100) & (price <= 100) & (k % 3 == 0):
print("There are %dck, %d hen, and %d chick" % (i,j,k))

鸡兔同笼问题

1
2
3
4
5
6
7
8
9
# 今有鸡兔同笼,上有三十五头,下有九十四足,问鸡兔各几只?

for i in range(1,35):
for j in range(1,35):
if (i*2 + j*4) == 94 and (i + j == 35):
print("There are %d chickens,and %d rabbits" % (i,j))

result = [(i,j) for i in range(1,35) for j in range(1,35) if (i*2 + j*4) == 94 and i + j ==35]
print(result)
0%