方格覆盖问题

tm__xk

这样吧，我用穷举法用不了几秒钟，那你也例举出来看看呗，只例2*5就可以了，然后说明覆盖方法有几种，再可能的话，试做出2*(2n+1)覆盖方法通项公式或者递推公式（其中2*3覆盖方法为3种）。

很简单的.比打一堆字简单多了.

葙對。。★

数学表示看不懂啊

骰迷

我记得m=2的好像是fibonacci数列
本来打算编程做一些表格出来可是想了一整天没什么好思路

lulijie

13楼的想法是正确的，证明很简单。用f(n,m)表示n*m的总覆盖方法总数。
从以下递推公式就马上能看出f(2,m)是fibonacci数列。
f(2,m)=f(2,m-1)+f(2,m-2)

骰迷

又是fibonacci...跟那个'木木木木木'帖子一样
假设加两块到右边，两种情况：
这两块连在一起；
这两块各自跟左边的连一起。于是
f(2,m)=f(2,m-1)+f(2,m-2)

lulijie

f(n,m)为奇数，那么就要求覆盖图形为左右对称且上下对称的覆盖方法数为奇数。
不满足有两个对称轴的覆盖方法都可以用映射的方法得到另一种覆盖方法。

tm__xk

所以就像2l所说..到偶数就纠结了....

lulijie

n、m中至少有一个偶数，不妨设n为偶数。
若要求f(n,m)为奇数：
根据两个对称轴的覆盖方法数为奇数，那么n必须是4u+2的形式。


---------------------------------
修正一下，上述是讨论n为偶数，m为奇数的情况。

[ 本帖最后由 lulijie 于 2011-5-31 22:10 编辑 ]

tm__xk

还没看出来..
5*8ms是奇数?是我看错了么?

lulijie

从我的叙述中，应该是f(8,5)必为偶数。
--------------------------------------------
即：
f(4u,2v+1)必为偶数，而f(4u+2,2v+1)才有可能是奇数。