题目

外观数列是指具有以下特点的整数序列：

1

d, d1, d111, d113, d11231, d112213111, ...

它从不等于 1 的数字 d 开始，序列的第 n+1 项是对第 n 项的描述。比如第 2 项表示第 1 项有 1 个 d，所以就是 d1；第 2 项是 1 个 d（对应 d1）和 1 个 1（对应 11），所以第 3 项就是 d111。又比如第 4 项是 d113，其描述就是 1 个 d，2 个 1，1 个 3，所以下一项就是 d11231。当然这个定义对 d = 1 也成立。本题要求你推算任意给定数字 d 的外观数列的第 N 项。

输入格式：

输入第一行给出 [0,9] 范围内的一个整数 d、以及一个正整数 N（ $\le$ 40），用空格分隔。

输出格式：

在一行中给出数字 d 的外观数列的第 N 项。

输入样例：

1

1 8

输出样例：

1

1123123111

思路

我说过遇到一些数学性比较强的题目会给出比较严谨的说明，看到这题，我要收回这句话。。

因为这道题我求不出一个比较小的字符串长度下限啊，根本不会分析。。。

不过幸好输入的可能情况很少，在自己写的时候尝试一下就好了。

大致思路：

这道题要求解一个递推的序列，递推关系和上一个数中数字的出现模式相关。逻辑上还是好理解的，实现上也不是很难。我的思路是这样的：

  • 用两个字符串做存储，交替地存放新产生的递归序列
  • 用两个指针分别指向代表第k个和第k+1个序列的字符串，这样交替的时候交换字符串就可以了
  • 共N-1次（因为最初的算序列的第一个）扫描第k个字符串，同时生成第k+1个。具体为：
    • 初始化计数变量
    • 从第一个字符开始向后遍历第k个字符串，直到最后一个字符
      • 我先增加了计数变量，因为我是从0开始计数的，因此任何情况都要增加计数
      • 比较该字符和后一个字符，看是否相等：相同的话，上面已增加过计数，什么都不做；不相同的话，向另一个字符串里记录该字符和出现次数，并重置计数

思考：

关于字符串长度： 这个题目很难分析需要多长的字符串，不过输入只可能有0-9十种数字和1-40的N值，因此只需让N=40时，字符串足够长就够了。我测试的结果是：

  • d = 1, N = 40: 结果长63139个字符
  • d取其它, N = 40: 结果长73393个字符

所以我就开了长度为100 000的字符串。

关于算法的设计： 这道题我第一感觉其实是不需要开数组，因为每次递归过程仅需要知道局部的信息即可，不需要对整体的信息进行整理。但是问题是这道题需要多次利用已生成的结果作为新的数据进行处理，所以一定要把结果保留下来才可以进行多次的递归。至少我是觉得这道题一定要开数组进行存储才可以。

代码

Github最新代码，欢迎交流

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

#include <stdio.h>

int main()
{
	int N, count;
	char string1[100000] = {0}, string2[100000] = {0};
	char *s1 = string1, *s2 = string2, *temp;
	char *p1, *p2;

	scanf("%s %d", s1, &N);

	for (int i = 1; i < N; i++) { /* Loop through nth string */
		for (p1 = s1, p2 = s2, count = 0; *p1; p1++) {
			count++;    /* Magic, don't touch! */
			if (*p1 != *(p1 + 1)) {      /* New char or end */
				*p2++ = *p1;            /* Record character */
				*p2++ = count + '0';    /* Record count */
				count = 0;              /* Reset count */
			}
		}
		/* Swap */
		temp = s1, s1 = s2, s2 = temp;
	}

	puts(s1);

	return 0;
}