蓝桥杯试题——FJ的字符串

title: 蓝桥杯试题——FJ的字符串
date: 2019年2月17日20:33:05
tags:

蓝桥杯试题
算法
categories: 蓝桥杯试题
mathjax: true

FJ的字符串

问题描述

FJ在沙盘上写了这样一些字符串：

A1 = “A”

A2 = “ABA”

A3 = “ABACABA”

A4 = “ABACABADABACABA”

… …

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

输入格式

仅有一个数：N ≤ 26。

输出格式

请输出相应的字符串AN，以一个换行符结束。输出中不得含有多余的空格或换行、回车符。

样例输入

样例输出

ABACABA

思路

解法1 使用匹配所有下标的形式，找出所有相同字母下标的出现规律，仔细观察:

$A -> 2n_1 - 2 = 2^1 - (2^0 *n_1+ 1)$

$B -> 4n_2 - 3 = 2^2 - (2^1 *n_2 + 1)$

$C -> 8n_3- 5 = 2^3 - (2^2 *n_3+ 1)$

$D -> 16n_4 - 9 = 2^4 - (2^3 *n_4+ 1)$

又因为：

$n_1 = 8 = 2^3$

$n_2 = 4 = 2^2$

$n_3 = 2 = 2^1$

$n_4 = 1 = 2^0$

所以我们只需要外层循环控制ABCD的个数，里层循环控制n的个数，就很容易得出代码。

注意点：这里使用指针字符来作为存储字符的方式，能够满足题目要求的字母个数小于26，如果要使用字符数组的话，作为局部变量可以实现数组的动态分配，但是n大于20时会导致数组内存溢出，因为局部变量的内存限制为2M，或者把字符数组当做全局变量来处理，只要初始化分配足够大的也可以处理。

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

int main(){
    long i,j;
    int n;
    scanf("%d",&n);
    char *a;
    a = (char*)malloc(sizeof(char)*(int)(pow(2,n))-1);
    for(i=0;i<n;i++){
        for(j=0;j<(int)(pow(2,i));j++){
            a[(int)(pow(2,n-i)) * (j+1)- (int)(pow(2,n-i-1)) - 1] = 'A' + n -i - 1;
        }
    } 
    
    for(i=0;i<(int)(pow(2,n))-1;i++){
        printf("%c",a[i]);
    }
    return 0;
}

思路

利用递归的方式

#include<stdio.h>
void fun(int i) {
    if (i==0) printf("");
    else {
        fun(i-1);
        printf("%c",'A'+i-1);
        fun(i-1);
    }
}

int main() {
    int n;
    scanf("%d",&n);
    fun(n);
    return 0;
}

image.png