我的PAT系列文章更新重心已移至Github变丧，歡迎來(lái)看PAT題解的小伙伴請(qǐng)到Github Pages瀏覽最新內(nèi)容。此處文章目前已更新至與Github Pages同步狡蝶。歡迎star我的repo庶橱。
題目
外觀數(shù)列是指具有以下特點(diǎn)的整數(shù)序列：
d, d1, d111, d113, d11231, d112213111, ...
它從不等于 1 的數(shù)字 d 開(kāi)始，序列的第 n+1 項(xiàng)是對(duì)第 n 項(xiàng)的描述贪惹。比如第 2 項(xiàng)表示第 1 項(xiàng)有 1 個(gè) d苏章，所以就是 d1；第 2
項(xiàng)是 1 個(gè) d（對(duì)應(yīng) d1）和 1 個(gè) 1（對(duì)應(yīng) 11）馍乙，所以第 3 項(xiàng)就是 d111。又比如第 4 項(xiàng)是 d113垫释，其描述就是 1 個(gè)
d丝格，2 個(gè) 1，1 個(gè) 3棵譬，所以下一項(xiàng)就是 d11231显蝌。當(dāng)然這個(gè)定義對(duì) d = 1 也成立。本題要求你推算任意給定數(shù)字 d 的外觀數(shù)列的第
N 項(xiàng)订咸。
輸入格式：
輸入第一行給出 [0,9] 范圍內(nèi)的一個(gè)整數(shù) d曼尊、以及一個(gè)正整數(shù) N（ 40），用空格分隔脏嚷。
輸出格式：
在一行中給出數(shù)字 d 的外觀數(shù)列的第 N 項(xiàng)骆撇。
輸入樣例：
1 8
輸出樣例：
1123123111
思路
我說(shuō)過(guò)遇到一些數(shù)學(xué)性比較強(qiáng)的題目會(huì)給出比較嚴(yán)謹(jǐn)?shù)恼f(shuō)明，看到這題父叙，我要收回這句話神郊。。
因?yàn)檫@道題我求不出一個(gè)比較小的字符串長(zhǎng)度下限啊趾唱，根本不會(huì)分析涌乳。。甜癞。
不過(guò)幸好輸入的可能情況很少夕晓，在自己寫的時(shí)候嘗試一下就好了。
大致思路：
這道題要求解一個(gè)遞推的序列悠咱，遞推關(guān)系和上一個(gè)數(shù)中數(shù)字的出現(xiàn)模式相關(guān)蒸辆。邏輯上還是好理解的，實(shí)現(xiàn)上也不是很難析既。我的思路是這樣的：
- 用兩個(gè)字符串做存儲(chǔ)吁朦，交替地存放新產(chǎn)生的遞歸序列
- 用兩個(gè)指針?lè)謩e指向代表第k個(gè)和第k+1個(gè)序列的字符串，這樣交替的時(shí)候交換字符串就可以了
- 共N-1次（因?yàn)樽畛醯乃阈蛄械牡谝粋€(gè)）掃描第k個(gè)字符串渡贾，同時(shí)生成第k+1個(gè)逗宜。具體為：
- 初始化計(jì)數(shù)變量
- 從第一個(gè)字符開(kāi)始向后遍歷第k個(gè)字符串，直到最后一個(gè)字符
- 我先增加了計(jì)數(shù)變量，因?yàn)槲沂菑?開(kāi)始計(jì)數(shù)的纺讲，因此任何情況都要增加計(jì)數(shù)
- 比較該字符和后一個(gè)字符擂仍，看是否相等：相同的話，上面已增加過(guò)計(jì)數(shù)熬甚，什么都不做逢渔；不相同的話，向另一個(gè)字符串里記錄該字符和出現(xiàn)次數(shù)乡括，并重置計(jì)數(shù)
思考：
關(guān)于字符串長(zhǎng)度： 這個(gè)題目很難分析需要多長(zhǎng)的字符串肃廓，不過(guò)輸入只可能有0-9十種數(shù)字和1-40的N值，因此只需讓N=40時(shí)诲泌，字符串足夠長(zhǎng)就夠了盲赊。我測(cè)試的結(jié)果是：
- d = 1, N = 40: 結(jié)果長(zhǎng)63139個(gè)字符
- d取其它, N = 40: 結(jié)果長(zhǎng)73393個(gè)字符
所以我就開(kāi)了長(zhǎng)度為100 000的字符串。
關(guān)于算法的設(shè)計(jì)： 這道題我第一感覺(jué)其實(shí)是不需要開(kāi)數(shù)組敷扫，因?yàn)槊看芜f歸過(guò)程僅需要知道局部的信息即可哀蘑，不需要對(duì)整體的信息進(jìn)行整理。但是問(wèn)題是這道題需要多次利用已生成的結(jié)果作為新的數(shù)據(jù)進(jìn)行處理葵第，所以一定要把結(jié)果保留下來(lái)才可以進(jìn)行多次的遞歸绘迁。至少我是覺(jué)得這道題一定要開(kāi)數(shù)組進(jìn)行存儲(chǔ)才可以。
代碼
最新代碼@github卒密，歡迎交流
#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;
}
