题目

一个找规律的题目：

f(1) = 1
f(2) = 11
f(3) = 21
f(4) = 1211
f(5) = 111221
f(6) = 312211

要求

多组输入，读到文件结束，每组一个整数n（1≤n≤30）。输出为每个n相应的序列，样例如下：

Input:

1
3
7
eof

output:

1
2
3

1
21
13112221

解析

规律

这是一个类似斐波那契数列的迭代过程。n=1时，f(1)=1。将其看作一个字符串，这就是1个’1’，将两个数字写在一起就是：f(2)=’11’。依此类推，’11’是2个’1’，f(3)就应该是’21’；’21’是1个’2’，1个’1’，因此f(4)=’1211’。

实现

对于上述的迭代过程，考虑使用递归函数来实现。对于任意一个n值，要得到相应的序列，都需要从1开始迭代n次。每次迭代，对当前已知的字符串进行计数，逐字符的统计出某个字符连续出现的次数，并生成相应字符串附加到一个新串的串尾。

比如，通过f(4)得到f(5)，转化算法实现如下：f(4)作为主串传入，新建一个串str，一个计数器cnt，一个用于记录前个字符的pre，扫描f(4)=’1211’，将pre设为首个字符’1’，将cnt+1；扫描’2’，对比发现pre不等于’2’；这时得知有cnt个pre，也即1个’1’，将字符串”11”附加在新串str后······最终得到新串str = f(5)，如果此时迭代仍未结束，则将str作为主串，递归调用这个转化函数，直至满足需要。

此外，还要注意边界情况的考虑，即对首个字符和最后一个字符要特殊处理。

C++知识

题目提到要有多组输入，一直读到文件尾。在c++中，可以通过一个while循环来实现这个功能：

1
2
3

while(cin >> n){
    // your code here
}

代码

#include "iostream"
#include "cstring"
using namespace std;

void transform(string &s, int n){
    if(n == 1){          
        cout << s << endl;  
        return;
    }
    int cnt = 0; char pre = s[0];
    string str;
    for(int i=0; i<s.length(); ++i){
        if(i == 0){                 
            ++cnt;                  
            if(s.length() == 1){                
                str.append(1, s[0]).append(1, char(cnt + '0'));
                break;
            }
            continue;
        }
        if(i == s.length()-1){
            if(s[i] == pre){
                str.append(1, char(++cnt + '0')).append(1, pre);
            }else{
                str.append(1, char(cnt + '0')).append(1, pre).append(1, '1').append(1, s[i]);
            }
        }else{
            if(s[i] == pre){
                ++cnt; 
                continue;
            }else{
                str.append(1, char(cnt + '0')).append(1, s[i-1]);
                cnt = 1; 
                pre = s[i];
            }
        }
    }
    transform(str, n-1);  
}

int main(int argc, char const *argv[])
{
    string s = "1"; 
    int n;  
    while(cin >> n){
        transform(s, n);
    }
    return 0;
}