骨牌游戏 我要思路
【总体思路】
1、找到所有点数差最小的排列方案
2、从上一步结果集中,选取旋转次数最少的方案
3、针对此方案,列出旋转方法
【实现算法】
以下列数据为例,进行说明
3
6 1
1 5
1 3
--------------------------
1、找到所有点数差最小的排列方案
1.1、计算每块骨牌的上下点数差,例如:
6 1 => 5
1 5 => 4
1 3 => 2
1.2、利用计算机的高速度进行暴力全排列,分别计算每种排列的点数差。
此处实际上就是在每块骨牌点数差前,添加正号或负号,然后求和。例如:
+5 +4 +2 => 11
+5 +4 -2 => 7
+5 -4 +2 => 3
+5 -4 -2 => 1
-5 +4 +2 => 1
-5 +4 -2 => 3
-5 -4 +2 => 7
-5 -4 -2 => 11
1.3、从上一步结果中,挑出点数差最小的方案。上例中点数差最小是1。
注意:这一步的算法可以优化一些。虽然总共会有2^n种方案,但从上面的例子可以看出,当把所有数字进行排序后,前一半和后一半的方案是对称的,所以只需要计算一半的排列即可。这样只需要计算2^(n-1)种方案,找到最优方案后很容易就可以得到对称的方案。
-------------------------------
2、从上一步结果集中,选取旋转次数最少的方案
2.1、当最优方案只有一种时,本步骤的目的已经达到,可直接进行后续的处理。
2.2、当最有方案有两种以上是,需要再次筛选旋转次数最小的方案。
这实际上就是判断哪一种方案与输入的方案匹配度最高,这样就转换成了集合交集的计算。例如:
输入方案: 6_1, 1_5, 1_3
方案1: 6_1, 1_5, 3_1 => 与输入方案的交集为:6_1, 1_5,两个元素
方案2: 6_1, 5_1, 3_1 => 与输入方案的交集为:6_1,一个元素
显然,方案1 与 输入方案 的匹配度更高。
-------------------------------
3、针对此方案,列出旋转方法
这一步处理很容易,仍然是计算输入方案和最优方案的交集(上一步计算可以缓存交集结果),凡是不在交集中的骨牌,都需要旋转。例如:
输入方案:6_1, 1_5, 1_3
最优方案:1_6, 1_5, 1_3 => 交集是1_5, 1_3
那么需要旋转的就是:6_1这块骨牌。
【结论】
看我敲字这么辛苦,多少给点分吧?...
2013