C语言小程序之ABA字符串

C语言小程序之ABA字符串

题目

FJ在沙盘上写了这样一些字符串：
　　A1 = "A"
　　A2 = "ABA"
　　A3 = "ABACABA"
　　A4 = "ABACABADABACABA"
　　… …

你能找出其中的规律并写所有的数列AN吗？

---

分析

n的值
1 字母1个
2 字母2个
3 字母3个
4 字母4个

新的字符串
旧的字符串+新字母+串符字的旧

字符串长度
l(n) = 2*l(n-1)+1

---

代码

#include <stdio.h>
#include <stdlib.h>

char *getString(int n)
{
    // 初始化旧字符串
    int oldLength = 1;  
    char *oldStr = malloc(sizeof(char)*oldLength+1);
    oldStr[0] = 'A';
    oldStr[1] = '\0';
    
    // n为1直接返回
    if(n<=1)
        return oldStr;
    else
    {
        // 定义新的字符串
        char *newStr;
        int newLength;
        
        for(int i=1; i<n; i++)
        {
            // 申请内存
            newLength = 2*oldLength+1;
            newStr = malloc(sizeof(char)*newLength+1);
            
            // 循环赋值
            for(int j=0; j<oldLength; j++)
            {
                newStr[j] = oldStr[j];
                newStr[newLength-j-1] = oldStr[j];
            }
            
            // 新字母并结尾
            newStr[oldLength] = 'A'+i;
            newStr[newLength] = '\0';
            
            // 释放旧内存
            free(oldStr);
            
            // 指向新内存
            oldStr = newStr;
            oldLength = newLength;
            
            // 指向NULL
            newStr = NULL;
        }
        // 返回字符串
        return oldStr;
    }
}

int main()
{
    int length = 1;
    scanf("%d", &length);
    
    char *str = getString(length);
    printf("%s\n", str);
    free(str);
    
    return 0;
}

---

原题地址：
http://www.hgacm.com/problem/2/

---

C语言小程序之ABA字符串