PDF《离散数学作业 10-递归与结构归纳法》

离散数学作业 10-递归与结构归纳法 习题

1 给出下述集合的递归定义: a) 正偶数集合.

b)

3 的正整数次幂的集合. c) 整系数多项式的集合. 习题

2 确定用欧几里得算法求出斐波那契数 fn 和fn+1 的最大公因子所用的除法 的次数,其中 n 是非负整数.用数学归纳法验证你的答案. 习题

3 a) 对于表示十进制数字的非空字符串 s,给出计算 s 中最小数字的函数 m(s) 的递归定义. b) 用结构归纳法证明 m(s ・ t) = min(m(s), m(t)).( 其中 s ・ t 表示位串 s 和位串 t 的连接 )

1 习题

4 正整数 n 的分拆是把 n 写成正整数之和的方式.例如,7 =

3 +

2 +

1 +

1 是7的拆分.设Pm 等于 m 的不同分拆的数目,其中和式里项的顺序无关紧 要,并设 Pm,n 是用不超过 n 的正整数之和来表示 m 的不同方式数. a) 证明:Pm,m = Pm. b) 证明:下面的 Pm,n 的递归定义是正确的. Pm,n = ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

1 m =

1 1 n =

1 Pm,m m < n

1 + Pm,m?1 m = n >

1 Pm,n?1 + Pm?n,n m > n >

1 c) 用这个递归定义求出

5 和6的拆分数. 习题

5 求出阿克曼函数值 A(3, 4).阿克曼函数的定义为: A(m, n) = ? ? ? ? ? ? ? ? ? n +

1 m =

0 A(m ? 1, 1) m > 0,n =

0 A(m ? 1, A(m, n ? 1)) m > 0,n >

0 习题

6 证明: 对第 n 个斐波那契数 fn, 当n是正整数时, 有f1 +f3 +・ ・ ・+f2n?1 = f2n. 习题

7 斐波那契树 Tk 是一种特殊的二叉树并满足以下定义:

2 a)T1 和T2 是只有一个顶点的二叉树. b) 对于任意的 n > 2,Tn 由一个根节点和左子树 Tn?1 和右子树 Tn?2 组成. 使用结构归纳证明:对于任意大于

1 的整数 n,Tn 的高度为 n ? 2. 习题

8 给出字符串的倒置的递归定义.( 一个字符串的倒置 ( 反转 ),是由原字符 里的符号以相反顺序组成的字符串.把字符串 w 的倒置表示为 wR .) 3