描述
  YCC XHB ZXY在长期的革命生活中建立了深厚的友谊，于是ZXY找来一个金属条，打算刻下一段字符，长度为n，来纪念这一段激情燃烧的岁月。
  这段字符只会包含三种字符：分别是三个人姓名拼音的首字母：X Y Z，但是ZXY觉得XX会让人有邪恶的联想，所以禁止有连续的X出现的出现。
现在ZXY想知道一共有几种不同的刻法，你能帮助他吗？
输入
第一行为数字T;
在接下来的T行中，每行都有一个整形数字n，代表字符串的长度。 (0 < n < 21)
输出
对于每个n，输出长度为n的字符串共有多少种符合情况的组合方式
样例输入
2
1
3
样例输出
3
22


这个思路是怎样的？求高手给个思路，或者干脆代码吧。。。我WA了好几次了。。。

#include <stdio.h>
int main()
{
    int Total , n , i ;
    __int64 f[21] = { 0, 3, 8, 0 } ;
    for( i = 3 ; i < 21 ; ++i )
        f[i] = 2 * ( f[i-1] + f[i-2] ) ;
    scanf("%d", &Total ) ;
    while( Total-- )
    {
        scanf("%d", &n ) ;
        printf("%I64d\n", f[n] ) ;
    }
    return 0 ;
}

LS正解

啊啊啊啊 为什么这个递归关系我怎么都发现不了。。。。。。。好打击啊。。。。。数学得好好补不了。。。。

f(i)=2*(f(i-1)+f(i-2))  能不能告诉下我这个函数关系怎么得来的？？？

还有，__int64 f[21] = { 0, 3, 8, 0 } ;后面那个f(3)赋值成0是什么意思啊？__int64 f[21] = { 0, 3, 8 } ;这样貌似也可以啊。。。。。。。。

这就是斐波那契数列的变种吧。
根据这题，怎么找出来的这关系呢？数学归纳法？？

用f[i]表示以i长的字符串有多少种可能，如果结尾为Y或者Z，则各有f[i-1]种可能，即2*f[i-1];
如果结尾为X，则第i-1位只能为Y或者Z，各有有f[i-2]种可能

所以递推式就是f[i]=2*(f[i-1]+f[i-2])

什么意思？没看懂

你可以一步步递推的。比如说i=1时，有f(1)=3种可能：x y z
f(2):①：_x （2种可能）------------------------以x结尾
     ②：_y(f(1)种可能)------------------------以y结尾
     ③：_z(f(1)种可能）-----------------------以z结尾
注意是i>=3时才有（f(i)=2*f(i-1)+2*f(i-2)),和斐波那契数列类似，这只是介绍这种递推方法。f(0)、f(1)、f(2)是要赋初值的！
f(3):_ _ x(由于x前面不能是x,所以前两个字符形式是②、③，为2*f(1))
     _ _ y(这种情况的可能值就是f(2),这个好理解吧）
     _ _ z(同上）
则f(3)=2*(f(1)+f(2));
f(4)：
...
f(5):
...
下面的你应该会自己推了。


你应该问问czz5242199  laoyang103  beyondyf，他们都是高手啊！我在论坛上发的好多求助帖都有过他们的帮助！对我这样一个菜鸟能保持耐心，当真是谢谢了！而且看得出他们对编程的热爱，绝对是良师益友！

[ 本帖最后由 cb_1212 于 2011-11-21 21:48 编辑 ]