产生无连续重复部分的字符串。（60分）
（1）描述：编写程序，产生由1，2，3这3个数字符号所构成、长度为n的字符串，并且在字符串中对于任何一个子串而言，都不会有相邻的、完全相同的子串；
（2）输入：字符串长度n；
（3）输出：无相邻重复子串的所有字符串，每个字符串换行输出。
各位大侠。。。可不可以讲一下。。。怎么求出一个字符串，，字符串中对于任何一个子串而言，都不会有相邻的、完全相同的子串。。。是怎么求啊。。。

帮顶

比如
"12313123"截取子串"31"有两个，而且相邻，所以不符合要求
"12313213"虽然也有相同的两个"13"，但他们不相邻，所以符合要求

[ 本帖最后由 azzbcc 于 2012-12-8 02:08 编辑 ]

可否具体点

有趣，不难。但是分太少。

这题dfs可以，但感觉应该有数学方法吧？

呵呵，我的兴趣也在于寻找这种串的数量与其长度的函数关系

至于输出倒确实不是什么难事，我倾向于回溯法穷举。

估计要被删帖了。做作业呃

我倒不会删有意思的作业题。

关于这个问题，通过观察实际结果我总结出串长n与数量f(n)的一个有趣的递推式

f(1) = 3
f(n) = f(n - 1) + f([(n + 1) / 2])

很漂亮的式子，但目前还不理解其意义，也没有证明。

我想要用到树