第3章程序与递归_组合、抽象与构造练习题答案解析

第3章程序与递归：组合、抽象与构造

1、关于计算系统与程序，下列说确的是_____。

(A)只有用计算机语言编写出来的代码才是程序，其他都不能称其为程序；

(B)构造计算系统是不需要程序的，程序对构造计算系统没有什么帮助；

(C)任何系统都需要程序，只是这个程序是由人来执行还是由机器自动执行，可以由机器自动执行程序的系统被称为计算系统；

(D)程序是用户表达的随使用者目的不同而千变万化的复杂动作，不是使用者实现的而是需要计算系统事先完成的。

答案：C

解释：

本题考查程序，计算系统等的概念；

（A）程序= 基本动作指令的一个组合或执行序列, 用以实现复杂的动作，只用计算机语言编写出来的代码称为程序，这个概念太狭隘了，A错误；（B）计算系统的一部分是由程序组成的，所以B错误；（C）计算系统= 基本动作+ 指令+ 程序执行机构，任何系统都需要系统，C完全正确；（D）程序= 基本动作指令的一个组合或执行序列, 用以实现复杂的动作，并不是由用户表达的，随使用者的不同而千变万化的复杂动作。所以D是错的；

具体容参考第三章视频之“程序的作用和本质”及第三章课件。

2、关于程序，下列说法不正确的是_____。

(A)“程序”是由人编写的、以告知计算系统实现人所期望的复杂动作；

(B)“程序”可以由系统自动解释执行，也可以由人解释由系统执行；

(C)普通人是很难理解“程序”的，其也和“程序”无关；

(D)“程序”几乎和每个人都有关系，如自动售票系统、自动取款机等。

答案：C

解释：

本题考查程序的概念；

程序= 基本动作指令的一个组合或执行序列, 用以实现复杂的动作，所以A,B，D都是正确的；C说普通人很难理解程序，这显然是错误的。所以选C；

具体容参考第三章视频之“程序的作用和本质”及第三章课件。

3、关于程序，下列说法不正确的是_____。

(A)程序的基本特征是复合、抽象与构造；

(B)复合就是对简单元素的各种组合，即将一个(些)元素代入到另一个(些)元素中；

(C)抽象是对各种元素的组合进行命名，并将该名字用于更复杂的组合构造中；

(D)程序就是通过组合、抽象、再组合等构造出来的；

(E)上述说法有不正确的。

答案：E

解释：

本题考查程序的概念；

（A）程序的特征即是：组合-抽象-构造，所以A正确；（B）复合即是将简单的基本动作指令组合起来，实现复杂动作。B正确；（C）抽象：将经常使用的、可由低层次系统实现的一些复杂动作，进行命名，以作为高层次系统的指令被使用，C正确；（D）通过前面三个选项可知，程序就是通过组合，抽象，再组合这样构造出来的。综上可知E不正确。

具体容参考第三章视频之“程序的作用和本质”及第三章课件。

4、一般而言，设计和实现一个计算系统，需要设计和实现_____。

(A)基本动作和程序；

(B)基本动作和控制基本动作的指令；

(C)基本动作、控制基本动作的指令和一个程序执行机构；

(D)基本动作、控制基本动作的指令和程序。

答案：C

解释：

本题考查计算系统的概念；

计算系统= 基本动作+ 指令+ 程序执行机构，所以ABC都描述不完整，只有C正确；

具体容参考第三章视频之“程序的作用和本质”及第三章课件。

5、一般而言，一个较高抽象层次的计算系统是可以这样实现的，即_____。

(A)将较低抽象层次的重复性组合，命名为较高抽象层次的指令；

(B)利用较高抽象层次的指令进行复合、抽象与构造，即形成高抽象层次的程序；

(C)高抽象层次的程序通过其程序执行机构解释为高抽象层次的指令及其操作次序；

(D)高抽象层次的指令被替换为低抽象层次的程序，再由低抽象层次的程序执行机构解释并执行。

(E)上述A-D全部。

答案：E

解释：

本题考查计算系统的概念；

（A ）抽象：将经常使用的、可由低层次系统实现的一些复杂动作，进行命名，以作为高层次系统的指令被使用，所以，A 正确；（B ）程序本身即是复合，抽象，构造的过程，B 正确；（C ）

（D ）的描述都完全正确；所以综上所述，应该选E ；

具体容参考第三章视频之“程序的作用和本质” 及第三章课件。

6、熟悉下列运算组合式(前缀表达式)，其中结果为56的是_____。

(A) (* 7 (+ 5 2))；

(B) (* (+ 5 3) (+ 5 2))；

(C) (+ 20 (+ 6 6))；

(D) (- (* 9 8) (- 20 2))。

答案：B

解释：

本题考查基本运算组合式的构造与计算，尤其是嵌套的运算组合式的计算

对于一个前缀表达式的求值而言，首先要从右至左扫描表达式，从右边第一个字符开始判断，如果当前字符是数字则一直到数字串的末尾再记录下来，如果是运算符，则将右边离得最近的两个“数字串”作相应的运算，以此作为一个新的“数字串”并记录下来。一直扫描到表达式的最左端时，最后运算的值也就是表达式的值。所以，（A ）的中缀表达式7*（2+5）=49；（B ）（3+5）*（2+5）=56；所以选B ；（C ）20+（6+6）=32；（D ）（9*8）-（20 - 2）=54；所以答案选B ；

具体容参考第三章视频之“程序构造示例(I)” 及第三章课件。

7、对于计算式2*86*34820

10+++

，其正确的运算组合式(前缀表示法)为_____。 (A) (/ (+ 10 / 20 + 8 4) (+ * 3 6 * 8 2 ))；

(B) ((10 + (20 / (8 + 4))) / ((3 * 6) + (8 * 2)))；

(C) (/ (+ 10 (/ 20 (+ 8 4))) (+ (* 3 6) (* 8 2)))；

(D) (/ (/ 20 (+ 10 (+ 8 4))) (* (+ 3 6) (+ 8 2)))。

答案：C

解释：

本题考查运算组合式的书写与构造

对于一个前缀表达式的求值而言，首先要从右至左扫描表达式，从右边第一个字符开始判断，如果当前字符是数字则一直到数字串的末尾再记录下来，如果是运算符，则将右边离得最近的两个“数字串”作相应的运算，以此作为一个新的“数字串”并记录下来。一直扫描到表达式的最左端时，最后运算的值也就是表达式的值。我们可以将答案中的四个选项都转化成中缀表达式，发现C完全符合题意；

具体容参考第三章视频之“程序构造示例(I)”及第三章课件。

8、请用define运算，定义一个过程实现计算a3，其正确定义的过程为_____。

(A) (define cube a (* a a a))；

(B) (define (cube x) (* x x x))；

(C) (define (cube a (* a a a)))；

(D) (define (cube a) (* x x x)))。

答案：B

解释：

本题考查新运算符(即过程)的定义

（cube x）中，cube是新运算符，x是形式参数，使用时将被实际参数替代。（*x x x）是过程体，用于表示新运算符的具体计算规则，其为关于形式参数x的一种计算组合。

所以综上所述应选择B，满足条件；

具体容参考第三章视频之“程序构造示例(II)”及第三章课件。

9、已知一个新运算被定义为(define (newCalc x y) (* (+ x 1) (* y 2)))，问newCalc 可以完成的计算功能为_____。-

(A) (x+1)+2y；

(B) (x+1)*2y；

(C) (x+1) +(y+2)；

(D) (x+1)*(y+2)。

答案：B

解释：

本题考查新运算符(即过程)的定义

此题是定义了个一个有关x和y的心运算newCale，后面(* (+ x 1) (* y 2))转化成中缀表达式：即为(x+1)*2y，所以选B；

具体容参考第三章视频之“程序构造示例(II)”及第三章课件。

10、已知一个新运算被定义为(define (newCalc x y) (* (+ x 1) (* y 2)))，问正确使用了newCalc并得到正确结果的为_____。

(A) ((newCalc) (4 5))，其结果为50；

(B) (newCalc 4)，其结果为40；

(C) (newCalc 4 5)，其结果为50；

(D) (newCalc 2 3)，其结果为21。

答案：C

解释：

本题考核新运算符(即过程)的定义和使用。

本题定义的新运算是(x+1)*(y*2)。(A)和(B)使用方法不正确；(C)将x=4，y=5代入新运算得50，所以是正确的；(D)将x=2，y=3代入新运算得18，是错误的。

具体容请参考第三章课件之“程序构造示例”及第三章课件。

11、已知一个新运算被定义为(define (newCalc x y) (* (+ x 1) (+ y 1)))，问(newCalc (newCalc (newCalc 1 1) 2) 3)的计算结果为_____。

(A) 6 ；(B) 13；(C) 64；(D) 24。

答案：C

解释：

本题考核新运算符(即过程)的定义和嵌套使用。

本题定义的新运算是(x+1)*(y+1)。先计算最里层的(newCalc 1 1)=(1+1)*(1+1)=4；再计算(newCalc (newCalc 1 1) 2)=(newCalc 4 2)= (4+1)*(2+1)=15；最后计算(newCalc (newCalc (newCalc 1 1) 2) 3)=(newCalc 15 3) = (15+1)*(3+1)=64，即最终结果是64，所以(C)是正确的。

具体容请参考第三章课件之“程序构造示例”及第三章课件。

12、已知一个新运算被定义为(define (newCalc x y) (* (+ x 1) (+ y 1)))，问(newCalc (newCalc (newCalc 1 1) (newCalc 1 1)) (newCalc 1 1))的计算结果为_____。

(A) 1 ；(B) 64；(C) 130；(D) 8。

答案：C

解释：

本题考核新运算符(即过程)的定义和嵌套使用。

本题定义的新运算是(x+1)*(y+1)。先计算(newCalc 1 1)=(1+1)*(1+1)=4；再计算(newCalc (newCalc 1 1) (newCalc 1 1))=(newCalc 4 4)= (4+1)*(4+1)=25；最后计算(newCalc (newCalc

(newCalc 1 1) (newCalc 1 1)) (newCalc 1 1))=(newCalc 25 4) = (25+1)*(4+1)=130，即最终结果是130，所以(C)是正确的。

具体容请参考第三章课件之“程序构造示例”及第三章课件。

13、已知一个运算被定义为(define (firstCalc x) (* x x))，在其基础上进一步定义新运算secondCalc为x2+y2+z2，下列运算组合式书写正确的是_____。

(A) (define secondCalc (+ (firstCalc x) (firstCalc y) (firstCalc z)))；

(B) (define (secondCalc x y z) (+ firstCalc x y z))；

(C) (define (secondCalc x y z) (+ (firstCalc x) (firstCalc y) (firstCalc z)))；

(D) (define secondCalc x y z (+ (firstCalc x) (firstCalc y) (firstCalc z)))。

(E) (define (secondCalc x y z) (+ (firstCalc x) (firstCalc x) (firstCalc x)))。

答案：C

解释：

本题考核新运算符(即过程)的定义，以及形式参数的使用。

本题首先定义的新运算是(firstCalc x) =x2，最终要定义的新运算是x2+y2+z2 ，只需要将(firstCalc x) 、(firstCalc y) 和(firstCalc z)这三项加起来即可。其中(A)选项定义的新运算符secondCalc后没有跟参数，错误；(B)选项调用运算(firstCalc x)时错误；(C)选项正确；(D)选项secondCalc x y z没有加括号；(E)选项后面的运算是x2+x2+x2，错误。

具体容请参考第三章课件之“程序构造示例”及第三章课件。

14、已知一个运算被定义为(define (firstCalc x) (* x x))，在其基础上进一步定义新运算为(define (secondCalc x) (firstCalc (firstCalc (firstCalc x))))，问secondCalc表达的运算功能为_____。

(A) x*x*x；

(B) x2+x2+x2；

(C) ((x2)2)2；

(D) x4。

答案：C

解释：

本题考核新运算符(即过程)的定义和嵌套使用。

本题首先定义的新运算是(firstCalc x) =x2，下面计算进一步定义的新运算secondCalc，从最里层开始计算(firstCalc x) =x2，然后计算(firstCalc (firstCalc x)) = (firstCalc x2) = (x2)2，最后计算(firstCalc (firstCalc (firstCalc x))) = (firstCalc (x2)2) = ((x2)2)2，所以(C)选项是正确的。

具体容请参考第三章课件之“程序构造示例”及第三章课件。

15、用条件运算符定义一个过程y

x if y x if y x if y x y x f <=>?????=33

),(。正确的定义为_____。 (A) (define (f x y) (cond ((x>y) (* x x x))

((x=y ) 0)

((x

(B) (define (f x y) (cond ((> x y ) (* x x x))

((= x y ) 0)

((< x y ) (* y y y)) ))；

(C) (define (f x y) (cond ((x>y) (x*x*x))

((x=y ) 0)

((x

(D) (define (f x y) (cond ((< x y ) (* x x x))

((= x y ) 0)

((> x y ) (* y y y)) ))。

答案：B

解释：

本题考核条件运算符的使用及分支处理。

(A)选项，条件书写错误，应该用前缀表示法，即运算符在前面； (B)选项正确；(C)选项，条件和表达式都书写错误，应该用前缀表示法，而选项中用的是中缀表示法；(D)选项，条件书写错误，把x>y 和x

具体容请参考第三章课件之“程序构造示例”及第三章课件。

16、用条件运算符定义一个过程???>-<=1

)!1(*21!n if n n n if n 。正确的定义为_____。 (A) (define (f n) (cond ((n<2 ) 1)

((n>1) (n* f(n-1)) )

(B) (define (f n) (cond ((< n 2 ) 1)

((> n 1 ) (* n (f (- n 1)))) ))；

(C) (define (f n) (cond ((n<2) 1)

((n>1 ) (n* f(n-1) )) ))；

(D) (define (f n) (cond ((< n 2 ) 1)

((> n 1 ) (* n (f n-1))) ))。

答案：B

解释：

本题考核递归过程的定义。

(A)选项，首先条件书写错误，其次n>1时，表达式书写错误，最后右括号数目不够；(B)选项正确；(C)选项，首先条件书写错误，其次n>1时，表达式书写错误；(D)选项，调用f(n-1)时书写错误。

具体容请参考第三章视频之“运用递归和迭代”及第三章课件。

17、若要表达从1计算到n的运算组合式，(* …(* (* (* (* 1 1) 2) 3) 4) …n)

定义一个过程。正确的定义为_____。

(A) (define (f product counter max-count)

(f (* counter product) (+ counter 1) max-count ))；

(B) (define (f product counter max-count)

(cond ((> counter max-count) product)

((<= counter max-count) (f (counter*product) (counter+ 1) max-count )) ))；

(C) (define (f product counter max-count)

(cond ((> counter max-count) product)

((<= counter max-count) (f (* counter product) (+ counter 1) max-count )) ))；

(D) (define (f product counter max-count)

(cond ((> counter max-count) product)

((<= counter max-count) (f product counter max-count )) ))；

答案：C

解释：

本题考核迭代过程的定义。

本题需要计算1*2*3*---*n，选项中product表示每次迭代的结果，counter表示本次迭代要相乘的数，max-count 即n，在每次迭代中，要把product * counter 赋给product，把counter+1赋给counter。(A)选项，没有结束条件，会一直迭代下去；(B)选项，(f (counter*product) (counter+ 1) max-count )没有用前缀表示法；(C)选项正确，计算1*2*3*---*n即(define (f 1 1 n))；(D)选项，当counter<=max-count时，表达式错误。

具体容请参考第三章视频之“运用递归和迭代”及第三章课件。

18、关于原始递归函数的理解，下列说法不正确的是_____。

(A)“复合”即是将一组函数g1,g2,…,g n作为参数代入到另一函数f(x1,x2,…,x n)中，即n个函数g1,g2,…,g n被组合到了一起，是按函数f的形式进行的组合。

(B)“原始递归”即是要定义h(0),h(1),…,h(n),h(n+1)，其中h(0)需要直接给出，而h(n+1)需要用h(n)进行定义，即h(n+1)是将h(n)和n复合在一起。

(C)复合是构造新函数的一种手段，原始递归也是构造新函数的一种手段；

(D)递归函数是描述程序组合与构造问题的一种数学形式。

(E)上述说法有不正确的。

答案：E

解释：

本题考核对原始递归函数的理解。

(A)、(B)、(C)和(D)的说法都是正确的，所以(E)选项错误。

具体容请参考第三章视频之“原始递归”及第三章课件。

19、按原始递归的定义，h是由f和g递归地构造出来的。假设已知h(n) = n!，请给出构造h的f 和g的函数。正确的是_____。

(A) f()是常数为1的函数；g(x1,x2) = x1* x2。

(B) f()是常数为1的函数；g(x1,x2) = x1* (x2+1)。

(C) f()是常数为1的函数；g(x1,x2) = (x1+1)*(x2+1)。

(D) f()是常数为1的函数；g(x1) = n * (x1)。

答案：B

解释：

本题考核原始递归的定义,当f()是常数为1的函数，若g(x1,x2) = x1* x2。则h(n) = 1；若g(x1,x2) = x1* (x2+1)。则h(n) = n!；若g(x1,x2) = (x1+1)*(x2+1)。递归从2开始；若g(x1) = n * (x1)。h(n) 为N的N次方；所以B选项正确。

具体容请参考“递归的概念’及第三章课件。

20、已知f(x)=x，g(x1,x2,x3)=x1+x2+x3, 其中x,x1,x2,x3均为自然数，新函数h可递归的构造如下：h(0,x) = f(x), 且h(S(n), x) = g(h(n,x),n,x)，请按递归式进行计算下列式子，正确的是_____。

(A) h(1，x) = x；

(B) h(2，x) = 2x；

(C) h(3，x) = 3x+1；

(D) h(4，x) = 5x+6；

(E)上述都不正确。

答案：D

解释：

本题考核递归。h(0,x)=f(x) =x

h(1,x)=h(S(0),x) = g(h(0,x),0,x) = g(f(x),0,x) = f(x) +0+ x =2x

h(2,x)=h(S(1),x) = g(h(1,x),1,x)=g(g(f(x),0,x),1,x)=g(2x, 1, x)=3x+1

h(3,x)=h(S(2),x) =g(h(2,x),2,x)=g(g(h(1, x),1, x),2, x)= g(g(g(h(0,x),0,x),1,x),2,x)

= …= 4x+3

h(4，x) =h(S(3),X)= g(h(3,X),3,x)=......= 5x+6;

所以选D；

具体容请参考“原始递归函数构造’及第三章课件。

21、已知f(x)=5，g(x1,x2,x3)=x1, 其中x,x1,x2,x3均为自然数，新函数h可递归的构造如下：h(0,x) = f(x), 且h(S(n), x) = g(h(n,x),n,x)，请按递归式进行计算下列式子，正确的是_____。

(A) h(1，x) = 5；

(B) h(2，x) = 5+x；

(C) h(3，x) = 5+2x；

(D) h(4，x) = 5+3x ；

(E)上述都不正确。

答案：A

解释：

本题考核递归。

h(1,x) =h(S(0),x) = g(h(0,x),0,x) = g(f(x),0,x) = f(x) =5；

h(2,x)=h(S(1),x) = g(h(1,x),1,x)=g(g(f(x),0,x),1,x)=g(5, 1, x)=5；

h(3,x)=h(S(2),x) =g(h(2,x),2,x)=g(g(h(1, x),1, x),2, x) =g(g(g(h(0,x),0,x),1,x),2,x)

= …= 5；

h(4，x) =h(3,x)=...=5;所以选A；

具体容请参考“原始递归函数构造’及第三章课件。

22、已知f(x)=x，g(x1,x2,x3)=x1*(x2+1), 其中x,x1,x2,x3均为自然数，新函数h可递归的构造如下：h(0,x) = f(x), 且h(S(n), x) = g(h(n,x),n,x)，请按递归式进行计算下列式子，不正确的是_____。

(A) h(1，x) = x；

(B) h(2，x) = 2x；

(C) h(3，x) = 6x；

(D) h(4，x) = 12x；

答案：D

解释：

本题考核递归。

h(0,x) = f(x)；h(1，x) =h(S(0), x)=g(h(0,x),0,x)=f(x)=x；

h(2，x) =h(S(1), x)=g(h(1,x),1,x)=h(1,x)*2=2x；

h(3，x) =h(S(2), x)=g(h(2,x),2,x)=h(2,x)*3=6x；

h(4，x) =h(S(3), x)=g(h(3,x),3,x)=h(3,x)*4=24x；

所以选D；

具体容请参考“原始递归函数构造’及第三章课件。

23、关于“递归”，下列说法不正确的是_____。

(A)“递归”源自于数学上的递推式和数学归纳法。

(B)“递归”与递推式一样，都是自递推基础计算起，由前项(第n-1项)计算后项(第n项)，直至最终结果的获得。

(C)“递归”是自后项(即第n项)向前项(第n-1项)代入，直到递归基础获取结果，再从前项计算后项获取结果，直至最终结果的获得；

(D)“递归”是由前n-1项计算第n项的一种方法。

答案：B

解释：

本题考核递归相关容。

递归”源自于数学上的递推式和数学归，是自后项(即第n项)向前项(第n-1项)代入，直到递归基础获取结果，再从前项计算后项获取结果，直至最终结果的获得，是由前n-1项计算第n项的一种方法。所以选B；

具体容请参考“递归的概念”及第三章课件。

24、关于“递归”，下列说法不正确的是_____。

(A)可以利用“递归”进行具有自相似性无限重复事物的定义。

(B)可以利用“递归”进行具有自重复性无限重复动作的执行，即“递归计算”或“递归执行”。

(C)可以利用“递归”进行具有自相似性无限重复规则的算法的构造；

(D)上述说法不全正确。

答案：D

解释：

本题考核递归概念容。递归”可以进行具有自相似性无限重复事物的定义，进行具有自重复性无限重复动作的执行，即“递归计算”或“递归执行”，进行具有自相似性无限重复规则的算法的构造。

具体容请参考“递归的概念”及第三章课件。

25、关于递归定义的函数，下列说确的是_____。

(A)递归定义的函数一定是“递归计算”的；

(B)递归定义的函数一定是“迭代计算”的；

(C)有些递归定义的函数可以“迭代计算”，有些递归定义的函数则必须“递归计算”；

(D)凡是可以“迭代计算”的函数，一定可以“递归计算”，凡是可以“递归计算”的函数，也一定可以“迭代计算”。

答案：C

解释：

本题考核递归与迭代，有些递归定义的函数可以“迭代计算”，有些递归定义的函数则必须“递归计算”所以选C。

具体容请参考“递归与迭代概念”及第三章课件。

26、用递归是可以定义语言的。如表述命题逻辑的一种语言可以如下定义：

(1)一个命题是其值为真或假的一个判断语句；

(2)如果X是一个命题，Y也是一个命题，则X and Y，X or Y, not X也是一个命题；

(3)如果X是一个命题，则(X)也是一个命题，括号的命题运算优先；

(4)命题由以上方式构造。

若X，Y，Z，M等均是一个命题，问不符合上述递归定义的语句是_____。

(A) X；

(B) ( X and Y not Z)；

(C) (X)；

(D) ((X and Y) or (not Z)) and (not M)。

答案：B

解释：

本题考核递归的定义。由前n项或第n项定义第n+1项；由低阶f(k)且k

具体容请参考“递归的概念”及第三章课件。

27、递归计算是重要的执行手段。例如一种形式的阿克曼函数如下所示：

?????>==---+=0

,00))1,(,1()

1),1((1),(n m n m n m A m A m A n n m A 若若若 任何一个A(m, n)都可以递归地进行计算，例如A(1,2)的递归计算过程如下所示：

A(1,2) = A(0,A(1,1)) = A(0, A(0,A(1,0))) = A(0, A(0,A(0,1)))=A(0,A(0,2))=A(0,3)=4。

请你按上述方法递归计算下列项，并判断，计算结果正确的是_____。

(A) A(1, 8) = 9；

(B) A(2, 0) = 2；

(C) A(2, 1) = 4；

(D) A(1, n) = n+2。

答案：D

解释：

本题考查对程序和递归的综合理解，以正面叙述为主，便于学生复习

A(1,n) =A(0, A(1,n-1))=A(0. <…代入前式计算过程>)=A(0,n+1)=n+2。所以A(1, 8) =10； A(2，0)=A(1，1)=3；

A(2,1) = A(1，A(2，0)) = A(1，A(1，1)) =A(1，A(0，A(1，0)))

= A(1，A(0，A(0，1))) = A(1，A(0，2)) = A(1，3) =A(0，A(1，2))

= A(0，A(0，A(1，1))) = A(0，A(0，A(0，A(1，0))))

= A(0，A(0，A(0，A(0,1))) = A(0，A(0，A(0，2))) = A(0，A(0，3))

= A(0，4) = 5。

所以选D

具体容请参考“阿克曼函数”及第三章课件。

28、递归计算是重要的执行手段。例如一种形式的阿克曼函数如下所示：

1

,2

0)1),,1((),(2)0,(1),0(2

)0,1(≥≥≥--=+===m n n m m m n A A m n A n n A m A A 任何一个A(n, m)都可以递归地进行计算，例如m=1时，A(n,1)的递归计算过程如下所示：

m=1时，A(n,1)=A (A(n-1,1),0)=A(n-1,1)+2，和A(1,1)=2故A(n,1)=2n

请你按上述方法递归计算m=2时，即A(n,2)，并判断计算结果正确的是_____。

(A) A(n, 2) = 2n ；

(B) A(n, 2) = 2n ；

(C) A(n, 2) = (n+2)2；

(D) A(n, 2) = n+2。

答案：B

解释：

本题考核递归与迭代的实际应用。具体计算步骤为：

A(n,2)=A(A(n-1,2),1)=A(A(A(n-1,2)-1,1),0)=2A(n-1,2)=2n A(0,2)=2n 因此(B)是正确的。 具体容请参考第三章视频之“递归与迭代”以及第三章课件。

29、斐波那契数列与阿克曼函数都是递归函数，但它们是不同的，下列说法不正确的是_____。

斐波那契数列110)2()1(11)(>==??

???-+-=n n n n F n F n F 与阿克曼函数?????>==---+=0

,00))1,(,1()1),1((1),(n m n m n m A m A m A n n m A 若若若 (A) 斐波那契数列是原始递归的，而阿克曼函数不是原始递归的；

(B) 斐波那契数列可以递推地计算即迭代计算；而阿克曼函数只能递归地计算；

(C) 阿克曼函数也可如斐波那契数列一样自前项(第n-1项)计算到后项(第n 项)；

(D) 阿克曼函数是双递归函数，不仅函数自身是递归定义的，同时函数的变量也是递归定义的。

答案：C

解释：

本题考核递归与递推的差异。

(A)正确，阿克曼函数是一个双重递归，m,n>0时的公式不能通过m=0和n=0时的公式推出；

(C)不正确，阿克曼函数只能递归，由后向前递归地计算。(B)(D)正确。

具体容请参考第三章视频之“原始递归”和“递归与迭代”以及第三章课件。

30、关于“程序”和“递归”的关系，下列说法不正确的是_____。

(A) “程序”是计算系统体现千变万化功能的一种重要手段：计算系统仅需要实现简单元素以及一个程序执行机构即可；

(B) 本质上章，“程序”就是对简单元素的组合(或称复合)；此外，“程序”需要有能力对一些常见的组合A 进行命名，并利用该名字参与更为复杂的组合B 的构造中，此即为“抽象”；在执行时(或称计算时)，再将该组合A 替换组合B 中的该名字，实现计算并获取结果；

(C) “程序”的基本特征是复合、抽象与构造。而最重要的是，如何解决近乎无限的、具有自相似性的复杂组合的构造问题，这就需要递归和迭代；

(D) 递归和迭代是解决近乎无限的、重复的、嵌套的组合构造的基本手段，它采用“利用自身定义自身”、“自身调用自身”、“自身用自身来计算”的方法，将程序的复杂组合构造问题以简便的、明确的形式表达出来计算出来；

(E) 上述说法有不正确的。

答案：E

解释：

本题考核对程序和递归的综合理解，以正面叙述为主，便于学生复习。

(A)(B)(C)(D)均为正确叙述。

具体容请参考第三章视频之“程序的作用及本质”以及第三章课件。

《算法设计与分析》实验一

学号1607070212 《算法设计与分析》 实验报告一 学生姓名张曾然 专业、班级16软件二班 指导教师唐国峰 成绩 计算机与信息工程学院软件工程系 2018 年9 月19 日

实验一：递归策略运用练习 一、实验目的 本次实验是针对递归算法的算法设计及应用练习，旨在加深学生对该算法原理的理解，提高学生运用该算法解决问题的能力。 二、实验步骤与要求 1．实验前复习课程所学知识以及阅读和理解指定的课外阅读材料； 2．学生独自完成实验指定内容； 3．实验结束后，用统一的实验报告模板编写实验报告。 4．提交说明： （1）电子版提交说明： a 需要提交Winrar压缩包，文件名为“《算法设计与分析》实验一_学号_姓名”， 如“《算法设计与分析》实验一_09290101_张三”。 b 压缩包内为一个“《算法设计与分析》实验一_学号_姓名”命名的顶层文件夹， 其下为两个文件夹，一个文件夹命名为“源程序”，另一个文件夹命名为“实验 报告电子版”。其下分别放置对应实验成果物。 （2）打印版提交说明： a 不可随意更改模板样式。 b 字体：中文为宋体，大小为10号字，英文为Time New Roman，大小为10号 字。 c 行间距：单倍行距。 （3）提交截止时间：2018年10月10日16:00。 三、实验项目 1．运用递归策略设计算法实现下述题目的求解过程。 题目列表如下： 【必做题】 （1）运动会开了N天，一共发出金牌M枚。第一天发金牌1枚加剩下的七分之一枚，第二天发金牌2枚加剩下的七分之一枚，第3天发金牌3枚加剩下的七分之一枚，以后每天都照此办理。到了第N天刚好还有金牌N枚，到此金牌全部发完。编程求N和M。 （2）国王分财产。某国王临终前给儿子们分财产。他把财产分为若干份，然后给第一个儿子一份，再加上剩余财产的1/10；给第二个儿子两份，再加上剩余财产的1/10；……；给第i 个儿子i份，再加上剩余财产的1/10。每个儿子都窃窃自喜。以为得到了父王的偏爱，孰不知国王是“一碗水端平”的。请用程序回答，老国王共有几个儿子？财产共分成了多少份？

递归算法与递归程序#

一、教学目标 1、知识与技能 (1)．认识递归现象。 (2)．使用递归算法解决问题往往能使算法的描述乘法而易于表达 (3)．理解递归三要素：每次递归调用都要缩小规模；前次递归调用为后次作准备：递归调用必须有条件进行。 (4)．认识递归算法往往不是高效的算法。 (5)．了解递归现象的规律。 (6)．能够设计递归程序解决适用于递归解决的问题。 (7)．能够根据算法写出递归程序。 (8)．了解生活中的递归现象，领悟递归现象的既有重复，又有变化的 特点，并 且从中学习解决问题的一种方法。 2、方法与过程 本节让同学们玩汉诺塔的游戏，导入递归问题，从用普通程序解决斐波那契的兔子问题入手，引导学生用自定义了一个以递归方式解决的函数过程解决问题，同时让同学们做三个递归练习，巩固提高。然后让学生做练习(2)和练习(3)这两道题目的形式相差很远，但方法和答案却是完全相同的练习，体会其中的奥妙，加深对递归算法的了解。最后用子过程解决汉诺塔的经典问题。 3、情感态度和价值观 结合高中生想象具有较强的随意性、更富于现实性的身心发展特点，综合反映出递归算法的特点，以及递归算法解答某些实践问题通常得很简洁，从而激发学生对程序设计的追求和向往。 二、重点难点 1、教学重点 （1）了解递归现象和递归算法的特点。

（2）能够根据问题设计出恰当的递归程序。 2、教学难点 (1)递归过程思路的建立。 (2)判断问题是否适于递归解法。 (3)正确写出递归程序。 三、教学环境 1、教材处理 教材选自《广东省普通高中信息技术选修一：算法与程序设计》第四章第五节，原教材的编排是以本节以斐波那契的兔子问题引人，导出递归算法，从而自定义了一个以递归方式解决的函数过程。然后利用子过程解决汉诺塔的经典问题。 教材经处理后，让同学们玩汉诺塔的游戏，导入递归问题，从用普通程序解决斐波那契的兔子问题入手，引导学生用自定义了一个以递归方式解决的函数过程解决问题，同时让同学们做三个递归练习，巩固提高。然后让学生做练习(2)和练习(3)这两道题目的形式相差很远，但方法和答案却都是完全相同的练习，体会其中的奥妙，加深对递归算法的了解。最后用子过程解决汉诺塔的经典问题。 教学方法采用讲解、探究、任务驱动和学生自主学习相结合 2、预备知识 学生已掌握了用计算机解决问题的过程，掌握了程序设计基础，掌握了解析法、穷举法、查找法、排序法设计程序的技巧。 3、硬件要求 建议本节课在多媒体电脑教室中完成，最好有广播教学系统或投影仪，为拓展学习，学生机应允许上互联网。 4、所需软件 学生机要安装VB6.0或以上版本。 5、所需课时 2课时（90分钟）

递归下降分析法

《编译原理》课程实验报告 实验名称：递归下降分析法 一．实验目的 1.理解递归下降语法分析方法的主要原理 2.理解递归下降分析法对文法的要求 3．熟练掌握Predict集合的求法 4.熟练掌握文法变换算法（消除左递归和消除公共前缀） 二．实验内容 #include char token[20]; char sym; int p; void S(); void T(); void U(); void Scanner(); void Error(); void S() { if (sym == 'a' || sym == '^') Scanner(); else if (sym == '(') { Scanner(); T(); if (sym == ')') Scanner(); else Error(); } else Error();

} void T() { S(); U(); } void U() { if (sym == ',') { Scanner(); S(); U(); } else if(sym != ')') Error(); } void Scanner() { sym = token[p++]; } void Error() { //exit(0); } int main() { printf("输入: "); gets(token); p = 0; Scanner(); S(); if (sym == '$') printf("Success!"); else printf("Fail!"); return 0; } 三．实验步骤 调试程序的结果：

算法实验报告

实验一分治与递归算法的应用 一、实验目的 1．掌握分治算法的基本思想（分-治-合）、技巧和效率分析方法。 2．熟练掌握用递归设计分治算法的基本步骤（基准与递归方程）。 3．学会利用分治算法解决实际问题。 二 . 实验内容 金块问题 老板有一袋金块（共n块，n是2的幂（n≥2））,最优秀的雇员得到其中最重的一块，最差的雇员得到其中最轻的一块。假设有一台比较重量的仪器，希望用最少的比较次数找出最重和最轻的金块。并对自己的程序进行复杂性分析。 三.问题分析: 一般思路：假设袋中有n 个金块。可以用函数M a x（程序 1 - 3 1）通过n-1次比较找到最重的金块。找到最重的金块后， 可以从余下的n-1个金块中用类似法通过n-2次比较找出最轻的金块。这样，比较的总次数为2n-3。

分治法：当n很小时，比如说，n≤2，识别出最重和最轻的金块，一次比较就足够了。当n 较大时（n＞2），第一步，把这袋金块平分成两个小袋A和B。第二步，分别找出在A和B中最重和最轻的金块。设A中最重和最轻的金块分别为HA 与LA，以此类推，B中最重和最轻的金块分别为HB 和LB。第三步，通过比较HA 和HB，可以找到所有金块中最重的；通过比较LA 和LB，可以找到所有金块中最轻的。在第二步中，若n＞2，则递归地应用分而治之方法 程序设计 据上述步骤，可以得出程序1 4 - 1的非递归代码。该程序用于寻找到数组w [ 0 : n - 1 ]中的最小数和最大数，若n < 1，则程序返回f a l s e，否则返回t r u e。 当n≥1时，程序1 4 - 1给M i n和M a x置初值以使w [ M i n ]是最小的重量，w [ M a x ]为最大的重量。 首先处理n≤1的情况。若n>1且为奇数，第一个重量w [ 0 ]将成为最小值和最大值的候选值，因此将有偶,数个重量值w [ 1 : n - 1 ]参与f o r循环。当n 是偶数时，首先将两个重量值放在for 循环外进行比较，较小和较大的重量值分别置为Min和Max，因此也有偶数个重量值w[2:n-1]参与for循环。 在for 循环中，外层if 通过比较确定( w [ i ] , w [ i + 1 ] )中的较大和较小者。此工作与前面提到的分而治之算法步骤中的2) 相对应，而内层的i f负责找出较小重量值和较大重量值中的最小值和最大值，

编译原理-编写递归下降语法分析器

学号107 成绩 编译原理上机报告 名称：编写递归下降语法分析器 学院：信息与控制工程学院 专业：计算机科学与技术 班级：计算机1401班 姓名：叶达成 2016年10月31日

一、上机目的 通过设计、编制、调试一个递归下降语法分析程序，实现对词法分析程序所提供的单词序列进行语法检查和结构分析，掌握常用的语法分析方法。通过本实验，应达到以下目标： 1、掌握从源程序文件中读取有效字符的方法和产生源程序的内部表示文件的方法。 2、掌握词法分析的实现方法。 3、上机调试编出的词法分析程序。 二、基本原理和上机步骤 递归下降分析程序实现思想简单易懂。程序结构和语法产生式有直接的对应关系。因为每个过程表示一个非终结符号的处理，添加语义加工工作比较方便。 递归下降分析程序的实现思想是：识别程序由一组子程序组成。每个子程序对应于一个非终结符号。 每一个子程序的功能是：选择正确的右部，扫描完相应的字。在右部中有非终结符号时，调用该非终结符号对应的子程序来完成。 自上向下分析过程中，如果带回溯，则分析过程是穷举所有可能的推导，看是否能推导出待检查的符号串。分析速度慢。而无回溯的自上向下分析技术，当选择某非终结符的产生时，可根据输入串的当前符号以及各产生式右部首符号而进行，效率高，且不易出错。 无回溯的自上向下分析技术可用的先决条件是：无左递归和无回溯。 无左递归：既没有直接左递归，也没有间接左递归。 无回溯：对于任一非终结符号U的产生式右部x1|x2|…|x n，其对应的字的首终结符号两两不相交。 如果一个文法不含回路（形如P?+ P的推导），也不含以ε为右部的产生式，那么可以通过执行消除文法左递归的算法消除文法的一切左递归（改写后的文法可能含有以ε为右部的产生式）。 三、上机结果 测试数据： (1)输入一以#结束的符号串(包括+—*/（）i#)：在此位置输入符号串例如：i+i*i# (2)输出结果：i+i*i#为合法符号串 (3)输入一符号串如i+i*#,要求输出为“非法的符号串”。 程序清单： #include #include char str[50]; int index=0; void E(); //E->TX; void X(); //X->+TX | e void T(); //T->FY void Y(); //Y->*FY | e void F(); //F->(E) | i int main() /*递归分析*/ { int len; int m;

《递归算法与递归程序》教学设计

递归算法与递归程序 岳西中学：崔世义一、教学目标 1知识与技能 (1) ?认识递归现象。 (2) ?使用递归算法解决冋题往往能使算法的描述乘法而易于表达 (3) ?理解递归三要素：每次递归调用都要缩小规模；前次递归调用为后次作准备：递归调用必须有条件进行。 (4) ?认识递归算法往往不是咼效的算法。 (5) ? 了解递归现象的规律。 (6) ?能够设计递归程序解决适用于递归解决的问题。 (7) ?能够根据算法写出递归程序。 (8) ? 了解生活中的递归现象，领悟递归现象的既有重复，又有变化的特点，并且从中学习解决问题的一种方法。 2、方法与过程 本节让同学们玩汉诺塔的游戏，导入递归问题，从用普通程序解决斐波那契的兔子问题入手，引导学生用自定义了一个以递归方式解决的函数过程解决问题，同时让同学们做三个递归练习，巩固提高。然后让学生做练习(2) 和练习(3)这两道题目的形式相差很远，但方法和答案却是完全相同的练习，体会其中的奥妙，加深对递归算法的了解。最后用子过程解决汉诺塔的经典问题。 3、情感态度和价值观 结合高中生想象具有较强的随意性、更富于现实性的身心发展特点，综合反映出递归算法的特点，以及递归算法解答某些实践问题通常得很简洁，从而激发学生对程序设计的追求和向往。 二、重点难点 1、教学重点 (1) 了解递归现象和递归算法的特点。 (2) 能够根据问题设计出恰当的递归程序。 2、教学难点 (1) 递归过程思路的建立。 (2) 判断冋题是否适于递归解法。 (3) 正确写出递归程序。 三、教学环境 1、教材处理 教材选自《浙江省普通高中信息技术选修：算法与程序设计》第五章，原教材的编排是以本节以斐波那契的兔子问题引人，导出递归算法，从而自 定义了一个以递归方式解决的函数过程。然后利用子过程解决汉诺塔的经典问题。 教材经处理后，让同学们玩汉诺塔的游戏，导入递归问题，从用普通程序解决斐波那契的兔子问题入手，引导学生用自定义了一个以递归方式解决的函数过程解决问题，同时让同学们做三个递归练习，巩固提高。然后让学生做练习⑵ 和练习

递归下降分析法

编译原理课程实验报告 班级学号：姓名： 实验名称：递归下降分析法 一、实验目的： 根据某一文法编制调试递归下降分析程序，以便对任意输入的符号串进行分析。本次实验的目的主要是加深对递归下降分析法的理解。 二、实验要求： 对下列文法，用递归下降分析法对任意输入的符号串进行分析： （1）E->TG （2）G->+TG|—TG （3）G->ε （4）T->FS （5）S->*FS|/FS （6）S->ε （7）F->(E) （8）F->i 输出的格式如下： (1)递归下降分析程序，编制人：姓名，学号，班级 (2)输入一以#结束的符号串(包括+—*/（）i#)：在此位置输入符号串例如：i+i*i# (3)输出结果：i+i*i#为合法符号串 备注：输入一符号串如i+i*#,要求输出为“非法的符号串”。 注意： 1.表达式中允许使用运算符（+-*/）、分割符（括号）、字符i，结束符#； 2.如果遇到错误的表达式，应输出错误提示信息（该信息越详细越好）； 三、实验过程： 程序设计： 1.模块设计：将程序分成合理的多个模块（函数），每个模块做具体的同一事情。 2.写出（画出）设计方案：模块关系简图、流程图、全局变量、函数接口等。 程序编写： 1.定义部分：定义常量、变量、数据结构。 2.初始化：从文件将输入符号串输入到字符缓冲区中。 3.利用递归下降分析法，对每个非终结符编写函数，在主函数中调用文法开始符号的函数。 四、实验结果

（1）程序流程图 主函数main( )流程图 E( )过程流程图 T( )过程流程图

G( )过程流程图 F( )过程流程图

递归与循环的优缺点

递归与循环的优缺点（转载） 2011-08-24 17:49:40| 分类：算法数据结构| 标签：|字号大中小订阅 递归的话函数调用是有开销的，而且递归的次数受堆栈大小的限制。 以二叉树搜索为例： bool search(btree* p, int v) { if (null == p) return false; if (v == p->v) return true else { if (v < p->v) return search(p->left, v); else return search(p->right, v); } } 如果这个二叉树很庞大，反复递归函数调用开销就很大，万一堆栈溢出怎么办？现在我们用循环改写： bool search(btree* p, int v) { while (p) { if (v == p->v) return true; else { if (v < p->v) p = p->left; else p = p->right; } }

return false; } --------------------------------------------------------------------------------------------------------- 递归好处：代码更简洁清晰，可读性更好 递归可读性好这一点，对于初学者可能会反对。实际上递归的代码更清晰，但是从学习的角度要理解递归真正发生的什么，是如何调用的，调用层次和路线，调用堆栈中保存了什么，可能是不容易。但是不可否认递归的代码更简洁。一般来说，一个人可能很容易的写出前中后序的二叉树遍历的递归算法，要写出相应的非递归算法就比较考验水平了，恐怕至少一半的人搞不定。所以说递归代码更简洁明了。 递归坏处：由于递归需要系统堆栈，所以空间消耗要比非递归代码要大很多。而且，如果递归深度太大，可能系统撑不住。 楼上的有人说： 小的简单的用循环, 太复杂了就递归吧,,免得循环看不懂 话虽然简单，其实非常有道理：对于小东西，能用循环干嘛要折腾？如果比较复杂，在系统撑的住的情况下，写递归有利于代码的维护（可读性好） 另：一般尾递归（即最后一句话进行递归）和单向递归（函数中只有一个递归调用地方）都可以用循环来避免递归，更复杂的情况则要引入栈来进行压栈出栈来改造成非递归，这个栈不一定要严格引入栈数据结构，只需要有这样的思路，用数组什么的就可以。 至于教科书上喜欢n!的示例，我想只是便于递归思路的引进和建立。真正做代码不可能的。 -------------------------------------------------------------------------------------------------------------------- 循环方法比递归方法快, 因为循环避免了一系列函数调用和返回中所涉及到的参数传递和返回值的额外开销。 递归和循环之间的选择。一般情况下, 当循环方法比较容易找到时, 你应该避免使用递归。这在问题可以按照一个递推关系式来描述时, 是时常遇到的, 比如阶乘问题就是这种情况。反过来, 当很难建立一个循环方法时, 递归就是很好的方法。实际上, 在某些情形下, 递归方法总是显而易见的, 而循环方法却相当难找到。当某些问题的底层数据结构本身就是递归时, 则递归也就是最好的方法了。

递归下降语法分析程序设计

编译方法实验报告实验名称：简单的语法分析程序设计

实验要求 1.功能：对简单的赋值语句进行语法分析 随机输入赋值语句，输出所输入的赋值语句与相应的四元式 2.采用递归下降分析程序完成（自上而下的分析） 3.确定各个子程序的功能并画出流程图 4.文法如下：

5.编码、调试通过 采用标准输入输出方式。输入输出的样例如下： 【样例输入】 x:=a+b*c/d-(e+f) 【样例输出】(说明，语句和四元式之间用5个空格隔开) T1:=b*c (*,b,c,T1) T2:=T1/d (/,T1,d,T2) T3:=a+T2 (+,a,T2,T3) T4:=e+f (+,e,f,T4) T5:=T3-T4 (-,T3,T4,T5) x:=T5 (:=,T5,-,x) 【样例说明】程序除能够正确输出四元式外，当输入的表达式错误时，还应能检测出语法错误，给出相应错误提示。 6.设计3-5个赋值语句测试实例，检验程序能否输出正确的四元式；当输入错误 的句子时，检验程序能够给出语法错误的相应提示信息。 7.报告内容包括： 递归程序的调用过程，各子程序的流程图和总控流程图，详细设计，3-5个测试用例的程序运行截图及相关说明，有详细注释的程序代码清单等。

目录 1.语法分析递归下降分析算法............................... 错误!未定义书签。 背景知识............................................. 错误!未定义书签。 消除左递归........................................... 错误!未定义书签。 2.详细设计及流程图....................................... 错误!未定义书签。 函数void V( ) .|z ................................. 错误!未定义书签。 函数void A( ) 错误!未指定书签。错误!未指定书签。错误!未指定书签。错误!未指定书签。错误!未指定书签。试用例及截图........................ 错误!未定义书签。 测试用例1及截图..................................... 错误!未定义书签。 测试用例2及截图..................................... 错误!未定义书签。 测试用例3及截图..................................... 错误!未定义书签。 代码清单................................................. 错误!未定义书签。

实验三 递归下降分析程序实现

实验三递归下降分析法 一、实验目的： 根据某一文法编制调试递归下降分析程序，以便对任意输入的符号串进行分析。本次实验的目的主要是加深对递归下降分析法的理解。 程序比较复杂，需要利用到程序设计语言的知识和大量编程技巧，递归下降分析法是一种较实用的分析法，通过这个练习可大大提高软件开发能力。通过练习，掌握函数间相互调 用的方法。 二、实验要求 1.模块设计：将程序分成合理的多个模块（函数），每个模块做具体的同一事情。 2.写出（画出）设计方案：模块关系简图、流程图、全局变量、函数接口等。 3.编程时注意编程风格：空行的使用、注释的使用、缩进的使用等。 三、实验内容 程序输入/输出示例： 对下列文法，用递归下降分析法对任意输入的符号串进行分析： （1）E-TG （2）G-+TG|—TG （3）G-ε （4）T-FS （5）S-*FS|/FS （6）S-ε （7）F-(E) （8）F-i 输出的格式如下： (1)递归下降分析程序，编制人：姓名，学号，班级 (2)输入一以#结束的符号串(包括+—*/（）i#)：在此位置输入符号串例如：i+i*i# (3)输出结果：i+i*i#为合法符号串 备注：输入一符号串如i+i*#,要求输出为“非法的符号串”。 引用也要改变）。 注意：1.表达式中允许使用运算符（+-*/）、分割符（括号）、字符I，结束符#； 2.如果遇到错误的表达式，应输出错误提示信息（该信息越详细越好）； 3.对学有余力的同学，可以详细的输出推导的过程，即详细列出每一步使用的产生式。 四、实验学时 4学时 五、实验步骤 （一）准备：

1.阅读课本有关章节， 2.考虑好设计方案； 3.设计出模块结构、测试数据，初步编制好程序。 （二）上课上机： 将源代码拷贝到机上调试，发现错误，再修改完善。第二次上机调试通过。 （三）程序思路（仅供参考）： 0.定义部分：定义常量、变量、数据结构。 1.初始化：从文件将输入符号串输入到字符缓冲区中。 2.利用递归下降分析法分析，对每个非终结符编写函数，在主函数中调用文法开始符号的函数。 六、实验预习提示 1、递归下降分析法的功能 词法分析器的功能是利用函数之间的递归调用模拟语法树自上而下的构造过程。 2、递归下降分析法的前提 改造文法：消除二义性、消除左递归、提取左因子，判断是否为LL（1）文法， 3、递归下降分析法实验设计思想及算法 为G的每个非终结符号U构造一个递归过程,不妨命名为U。 U的产生式的右边指出这个过程的代码结构： (1)若是终结符号，则和向前看符号对照， 若匹配则向前进一个符号；否则出错。 (2)若是非终结符号，则调用与此非终结符对应的过程。当A的右部有多个产生式时,可用选择结构实现。 具体为： （1）对于每个非终结符号U-u1|u2|…|un处理的方法如下： U( ) { ch=当前符号; if(ch可能是u1字的开头) 处理u1的程序部分; else if(ch可能是u2字的开头)处理u2的程序部分; … else error() } （2）对于每个右部u1-x1x2…xn的处理架构如下： 处理x1的程序； 处理x2的程序； … 处理xn的程序； （3）如果右部为空，则不处理。

递归算法和非递归算法的区别和转换

递归算法向非递归算法转换 递归算法实际上是一种分而治之的方法，它把复杂问题分解为简单问题来求解。对于某些复杂问题(例如hanio塔问题)，递归算法是一种自然且合乎逻辑的解决问题的方式，但是递归算法的执行效率通常比较差。因此，在求解某些问题时，常采用递归算法来分析问题，用非递归算法来求解问题；另外，有些程序设计语言不支持递归，这就需要把递归算法转换为非递归算法。 将递归算法转换为非递归算法有两种方法，一种是直接求值，不需要回溯；另一种是不能直接求值，需要回溯。前者使用一些变量保存中间结果，称为直接转换法；后者使用栈保存中间结果，称为间接转换法，下面分别讨论这两种方法。 1. 直接转换法 直接转换法通常用来消除尾递归和单向递归，将递归结构用循环结构来替代。 尾递归是指在递归算法中，递归调用语句只有一个，而且是处在算法的最后。例如求阶乘的递归算法： long fact(int n) { if (n==0) return 1; else return n*fact(n-1); } 当递归调用返回时，是返回到上一层递归调用的下一条语句，而这个返回位置正好是算法的结束处，所以，不必利用栈来保存返回信息。对于尾递归形式的递归算法，可以利用循环结构来替代。例如求阶乘的递归算法可以写成如下循环结构的非递归算法： long fact(int n) { int s=0; for (int i=1; i<=n;i++) s=s*i; //用s保存中间结果 return s; } 单向递归是指递归算法中虽然有多处递归调用语句，但各递归调用语句的参数之间没有关系，并且这些递归调用语句都处在递归算法的最后。显然，尾递归是单向递归的特例。例如求斐波那契数列的递归算法如下： int f(int n) {

循环与递归算法实验

目录 实验一循环与递归算法的应用.................................. - 2 - 一、实验目的............................................... - 2 - 二、实验内容............................................... - 2 - 三、实验步骤............................................... - 3 - 四.程序调试及运行结果分析.................................. - 5 - 五.实验总结................................................ - 5 - 附录：程序清单（程序过长，可附主要部分）.................. - 6 -

实验一循环与递归算法的应用 一、实验目的 1．掌握循环、递归算法的基本思想、技巧和效率分析方法。 2．熟练掌握循环和递归的设计要点，清楚循环和递归的异同。 3．学会利用循环、递归算法解决实际问题。 二、实验内容 1.问题描述： 题目一：打印图形 编写程序：根据参数n打印具有下面规律的图形， 如，当n=4时，图形如下： 1 5 2 8 6 3 10 9 7 4 题目二：回文判断 判断s字符串是否为“回文”的递归程序。 题目三：计算前n项和 根据参数n，计算1+2+……+n。 要求：用循环和递归分别实现

2.数据输入：个人设定，由键盘输入。 3.要求： 1）上述题目中学号为单数的做题目一和三，双数做二和三。上机前，完成程序代码的编写 2）独立完成实验及实验报告 三、实验步骤 1.理解算法思想和问题要求； 2.编程实现题目要求； 3.上机输入和调试自己所编的程序； 4.验证分析实验结果； 5.整理出实验报告。

编译原理-递归下降子程序-课程设计报告

编译原理课程设计报告 2011 年 12 月 2 日 设计题目 递归下降分析程序的实现 学 号 专业班级 计算机科学与技术 学生姓名 指导教师

一、实验目的: （1）掌握自上而下语法分析的要求与特点。 (2）掌握递归下降语法分析的基本原理和方法。 （3)掌握相应数据结构的设计方法。 二、实验内容: 递归下降分析程序的实现 设计内容及要求： 对文法 G： E→E+T｜Ｔ构造出G的递归下降分析程序。程序显示输出T→T*F|Ｆ匹配过程（即自上而下生成语法分析树的步骤， F→（E）|i 输出各匹配产生式序号即可）。 三、设计思路： (１)语法分析: 语法分析是编译程序的核心部分，任务是分析一个文法的句子结构。递归下降分析程序的实现的功能:按照文法的产生式(语言的语法规则)，识别输入符号串是否为一个句子（合式程序）。 （2)自上而下分析: 从文法的开始符号出发,向下推导,推出句子。可分为带“回溯”的和不带回溯的递归子程序(递归下降)分析方法。 它的主旨是对任何输入串，试图用一切可能的办法,从文法开始符号(根结点）出发，自上而下地为输入串建立一棵语法树。或者说,为输入串寻找一个最左推导。也即从文法的开始符号出发，反复使用各种产生式，寻找"匹配＂的推导。 (3)递归下降分析法： 对每一语法变量(非终结符)构造一个相应的子程序,每个子程序识别一定的语法单位，通过子程序间的信息反馈和联合作用实现对输入串的识别。 (４）分析过程中遇到的问题: a. 分析过程中，当一个非终结符用某一个候选匹配成功时，这种匹配可能是暂时的。出错时,不得不“回溯”。 b．文法左递归问题。含有左递归的文法将使自上而下的分析陷入无限循环。 (5)构造不带回溯的自上而下分析算法： ａ.要消除文法的左递归性：一个文法可以消除左递归的条件是①不含以 为右部的产生式②不含回路。

实验三_递归下降法的语法分析器

魏陈强 23020092204168 实验3 递归下降法的语法分析器 一、实验目的 学习用递归下降法构造语法分析器的原理，掌握递归下降法的编程方法。 二、实验内容 用递归下降法编写一个语法分析程序，使之与词法分析器结合，能够根据语言的上下文无关文法，识别输入的单词序列是否文法的句子。 这里只要求实现部分产生式，文法的开始符号为program。（完整的源语言的文法定义见教材附录 A.1，p394） program→ block block→{stmts } stmts→stmt stmts | stmt→id=expr; | if(bool)stmt | if( bool)stmt else stmt | while(bool)stmt | do stmt while(bool ) ; | break ; | block bool →expr < expr | expr <= expr | expr > expr | expr >= expr | expr expr→ expr + term | expr - term | term

term→ term * factor | term / factor | factor factor→ ( e xpr ) | id| num 三、实验要求 １．个人完成，提交实验报告。 ２．实验报告中给出采用测试源代码片断，及其对应的最左推导过程（形式可以自行考虑）。 测试程序片断： { i = 2; while (i <=100) { sum = sum + i; i = i + 2; } } 对应的推导过程为： program?block ?{stmts } ?{stmt stmts} ?{id=expr;stmts } ?{id=num;stmts } ?{id=num;stmt stmts } ?{id=num;while(bool)stmt stmts } ?{id=num;while(e xpr<= expr)stmt stmts } ?{id=num;while(id<= expr)stmt stmts } ?{id=num;while(id<= num)stmt stmts } ?{id=num;while(id<= num)block stmts } ?{id=num;while(id<= num){stmts }stmts } ?．．．．．．． 四、实验思路 之前编写的词法分析器，能够将语句中的每一个词素都识别出来，因此，在此基础上，定义一个二维字符串数组finaltable[100][20]，用于存放由词法分析器提取出来的每个词素，比如，i=2，则finaltable[0]=”id”，

算法设计及分析递归算法典型例题

算法递归典型例题 实验一：递归策略运用练习 三、实验项目 1．运用递归策略设计算法实现下述题目的求解过程。 题目列表如下： （1）运动会开了N天，一共发出金牌M枚。第一天发金牌1枚加剩下的七分之一枚，第二天发金牌2枚加剩下的七分之一枚，第3天发金牌3枚加剩下的七分之一枚，以后每天都照此办理。到了第N天刚好还有金牌N枚，到此金牌全部发完。编程求N和M。 （2）国王分财产。某国王临终前给儿子们分财产。他把财产分为若干份，然后给第一个儿子一份，再加上剩余财产的1/10；给第二个儿子两份，再加上剩余财产的1/10；……；给第i 个儿子i份，再加上剩余财产的1/10。每个儿子都窃窃自喜。以为得到了父王的偏爱，孰不知国王是“一碗水端平”的。请用程序回答，老国王共有几个儿子？财产共分成了多少份？ 源程序： （3）出售金鱼问题：第一次卖出全部金鱼的一半加二分之一条金鱼；第二次卖出乘余金鱼的三分之一加三分之一条金鱼；第三次卖出剩余金鱼的四分之一加四分之一条金鱼；第四次卖出剩余金鱼的五分之一加五分之一条金鱼；现在还剩下11条金鱼，在出售金鱼时不能把金鱼切开或者有任何破损的。问这鱼缸里原有多少条金鱼？ （4）某路公共汽车，总共有八站，从一号站发轩时车上已有n位乘客，到了第二站先下一半乘客，再上来了六位乘客；到了第三站也先下一半乘客，再上来了五位乘客，以后每到一站都先下车上已有的一半乘客，再上来了乘客比前一站少一个……，到了终点站车上还有乘客六人，问发车时车上的乘客有多少？ （5）猴子吃桃。有一群猴子摘来了一批桃子，猴王规定每天只准吃一半加一只（即第二天吃剩下的一半加一只，以此类推），第九天正好吃完，问猴子们摘来了多少桃子？ （6）小华读书。第一天读了全书的一半加二页，第二天读了剩下的一半加二页，以后天天如此……，第六天读完了最后的三页，问全书有多少页？ （7）日本著名数学游戏专家中村义作教授提出这样一个问题：父亲将2520个桔子分给六个儿子。分完后父亲说：“老大将分给你的桔子的1/8给老二；老二拿到后连同原先的桔子分1/7给老三；老三拿到后连同原先的桔子分1/6给老四；老四拿到后连同原先的桔子分1/5给老五；老五拿到后连同原先的桔子分1/4给老六；老六拿到后连同原先的桔子分1/3给老大”。结果大家手中的桔子正好一样多。问六兄弟原来手中各有多少桔子？ 四、实验过程 （一）题目一：…… 1.题目分析 由已知可得，运动会最后一天剩余的金牌数gold等于运动会举行的天数由此可倒推每一 天的金牌剩余数，且每天的金牌数应为6的倍数。 2.算法构造 设运动会举行了N天， If(i==N)Gold[i]=N; Else gold[i]=gold[i+1]*7/6+i;

高中信息技术 算法与程序设计-递归算法的实现教案 教科版

递归算法的实现 【基本信息】 【课标要求】 （三）算法与问题解决例举 1. 内容标准 递归法与问题解决 （1）了解使用递归法设计算法的基本过程。 （2）能够根据具体问题的要求，使用递归法设计算法、编写递归函数、编写程序、求解问题。 【教材分析】 “算法的程序实现”是《算法与程序设计》选修模块第三单元的内容，本节课是“递归算法的程序实现”，前面学习了用解析法解决问题、穷举法解决问题、在数组中查找数据、对数进行排序以及本节的前一小节知识点“什么是自定义函数”的学习，在学习自定义函数的基础上，学习递归算法的程序实现是自定义函数的具体应用，培养学生“自顶向下”、“逐步求精”的意识起着重要的作用。 『递归算法在算法的学习过程中是一个难点，在PASCAL和C语言等程序语言的学习过程中，往往是将其放在“函数与过程”这一章节中来讲解的。递归算法的实现也是用函数或是过程的自我调用来实现的。从这一点上来讲，作者对教材的分析与把握是准确的，思路是清晰的，目标是明确的。』 【学情分析】 教学对象是高中二年级学生，前面学习了程序设计的各种结构，在学习程序设计各种结构的应用过程中培养了用计算机编程解决现实中问题的能力，特别是在学习循环语句的过程中，应用了大量的“递推”算法。前一节课学习了如何自定义函数，在此基础上学习深入学习和体会自定义函数的应用。以递推算法的逆向思维进行求解问题，在学习过程中体会递归算法的思想过程。多维度的思考问题和解决问题是提高学生的学习兴趣关键。 『递归算法的本质是递推，而递推的实现正是通过循环语句来完成的。作者准确把握了学生前面的学习情况，对递归算法的本质与特征也分析的很透彻，可以说作者对教学任务的分析是很成功的，接来就要看，在成功分析的基础上作者是如何通过设计教学来解决教学难点的了。』 【教学目标】

(完整word版)分治法循环赛日程表实验报告

西北农林科技大学信息工程学院《算法分析与设计》综合训练实习报告 题目：分治法循环赛日程表 学号 姓名 专业班级 指导教师 实践日期2011年5月16日-5月20日

目录 一、综合训练目的与要求 (1) 二、综合训练任务描述 (1) 三、算法设计 (1) 四、详细设计及说明 (3) 五、调试与测试 (4) 六、实习日志 (6) 七、实习总结 (6) 八、附录：核心代码清单 (6)

一、综合训练目的与要求 本综合训练是软件工程专业重要的实践性环节之一，是在学生学习完《算法分析》课程后进行的综合练习。本课综合训练的目的和任务： （1）巩固和加深学生对算法分析课程基本知识的理解和掌握； （2）培养利用算法知识解决实际问题的能力； （3）掌握利用程序设计语言进行算法程序的开发、调试、测试的能力； （4）掌握书写算法设计说明文档的能力； （5）提高综合运用算法、程序设计语言、数据结构知识的能力。 二、综合训练任务描述 假设有n=2k 个运动员要进行网球循环赛。设计一个满足一下要求的比赛日程表：（1）每个选手必须与其他n-1个选手各赛一次 （2）每个选手一天只能赛一次 （3）循环赛一共进行n-1天 利用Java语言开发一个界面，输入运动员的个数，输出比赛日程表。对于输入运动员数目不满足n=2k时，弹出信息提示用户。 三、算法设计 (1) 文字描述 假设n位选手顺序编号为1，2，3……n，比赛的日程表是一个n行n-1列的表格。第i行j列表示第i号选手在第j天的比赛对手，根据分治法，要求n个选手的比赛日程，只要知道其中一半的比赛日程，所以使用递归最终可以分到计算两位选手的比赛日程，然后逐级合并，得出结果。 (2) 框图

递归算法详解

递 归 冯文科 一、递归的基本概念。 一个函数、概念或数学结构，如果在其定义或说明内部直接或间接地出现对其本身的引 用，或者是为了描述问题的某一状态，必须要用至它的上一状态，而描述上一状态，又必须用到它的上一状态……这种用自己来定义自己的方法，称之为递归或递归定义。在程序设计中，函数直接或间接调用自己，就被称为递归调用。 二、递归的最简单应用：通过各项关系及初值求数列的某一项。 在数学中，有这样一种数列，很难求出它的通项公式，但数列中各项间关系却很简单，于是人们想出另一种办法来描述这种数列：通过初值及n a 与前面临近几项之间的关系。 要使用这样的描述方式，至少要提供两个信息：一是最前面几项的数值，一是数列间各项的关系。 比如阶乘数列 1、2、6、24、120、720…… 如果用上面的方式来描述它，应该是： ???>==-1 ,1,11n na n a n n 如果需要写一个函数来求n a 的值，那么可以很容易地写成这样：

这就是递归函数的最简单形式，从中可以明显看出递归函数都有的一个特点：先处理一 些特殊情况——这也是递归函数的第一个出口，再处理递归关系——这形成递归函数的第二个出口。 递归函数的执行过程总是先通过递归关系不断地缩小问题的规模，直到简单到可以作为 特殊情况处理而得出直接的结果，再通过递归关系逐层返回到原来的数据规模，最终得出问题的解。 以上面求阶乘数列的函数)(n f 为例。如在求)3(f 时，由于3不是特殊值，因此需要计 算)2(*3f ，但)2(f 是对它自己的调用，于是再计算)2(f ，2也不是特殊值，需要计算 )1(*2f ，需要知道)1(f 的值，再计算)1(f ，1是特殊值，于是直接得出1)1(=f ，返回上 一步，得2)1(*2)2(==f f ，再返回上一步，得62*3)2(*3)3(===f f ，从而得最终解。 用图解来说明，就是 下面再看一个稍复杂点的例子。 【例1】数列}{n a 的前几项为

实验1++递归与分治算法

淮海工学院计算机工程学院实验报告书 课程名：《算法分析与设计》 题目：实验1 递归与分治算法 班级： 学号： 姓名：

实验1 递归与分治算法 实验目的和要求 （1）进一步掌握递归算法的设计思想以及递归程序的调试技术； （2）理解这样一个观点：分治与递归经常同时应用在算法设计之中。 （3）分别用蛮力法和分治法求解最近对问题； （4）分析算法的时间性能，设计实验程序验证分析结论。 实验内容 设p1=(x1, y1), p2=(x2, y2), …, pn=(xn, yn)是平面上n个点构成的集合S，设计算法找出集合S中距离最近的点对。 实验环境 Turbo C 或VC++ 实验学时 2学时，必做实验 数据结构与算法 核心源代码 蛮力法： #include #include #include int ClosestPoints(int x[ ], int y[ ], int n); int main() { int x[3],y[3]; printf("请输入各点的横坐标: "); for(int i=0;i<4;i++) { scanf("%d",&x[i]); } printf("请输入各点的纵坐标: "); for(int j=0;j<4;j++)

{ scanf("%d",&y[i]); } ClosestPoints(x,y,4); return 0; } int ClosestPoints(int x[ ], int y[ ], int n) { int index1, index2; //记载最近点对的下标 int d, minDist = 1000; //假设最大距离不超过1000 for (int i = 0; i < n - 1; i++) for (int j = i + 1; j < n; j++) //只考虑i＜j的点对 { d =sqrt ((x[i]-x[j])* (x[i]-x[j]) + (y[i]-y[j])* (y[i]-y[j])); if (d < minDist) { minDist = d; index1 = i; index2 = j; } } cout<<"最近的点对是："< #include const int n = 4; struct point //定义点的结构体 { int x, y; };