2190 ACM 数学概率论的乘法和加法原则

题目：http://acm.hdu.edu.cn/showproblem.php?pid=2190

思路：明显我们要寻找边长为n和边长为n-1，n-2，n-3·····的规律，这样得出一个递推公式就能方便的得出f（n）（边长为n的值）

由于只有两种类型的地板砖，2*2 1*1，所以最后加入的一行，可能是1*1的砖块，也可能是2*2砖块的一部分，所以 f(n)就和f(n-1)和f(2)有关

接下来推导：

由数学概论论可知：

两种个情况，不同情况之间用加号

同一情况下，的下一步操作的方法数之间用乘法

1 第n行放的是1*1的砖块

所以只需要在f(n-1)的基础上放即可，且1*1砖块的方法只有一种

2 第n行放的是2*2砖块的一部分

所以在f(n-2)的基础上放即可，本来有三种的，但是舍弃1*1的情况，因为和上述情况重复，2*2放左边或右边，两种情况

结论：f(n)=f(n-1)*1+f(n-2)*2

代码：

#include<iostream>

#include<cstdio>

using namespace std;

int main()

{

    int c;

    int sch[];

    sch[]=;

    sch[]=;

    sch[]=;

    for(int i=;i<;i++)

        sch[i]=sch[i-]+sch[i-]*;

    cin>>c;

    while(c--)

    {

        int n;

        cin>>n;

        cout<<sch[n]<<endl;

    }

    return ;

}

巴特西

2190 ACM 数学概率论的乘法和加法原则

最新文章

热门文章