3.2　求解递归数据

我们在构造问题的数学模型时，有时会发现数据的结构形式是一种递归关系。例如，二叉树的遍历或图的深度优先遍历本身就是按递归定义的，有关这方面内容将在第三篇和第四篇阐释。下面给出一个浅显而有趣的实例。

【3.2.1　Symmetric Order】

你在Albatross Circus Management工作，刚写了一个以长度非递减的顺序输出姓名列表的程序（每个姓名至少要和前面的名字一样长）。然后，你的老板不喜欢这样的输出方式，他要求改为看上去对称的输出形式，最短的字符串在顶部和底部，最长的在中间。他的规则是每一对姓名在列表对等的地方，每一对姓名中的第一个在列表的上方。如在下面的样例输入的第一个例子中，Bo和Pat是第一对，Jean和Kevin是第二对，等等。

输入

输入由一个或多个字符串集合组成，以0结束。每个集合以一个整数n开始，表示该集合中字符串的个数，每个字符串一行，字符串以长度的非递减顺序排列。字符串不含空格。每个集合中的字符串至少有1个，至多有15个。每个字符串至多有25个字符。

输出

对每个输入的集合输出一行“SET n”，其中n从1开始，后面跟着输出集合，如样例输出所示。

试题来源：ACM Mid-Central USA 2004

在线测试：POJ 2013，ZOJ 2172，UVA 3055

试题解析

以长度非递减的顺序输出的姓名列表为s[1]…s[n]。要求输出的格式是对称的，最短的字符串在顶部和底部，最长的在中间。也就是说，在输出的上半区，姓名的长度是递增的；而在输出的下半区，姓名的长度是递减的。本题有两种解法：非递归的方法和递归的方法。

（1）非递归的方法

输入的字符串集合中的字符串以长度非递减的顺序排列。输出是对称的，最短的字符串在顶部和底部，最长的在中间，所以，上半区的输出如下：

s[1]
s[3]
s[5]
…
s[n]，如果n是奇数；s[n-1]，如果n是偶数

也就是说，循环语句“for(int i=1;i<=n;i+=2)cout<<s[i]<<endl;”实现上半区的输出。

下半区的输出如下：

s[n-(n%2)]
s[n-(n%2)-2]
s[n-(n%2)-4]
…
s[2]

也就是说，循环语句“for(int i=n-(n%2);i>1;i-=2)cout<<s[i]<<endl;”实现下半区的输出。

（2）递归的方法

n个字符串被划分为组，每组由两个相邻的字符串s[1]s[2]，s[3]s[4]，…，s[2×k-1]s[2×k]，…组成，。我们通过递归函数print(n)，输入字符串数组s[]，计算和输出其对称形式。

设字符串数组s[]为递归子程序print()的局部变量，使之成为编译系统的一个栈区，s[]中的字符串呈这样的递归关系：

·直接输入，并输出当前组的第一个字符串s[2×k-1]。

·若当前组存在第二个字符串s[2×k]的话，则输入；若存在下一组的话，则通过递归调用print()将其送入系统栈区。执行完print()后回溯时，栈中的字符串按先进后出的顺序出栈并输出。

计算过程如下。

直接输入/输出当前组的第一个字符串s[2×k-1]，s[]的长度n--；如果n>0，则输入当前组的第二个字符串s[2×k]，s[]的长度n--。若存在下一组（n>0），则通过递归调用print(n)将s[2×k]压栈，继续处理下一组……这个过程进行至n==0为止。然后回溯，按先进后出的顺序依次处理栈中的字符串。显然，若n是偶数，则s[n-1]s[n-3]…s[2]出栈并输出；若n是奇数，则s[n]s[n-2]…s[2]出栈并输出。

参考程序

#include <iostream>                 //预编译命令
using namespace std;                //使用 C++标准程序库中的所有标识符
void print(int n)                   //输入n个字符串，并按对称格式输出
{
    string s;                       //当前字符串
    cin >> s;                       //输入和输出当前组的第一个字符串
    cout << s << endl;            
    if (--n) {                      //输入当前组的第二个字符串并通过递归压入系统栈区
        cin >> s;
        if (--n) print(n);
        cout << s << endl;          //回溯，栈首字符串出栈后输出
    }
}
int main(void)
{
    int n, loop = 0;                //字符串集合序号初始化
    cin >> n;                       //输入第一个字符串集合的字符串个数
    while (n) {
        cout<<"SET "<<++loop<<endl; //输出当前字符串集合的序号
        print(n);                   //按照对称格式输出当前字符串集合中的n个字符串
        cin >> n;                   //输入下一个字符串集合的字符串个数
    }
    return 0;
}
上一章目录下一章