计数和数数

来源:@计蒜客—计数和数数

题目

一个找规律的题目:

1
2
3
4
5
6
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
2
3
4
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
}

代码

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#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;
}

转载请注明来源:©Tinshine