1、枚举算法(第一十八课时)年年 级:高一级:高一 学学 科:信息技术(人教科:信息技术(人教/中图版)中图版)顺序顺序结构结构选择选择结构结构循环循环结构结构解析算法解析算法通过找出解决问题的前提条件与通过找出解决问题的前提条件与结果之间关系的表达式,并计算结果之间关系的表达式,并计算表达式的值来实现问题的求解。表达式的值来实现问题的求解。复习今有雉兔同笼,上有三十五头,下有九十四足,问雉兔各几何?(雉兔至少有一只)复习x+y=a2x+4y=bx=2*a b/2y=b/2-a解析法解鸡兔同笼问题解析法解鸡兔同笼问题1.分析问题隐含关系已知条件求解目标x+y=352x+4y=94求鸡的个数求兔的个
2、数鸡和兔的个数必须同时满足已知所有条件解析法解鸡兔同笼问题鸡兔头的数量脚的数量111 +1=21*2+1*4=6 121+2=31*2+2*4=10131+3=41*2+3*4=1434134+1=35 34*2+1*4 =72 1.分析问题解析法解鸡兔同笼问题1.分析问题鸡兔脚的数量1341*2+34*4=1382332*2+33*4=1363323*2+32*4=1344314*2+31*4=13234134*2+1*4 =72解析法解鸡兔同笼问题1.分析问题:一一列举列举可能的解,即枚举范围是多少?解析法解鸡兔同笼问题1.分析问题:逐一检验检验可能的解,判断条件是什么?鸡与兔共94只脚解
3、析法解鸡兔同笼问题2.设计算法解析法解鸡兔同笼问题算法优化枚举算法的思想枚举算法的思想用自己的话说说看枚举算法的思想枚举算法的思想:枚举算法要注意的问题题解的可能范围,不重重不漏漏考虑优化算法,缩小缩小枚举范围,提高解决问题的效率实践活动1:小明的幸运年老师问小明的年龄,小明说:今年是我的幸运年。我出生年份的四位数字加起来刚好是我的年龄(周岁)。已知今年是2020年,请推断出小明的出生年份(4位整数,默认小明100岁)。实践活动1:小明的幸运年1.分析问题:需要存储哪些数据?变量是何种数据类型?实践活动1:小明的幸运年1.分析问题:一一列举列举可能的解,即枚举范围是多少?实践活动1:小明的幸运
4、年1.分析问题:逐一检验检验可能的解,判断条件是什么?出生年份的四位数字加起来刚好是小明的年龄实践活动1:小明的幸运年1.分析问题:如何得到出生年份的数位之和呢?实践活动1:小明的幸运年y/=10y/=10sum+=y%10sum+=y%10实践活动1:小明的幸运年y/=10y/=10sum+=y%10sum+=y%10实践活动1:小明的幸运年1.分析问题:如何得到出生年份的数位之和呢?实践活动1:小明的幸运年2.设计算法:输出结果输出结果输入数据输入数据处理数据处理数据实践活动1:小明的幸运年3.编程调试 如何得到出生年份的数位之和呢?实践活动1:小明的幸运年3.编程调试 将其转换为函数形式
5、:实践活动1:小明的幸运年3.编程调试实践活动1:小明的幸运年实践活动1:小明的幸运年1.分析问题:如何得到出生年份的数位之和呢?实践活动1:小明的幸运年str(y)for j in str(y)int(j)实践活动1:小明的幸运年3.编程调试 如何得到出生年份的数位之和呢?实践活动1:小明的幸运年实践活动2:水仙花数“水仙花数”是指一个三位自然数,其各位数字的立方和等于该数本身。编程输出所有的水仙花数,每行一个。例如153是“水仙花数”,因为:153=13+53+33。实践活动2:水仙花数1.分析问题:需要存储哪些数据?变量是何种数据类型?实践活动2:水仙花数1.分析问题:逐一检验检验可能的
6、解,判断条件是什么?实践活动2:水仙花数2.设计算法:输出结果输出结果输入数据输入数据处理数据处理数据实践活动2:水仙花数3.编程调试 如何分离各位数字,并得到三位数字的立方之和?实践活动2:水仙花数实践活动2:水仙花数1.分析问题:一一列举列举可能的解,即枚举范围是多少?实践活动2:水仙花数1.分析问题:逐一检验检验可能的解,判断条件是什么?实践活动2:水仙花数2.设计算法:输出结果输出结果输入数据输入数据处理数据处理数据实践活动2:水仙花数3.编程调试可以用枚举算法解决吗破解密码求方程2x+y=9的整数解寻找1000以内的所有素数求方程2x+y=9的正整数解求方程2x+y=9的实数解枚举算法的应用警察抓了A、B、C、D四名偷窃嫌疑犯,其中有一人是小偷。审问中:A说:“我不是小偷”。B说:“C是小偷”。C说:“小偷肯定是D”。D说:“C冤枉人”。现在已经知道四人中三人说的是真话,一人说的是假话。到底谁是小偷呢?枚举算法的应用只运用+、-、*、/和括号,连接四个数字,可乱序,使得最后得数为24,符号运用次数不限。小结与练习小结与练习编写程序解决以下问题:Q1:从2000年到2050年,哪些年份是闰年?能够被4整除但不能被100整除的是闰年 能够被400整除的也是闰年Q2:寻找1000以内的所有素数。