铺地砖

Time Limit:1000MS  Memory Limit:65536K
Total Submit:711 Accepted:224

Description

元旦过去了，新年大酬宾活动也已经告一段落了。陈盖历望着堆在仓库的瓷砖，很无聊的他把这些瓷砖裁成很多1X1 1X2 1X3的小瓷砖，然后他把这些小瓷砖排在地上画的一个1*n的长方形里。问铺满这个长方形共有多少种方法？

Input

首先输入一个整数T,表示有T组测试数据
然后是T行，每行输入1个正整数n(n<=50)

Output

对于每个n输出铺的方法种数

Sample Input


3
1
2
3

Sample Output
1
2
4
我想的是先穷举面积和等于n的所有情况，再排列组合
可是这个程序运行还行，交上去不知道为什么runtime error，说可能有除以0的情况
我在前面写了两个阶乘函数
#include<stdio.h>//kan xia si da de dai ma!
int F(int n)
{
    int i,p;
    p=1;
    for(i=1;i<=n;i++)
    {
        p*=i;
    }
    return p;
}
int f(int m,int n)
{
    int i,p;
    p=1;
    for(i=n-m+1;i<=n;i++)
    {
        p*=i;
    }
    return p;
}
int main()
{
    int T,i,n,count,j,k,l,m;
    scanf("%d",&T);
    for(i=0;i<T;i++)
    {
        count=0;
        scanf("%d",&n);
        for(j=0;j<=50;j++)
        {
            for(k=0;k<=25;k++)
            {
                for(l=0;l<=16;l++)
                {
                    if(n==j+2*k+3*l)
                    {m=j+k+l;
                     count+=F(m)-(F(j)-1)*(f(j,m)/F(j))-(F(k)-1)*(f(k,m)/F(k))-(F(l)-1)*(f(l,m)/F(l));//所有排列情况减去重复的情形
                    }
                }
               
            }
        }
        printf("%d\n",count);
    }
    return 0;
}

或者大家有更好方法，求教~~！

注意int的范围！

那要怎么改？

对于1*n地面，第一块可以放1X1，也可以放1X2，也可以放1X3
也就是 f(n) = f(n-1) + f(n-2) + f(n-3);
因此你可以写个递归
unsigned foo( unsigned n )
{
    if(n==1u) return 1u;
    if(n==2u) return 2u;
    if(n==3u) return 4u;
    return foo(n-1) + foo(n-2) + foo(n-3);
}

这递归一看就知道效率很差，因此可以反过来做
f(4) = f(1)+f(2)+f(3);
f(5) = f(2)+f(3)+f(4);
f(6) = f(3)+f(4)+f(5);
……
一直到你需要的f(n)

谢谢楼上 明白了