魔方吧·中文魔方俱乐部

 找回密码
 注册
搜索
热搜: 魔方
楼主: superacid

方格覆盖问题 [复制链接]

Rank: 4

积分
1206
帖子
1153
精华
0
UID
82168
性别
保密
居住地
其他
兴趣爱好
破解
理论
其它

八年元老

发表于 2011-5-31 19:36:35 |显示全部楼层

回复 8# 的帖子

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

很简单的.比打一堆字简单多了.
不知不觉这个号就申了四年多了吖..关键是还有密码登..
赶脚还有另一个号..也不造是哪个新点..

一眨眼都八年多了....

使用道具 举报

Rank: 2

积分
268
帖子
216
精华
0
UID
1300759
性别
保密
发表于 2011-5-31 19:47:04 |显示全部楼层
数学表示看不懂啊

使用道具 举报

红魔

All Blue

Rank: 4

积分
1196
帖子
999
精华
2
UID
38845
性别
发表于 2011-5-31 20:06:32 |显示全部楼层
我记得m=2的好像是fibonacci数列
本来打算编程做一些表格出来可是想了一整天没什么好思路
公式D F2 U L2 U B2 U R2 U R' F2 R L U L' R' U R L' U L U L U2 L' U' L U2 L'
数列11121131221231321332223233311

使用道具 举报

Rank: 4

积分
1194
帖子
924
精华
6
UID
44804
性别
保密
发表于 2011-5-31 20:19:32 |显示全部楼层
13楼的想法是正确的,证明很简单。用f(n,m)表示n*m的总覆盖方法总数。
从以下递推公式就马上能看出f(2,m)是fibonacci数列。
f(2,m)=f(2,m-1)+f(2,m-2)

使用道具 举报

红魔

All Blue

Rank: 4

积分
1196
帖子
999
精华
2
UID
38845
性别
发表于 2011-5-31 20:26:40 |显示全部楼层
又是fibonacci...跟那个'木木木木木'帖子一样
假设加两块到右边,两种情况:
这两块连在一起;
这两块各自跟左边的连一起。于是
f(2,m)=f(2,m-1)+f(2,m-2)
公式D F2 U L2 U B2 U R2 U R' F2 R L U L' R' U R L' U L U L U2 L' U' L U2 L'
数列11121131221231321332223233311

使用道具 举报

Rank: 4

积分
1194
帖子
924
精华
6
UID
44804
性别
保密
发表于 2011-5-31 20:28:05 |显示全部楼层
f(n,m)为奇数,那么就要求覆盖图形为左右对称且上下对称的覆盖方法数为奇数。
不满足有两个对称轴的覆盖方法都可以用映射的方法得到另一种覆盖方法。

使用道具 举报

Rank: 4

积分
1206
帖子
1153
精华
0
UID
82168
性别
保密
居住地
其他
兴趣爱好
破解
理论
其它

八年元老

发表于 2011-5-31 20:30:09 |显示全部楼层
所以就像2l所说..到偶数就纠结了....
不知不觉这个号就申了四年多了吖..关键是还有密码登..
赶脚还有另一个号..也不造是哪个新点..

一眨眼都八年多了....

使用道具 举报

Rank: 4

积分
1194
帖子
924
精华
6
UID
44804
性别
保密
发表于 2011-5-31 21:01:20 |显示全部楼层
n、m中至少有一个偶数,不妨设n为偶数。
若要求f(n,m)为奇数:
根据两个对称轴的覆盖方法数为奇数,那么n必须是4u+2的形式。


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

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

使用道具 举报

Rank: 4

积分
1206
帖子
1153
精华
0
UID
82168
性别
保密
居住地
其他
兴趣爱好
破解
理论
其它

八年元老

发表于 2011-5-31 21:55:42 |显示全部楼层

回复 18# 的帖子

还没看出来..
5*8ms是奇数?是我看错了么?
不知不觉这个号就申了四年多了吖..关键是还有密码登..
赶脚还有另一个号..也不造是哪个新点..

一眨眼都八年多了....

使用道具 举报

Rank: 4

积分
1194
帖子
924
精华
6
UID
44804
性别
保密
发表于 2011-5-31 22:06:22 |显示全部楼层
从我的叙述中,应该是f(8,5)必为偶数。
--------------------------------------------
即:
f(4u,2v+1)必为偶数,而f(4u+2,2v+1)才有可能是奇数。

使用道具 举报

您需要登录后才可以回帖 登录 | 注册

Archiver|手机版|魔方吧·中文魔方俱乐部

GMT+8, 2020-12-5 22:17

Powered by Discuz! X2

© 2001-2011 Comsenz Inc.

回顶部