蓝桥杯练习--递归篇（一）：FJ的字符串--数列AN

题目：

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

A1 = “A”

A2 = “ABA”

A3 = “ABACABA”

A4 = “ABACABADABACABA”

… …

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

输入

仅有一个数：N ≤ 26。

输出

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

样例输入

3

样例输出

ABACABA

解题思路：

我们来从A4开始看，可以看到最中间是字母“D”，以“D”为界限分开，左右两边的字母都相同，并且恰好是A3。那么这种第n个结果依赖于第n-1个结果的题目，自然而然就能想到要用递归。

递归需要有程序停止的条件，可以想见是当n=1时，输出A1（即输出字母“A”）。

那么我们来写一个打印AN数列的方法：

static void printAN(int n){
        if (n==1)
            System.out.print('A');
        else{
            printAN(n-1);
            System.out.print((char)('A'+n-1));
            printAN(n-1);
        }
    }
           

可以看到这个代码非常简单，需要输入一个参数n。当n=1时，那么就输出一个‘A’，也是递归结束的条件。当n>1时，我们就通过递归的方法打印出来。

例如n=4时，如上面的思路所说，我们需要先打印一个A3，再打印字母“D”，再打印一个A3。即打印任意一个数列，都是先打印一次上一个项，再打印一个字母，最后再打印一次上一个项。

else{
            printAN(n-1);
            System.out.print((char)('A'+n-1));
            printAN(n-1);
        }
           

我们调用这个函数，传入n-1作为参数，以达到打印上一个项的目的。

至于中间这个字母，很明显跟输入的参数n有关，那么就可以用ASCAII码表，以“A”为起点，去输出A之后的字母，注意要-1。

完整代码如下（经检测符合C语言网蓝桥杯练习系统的要求）：

import java.util.Scanner;

public class Main{

    static void printAN(int n){
        if (n==1)
            System.out.print('A');
        else{
            printAN(n-1);
            System.out.print((char)('A'+n-1));
            printAN(n-1);
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        printAN(sc.nextInt());
        sc.close();
    }
}
           

继续加油