title: 藍(lán)橋杯試題——FJ的字符串
date: 2019年2月17日20:33:05
tags:
- 藍(lán)橋杯試題
- 算法
categories: 藍(lán)橋杯試題
mathjax: true
FJ的字符串
問(wèn)題描述
FJ在沙盤(pán)上寫(xiě)了這樣一些字符串：
A1 = “A”
A2 = “ABA”
A3 = “ABACABA”
A4 = “ABACABADABACABA”
… …
你能找出其中的規(guī)律并寫(xiě)所有的數(shù)列AN嗎咱枉？
輸入格式
僅有一個(gè)數(shù)：N ≤ 26固蛾。
輸出格式
請(qǐng)輸出相應(yīng)的字符串AN川背，以一個(gè)換行符結(jié)束叨恨。輸出中不得含有多余的空格或換行旷余、回車符。
樣例輸入
3
樣例輸出
ABACABA
思路
解法1 使用匹配所有下標(biāo)的形式站玄，找出所有相同字母下標(biāo)的出現(xiàn)規(guī)律朗徊，仔細(xì)觀察:
又因?yàn)椋?/strong>
所以我們只需要外層循環(huán)控制ABCD的個(gè)數(shù)，里層循環(huán)控制n的個(gè)數(shù)娜庇，就很容易得出代碼拇泛。
注意點(diǎn)：這里使用指針字符來(lái)作為存儲(chǔ)字符的方式滨巴，能夠滿足題目要求的字母?jìng)€(gè)數(shù)小于26，如果要使用字符數(shù)組的話俺叭，作為局部變量可以實(shí)現(xiàn)數(shù)組的動(dòng)態(tài)分配恭取，但是n大于20時(shí)會(huì)導(dǎo)致數(shù)組內(nèi)存溢出，因?yàn)榫植孔兞康膬?nèi)存限制為2M熄守，或者把字符數(shù)組當(dāng)做全局變量來(lái)處理蜈垮，只要初始化分配足夠大的也可以處理。
#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
