我也发个“铺瓷砖”的题（9.12更新）

Cielo

<P>（呵呵这个是非原创的题，肯定没有金眼睛的题那么难）</P>
<P>&nbsp;</P>
<P>长宽都是23米的房间，用1x1，2x2，3x3（单位都是米）的瓷砖铺满地板，问至少需要多少块1x1的小瓷砖？</P>
<P>&nbsp;</P>
<P>--------------------------------------------------------------------------------------------------------------------------------------</P>
<P>&nbsp;</P>
<P>很快大家就构造出只用一块1x1小瓷砖的拼法了，但能否一块都不用呢？</P>
<P>下面给几个类似的问题，也可以算作一种提示吧</P>
<P>&nbsp;</P>
<P>1、8x8 的地板能否用1块2x2和15块1x4的瓷砖铺满？</P>
<P>&nbsp;</P>
<P>2、8x8 的地板能否用1块2x2和15块T字形瓷砖铺满？（T字形如图□□□）</P>
<P>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; □</P>
<P>3、8x8的地板挖掉左上角1x1的小方块后，能否用21块1x3的瓷砖铺满？</P>
<P>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;如果不能，那挖去的1x1小方块在什么位置时，能保证剩下的部分能用21块1x3的瓷砖铺满？</P>

[ 本帖最后由 Cielo 于 2008-9-12 19:37 编辑 ]

龚永明魔方

两题有解：

alinit

属于超难题，等待解决...

小小手

这图看的真明白。高手。

penguiji

[localimg=334,300]1[/localimg]

penguiji

最少一块1*1

penguiji

最少一块1*1

金眼睛

哈哈，强，怎么忘了染色原理了呢， <BR><BR>脑子都想着编程序的事情了，哈哈，这道题编一个高效的求解程序也很有趣，思路很重要，呵呵！<BR><BR>对了，忘了说了，23*23的我也用程序验证过了，确实必须用1*1，不过还是LZ的解释巧妙啊！

Cielo

原帖由 <i>金眼睛</i> 于 2008-9-15 11:42 发表 <a href="http://bbs.mf8-china.com/redirect.php?goto=findpost&amp;pid=239687&amp;ptid=13624" target="_blank"><img src="http://bbs.mf8-china.com/images/common/back.gif" alt="" border="0"></a>
Cielo，看到了你的更新，来捧个场，呵呵！
&nbsp;
不过有个问题，更新的几种情况你都验证过么？
&nbsp;
□&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 我的思路：如左图所 ...

<br><br>呵呵你的答案全对！不过有更巧妙的方法哦<img smilieid="17" src="http://bbs.mf8-china.com/images/smilies/default/handshake.gif" border="0"><br>----------------------------------------------------------------<br>我来说说我解原题的方法吧：<br>构造只用一块1x1的拼法很简单，利用风车形：即4个11x12的部分围绕中间1x1的即可。而11x12很容易用2x2、3x3铺满。下面证明一块是最少的：<br><br>将地板看做23x23的方格阵，我们把第1行染黑色，第2行染白色……依次交替染色。这样黑格比白格多23个。<br><br>而无论2x2的瓷砖放在什么位置，只能盖住两黑两白；无论3x3的瓷砖放在什么位置，它盖住的黑、白两色格的个数相差3个。<br><br>由于23不能被3整除，所以无法不用1x1的！<br>

金眼睛

<P>Cielo，看到了你的更新，来捧个场，呵呵！</P>
<P>&nbsp;</P>
<P>不过有个问题，更新的几种情况你都验证过么？</P>
<P>&nbsp;</P>
<P>□&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <STRONG>我的思路：</STRONG>如左图所示，由于对称性，特殊块的左上角只要遍历8*8格子左上角的这十个位置，就可以认为代</P>
<P>□□&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 表了所有的情况。</P>
<P>□□■&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <STRONG>计算方法：</STRONG>编程计算，不过暴力破解的计算量太大，我采用了先输入少量初始条件，然后进行试探的方法。</P>
<P>□□□□&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 每种情况的每个位置，运行时间大约为一秒钟。</P>
<P>&nbsp;</P>
<P>通过计算发现，情况1，2均无解，情况3只有那个1*1的小块在如图黑块所在的位置时才有解。</P>
<P>&nbsp;</P>
<P>由于初始条件输入可能有差错，程序也可能有小错误，所以想问LZ是否验证过这些情况，如果1，2，3的其他位置有解，希望提供一个例子，因为有了例子，就可以很快发现程序的错误，<IMG alt="" src="http://bbs.mf8-china.com/images/smilies/default/handshake.gif" border=0 smilieid="17"> </P>