CSDN上的两个问题

liangbch

10# litaoye

      9# 的回复有道理。我刚刚想到这个，对于每个图形（通过旋转的得到的各个图形视为同一个图形。）可用width, height, 和2进制串来唯一标识。其中规定width>=height. 对于如果height>width,可将其旋转90度。对于width!= height, 最多有2种变体，对于width== height的图形，最多有4种变体。 每个变体可表示为1个2进制串，2进制串字段存储这些这些变体对应的2进制串的最小值。
   到现在，我感卷我的思路已经很清晰了，所有的关节都打通了。剩下的只是编程问题了。

litaoye

太好了，int32做Hash应该可以把前9项都求出来，到时候再到
http://www.research.att.com/ 去搜一下，可能能找到一些更直接的数学方法

10# litaoye

      9# 的回复有道理。我刚刚想到这个，对于每个图形（通过旋转的得到的各个图形视为同一个图形。）可用width, height, 和2进制串来唯一标识。其中规定width>=height. 对于如果height>width,可将 ...
liangbch 发表于 2009-11-13 10:39

liangbch

我觉得还是csdn 92楼的复杂度低一些。因为，在n个方块构成的图案的基础上，增加一个方块以得到n+1个方块的图案时，有太多的构造方法。例如
  若n=13, 则包络矩形的面积最大可至7 *7 ，若在此基础上构造14个方块的图案，需要在 9*9的画布上的每一个方格进行尝试。
  而csdn 92楼的，在n个方块构成的图案的基础上，增加一个方块以得到n+1个方块的图案时，只有3种方法(n=1时是4种方法)。 此法的缺点是
   1. 在构造n+1个方块的图案时，需要保留n个方块的所有图案，即使这些图案中有大量是同构的（包括方位相同图案全等，和方位不等图案全等2种情况）也不能删除。
   2. 有些合法的图案构造不出来，参见15楼。

litaoye

92楼的构造方法稍微有些问题，这样的图案似乎构造不出来，
■ ■ ■ ■
　■

另外也不是每步有3个选择，其实只有2个，并且如果只按照这两个方向走下去的话，
有更直接的计算方法。

1 1 1 1 1
1 2 3 4 5
1 3 6 10 15
1 4 10 20 35
1 5 15 35 70

基本上就是2^(n-1)减去同构的，同构的个数也是可以计算的。

我觉得还是csdn 92楼的复杂度低一些。因为，在n个方块构成的图案的基础上，增加一个方块以
得到n+1个方块的图案时，有太多的构造方法。例如
  若n=13, 则包络矩形的面积最大可至7 *7 ，若在此基础上构造14个方块的图 ...
liangbch 发表于 2009-11-13 12:11

liangbch

13# liangbch
     下图是4个方块组成的合法的图案，可按照csdn92楼的方法构造不出来。

mathe

csdn中92#的方法显然不行。
用n个方格的方案构造n+1个方案的方案是比较可行的。而且设计的好，可以不需要保存n个方格的方案，而且可以不重复产生。

northwolves

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

n=5时找到18种方案,n=6时60种方案,查了一下是这个序列:
http://www.research.att.com/~njas/sequences/A000988

northwolves

csdn中92#的方法显然不行。
用n个方格的方案构造n+1个方案的方案是比较可行的。而且设计的好，可以不需要保存n个方格的方案，而且可以不重复产生。
mathe 发表于 2009-11-13 13:27

这个感觉可行,只是还会重复

litaoye

看来我手工数的有问题，还是狼兄弟的这个答案比较靠谱，也发到CSDN上一份吧！

n=5时找到18种方案,n=6时60种方案,查了一下是这个序列:
http://www.research.att.com/~njas/sequences/A000988
northwolves 发表于 2009-11-14 14:25

litaoye

已经提前在CSDN上给northwolves 同志做个广告，呵呵。

第一题大家有什么更巧的方法么？