天天看点

【算法】求字母表∑的所有情况

字母表 ∑ 为  {a , b}

1.设计函数,用以计算建立在 ∑上长度小于n 的字符串的个数,并给出n=5时的字符串个数。

2.在上述功能的基础上,增加列出所有符合条件的字符串功能。

输入输出样例:

输入:

1

输出:

a

b

2

aa

ab

ba

bb

3

aaa

aab

aba

abb

baa

bab

bba

bbb

ac代码:

例如输入3:

结果:

分析过程:

先是aaa,无b,不执行while,

遇到if,最后一个+1变成b,

回到顶端输出aab。

之后b被while隔过去

剩aa,遇到if,最后一个+1变成b,此时为ab。

回到顶端发现不够3,加一个a(此时为aba),

continue回到顶端,输出aba。

回到顶端输出abb。

之后bb被while隔过去

剩a,遇到if,最后一个+1变成b,此时为b。

回到顶端发现不够3,加两个a(此时为baa),

continue回到顶端,输出baa。

回到顶端输出bab。

剩ba,遇到if,最后一个+1变成b,此时为bb。

回到顶端发现不够3,加一个a(此时为bba),

continue回到顶端,输出bba。

回到顶端输出bbb。

之后bbb被while隔过去,

剩空串,break出去,算法结束。

即是:一开始是空串,然后遵循一下变化:

1.不够3位,补a。

2.后面有几位b,全去掉,若变成空串退出算法。

3.如果末尾是a,变成b,够3位输出。

二叉树遍历字母表∑的模型:

【算法】求字母表∑的所有情况

以上算法并不一定是最优的,还有其他方法,就不在一一叙述,有兴趣的可以自己去研究。

转载请注明出处:http://blog.csdn.net/acmman