有一点需要补充的就是，任何递推题，都会有临界条件。当N=1时，f(n)=3;,当N=2时，f(n)=7,这些都可以看成是临界条件。只有当N& gt;=3时，即上上步存在的情况下，就可以得出f(n)的一般通式：f(n)=2*f(n-1)+f(n-2) （本题还有其他的解法，同学们可以继续挖掘！） 【参考程序】
#include
int n; int i;
int fn_1,fn_2;
printf(\
scanf(\输入任意n值 int fn=0; if(n==1)
fn=3; //初始化当n=1和n=2时的临界条件 else if(n==2) fn=7; else{ fn_1=7; fn_2=3;
for(i=3;i<=n;i++) {
fn=2*fn_1+fn_2; //当n>=3时fn的通式 fn_2=fn_1;//更新fn_1和fn_2的值 fn_1=fn; } }
printf(\一共有%d种走法！\\n\//输出结果 return 0; }
阿牛的EOF牛肉串
Problem Description
今年的ACM暑期集训队一共有18人，分为6支队伍。其中有一个叫做EOF的队伍，由04级的阿 牛、XC以及05级的COY组成。在共同的集训生活中，大家建立了深厚的友谊，阿牛准备做点什么来纪念这段激情燃烧的岁月，想了一想，阿牛从家里拿来了一 块上等的牛肉干，准备在上面刻下一个长度为n的只由\\三种字符组成的字符串（可以只有其中一种或两种字符，但绝对不能有
其他字符）,阿牛同时禁止在串中出现O相邻的情况，他认为，\看起来就像发 怒的眼睛，效果不好。
你，NEW ACMer,EOF的崇拜者，能帮阿牛算一下一共有多少种满足要求的不同的字符串吗？
PS: 阿牛还有一个小秘密，就是准备把这个刻有 EOF的牛肉干，作为神秘礼物献给杭电五十周年校庆，可以想象，当校长接过这块牛肉干的时候该有多高兴！这里，请允许我代表杭电的ACMer向阿牛表示感谢！
再次感谢！
Input
输入数据包含多个测试实例,每个测试实例占一行,由一个整数n组成，(0 Output 对于每个测试实例，请输出全部的满足要求的涂法，每个实例的输出占一行。 Sample Input 1 2 Sample Output 3 8 设n位字符串，最后一位是O的字符串的个数为a[n],最后一位不是O的字符串的个数是b[n], 总字符串个数为x[n]， 则有 x[n]=a[n]+b[n]; a[n]=b[n-1]; b[n]=2*x[n-1]; ====>x[n]=2*x[n-1]+2*x[n-2] #include __int64 x[40] = {0, 3, 8}; int main(){ int n; for(n = 3; n != 40; ++n) x[n] = 2 * (x[n-1] + x[n-2]); while(scanf(\ printf(\ return 0; } 不容易系列之(4)——考新郎 Problem Description 国庆期间,省城HZ刚刚举行了一场盛大的集体婚礼,为了使婚礼进行的丰富一些,司仪临时想出了有一个有意思的节目,叫做\考新郎\具体的操作是这样的: 首先,给每位新娘打扮得几乎一模一样,并盖上大大的红盖头随机坐成一排; 然后,让各位新郎寻找自己的新娘.每人只准找一个,并且不允许多人找一个. 最后,揭开盖头,如果找错了对象就要当众跪搓衣板... 看来做新郎也不是容易的事情... 假设一共有N对新婚夫妇,其中有M个新郎找错了新娘,求发生这种情况一共有多少种可能. Input 输入数据的第一行是一个整数C,表示测试实例的个数，然后是C行数据，每行包含两个整数N和M(1 Output 对于每个测试实例，请输出一共有多少种发生这种情况的可能，每个实例的输出占一行。 Sample Input 2 2 2 3 2 Sample Output 1 3 错排 + 组合数 错排公式：a[i]=(i-1)*(a[i-1]+a[i-2]); 然后乘以从m个中挑出t个的排列组合 #include int a,n,m,i; __int64 p; __int64 q; __int64 cuopai[22]={0,0,1,2}; for(i=4;i<22;i++) { cuopai[i]=(i-1)*(cuopai[i-1]+cuopai[i-2]); } scanf(\ while(a--) { scanf(\ p=1;q=1;
