題目描述

The count-and-say sequence is the sequence of integers beginning as follows:
1, 11, 21, 1211, 111221, ...

1 is read off as"one 1"or11.
1 1is read off as"two 1s"or21.
2 1is read off as"one 2, thenone 1"or1211.

Given an integer n, generate the n ^th sequence.

Note: The sequence of integers will be represented as a string.

題目大意

題意是：
n=1時(shí)輸出字符串1；
n=2時(shí)，數(shù)上次字符串中的數(shù)值個(gè)數(shù)，因?yàn)樯洗巫址?個(gè)1，所以輸出11；
n=3時(shí)，由于上次字符是11，有2個(gè)1，所以輸出21；
n=4時(shí)，由于上次字符串是21，有1個(gè)2和1個(gè)1，所以輸出1211

思路

就每次計(jì)算一下pre_out中各個(gè)數(shù)字的個(gè)數(shù)，然后儲(chǔ)存到新的cur_out中就好了。

代碼

#include<iostream>
#include<cstring>
using namespace std;
string help_fun(string pre_out);
string countAndSay(int n)
{
    if(n == 0)return "";

    string cur_out = "1";

    // 輸出第n個(gè)結(jié)果，就是說(shuō)要計(jì)數(shù)到第n個(gè)
    for(int i=1; i<n; i++)
    {
        // 每次用當(dāng)前的cur_out計(jì)算的下一次的cur_out
        cur_out = help_fun(cur_out);
    }

    return cur_out;
}

string help_fun(string pre_out)
{
    string cur_out = "";
    // 用前一次的pre_out計(jì)數(shù)當(dāng)前的cur_out
    for(int i=0; i<pre_out.size(); )
    {
        char c = pre_out[i]; // 一個(gè)新的數(shù)字字符
        int j = i;
        // 是當(dāng)前數(shù)字字符就讓j++
        while(j<pre_out.size() && pre_out[j]==c)
        {
            j++;
        }
        // 計(jì)數(shù)當(dāng)前數(shù)字字符
        cur_out += (char)('0' + (j - i)); // 保存數(shù)字字符個(gè)數(shù)
        cur_out += c; // 保存數(shù)字字符
        i = j; // 更新下標(biāo)
    }

    return cur_out;
}

int main()
{
    int n;
    while(1)
    {
        cout<<"輸入：";
        cin>>n;
        cout<<"輸出："<<countAndSay(n)<<endl;
    }
    return 0;
}

運(yùn)行結(jié)果

以上。