《计算水仙花数ppt课件.ppt》由会员分享，可在线阅读，更多相关《计算水仙花数ppt课件.ppt（17页珍藏版）》请在三一办公上搜索。
1、第21课 计算水仙花数,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）尽可能地使可能解的罗列范围最小，这是为了提高解决问题的效率。,实践活动,寻找水仙花数。水仙花数是指这样的三位整数，其各个位上的数之立方和恰好等于该数自己，例如371，是水仙花数，因为371=33+73+13,设计一个算法寻找出所有的水仙花数。 （1）.算法
3、分析（点击打开算法分析）：水仙花数是三位整数，从100到999共900种可能，罗列出问题所有可能的解并判断 每个位上数字的3次方之和是否恰好等于它自己，使用运算符MOD和对每个整数进行分解，分别得到百位上的数字、十位上的数字和个位上的数字。,算法分析,（2）.分析并编写程序代码：程序界面设计：,控件属性值的设置 参考如下表,分析算法流程，编写代码；Private Sub Command1_Click()Dim sum As IntegerDim i, a, b, c As IntegerList1.ClearFor i = 100 To 999a = i 100 求得百位上的数字ab = i
4、10 Mod 10 求得十位上的数字b c = i Mod 10 求得个位上的数字cIf a 3 + b 3 + c 3 = i Then 判断是否满足条件List1.AddItem (Str(i)sum = sum + 1End IfNext iLabel1.Caption = 个数： + Str(sum)End Sub 运行调试程序;,课堂练习,1.寻找水仙花数问题，请将划线处填写完整：Private Sub Command1_Click()Dim sum As IntegerDim a As Integer, b As Integer, k As IntegerList1.ClearFo
5、r a = 1 To 9For b= 0 To 9For k = 0 To 9If _ Then (1) List1.AddItem (Str(100 * a+ 10 * b+ k)sum = sum + 1End IfNext kNext b_ (2)Label1.Caption = 个数： + Str(sum)End Sub,a 3 + b 3 + k 3 = 100 * a+ 10 * b+ k,Next a,2. 把一个两位数的个位数字与其十位数字交换后得到一个新数，它与原数相加，结果恰好是一个自然数的平方，这样的两位数有多少？请将下面代码中的划线处填写完整：Private Sub C
6、ommand1_Click()Dim s1 As Integer,s2 as IntegerDim a As Integer, b As IntegerList1.ClearFor a = 1 To 9For b = a To 9 假设ba,避免重复s1=10*a+b_ (1) If _ ThenList1.AddItem (str(s1) (1)寻找满足条件的方案Next bNext aEnd Sub,s2=10*b+a,int(sqr(s1+s2)2=s1+s2,算 法 的 效 率（一）,评价一个算法的效率主要是考察算法执行时间的情况。可以在相同的规模下，根据执行时间的长短来评价一个算法的
7、优劣。一个算法的好坏对计算机的效能影响有多大呢？我们来做这样一个比较，假设有两台计算机分别是计算机A和计算机B，计算机A的运算处理速度比计算机B大约快50倍。以求解“百钱买百鸡”（“鸡翁一，值钱五，鸡母一，值钱三，鸡雏三，值钱一。百钱买百鸡。问鸡翁、母、雏各几何？”）为例子，设鸡翁为x只，鸡母为y只，鸡雏为z只。算法A：把公鸡、母鸡、小鸡的枚举范围都是1100；算法B：经粗略计算公鸡的枚举范围为120，母鸡的枚举范围为133，而小鸡的枚举范围应是100 xy。在计算机A上运行算法A程序，在计算机B上运行算法B程序，两台计算机谁先把结果运算出来呢？,算法A的程序代码如下：For x = 1 To
8、 100For y = 1 To 100For z = 1 To 100If (x+y+z=100) And (5* x + 3 * y + z/3 = 100) ThenList1.AddItem Str(x) + “ ” + Str(y) + “ ” + Str(z)End IfNext zNext yNext x算法B程序代码如下：For x = 1 To 20For y = 1 To 33Z=100-x-yIf 5* x +3* y + z/3 = 100 ThenList1.AddItem Str(x) + “ ” + Str(y) + “ ” + Str(z)End IfNext
9、yNext x,运算结果是计算机B先把结果运算出来。为什么会这样呢？我们来分析一下，算法A需要执行100100100=1000000次内循环，而算法B只需要执行2033=660次内循环，虽然计算机A比计算机B快50多倍，但还是计算机B先求得计算结果。 一个好的算法可以算得更快。什么样的算法是好算法呢？通常从时间复杂度和空间复杂度两方面来评价，在这里我们主要讨论时间复杂度。通常我们把算法的基本操作执行的次数作为算法的时间量度T(n)=O(f(n)，表示随着规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称时间复杂度，估算时按该算法对各种输入情况的平均值来考虑。在最坏情况下的复杂度和平均
10、情况下的复杂度是评估算法两种衡量标准。,1.寻找水仙花数。水仙花数是指这样的三位整数，其各个位上的数之立方和恰好等于该数自己，例如371，是水仙花数，因为371=33+73+13,设计一个算法寻找出所有的水仙花数。 算法流程图 程序代码设计 示例程序,2.寻找玫瑰花数。玫瑰花数是指这样的四位整数，其各个位上的数之4次方和恰好等于该数自己，例如1634，1634=14+64+34+44,设计一个算法寻找出所有的玫瑰花数。算法流程图 程序代码设计 示例程序,3.寻找勾股数。“勾股数”指满足勾股定理关系的一组整数，也就是直角三角形三边长恰好都取整数值的特殊情况，3，4，5就是一组勾股数大家都知道32+42=52， 输出50以内能够组成勾股数。算法流程图 程序代码设计 示例程序,4.“百钱买百鸡”问题。中国古代数学家张丘建在张丘建算经中提出一个问题。“鸡翁一，值钱五，鸡母一，值钱三，鸡雏三，值钱一。百钱买百鸡。问鸡翁、母、雏各几何？”。算法流程图 程序代码设计 示例程序,
