3.8递归算法实例及程序实现.ppt

38递归算法实例及程序实现,1递归算法的概念一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，称为递归算法。递归算法的基本思想是把规模较大的、较难解决的问题变成规模较小的、容易解决的同一问题，规模较小的问题又变成规模更小的问题，当问题小到一定程度时，可以直接得出它的解，从而得到原来问题的解。即采用“大事化小、小事化了”的基本思想。诸如著名的汉诺塔问题、八皇后问题、斐波那契(Fibonacci)的兔子问题、猴子吃桃问题、年龄问题等都是递归问题。VB允许一个自定义函数在函数体的内部调用自己，这样的函数就叫递归函数。,2递归算法的实现要点递归调用必须是有限制的，有限才有意义。所以在进行算法描述时必须设置相关的控制条件，使其成为有限。这可以通过条件语句(If语句)来实现，即只有在设定的条件成立时递归才继续，否则终止递归。可见，构成递归的必须满足以下条件：(1)有明确的结束递归的边界条件(又称终止条件)以及结束时的边界值；(2)函数的描述中包含其本身，即能用递归形式表示，且递归终止条件的发展。,3递归算法的设计方法当所求解问题难于直接求解时，首先，把问题分解成若干个难度较小、较容易求解的子问题，子问题与原问题具有类同的结构。如果子问题能够直接求解，则解之；如果子问题仍不能直接求解，将每个子问题再分解成若干个更简单的子问题，直到解出的子问题能够很容易地求解或解为已知，这是实现递归的模板。然后，设计递归出口(即结束递归的边界条件)，在满足出口条件时，递归函数不能再调用自己，必须返回一个确定的值。将这两方面的问题分析好之后，就可以在程序体中定义递归调用了。,在通常情况下，递归调用都是要受到条件控制的，而且在被调用的过程中，会对调用条件进行有规律的修改，直到满足边界条件，返回边界值，结束递归；然后按原来的路径逐层返回，求出原问题的解。由此可知，递归算法的设计关键在于递归描述和递归终止条件。,如下图所示是递归算法调用过程示意图：,4递归算法的实现过程递归算法的过程是不断的自调用，直到到达递归出口才结束。然后，递归算法开始按最后调用的过程最先返回的次序逐层返回，返回到最外层的调用语句时递归算法执行过程结束。可见，递归的实现过程包含了“调用”和“返回”两个阶段。许多问题都是可以利用递归算法进行求解的。VB中一个最常用的例子就是计算阶乘。例如，用递归函数实现计算机n！的求解。运行界面如下图所示。,代码如下：PrivateSubCommand1_Click()DimnAsInteger,mAsDoublenVal(Text1.Text)mf(n)Text2.TextStr(n)“的阶乘为”Str(m)EndSubFunctionf(nAsInteger)AsDoubleIfn1Thenf1Else参数n的值大于1fn*f(n1)递归实现调用自身来计算f(n1)的值EndIfEndFunction注：该示例程序在素材文件夹下vb36文件夹中。,本节的学习要求掌握递归算法的基本思想，掌握递归程序的实现要点。学会编写简单的递归函数。考查方式为选择题与填空题。,1下列有关递归的说法，错误的是()A递法算法的代码一般较少B递归算法一定要有终止条件C递归算法体现了大事化小的思想D递归函数中可以不包含条件控制语句,D,2文本框对象Text1中的Text属性发生改变时，会驱动以下事件处理过程PrivateSubText1_Change()IfLen(Text1.Text)8ThenText1.TextText1.TextText1.TextEndSub该过程体现的算法思想是()A排序算法B递归算法C查找算法D解析算法,B,3下列VB程序模块可以计算正整数n阶乘的值。Functionf(nAsInteger)AsDoubleIfn1Thenf1Elsefn*f(n1)EndIfEndFunction该模块采用的是()A查找算法B解析算法C递归算法D排序算法,C,4有五个人坐在一起，问第5个人多少岁？他说比第4个人大2岁，问第四个人岁数，他说比第3个人大2岁，问第三个人岁数，他说比第二个人大2岁，问第二个人岁数，他说比第1个人大2岁，问第1个人岁数，他说他10岁，请问第五个人多大？以下是VB程序代码：PublicFunctionage(nAsInteger)AsLongIfn1Thenage10Elseageage(n1)2EndIfEndFunctionPrivateSubCommand1_Click()MsgBox“第五个人的年龄为”Str(age(5)EndSub该程序采用的算法是_。,递归算法,5用递归算法求1n个连续自然数的和的VB程序段代码如下：Functionsum(nAInteger)AInteger求1n个连续自然数的和Ifn1Thensum1Elsesum_EndIfEndFunctionPrivateSubCommand1_Click()Inputbox“请输入n的值”Msgbox“1n的和为”str(sum(n)EndSub,n+sum(n-1),划线处应填入的语句是_。,6编写一个VB程序，实现字符串反序显示。该程序如下图所示：,Functionreverse(stAsString)AsString字符串反序IfLen(st)1ThenreversestElsereverseRight(st,1)&reverse(Left(st,Len(st)1)EndIfEndFunctionPrivateSubCommand1_Click()Text2.Text_EndSub,在文本框Text1中输入一个字符串，点击“返序”按钮Command1，在文本框Text2中以反向方式显示该字符串。实现该程序的代码如下：,(1)实现该程序的算法是_。(2)划线处应填入的语句是_。注：该示例程序在素材文件夹下vb37文件夹中。,递归算法,reverse(Text1.text),7编写一个实现将一个十进制整数转换成二进制的VB程序。运行该程序，如下图所示。在文本框Text1中输入数n，点击“转换”按钮，在标签Label2中显示转换结果。,PrivateSubCommand1_Click()DimnAsIntegerDimsAsStringnVal(Text1.Text)strans(n)Label2.Caption“该数的二进制为：”sEndSubFunctiontrans(nAsInteger)AsStringIfn1ThentransnElsetrans_EndIfEndFunction,(1)实现该程序的算法是_。(2)划线处应填入的语句是_。,递归算法,trans(n2)&(nMod2),8回文数是一个数顺着读倒着读都是一样大小的数。例如数：12321，顺着序倒着读都是同一个数。请在VB中，实现用递归算法判断一个数是否是回文数。程序运行界面如下所示，在文本框Text1中输入一个数，点击“判断”按钮Command1，在标签Label2中显示判断结果。,程序代码如下：Functionhws(stAsString)AsBoolean判断一个数是否是回文数IfLen(st)Right(st,1)ThenExitFunctionEndIfhwshws(Mid(st,2,Len(st)2)EndFunctionPrivateSubComma