CSDN上的两个问题

litaoye

问题1

一些物件放置到B1,B2,...,Bn共n个盒子里。取出后放置在C1,C2,...,Cn+1共n+1个盒子里。没有1个盒子是空的。这意味着至少有n+1个物件。证明至少有2个物件，它们所在的盒子中的物件数比它们之前所在的盒子中的物件数少。

http://topic.csdn.net/u/20091101 ... 1-d718844ecb85.html

已经有人给出了一个解答，但总觉得应该有更巧妙的方法，大家帮忙想想？

问题2

总所周知
俄罗斯方块是通过4个正方形组成7个不同的图形来进行的游戏

那么依据同样的生成图形的规则
5个正方形可以生成多少个图形
6个呢？
7
...
n个呢
能够推出来
以及通过编程实现
在编程方面
因为考虑到图形的旋转
感觉比较有难度

http://topic.csdn.net/u/20091025 ... 7-870db3c5fabe.html

目前好像还没有太好的答案！本来以为这题会比较简单，自己画了画，才发现很难，不知道有没有什么好的方法！

〇〇

中心对称算1个 轴对称算2个

litaoye

中心对称算1个 轴对称算2个
〇〇 发表于 2009-11-12 15:59

恩，是这个意思。

litaoye

根据前几个数，去http://www.research.att.com/ 找到了2个序列，不知道是不是俄罗斯方块的解
1, 1, 2, 7, 20, 58, 174, 519, 1550
0, 1, 2, 7, 20, 61, 182, 547, 1640

liangbch

关于第二个问题。csdn 的92楼有道理。但仍可以优化。
我的几点想法。
  1. 准备一个N*N的画布，0：表示空白，非零表示方块的序号。
  2.由于在一个大画布，移动相连的方块，得到新的相连方块的图案和原始图案是同构的，所以，第1步可考虑放在画布的左上角，而不是N*N种方法。
  2. 如果需要放新的方块，而新的方块不得不放在画布的外面，这时，可以将相连的方块在画布中平移。
  3. 采用广度优先搜索法。如果得到i个方块的所有组合。检查所有这些组合，哪些是同构的，并删除同构的图案，继续构造出 i+1 的组合，采用适当的剪枝算法，可是复杂度降低。
  4. 检查同构可能比较麻烦，需要设计一个适当的算法。

shshsh_0510

第一题看着挺简单
第二题看着挺不简单
csdn 的92楼大大低估了复杂度，因为新加入的不一定只与前一个相连。而且，枚举还好说，这个问题难就难在如何判别同构。
需要分类判别，较容易的一个是“外包矩形”，即能将所有块包围的最小矩形。
至于同一最小矩形内，有多少在旋转下不同构的构型，一时想不好。

liangbch

关于同构判别法的一点思考。
  1. 首先求出图案的“外包矩形”。将外包矩形形状相同者分入一组。 例如，矩形2*3 与3*2 视为相同，而1*4 和 2*2 是不同的矩形。
  2. 对于同组中的每一个矩形，可定义一个唯一的key,每一个图形的key是这么定义的。
  用1来表示图形中的黑块，用0来表示图形中的白块。对于下图的例子。这2个图形都是包含4个方块的图形。第一个是2行3列，可用2进制串表示为 111 010。 第一个3行2列的图像，可用2进制串表示为 01 11 01 。因为每个方块通过旋转（0，90，180，270度）可得到4个图形，相应的对应4个2进制串。取其4者较小的那个2进制串作为key。

liangbch

依据上面的做法，对于生成的每个图形，将其旋转后得到4个图形，将对应的2进制串最小的那个图形作为标准格式。在生成更多的方块的图形时，以标准图形为基准，在其周围放置一个新的方块，使其某边与现有的方面相邻，则构成一个新的方块。

   不知道这种构造key的方法有没有问题，那位找出一个反例，即图形不同，但得到的key相同。
   如果这种方式不行，对于每个图形，将其旋转得到的4个图形中，分别求出对应的2进制串，，然后将这4个2进制串排序后连接起来，得到一个更大的2进制串，来作为这个图形的key.

mathe

同构判断很简单。对于每个图案，最多有4个旋转后可能同构的图（也可能两个，也可能没有）。只要对每个图分别计算有多少个同构的图就可以了。7#的编码方法可以采用，不过还需要标明矩形的宽和高。那么对每个图，根据方向不同，最多可以有4个编码，我们统一采用数值最小的编码，比如7#的例子，就采用01/11/01而不是111/010.(而如果存在两个编码数值相等，举行宽和高不等，不如111/111和11/11/11，那么采用更宽的方案，既111/111).如此，每个方案的编码就唯一了。
搜索的方法可以有很多种，其中一种方法可以对n-1个方块的每个图案，依次在各个不同位置添加一个方块，计算每个结果的编码，淘汰重复的就可以了

litaoye

第2题搜索的话，确实可以解一些小规模的，但总觉得应该有个可以递推的方法，
大概可以得出个结论，f(n) >= f(n-1) * 2 (n>1)