递归定义集合B如下:(1)( )∈B,(2)若x∈B,则(x)∈A,(3)若x,y∈B,则(xy)∈A,(4)只有有限次应用(1)~(3
递归定义集合B如下:
(1)()∈B,
(2)若x∈B,则(x)∈A,
(3)若x,y∈B,则(xy)∈A,
(4)只有有限次应用(1)~(3)得到的符号串属于B.
问下述符号出是不属于B.
递归定义集合B如下:
(1)()∈B,
(2)若x∈B,则(x)∈A,
(3)若x,y∈B,则(xy)∈A,
(4)只有有限次应用(1)~(3)得到的符号串属于B.
问下述符号出是不属于B.
第1题
已知Ackerman函数定义如下:
(1)根据定义,写出它的递归求解算法;
(2)利用栈,写出它的非递归求解算法。
第2题
已知Ackerman函数的定义如下:
(1)写出递归算法;
(2)写出非递归算法;
(3)根据非递归算法, 画出求akm(2,1)时栈的变化过程。
第3题
已知集合A,B,其中是偏序集,定义BA上的二元关系R如下:
(1)证明R为BA上的偏序.
(2)给出<BA,R>存在最大元的充分必要条件和最大元的一般形式.
第4题
能否从这n件物品中选择若干件放入此背包中,使得放入的重量之和正好为s。如果存在一种符合上述要求的选择,则称此背包问题有解(或称其解为真);否则称此背包问题无解(或称其解为假)。试用递归方法设计求解背包问题的算法。(提示:此背包问题的递归定义如下:)
第6题
第8题
已知Ackermann函数定义如下:
①写出计算Ack(m,n)的递归算法,并根据此算法给出出Ack(2,1)的计算过程。
②写出计算Ack(m,n)的非递归算法。
第10题
二叉排序树的类型定义如下:
typedef struet BSTNode{//二叉排序树的结点结构
int data; //数据域
struct BSTNode*lchild,*rchild;//左、右孩子指针
}BSTNode,*BSTree;
设计递归算法,统计一棵二叉排序树T中值小于a的结点个数。