第5节 递归算法
模拟演练
选考题组
1.我们在用计算机解决问题时,常采用递归法。已知:f(3)=3;当n>3时,f(n)=f(n-1)*n;编程求f(5)的值。下列结果正确的是( )
A.120 B.60
C.3 D.23
答案 B 根据题意,得f(5)=f(4)*5,要算出f(5)的值需要知道f(4)的值,而f(4)=f(3)*4, f(3)的值已知,将f(3)=3代入算出 f(4)=12,继续代入算出f(5)=60。
2.有8阶楼梯,从第0阶开始往上走,每次可以走一步或者两步,自定义函数fg可以计算走完n阶楼梯有多少种走法:
Function fg(n as Integer)As Integer
If n=1 fg=1
If n=2 fg=2
If n>=3 fg=fg(n-1)+fg(n-2)
End Function
请问走完这8阶楼梯的走法有( )
A.34种 B.35种
C.36种 D.37种
答案 A 这是关于前2个数为1,2的斐波那契序列的应用,在程序中可以用递归思想解决。考虑站到第n阶台阶上有两种方法,分别是从n-1阶以及n-2阶上来,那么站到n-1阶台阶又可以有两种方法,分别是从n-2或者n-3上来,同理n-2阶也有两种方法上来,而站到第1阶只有一种方法,而站到第2阶有两种方法,这是一个递归问题。递推式:f(n)=f(n-1)+f(n-2),即计算前两项为1和2的斐波那契序列的第8项。
3.下列VB程序段:
Function s(n As Integer) As Integer
If n=1 Then
s=1
Else
s=s(n-1)+n
End If
End Function
Private Sub Form_Click()
Dim x As Integer
x=s(4)
Print x
End Sub
程序运行时,单击窗体后,变量x的值为( )
A.1 B.4
C.10 D.36
答案 C 变量x的值等于s(4),s是一个递归函数,n是形参。边界值是n=1时,s=1,因此s(1)=1;当n>1时,s=s(n-1)+n,因此s(2)=s(1)+2=3,s(3)=s(2)+3=6,s(4)=s(3)+4=10。
4.执行以下代码,单击命令按钮Command1后,显示在窗体上第二行的内容是 ( )
Private Sub Command1_Click()
Dim n As Integer,m As Integer
n=2:m=0
Do While m < 3
n=n+2
If fun(n) Then
Print n
m=m+1
End If
Loop
End Sub
Function fun(x As Integer) As Boolean
fun=false
If x/2=Int(x/2) Then
fun=fun(x/2)
Else
If x=1 Then fun=True
End If
End Function
A.4 B.6 C.8 D.16
答案 C 仔细分析自定义函数fun(x)的作用可知,当x为2的n次方时,fun函数返回值为True。而Command1_Click()事件中,只有fun(n)=True时,才会输出n的值并给m计数。m的值从0到2,共输出三行,满足条件的n的值分别为4,8,16,故第二行是8,选C。
5.有如下VB程序。
Function f(i As Integer)
If i=1 Then
f=2
Else
f=2 * 10 ^ (i-1)+f(i-1)
End If
End Function
Private Sub Command1_Click()
Dim n As Integer, s As Integer, i As Integer
n=Val(Text1.Text)
s=0
For i=1 To n
s=s+f(i)
Next i
Label1.Caption=Str(s)
End Sub
若在Text1中输入5,则Label1显示的内容为( )
A.22222 B.24690
C.20000 D.2468
答案 B 本题考查对递归的掌握。递归即调用自身函数,在函数中,每次循环调用2 * 10 ^ (i-1)+f(i-1),当i为1时,程序中利用了选择语句直接返回2,作为递归边界。假设i等于3,则第一次计算f函数得到f(3)=200+f(2),再次计算f(2)得到f(2)=20+f(1),即20+2,为22,加上200得到f(3)为222,所以f(n)函数的作用是得到一个n位数,其中每一位都是2,在主函数中将每一位数进行累加,所以当输入5时得到22222+2222+222+22+2=24690。
课件7张PPT。
第5节 递归算法一 递归算法二 递归算法的条件教材研读一、递归算法
函数或过程调用它本身,称为递归。递归算法的基本思想是把规模较大的、较难解决的问题变成规模较小的、容易解决的同一问题,规模较小 的问题又变成规模更小的问题,当问题小到一定程度时,可以直接得出它的解,从而得到原来问题的解。即采用“大事化小,小事化无”的基本思想。二、递归算法的条件
(1)每一步解决问题的方法要一致;
(2)有边界条件。C.题目1-2+3-4+…+(n-1)-n不能用递归法求解
D.函数或子程序一般不需要参数传递1.下列关于递归问题叙述正确的是?( A )
A.没有边界条件的递归会出现死循环或溢出等问题
B.已知函数A调用了函数B,B调用了A,这不属于递归问题解析 本题主要考查递归算法的基本特征。递归算法的条件之一 是要有边界条件,否则会出现死循环或溢出等问题。函数A调用了函数 B,B调用了A,也是递归,是间接递归。累加累乘问题都可以用递归法求 解。函数一般是有参数传递的。2.递归一般可以通过 ????来实现?( C )
A.标准函数 B.标准过程
C.自定义函数 D.标准函数和标准过程
