自动化求解问题的算法.pptVIP

阿姆斯特朗数 阿姆斯特朗数也叫水仙花数。 定义如下：若一个n位自然数的各位数字的n次方之和等于它本身，则称这个自然数为阿姆斯特朗数。 153 =13+33+53 8208=84+24+0+84 穷举过程 程序代码: For i = 1 To 9 For j = 0 To 9 For k = 0 To 9 x = 100 * i + 10 * j + k If i ^ 3 + j ^ 3 + k ^ 3 = x Then Print x Next k Next j Next i 穷举算法的优化 优化策略1：“用空间换时间”策略,是优化程序的一种常用方法。 优化思路2：减少穷举的变量，考虑元素之间的关联，其他元素通过计算和分析得出解元素的可能值。 优化思路3：减少穷举变量的值域，通过和穷举变量间的数学关系定义解元素的值域。 经过优化的代码 For x = 100 To 999 i = x \ 100 '整除运算 j = x \ 10 Mod 10 '先整除再取余 k = x Mod 10 '取余运算 If i ^ 3 + j ^ 3 + k ^ 3 = x Then Print x Next x 邮票面值。邮局发行一套票面有四种不同值的邮票，如果每封信所贴邮票张数不超过三枚，存在整数Ｒ，使得用不超过三枚的邮票，可以贴出连续的整数１、２、３，…，Ｒ来，找出这四种面值数，使得Ｒ值最大。 袋中取球。口袋中有红、黄、蓝、白、黑五种颜色的小球。每次从口袋中取三个球，问最多有几种不同的取法，输出各种取法。 * 递推法 递推法是利用问题的递推关系求解的一种方法。 设要求问题规模为N的解，当N=1时，解或为已知，或能非常方便地得到解。 递推性质，即当得到问题规模为i-1的解后，由问题的递推性质，能从已求得的规模为1，2，…，i-1的一系列解，构造出问题规模为 i 的解。 程序可从i=0或i=1出发，重复地，由已知至i-1规模的解，通过递推，获得规模为i的解，直至得到规模为N的解。 s=1+2+3+4+5 S=0 S=0+1 S=1+2 (s=3) S=1+2+3 (s=6) S=1+2+3+4 (s=10) S=1+2+3+4+5 (s=15) i 规律： s←s+i 求：s=1+2+3+4+5： S=1+2+3+4+5+6 (s=21) S=1+2+3+4+5+6+7 (s=28) S=1+2+3+4+5+6+7+8 (s=36) +6+7+8 i←i+1 i=1 i=2 i=3 i=4 i=5 i=6 i=7 i=8 这种从头开始一步步地推出问题最终结果的方法，就是递推方法。递推是序列计算中的一种常用方法。 ? 递推算法运用关键： 找出变化规律，写出递推公式 确定递推次数，设计算法，编程 求s=1+2+3+4+…..＋n的值 i<=n S=0 i=i+1 s=s+i 真 假 S=0 Do while i<= n s=s+i i=i+1 Next i Print s S=1 S=1?2 S=1?2?3 S=1?2?3?4 S=1?2?3?4?5 规律： i←i+1 用递推法求阶乘：s=1?2?3… ?N …… 初值： s←s?i s←1 i←1 S=1 i=1 Do while i<= n s=s*i i=i+1 Next i Print s * 递归法 递归算法是一种直接或者间接地调用自身算法的过程。 在计算机编写程序中，递归算法对解决某一类问题是十分有效的，它往往使算法的描述简洁而且易于理解。 下面我给大家讲一个故事，故事说的是： 从前有座山，山上有座庙，庙里有个老和尚在给小和尚讲故事，他说 从前有座山，山上有座庙，庙里有个老和尚在给小和尚讲故事，他说……  递归法 上面的故事用递归算法描述： procedure tell-story begin  if 老和尚停止讲故事 then 此过程结束 else begin  从前有座山，山上有座庙，……他说  tell-story end ifend 从上面事例不难看出，递归算法存在的两个必要条件： （1）?过程的描述中包含它本身； （2）?必须有递归的终止条件