VB递归算法72633.ppt

递归算法 从前有座山 山里有座庙 庙里有个老和尚 给小和尚讲故事 故事是什么呢 从前有座山 山里有座庙 庙里有个老和尚 给小和尚讲故事 故事是什么呢 从前有座山 山里有座庙 庙里有个老和尚 给小和尚讲故事 故事是什么呢 老和尚的故事 案例一 小猴吃桃 有一天小猴子摘若干个桃子 当即吃了一半还觉得不过瘾 又多吃了一个 第二天接着吃剩下桃子中的一半 仍觉得不过瘾又多吃了一个 以后小猴子都是吃尚存桃子一半多一个 到第10天早上小猴子再去吃桃子的时候 看到只剩下一个桃子 问小猴子第一天共摘下了多少个桃子 我们能不能这样设一个函数 算法描述 function你有多少桃子 第几天 如果第10天 那么桃子数 1否则endfunction 桃子数 第n天的桃子数 第n 1天的桃子数 2 1 第n天的桃子数 第n 1天的桃子数 1 2 明天的桃数 1 2 算法实现 Functiontao daysAsInteger AsIntegerIfdays 10Thentao 1Elsetao tao days 1 1 2EndIfEndFunction Tao 1 tao 2 1 2 Tao 2 tao 3 1 2 Tao 3 tao 4 1 2 Tao 8 tao 9 1 2 Tao 9 tao 10 1 2 Tao 10 1 调用 调用 调用 调用 调用 返回 返回 返回 返回 返回 案例二 斐波那契数列问题 斐波纳契数列 又称黄金分割数列 指的是这样一个数列 1 1 2 3 5 8 13 21 34 55 这个数列从第三项开始 每一项都等于前两项之和 求 数列中的第N项是几 算法规则 1 最初两项值为12 第N项的值是它之前两项之和 求第N个斐波纳切数if是最初两项then斐波纳切数 1else斐波纳切数 前两个斐波纳切数之和endif 案例二 斐波那契数列问题 求第N个斐波纳切数if是最初两项then斐波纳切数 1else斐波纳切数 前两个斐波纳切数之和endif FunctionFib nasInteger asIntegerIfthenFib ElseFib EndifEndFunction n 3 Fib n 2 Fib n 1 1 1 1 2 3 5 8 13 21 34 65 案例三 求最大公约数 早在公元前300年左右 欧几里得就在他的著作 几何原本 中给出了高效的解法 辗转相除法 辗转相除法的方法是用较大的数X除以较小的数Y 得到余数Z如果余数为0 则较小数Y就是两者的最大公约数 例如 27和9的最大公约数就是9如果余数不为0 则较小数Y与余数Z的最大公约数就是X与Y的的最大公约数例如 33和9的最大公约数就是9与6的最大公约数 案例三 求最大公约数 求X与Y的公约数 Z是X除Y得到的余数IfZ为0then公约数 Else公约数 的公约数Endif FunctionGYS xasInteger yasInteger asIntegerDimzasIntegerz IfZ 0thenGYS ElseGYS EndifEndFunction XmodY Y GYS Y Z Y和Z Y 递归 将要处理的问题划分为一个或多个子问题 而处理子问题的方法与处理原问题的方法是一样的 这样的处理方法称为递归 递归算法小结 在程序中 递归算法表现为函数在运行过程中调用了自己 每一次递归调用 在处理问题的规模上都有所缩小在问题的规模极小时 必须能给出直接的解答 求年龄 FunctionAge nAsInteger AsIntegerifn 1thenage 3elseage age n 1 2 2endifEndFunction 求斐波那契数 FunctionFib nasInteger asIntegerIfn 3thenFib 1ElseFib Fib n 2 Fib n 1 EndifEndFunction 从前有座山 山里有座庙 庙里有个老和尚 给小和尚讲故事 故事是什么呢 从前有座山 山里有座庙 庙里有个老和尚 给小和尚讲故事 故事是什么呢 从前有座山 山里有座庙 庙里有个老和尚 给小和尚讲故事 故事是什么呢 再看老和尚的故事 这个过程算不算是递归 怎么改才能算是递归 拓展练习 求n n 1 2 3 4 nn n 1 n1 1 拓展练习 恶魔与农夫 有一位农夫不满于自己的贫困 一天 他正在抱怨上天的不公平 一个恶魔出现在他的眼前 他对农夫说 我可以帮助你 你只要从桥上每走