wustoj

Description

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

A1 = “A” A2 = “ABA” A3 = “ABACABA” A4 = “ABACABADABACABA” … … 你能找出其中的规律并写所有的数列AN吗？

Input

多组测试数据，每组仅有一个数：N ≤ 26。

Output

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

Sample Input 

3

Sample Output

ABACABA

分析:根据A1 A2 A3等分析可以找到规律,首先字符串长度是2^n,字符串中心的字符为n+'A',中心两边是对称的,两个又可以看成中间是n-1+'A'其两边也为对称的字符串,这么一看就是二分了,一个超级简单的二分算法==

参考代码:

#include<cstdio> #include<cmath> #include<cstring> #include<algorithm> #include<iostream> using namespace std; int n; void binary_char( int l, int r, int ch) { if( ch == 0) return; int mid = (l+r)/2; binary_char(l,mid-1,ch-1); //printf("%c",ch-1+'A'); printf("%c",ch-1+'A'); binary_char(mid+1,r,ch-1); //printf("%c",ch-1+'A'); } int main() { while( ~scanf("%d",&n)) { binary_char( 1,1<<n,n); putchar(10); } return 0; }