3.3 简单算法及其程序的实现-枚举算法的程序实现ppt课件（23张PPT）-2023新浙教版（2019）《高中信息技术》必修第一册.pptx

1、枚举枚举算法的程序实现算法的程序实现 孙子算经孙子算经孙子算经是中国古代重要的数学著作。约成书于四、五世纪，也就是大约一千五百年前，作者生平和编写年不详。卷下第31回，可谓是后世“鸡兔同笼”题的始祖，后来传到日本，变成“鹤龟算”。雉兔同笼雉兔同笼今有雉、兔同笼，上有三十五头，下有九十四足。问：雉、兔各几何？解析算法雉兔同笼用解析算法列数学表达式？假设鸡为x，兔子为y944y2x35yx2/)35*294(2/)9435*4xy（雉兔同笼雉兔同笼答曰：雉二十 三，兔一十二。雉兔同笼雉兔同笼 雉兔同笼 抬脚法 雉兔同笼除了抬脚法，还有什么方法？枚举算法mi枚 一一列举，逐个检验穷举法 算法思想1.

2、把问题的所有的可能解一 一地罗列出来2.每一个可能解进行判断3.确定这个可能解是否是问题的真正解枚举算法 枚举算法雉兔同笼当鸡为1的时候，兔子为1，满足条件吗？当鸡为1的时候，兔子为2，满足条件吗？当鸡为1的时候，兔子为3，满足条件吗？枚举算法雉兔同笼当鸡为2的时候，兔子为1，满足条件吗？当鸡为2的时候，兔子为2，满足条件吗？当鸡为2的时候，兔子为3，满足条件吗？枚举算法雉兔同笼鸡x的取值范围为 兔y的取值范围为 在这个取值范围内的所有x和y 判断：如果 x、y满足35个头 94只脚 那么我们要求的x、y初值终值135135 枚举算法雉兔同笼h=35f =94for x in range(1,

3、35):for y in range(1,35):if x+y=35 and 2*x+4*y=94:print(x,y)int(input(“head:”)int(input(“feet:”)hhh f 枚举算法雉兔同笼h=35f =94for x in range(1,35):for y in range(1,35):if x+y=35 and 2*x+4*y=94:print(x,y)孙子算经之韩信点兵孙子算经之韩信点兵孙子算经之韩信点兵孙子算经之韩信点兵 孙子算经之河妇荡杯河妇荡杯 今有妇人河上荡杯，津吏问曰：“杯何以多？”“家有客几十。”津吏曰：“客几何？”妇人曰：“二人共饭，三人共羹

4、，四人共肉，凡用杯六十五，不知客几何？”荡杯：洗碗二人共饭，三人共羹，四人共肉：二人共用一个饭碗，三人共用一个汤碗，4人共用一个菜碗 孙子算经之河妇荡杯河妇荡杯 for x in range(10,100):if 1/2*x+1/3*x+1/4*x=65:print(x)x=10while x100:if 1/2*x+1/3*x+1/4*x=65:print(x)x+=1 今今有妇人河上荡杯，津吏问曰：有妇人河上荡杯，津吏问曰：“杯何以多？杯何以多？”“”“家有客几十。家有客几十。”津吏曰：津吏曰：“客几何？客几何？”妇人曰：妇人曰：“二人共饭，三人共羹，四人共肉，凡用杯六十五，二人共饭，三人共羹，四人共肉，凡用杯六十五，不知客几何？不知客几何？”课堂小结1.不能遗漏任何一个真正解2.尽可能使可能解的罗列范围最小3.在编程时一般采用包含选择结构的循环结构4.枚举算法的效率一般并不高，但是适用于一些没有明显规律的问题。枚举算法23Thx!