每天一道算法：数数并说

36、数数并说

题目

“数数并说”序列是一个整数序列，第二项起每一项的值为对前一项的记数，其前五项如下：

1、1

2、11

3、21

4、1221

5、111221

序列规则：

1 读作 “1个1”，即 11。

11 读作 “两个1”，即 21。

21 读作 “一个2，一个1”，即 1211。

要求给定一个整数n，1 ≤ n ≤ 30，生成数数并说序列的第 n 项。

备注：该整数序列的每一项都输出为字符串。

思路

1、定义法

由于第 n 项的值，总是由第 n-1 项来决定的，因此可以使用递归法求解第 n-1 项的值，我们需要关心的，就是如何从第 n-1 项得到第 n 项。

根据序列的定义，需要对输入的序列从左到右进行数数，规则为：

1、如果相邻的数不同，则记为“1个X”

2、如果相邻的数相同，则继续向后遍历，直至出现了不同的数，那么前面这些相同的数作为一个整体记为“m个X”

3、从左到右依次遍历，直至遍历到最后一位。

这样，我们就知道了如何从第 n-1 项获取到第 n 项。

递归法还需要规定递归结束条件：n=1时，序列的第一项的值规定为 1。

代码

python实现