算法分析与设计算法分析与设计解锁智力玩具潜规则的求解21 玩具及游戏规则:玩具配置玩具配置玩具配置玩具配置：6 6根形状各异的木条根形状各异的木条根形状各异的木条根形状各异的木条，一个空的正方体框架空的正方体框架空的正方体框架空的正方体框架。:游游游游戏戏目目目目标标：将这6根形状各异的木条用一定的技巧全部装入全部装入全部装入全部装入空的正方体框架空的正方体框架空的正方体框架空的正方体框架。32 思考：3个问题:6根木条，在外部进行拼装，总共有多少种有多少种有多少种有多少种组组合方法合方法合方法合方法？:在外部拼装，有多少种有多少种有多少种有多少种组组合方法能正确地嵌入合方法能正确地嵌入合方法能正确地嵌入合方法能正确地嵌入？:是不是在外部嵌入好了在外部嵌入好了在外部嵌入好了在外部嵌入好了就一定能装入到正方体框架一定能装入到正方体框架一定能装入到正方体框架一定能装入到正方体框架中呢？43 编程求解：计算在外部拼装，有多少种嵌入方案:6根木条虽然形状各异，但表面可以看成8282大小的网格，每个方格要么凸起凸起凸起凸起，要么凹凹凹凹进进去去去去。:依次给6根木条编编号号号号(其中4号木条很不标准)。5用82的二维数组存储1根木条存储6根木条需要用682的三维数组第1根木条1 10 00 01 00 00 00 00 01 163.1 总共有多少种组合方法:6根木条排列数排列数排列数排列数：6!6! = 720720:在每种排列方案中，每个木条可以不旋不旋不旋不旋转转和旋旋旋旋转转，总共有2 26 6 = 64 = 64种情形。:因此，总共有7206472064种组合方法。7:组组合方法数的理解合方法数的理解合方法数的理解合方法数的理解。以下木条中的方格没有区分凸起区分凸起区分凸起区分凸起和凹和凹和凹和凹进进去去去去。8:存存存存储储旋旋旋旋转转后的木条后的木条后的木条后的木条：用26822682的四维数组存储不旋不旋不旋不旋转转和旋旋旋旋转转后的6根木条。/第1维：2-表示未旋转与旋转/第2维：6-6根木条/第3、4维：8、2-每根木条的大小int blocks2682 = /未旋转1,1,0,0,0,0,1,0,0,0,0,0,0,0,1,1, /11,1,0,0,0,0,1,0,1,0,1,0,1,1,1,1, /21,1,1,1,0,1,0,0,0,0,0,1,1,1,1,1, /31,1,0,1,0,0,0,1,0,1,1,1,1,1,1,1, /41,1,1,1,0,0,0,0,1,0,0,0,1,0,1,1, /51,1,1,0,0,0,0,0,1,0,0,0,1,0,1,1/6,/旋转1,1,0,0,0,0,0,0,0,1,0,0,0,0,1,1, /11,1,1,1,0,1,0,1,0,1,0,0,0,0,1,1, /21,1,1,1,1,0,0,0,0,0,1,0,1,1,1,1, /31,1,1,1,1,1,1,0,1,0,0,0,1,0,1,1, /41,1,0,1,0,0,0,1,0,0,0,0,1,1,1,1, /51,1,0,1,0,0,0,1,0,0,0,0,0,1,1,1/6;93.2 总共有多少正确的嵌入方法:两个正确嵌入正确嵌入正确嵌入正确嵌入的例子：11表示表示表示表示1 1号木条要旋号木条要旋号木条要旋号木条要旋转转。注意4、5、6已经反扣过来了。10旋转与反扣:除了旋旋旋旋转转外，反扣反扣反扣反扣的处理也很重要，o o、p p、q q这这一一一一组组木条木条木条木条需要反扣需要反扣需要反扣需要反扣过过来嵌入到来嵌入到来嵌入到来嵌入到i i、j j、k k这这一一一一组组中中中中。11旋转与反扣(continue)12判断每种组合是否能正确地嵌入注意反扣过来后对应方格的各自坐标。13旋转的处理（思想很重要）:i、j、k、o、p、q不旋转与旋转共26 = 64种组合，实际上就是6位二进制000000111111000000111111。:方法方法方法方法：设枚举时采用的变量为z，实际上就是需要枚举z取值为063的每种情形，对z的某个取值，假设其二进制形式为100111100111，需要依次取出每位上的数码，并判断每根木条旋转与否。比如第0位上的数码为1，代表木条i需要旋转，第3位上的数码为0，代表木条0不需要旋转。:取出各位上的二进制数码：“按位右移按位右移按位右移按位右移”运算和“按位与按位与按位与按位与”运算。14正确的嵌入方案:一共有256256种正确的嵌入方案。153.3 去除相同的解以下这组解case 256:6 5 4 2 1 3/木条的序号1 1 1 1 1 1/1表示旋转，0表示不旋转跟另外几组解实际上是同一组解。(1)6 5 4这一组整体旋转过来，则是4 5 6，而且原来单个木条旋转与否要改变。这时2 1 3这一组也整体旋转过来了，变成了3 1 2，而且原来单个木条旋转与否也都改变了。因此，“case 256”这一组解跟下一组解是同一组解。case 193:4 5 6 3 1 20 0 0 0 0 016(2)6根木条嵌入后，整体翻过来，每组3根木条顺序及翻转不变（只是i、j、k和o、p、q交换了），也是同一组解。因此，“case 256”这一组解跟下一组解是同一组解。case 58:2 1 3 6 5 41 1 1 1 1 1(3)6根木条嵌入后，整体翻过来，再按照(1)中的思路进行处理，得到的也是同一组解。因此，“case 256”这一组解跟下一组解是同一组解。case 106:3 1 2 4 5 60 0 0 0 0 0按照这种思路，256种解，只有64种解了。17:去除相同解的思路：用一个数组存储不相同的解。每得到一个解，按照前面的分析进行3次转换并在已有的解中进行查找，如果都查找不到，则说明是一个不相同的解。183.4 在外部能嵌入就能装入到正方体框架中？:不一定!