2023-2024学年浙教版高一下学期第五章第五节 递归算法实例及程序实现

2023-2024学年浙教版高一下学期第五章第五节 递归算法实例及程序实现 一、选择题 1．______是重复反馈过程的活动，______是重复调用函数自身（   ） A．递推，递归 B．递归，递推 C．迭代，递归 D．递归，迭代 2．19世纪末，在欧洲的商店中出售一种智力玩具，在一块铜板上有三根杆，最左边的杆上自上而下、由小到大顺序串着由64个圆盘构成的塔。玩家要将最左边杆上的盘子全部移到最右边的杆子上，要求一次只能移动一个盘，且不允许大盘放在小盘的上面。如果最左边杆子上只有3个盘子，则最少需要移动（    ）步才能将所有的盘子移至最右边杆。（   ） A．15 B．31 C．7 D．8 3．有如下程序段 Function Search(m As Integer, pre As Integer) As Integer Dim i As Integer If m < 0 Then Search = 0 ElseIf m = 0 Then Search = 1 Else For i = pre To m Search = Search + Search(m - i, i) Next i End If End Function Private Sub Command1_Click() Dim n As Integer n = Val(Text1.Text) Label1.Caption = Search(n, 1) End Sub 若在文本框 Text1 中输入“4”，则标签 Label1 中显示的内容为(   ) A．2 B．4 C．5 D．7 4．定义如下递归函数： def f(a, n):     n=n-1     if n==0:        return a     else:        return f(a-1,n)+f(a+1,n) print(f(5,3)) 程序运行后，输出的结果是（   ） A．10 B．20 C．30 D．40 5．有如下 VB 程序段： Dim n As Integer Dim sum As Integer Dim i As Integer Function fx(i As Integer) as Integer   If i = 1 Then fx = 5   Else   fx = 5 * 2 ^ (i - 1) + fx(i - 1)   End   if End Function Private Sub Command1_Click()   n = Val(Text1.Text): sum = 0   For i = 1 To n     sum = sum + fx(i)   Next i   Label1.Caption = Str(sum) End Sub 若在 Text1 中输入4，单击 Command1，则 Label1 中显示的内容为（   ） A．55 B．75 C．80 D．130 6．下列选项中没有体现递归思想是（   ） A．Hanoi塔问题 B．合并排序 C．插入排序 D．快速排序 7．求输入的两个自然数的最大公约数。如输入48和36则输出最大公约数为12，为其中的空白处选择合适的选项（    ）。 A．输出 a B．输出 b C．输出 r D．输出 a / b 8．下面代码的输出结果是（   ）。 def add(x): if x>0: return x＋add(x-l) else: return 0 result＝add(10) print(result) A．0 B．10 C．55 D．45 9．某VB程序使用了递归函数，代码如下： Private Sub Command1_Click() n= val(Text1.Text) Text2.Text = f(n) End Sub Function f(x As Integer) As String Dim t as integer If x = 1 Then  t = 1  Else  t = val(f(x - 1)) + 2 f=str(t) End Function 在文本框Text1中输入3，运行程序并点击按钮Command1后，文本框Text2中显示的内容是（    ） A．1 B．5 C．135 D．531 10．用递归求n!，当n=1时，f(1)=1，否则f(n)=f(n-1)*n，当n=3时，递归调用顺序正确的是（   ） A．f(1)、f(2)、f(3) B．f(2)、f(3)、f(1) C．f(3)、f(2)、f(1) D．以上都不对 11．下列关于递归算法的说法中，正确的是（    ） A．在1977年前后形成标准的计算机高级语言“F0RTRAN77”禁止在程序使用递归，原因之一是该方法可能会占用更多的内存空间 B．和非递归算法相比，解决同一个问题，递归算法一般运行得更快一些 C．对于较复杂的问题，用递归方式编程一般比非递归方式更难一些 D．对于已经定义好的标准数学函数sin（x），应用程序中的语句“y=sin（sin（x））；”就是一种递归调用 12．写出下列程序的输出结果 Private Sub Command1_Click() For i =" 1" To 4 If i Mod 3 <> 0 Then s =" s" + (-1) ^ (i + 1) * 1 / i Next i MsgBox s*100 End sub 该程序的运行结果是（   ） A．-25 B．-75 C．15 D．25 13．关于“递归”，下列说法不正确的是（  ） A．可以利用“递归”进行具有自相似性无限重复事物的定义 B．可以利用“递归”进行具有自重复性无限重复动作的执行，即“递归计算”或“递归执行” C．可以利用“递归”进行具有自相似性无限重复规则的算法的构造 D．递归算法的关键只要给出递归关系式即可求出问题的解 14．有如下 VB 程序段： Private Sub Command1_Click() Dim i As Integer,s As string s = "" For i = 1 To 3 Step 2   s = str(f(i)) + s Next i Text1. Text = s End Sub Function f(n As Integer) As Integer If n = 1 Then    f = 2 Else    f = f(n - 1) + n End If End Function 则执行该程序段后，s 的值为（    ） A．247 B．27 C．72 D．742 15．某VB程序段如下： Function f (n As Integer) As Long    If n = 1 Then f = 5 Else   f= 2*f(n-1) – 3 End If End Function Private Sub Command1_click()   Dim n As Integer   n = Val (Text1.Text)   Text2. Text = Str(f(n)) End Sub. 该程序段运行后，在文本框Text1中输入5，单击命令按钮Command1后，文本框Text2中显示的是（  ） A．18 B．35 C．63 D．123 二、填空题 16．下面程序的功能是：计算表达式1+3+5+…+(2n-1)的值，程序运行时在文本框Text1中输入n的值，计算结果在文本框Text2中输出。则程序中加框处的语句应分别更正为： （1）__________________ （2）__________________ Private Sub Command1_Click() Dim sum As Long,i As Integer,n As Integer sum = 0 n =Val（ Text1.Text） For i =" 1" To 2 * n - 1 Step 2 sum =" sum" + 2 Next i Text2.label=Str(sum) End Sub 17．选择算法，解决问题。 在使用计算机解决问题时，选择合适的算法，是有效解决问题的关键。 分析下面的问题，请选择最合适的算法： （请用英文字母填写） A．解析法      B．递归法      C．穷举法      D．排序法 猴子吃桃问题： 小猴有一天摘了若干个桃子，他非常贪吃，当天就吃掉了一半还多一个；第二天接着吃剩下的桃子一半多一个；以后每天都是如此，到了第七天吃桃子时，却发现只剩下一个。请问，小猴那天一共摘了几个桃子？ 18．如下程序段运行后，k的值是 Dim d(1 to 5)  As Integer k=0 For i="1" to 5 d( i )=i If d( i )>k Then k="d(" i ) Next i Print k 19．下面程序的功能是：计算表达式1×2×3×……×10的值，并在文本框Text1中输出表达式的值。为了实现这一功能，则程序中划线处的语句应更正为 （1） （2） （3） Private Sub Command1_Click() Dim I As Integer, t As Long t = 0 （1） For i =" 1" To 10 t =" t" + i（2） Next i Text1.caption =" Str(" t ) （3） End Sub 20．读流程图写结果 运行结果是___________________。 三、操作题 21．在平面坐标系中，给定一组有序的点。从原点出发，依次用线段连接这些点，构成一条折线。要求编写一个“计算折线长度”的程序，功能如下：在文本框Text1中依次输入这些点的坐标值（数据都用逗号分隔并以逗号结尾），单击“计算”按钮Cmd后，程序计算这条折线的长度，结果显示在Label1中。例如，三个点的坐标（5，10）、（8，12）、（6，17）输入格式如图所示。 （1） Cmd对象属于______类。 （单选，填字母：A．Form / B．Label / C．TextBox / D．CommandButton ） （2）实现上述功能的VB程序如下，请在划线处填入合适代码。 Private Sub Cmd_Click（） Dim i As Integer，j As Integer，k As Integer Dim x1 As Single，y1 As Single，x2 As Single，y2 As Single Dim d As Single，Totald As Single，v As Single，s As String s =______① x1 = 0： y1 = 0'出发点为坐标原点 k = 1 ： j = 1 ： Totald = 0 For i = 1 To Len（s） If Mid（s，i，1） ="，"Then v = Val（Mid（s，j，i - j））'提取坐标值，保存在变量v中 j = i + 1 If ② Then x2 = v Else y2 = v d = Sqr（（x2 — x1）^2 + （y2 — y1）^ 2） Totald = Totald + d x1 = x2 ： y1 = y2 End If k = k + 1 End If Next i Label1. Caption = Str（Totald） End Sub （3） 运行该程序，输入数据如上图所示，程序执行到循环结束时，变量k的值为______。 22．约翰·沃利斯（John Wallis，1616-1703，英国数学家）给出计算公式： 我们用S来代替π/2，,公式就变成了： 项数 1   2   3   4   5   6   7   8  …… 请观察公式中每一项，，……的变化规律， 1）如果用x/y表示每一项的分子和分母，请写出x和Y的变化规律。 2）如果要递推n项求π的值（n从外部输入），请写出VB代码。 四、简答题 23．请简述什么是递归函数，并给出一个递归函数的例子。 试卷第1页，共3页 试卷第1页，共3页 学科网（北京）股份有限公司 参考答案： 1．C 2．C 3．C 4．B 5．D 6．C 7．A 8．C 9．B 10．C 11．A 12．D 13．D 14．C 15．B 16．（1）sum =" sum" + i  （2）Text2.Text = Str(sum) 17．B 18．5 19．（1）t=1；（2）t=t*i；（3）Text1.Text=Str(t) 20．55 21．（1）D （2）①Text1.Text ②k Mod 2=1 （3）7 22．1)当x、y在奇数项时，x=n+1，y=n；x、y在偶数项时，x=n，y=n+1。 2）VB代码： Function sp(x As Long) As Double If x = 1 Then sp = 2 / 1 ElseIf x Mod 2 = 1 Then sp = sp(x - 1) * (x + 1) / x Else sp = sp(x - 1) * x / (x + 1) End If End Function Private Sub Command1_Click() Dim n As Long Dim s, pi As Double n = Val(InputBox("请输入递推项")) s = sp(n)pi = 2 * s Print "pi="; pi End Sub 23．递归函数是一种在函数体内调用自身的函数。一个递归函数的例子是计算斐波那契数列的函数，其中每个数是前两个数的和，递归定义为Fib(n) = Fib(n-1) + Fib(n-2)，基本情况是Fib(0) = 0和Fib(1) = 1。 答案第1页，共2页 答案第1页，共2页 学科网（北京）股份有限公司 $$