用递归法解决问题.ppt

3 5用递归法解决问题 徐州第二十六中学朱九妹 从前有座山 山里有座庙 庙里有个老和尚给小和尚讲故事 讲什么呢 从前有座山 山里有座庙 庙里有个老和尚给小和尚讲故事 讲什么呢 从前有座山 山里有座庙 庙里有个老和尚给小和尚讲故事 讲什么呢 从前有座山 山里有座庙 庙里有个老和尚给小和尚讲故事 讲什么呢 从前有座山 山里有座庙 庙里有个老和尚给小和尚讲故事 讲什么呢 从前有座山 山里有座庙 庙里有个老和尚给小和尚讲故事 讲什么呢 从前有座山 山里有座庙 庙里有个老和尚给小和尚讲故事 讲什么呢 从前有座山 山里有座庙 庙里有个老和尚给小和尚讲故事 讲什么呢 从前有座山 山里有座庙 庙里有个老和尚给小和尚讲故事 讲什么呢 从前有座山 山里有座庙 庙里有个老和尚给小和尚讲故事 讲什么呢 故事 这个故事有什么特点 自己调用自己 如果在一个函数中 它自己调用了自己 这种现象叫递归调用 如果A函数调用B函数 B函数又反过来调用A函数 那这种现象也叫做递归调用 如果一个函数在定义时 直接或间接的调用了自己 这种算法在程序设计中统称为递归法 递归算法的基本思想是 把规模大的 较难解决的问题变成规模较小的 易解决的同一问题 规模较小的问题又变成规模更小的问题 并且小到一定程度可以直接得出它的解 从而得到原来问题的解 子程序中定义递归调用 一般格式为 if边界条件1成立then赋予边界值1 elseif边界条件2成立then赋予边界值2 else调用解决问题的通式endif 自定义函数 递归法一般需要定义函数来实现 这里所讲的函数是自定义函数 虽然VB为我们提供了大量的标准函数 但我们在实际应用时难免有时还是找不到合意的 那就只有自己解决了 这样为了一个特定的任务而编出来的函数叫自定义函数 Abs len date sqr msgbox 等 二 自定义函数的作用1 可以方便的把较为复杂的问题分解成若干个小问题去处理 公司里就是采用这中模式的 2 使程序结构清晰 层次分明 增强了程序的可读性 一 标准函数VB给我们提供了一些标准函数 我们不用了解这些函数如何求出来的 只管直接调用它们 挺方便的 如正弦函数 余弦函数 算术平方根 有了这些函数 我们觉得很省事 如 求1加到100的算术平方根这个程序我们可以这样编写 例1dimIasinteger sassingles 0fori 1to100dos s sqr i nextiprint s s 在这个程序里 我们直接用到了求平方根函数 至于sqr 1 sqr 2 如何求出来的我们不需过问 只管直接用它的结果便是了 象这样 VB给我们提供的 我们不用了解这些函数如何求出来的 只管直接调用它们的这类函数叫做标准函数 二 用户自定义函数我们来看看下面一个例子 求 1 2 3 10 如果要编写程序 我们看到求阶乘的操作要执行10次 只不过每次所求的数不同 我们想 不至于编写10遍求阶乘的程序吧 我们希望有一个求阶乘的函数 假设为JS X 那么我们就可以这样求这道题了 例2dimIasinteger jasintegerdimsasintegers 0fori 1to10dos s js i nextiprint s s现在的问题是 VB没提供JS X 这样一个标准函数 这个程序是通不过的 如果是PASCAL的标准函数 我们可以直接调用 如前面的sqr i 而PASCAL提供给我们的可供直接调用的标准函数不多 没关系 我们编写自己的函数 三 函数编写 在VB中 自定义函数形式如下 Public Private Function 参数列表 As类型 局部常量 变量定义语句组函数名称 返回值EndFunction Public 公共的 全局变量 指在所有程序 包括主程序和过程 中都可以使用的内存变量 Private 私人的 局部变量 用private语句声明的变量可被本窗体 模块的任何过程访问 但其他模块却不能访问该变量 参数列表 ByVal ByRef 变量名 As类型 表示该参数按值传递不会修改变量原来的值 表示该参数按地址传递会直接改变原来的变量值 例3编写一求阶乘的函数 我们给此函数取一名字就叫JS fUNCTIONjs nasinteger asintegerdimIasinteger sasintegers 1fori 1tondos s inextijs send 自定义函数的调用 可以有三种格式 格式一 变量 函数名称 参数 格式二 Call函数名称 参数 格式三 函数名称参数 使用递归算法大致结构为 递归出口 递归体一个递归算法 当其问题求解的规模越来越小时必定有一个递归出口 就是不再递归调用的语句 递归体则是每次递归时执行的语句序列 递归调用算法 例如 编写递归函数求5 的值 PublicFunctions nAsInteger AsLongIfn 1Thens 1Elses n s n 1 EndifEndFunctionPrivateSubForm Cl