外观数列是一个非常有趣的数列，它的每一项都是对前一项的描述。例如，第一项是"1"，第二项描述第一项，即"一个1"，记作"11"，第三项描述第二项，即"两个1"，记作"21"，以此类推。今天，我们就来深入探讨一下这个数列，并通过C语言来实现它。

外观数列的定义

外观数列是由递归公式定义的数字字符串列:

• countAndSay(1)=“1”
• countAndSay(n)是对countAndSay(n-1)的描述，然后转换成另一个数字字符串。

前五项如下:

1. “1”
2. “11”
3. “21”
4. “1211”
5. “111221”

解题思路

解决这个问题的关键在于理解如何描述一个数字字符串。我们需要将字符串分割为最小数量的组，每个组都由连续的最多相同字符组成。然后对于每个组，先描述字符的数量，然后描述字符，形成一个描述组。要将描述转换为数字字符串，先将每组中的字符数量用数字替换，再将所有描述组连接起来。

程序展示：

以下是在VC6.0环境下运行调试的C语言程序：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char* countAndSay(int n) 
{
    if (n == 1) return "1";
    char* prev = countAndSay(n - 1);
    int len = strlen(prev);
    char* ret = (char*)malloc(2 * len * sizeof(char));
    int i = 0, j = 0;
    while (i < len) 
  {
        int count = 1;
        while (i + 1 < len && prev[i] == prev[i + 1]) 
    {
            i++;
            count++;
        }
        ret[j++] = count + '0';
        ret[j++] = prev[i];
        i++;
    }
    ret[j] = '\0';
    return ret;
}
int main() 
{
    int n = 5;
    char* ret = countAndSay(n);
    printf("%s\n", ret);
    return 0;
}

程序测试：

运行上述代码，在VC6.0的环境下，可以得到如下的输出：

111221

第一项是数字 1

描述前一项，这个数是1即“一个1"，记作"11"描述前一项，这个数是11即“二个1”，记作"2描述前一项，这个数是21即"一个2+一个1'描述前一项，这个数是1211即"一个1+-个要 描述 一个数字字符串，首先要将字符串分割为 最小数量的组，每个组都由连续的最多 相同字符 组成。然后对于每个组，先描述字符的数量，然后描述字符，形成一个描述组。要将描述转换为数字字符串，先将每组中的字符数量用数字替换，再将所有描述组连接起来。

这与题目给出的结果一致，说明我们的算法是正确的

代码获取：

我用夸克网盘分享了「20240119」，点击链接即可保存。打开「夸克APP」，无需下载在线播放视频，畅享原画5倍速，支持电视投屏。

链接：https://pan.quark.cn/s/56fd09c9bbed

下期预告

下期我们将探讨另一个有趣的问题：两数之和 I。给定一个已按照 非递减顺序排列 的整数数组 numbers，请你从数组中找出两个数满足相加之和等于目标数 target。敬请期待！

希望这篇文章对你有所帮助！如果你觉得有用，不妨分享给你的朋友，也欢迎关注我们的微信公众号“工控小新”，我们会持续更新更多的编程教学内容。谢谢你的阅读！

点赞加关注，学习不迷路

微信公众号｜工控小新

EPLAN电气绘图、TIA博图基础 、CAD、C语言教学、单片机基础、三菱PLC ... 每日持续更新中

#来点干货儿#