搜索
授课人：杨鹏第21课计算水仙花数高中信息技术必修2：算法与程序设计授课人：杨鹏1.寻找水仙花数。水仙花数是指这样的三位整数，其各个位上的数之立方和恰好等于该数自己，例如371，是水仙花数，因为371=33+73+13,设计一个算法寻找出所有的水仙花数。2.寻找玫瑰花数。玫瑰花数是指这样的四位整数，其各个位上的数之4次方和恰好等于该数自己，例如1634，1634=14+64+34+44,设计一个算法寻找出所有的玫瑰花数。3.寻找勾股数。“勾股数”指满足勾股定理关系的一组整数，也就是直角三角形三边长恰好都取整数值的特殊情况，3，4，5就是一组勾股数大家都知道32+42=52，输出50以内能够组成勾股数。4.“百钱买百鸡”问题。中国古代数学家张丘建在《张丘建算经》中提出一个问题。“鸡翁一，值钱五，鸡母一，值钱三，鸡雏三，值钱一。百钱买百鸡。问鸡翁、母、雏各几何？”。高中信息技术必修2：算法与程序设计授课人：杨鹏枚举算法枚举算法的基本思想是把问题所有的可能解一一地罗列出来，并对每一个可能解进行判断，以确定这个可能解是否是问题的真正解。在设计枚举算法时，必须注意的是：（1）不能遗漏任何一个真正解，这是问题本身所要求的；（2）尽可能地使可能解的罗列范围最小，这是为了提高解决问题的效率。高中信息技术必修2：算法与程序设计授课人：杨鹏实践活动寻找水仙花数。水仙花数是指这样的三位整数，其各个位上的数之立方和恰好等于该数自己，例如371，是水仙花数，因为371=33+73+13,设计一个算法寻找出所有的水仙花数。（1）.算法分析（点击打开算法分析）：水仙花数是三位整数，从100到999共900种可能，罗列出问题所有可能的解并判断每个位上数字的3次方之和是否恰好等于它自己，使用运算符MOD和\对每个整数进行分解，分别得到百位上的数字、十位上的数字和个位上的数字。高中信息技术必修2：算法与程序设计授课人：杨鹏算法分析i1000？输出一个水仙花数i结束Na←百位上的数字开始i←100b←十位上的数字c←个位上的数字是否是水仙花数？a3+b3+c3=i?Yi←i+1NY高中信息技术必修2：算法与程序设计授课人：杨鹏（2）.分析并编写程序代码：①程序界面设计：高中信息技术必修2：算法与程序设计授课人：杨鹏控件属性值的设置参考如下表对象名属性名属性值Form1Caption水仙花数List1（用绘制而成）list空白Command1Caption计算高中信息技术必修2：算法与程序设计授课人：杨鹏②分析算法流程，编写代码；PrivateSubCommand1_Click()DimsumAsIntegerDimi,a,b,cAsIntegerList1.ClearFori=100To999a=i\100‘求得百位上的数字ab=i\10Mod10'求得十位上的数字bc=iMod10'求得个位上的数字cIfa^3+b^3+c^3=iThen'判断是否满足条件List1.AddItem(Str(i))sum=sum+1EndIfNextiLabel1.Caption=个数：+Str(sum)EndSub③运行调试程序;高中信息技术必修2：算法与程序设计授课人：杨鹏课堂练习1.寻找水仙花数问题，请将划线处填写完整：PrivateSubCommand1_Click()DimsumAsIntegerDimaAsInteger,bAsInteger,kAsIntegerList1.ClearFora=1To9Forb=0To9Fork=0To9If__________________________________Then‘(1)List1.AddItem(Str(100*a+10*b+k))sum=sum+1EndIfNextkNextb_____________________’(2)Label1.Caption=个数：+Str(sum)EndSuba^3+b^3+k^3=100*a+10*b+kNexta高中信息技术必修2：算法与程序设计授课人：杨鹏2.把一个两位数的个位数字与其十位数字交换后得到一个新数，它与原数相加，结果恰好是一个自然数的平方，这样的两位数有多少？请将下面代码中的划线处填写完整：PrivateSubCommand1_Click()Dims1AsInteger,s2asIntegerDimaAsInteger,bAsIntegerList1.ClearFora=1To9Forb=aTo9'假设b≥a,避免重复s1=10*a+b____________________________‘(1)If__________________________ThenList1.AddItem(str(s1))‘(1)寻找满足条件的方案NextbNextaEndSubs2=10*b+aint(sqr(s1+s2))^2=s1+s2高中信息技术必修2：算法与程序设计授课人：杨鹏算法的效率（一）评价一个算法的效率主要是考察算法执行时间的情况。可以在相同的规模下，根据执行时间的长短来评价一个算法的优劣。一个算法的好坏对计算机的效能影响有多大呢？我们来做这样一个比较，假设有两台计算机分别是计算机A和计算机B，计算机A的运算处理速度比计算机B大约快50倍。以求解“百钱买百鸡”（“鸡翁一，值钱五，鸡母一，值钱三，鸡雏三，值钱一。百钱买百鸡。问鸡翁、母、雏各几何？”）为例子，设鸡翁为x只，鸡母为y只，鸡雏为z只。算法A：把公鸡、母鸡、小鸡的枚举范围都是1～100；算法B：经粗略计算公鸡的枚举范围为1～20，母鸡的枚举范围为1～33，而小鸡的枚举范围应是100－x－y。在计算机A上运行算法A程序，在计算机B上运行算法B程序，两台计算机谁先把结果运算出来呢？高中信息技术必修2：算法与程序设计授课人：杨鹏算法A的程序代码如下：Forx=1To100Fory=1To100Forz=1To100If(x+y+z=100)And(5*x+3*y+z/3=100)ThenList1.AddItemStr(x)+“”+Str(y)+“”+Str(z)EndIfNextzNextyNextx算法B程序代码如下：Forx=1To20Fory=1To33Z=100-x-yIf5*x+3*y+z/3=100ThenList1.AddItemStr(x)+“”+Str(y)+“”+Str(z)EndIfNextyNextx高中信息技术必修2：算法与程序设计授课人：杨鹏运算结果是计算机B先把结果运算出来。为什么会这样呢？我们来分析一下，算法A需要执行100×100×100=1000000次内循环，而算法B只需要执行20×33=660次内循环，虽然计算机A比计算机B快50多倍，但还是计算机B先求得计算结果。一个好的算法可以算得更快。什么样的算法是好算法呢？通常从时间复杂度和空间复杂度两方面来评价，在这里我们主要讨论时间复杂度。通常我们把算法的基本操作执行的次数作为算法的时间量度T(n)=O(f(n))，表示随着规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称时间复杂度，估算时按该算法对各种输入情况的平均值来考虑。在最坏情况下的复杂度和平均情况下的复杂度是评估算法两种衡量标准。高中信息技术必修2：算法与程序设计授课人：杨鹏1.寻找水仙花数。水仙花数是指这样的三位整数，其各个位上的数之立方和恰好等于该数自己，例如371，是水仙花数，因为371=33+73+13,设计一个算法寻找出所有的水仙花数。算法流程图程序代码设计示例程序高中信息技术必修2：算法与程序设计授课人：杨鹏2.寻找玫瑰花数。玫瑰花数是指这样的四位整数，其各个位上的数之4次方和恰好等于该数自己，例如1634，1634=14+64+34+44,设计一个算法寻找出所有的玫瑰花数。算法流程图程序代码设计示例程序高中信息技术必修2：算法与程序设计授课人：杨鹏3.寻找勾股数。“勾股数”指满足勾股定理关系的一组整数，也就是直角三角形三边长恰好都取整数值的特殊情况，3，4，5就是一组勾股数大家都知道32+42=52，输出50以内能够组成勾股数。算法流程图程序代码设计示例程序高中信息技术必修2：算法与程序设计授课人：杨鹏4.“百钱买百鸡”问题。中国古代数学家张丘建在《张丘建算经》中提出一个问题。“鸡翁一，值钱五，鸡母一，值钱三，鸡雏三，值钱一。百钱买百鸡。问鸡翁、母、雏各几何？”。算法流程图程序代码设计示例程序