9.6  编程项目

更多深层次的项目参见网址：www.cs.colorado.edu/~main/projects/

1. 编写一个函数，要求产生如下所示的输出：

This was written by call number 1.

 This was written by call number 2.

  This was written by call number 3.

   This was written by call number 4.

    This was written by call number 4.

   This was written by call number 3.

  This was written by call number 2.

 This was written by call number 1.

在这个例子中，当递归到达第4级时，该递归停止。但是，函数应当能够继续，直到任意指定的一级。

2. 编写一个带有两个参数的函数，两个参数分别是prefix(一个字符串，使用来自<string>的字符串类)和levels(一个无符号整数)。该函数输出字符串prefix，后跟“节数”，其形式为1.1、1.2、1.3，等等。参数levels决定节数的级数。例如，如果levels是2，那么节数的形式是x.y。如果levels是3，那么节数的形式是x.y.z。每一级允许的数字总是从‘1’到‘9’。举例来说，如果prefix是字符串“BOX:”，levels是2，那么函数从输出如下的内容开始：

BOX:1.1.

BOX:1.2.

BOX:1.3.

最后输出的是：

BOX:9.7.

BOX:9.8.

BOX:9.9.

当levels到达0时，停止条件就会发生。这里需要的基本字符串操作技术是创建一个新字符串，该字符串包含prefix，后面紧接一个数字和一个句点。如果s是希望创建的字符串，i是数字(1到9之间的整数)，那么下面的语句将完成这个任务：

s = prefix;

s+= '.';

s+= char('0' + i);

第三个语句把character(‘0’+i)放到了字符串的末端，这个字符是与整数i对应的ASCII值。新字符串s可以作为参数传递给函数的递归调用。

3. 编写一个带有两个输入字符串(来自<string>)参数first和second的递归函数。函数将输出first中所有字母的重新排列，然后输出second。举例来说，如果first是字符串CAT，second是字符串MAN，那么函数将输出字符串CATMAN、CTAMAN、ACTMAN、ATCMAN、TACMAN和TCAMAN。当first的长度为0个字符时函数出现停止条件。我们把递归思想留给你来完成，但是这里也提示一下，利用如下两个字符串成员函数可以使问题变得更容易解决：

void string::insert(

    size_type position,

    size_type number_of_copies,

    char c

);

// Postcondition: The specified number of

// copies of c have been inserted into the

// string at the indicated position. Chars

// that used to be at or after the given

// position have been shifted right one spot.

void string::erase

(size_type position, size_type n);

// Postcondition: n characters have been

// removed from the string, beginning at the

// specified position.

4. 编写一个递归程序，协助你对房间中的所有盒子进行计数。程序以提问一个“你看到了多少个未编号的盒子？”之类的问题开始。然后，程序让你按照从1到m的顺序对那些盒子进行编号，其中的m就是你的回答。但是，要知道每个盒子里面可能有更小的盒子，所以一旦程序知道你看到了m个盒子之后，它就会要求你打开第1个盒子，拿出在其中找到的盒子，把这些盒子编号为1.1、1.2等等。程序还会要求你打开第2个盒子，拿出在其中找到的盒子，把它们编号为2.1、2.2等等。然后第3个、第4个盒子，直到第m个盒子。当然，每次把一个盒子编号为1.1、3.8或者类似的标记时，这个盒子中可能还有盒子。3.8中的盒子可以编号为3.8.1、3.8.2等等。最后，程序应该输出一个单独的数字，告诉你房间中盒子的总数。

5. 编写一个名为sumover的递归函数，该函数有一个无符号整数参数n。函数返回一个双精度数值，即前n个正整数的倒数和(x的倒数是分数1/x)。例如，sumover(1)返回1.0(即1/1)；sumover(2)返回1.5(即1/1+1/2)；sumover(3)返回大约1.833(即1/1+1/2+1/3)。定义sumover(0)为0。要求在函数中不使用任何局部变量。

6. 如果要从含有n个元素的集合中选出r个不同的元素，可以有多种选择方法，其计算公式如下：

在这个公式中，阶乘函数由一个感叹号(!)表示，其定义为：

找出公式C(n, r)的一个递归版本，并编写计算这个公式的值的递归C++函数。把这个函数嵌入一个程序并加以测试。

7. 编写一个递归函数，其参数为一个字符数组和数组索引的两个边界。函数应该颠倒数组中索引位于两个边界之间的数据项的顺序。举例来说，假设数组是：

a[0] = 'A'   a[1] = 'B'   a[2] = 'C'

a[3] = 'D'   a[4] = 'E'

边界是1和3。那么在函数运行之后，数组元素应该是：

a[0] = 'A'   a[1] = 'D'   a[2] = 'C'

a[3] = 'B'   a[4] = 'E'

把这个函数嵌入到一个程序中并加以测试。

8. 编写一个能产生n行星号的递归程序。第一行包含一个星号，下一行包含两个，如此增加下去，直到第n行包含n个星号。第n+1行也包含n个星号，下一行包含n–1个，如此下去，直到第2n行只有一个星号。

9. 分析下面的由星号和空格组成的图案，编写一个能产生这种图案的递归函数：

10. 这是一个数字迷项目。下面介绍一下规则：老师给你一定数量的软盘，软盘的数量为initial。现在你有两种选择：(a)再请求(并接收)53张软盘，或者(b)如果你有偶数张软盘，那么可以返还一半软盘给老师。每做一次(a)或者(b)，在游戏中就称为一步。你的目标是在n步或者更少的步内恰好达到91张软盘。举例来说，如果initial是99，n是4，那么可以通过下面的步骤序列到达目标91：

对于这一项目，编写一个递归函数goal，用于确定从数字initial开始，经过至多n步后，是否可以达到目标(91)。基本条件出现在initial为91时(因为在这种情况下，答案是yes)，或者出现在n为0并且initial不等于91时(因为在这种情况下，答案是no)。如果没有遇到基本条件，那么通过一个或两个递归调用(一个调用是goal(initial+53, n–1)，另一个是goal(initial/2, n–1)—— 尽管第二个调用需要保证initial为偶数)来解决这一问题。

11. 让我们回忆一下你所在的计算机系班级。你可能认识几个学生，也许是Judy、Jervis、Walter和Michael。这些学生中的每个人都认识另外几个学生，另外的学生又认识其他的学生，依次类推。现在，你想认识一个名字为Dor的学生。认识Dor的方法是你与他有共同认识的学生：例如，你认识Judy，而Judy认识Dor，所以Judy可以把你介绍给Dor。或者，可以通过一个更长的途径认识Dor：例如，你认识Judy、Judy认识Harry、Harry认识Cathy、Cathy认识Dor。在这种情况下，Judy可以把你介绍给Harry，Harry可以把你介绍给Cathy，Cathy可以把你介绍给Dor。

编写一个交互式程序，帮助你确认是否有一条使你认识Dor的途径。程序包含一个递归函数，函数唯一的参数person是你们班级中的一个人的名字。函数确定是否有一条路径使得person认识Dor。提示：这个程序与9.2节的迷宫问题有些类似，但是要注意潜在的无限递归！一个避免无限递归的方法是在搜索到Dor的路径的过程中，创建一个包含学生姓名的包，这个包跟踪已经访问过的学生的姓名。

12. 完美的输出程序可以处理不带任何特定方式缩进的程序代码，并且生成带缩进的同一程序的副本，从而使得括号对({和})整齐排列，内层括号对要比外层括号对缩进得更多，并使得if-else语句按照本书所采用的方式缩进，其他的缩进也是如此。编写一个程序，该程序从一个文本文件中读入一个C++程序，并在第二个文本文件中生成该程序的完美输出版本。为了使问题更简单，只处理程序体，忽略声明，并且假设复杂语句(除了复合语句本身)的所有子语句都是复合语句(也就是被括号括起来的语句)。

13. 重新编写图9-11中的递归函数pow，使得计算pow(x, n)需要花费的时间是log(n)。提示：利用公式x²ⁿ=xⁿ×xⁿ。

14. 编写一个递归调用函数，把数字的字符串形式转化为整数值。例如：convert(“1234”)返回1234。提示：为了把一个字符转化为一个数字，可以把字符的ASCII值减去‘0’的ASCII值。举例来说，如果字符串s仅有一个字符，那么函数的返回值可以是s[0]–‘0’。

15.  Ackermann函数是以德国数学家Wilhelm Ackermann的名字命名的，此函数用于递归函数的理论。这个函数有几个变体，这些变体的共同属性是：函数具有两个参数(x和y)，并且函数的增长速度非常快(增长速度大大高于多项式或指数)。下面是Ackermann函数的一个变体：

(1) 如果x = 0，那么Ackermann(x, y) = 2y。

(2) 如果x >= 1且y = 0，那么Ackermann(x, y) = 0。

(3) 如果x >= 1且y = 1，那么Ackermann(x, y) = 2。

(4) 如果x >= 1且y >= 2，那么Ackermann(x, y) = Ackermann(x–1, Ackermann(x, y–1))。

用递归函数实现Ackermann函数的这个变体。