作者jurian0101 (Hysterisis)
看板puzzle
标题Re: [问题] 踩地雷的数字
时间Sun Aug 14 21:40:28 2011
※ 引述《EIORU ()》之铭言：
初级版
9x9的踩地雷 共10颗
地雷随机分布下
当八个方向一格内有X个地雷就有数字X
(1)数字总和最大为多少? ★
(2)数字积最大为多少? ★★
作为对照:
1207959552 = 2^27 * 3^2
1934917632 = 2^15 * 3^10
叫程式找到三组排法，结果出乎意料的大，
0 0 0 0 1 1 2 1 1
0 0 0 0 1 ■ 3 ■ 2
0 0 0 0 2 2 4 ■ 2
0 0 0 0 2 ■ 4 2 2
0 0 0 0 2 ■ 3 ■ 1
0 0 0 0 2 2 4 2 2
0 0 0 0 2 ■ 4 ■ 2
0 0 0 0 2 ■ 4 ■ 2
0 0 0 0 1 1 2 1 1
乘积 = 2415919104 = 2^ 28 * 3^ 2
0 0 0 0 0 0 0 0 0
0 1 2 2 2 2 2 1 0
0 1 ■ ■ 2 ■ ■ 1 0
0 2 3 4 3 4 3 2 0
0 1 ■ 2 ■ 3 ■ 2 0
0 2 2 4 2 4 ■ 2 0
0 1 ■ 2 ■ 2 1 1 0
0 1 1 2 1 1 0 0 0
0 0 0 0 0 0 0 0 0
乘积 = 2717908992 = 2^ 25 * 3^ 4
0 0 0 0 0 0 0 0 0
0 1 2 2 2 2 2 1 0
0 1 ■ ■ 2 ■ ■ 1 0
0 2 3 4 3 4 3 2 0
0 1 ■ 2 ■ 2 ■ 1 0
0 2 2 4 2 4 2 2 0
0 1 ■ 2 ■ 2 ■ 1 0
0 1 1 2 1 2 1 1 0
0 0 0 0 0 0 0 0 0
乘积 = 3623878656 = 2^ 27 * 3^ 3
程式的大纲是
1. 随机产生一百组地图作为亲代
2. 对每个亲代作以下操作，以逐步得到改进
> 10颗地雷往八个方向(国王走法)作「扰动」最多得到80种合理的新「子代」
> 取最高(进化的)的替换原先的亲代。
> 万一无法再做任何改进，(进化死胡同) 则随机重取一组代替亲代。
3. 100组都调整过後输出一个乘积最大的结果
4. 重覆2 & 3
虽然不保证最终会算出所有排法的最大值，但是这大概是仅次於枚举的方法了。
而 C(81,10) = 1.8 * 10^12 就不太可能枚举 =v=
继续跑程式...
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 218.164.3.230
1F：→ jurian0101:看样子是找不到比那个M字大的排法了 08/14 22:06
2F：→ jurian0101:看萤幕上子代们用类似Game of live的方式爬行非常有趣 08/14 22:09
3F：→ EIORU:2^ 28 * 3^ 2 =2415919104 08/15 11:48
※ 编辑: jurian0101 来自: 218.164.11.21 (08/15 13:06)
4F：推 Favonia:酷！ 08/18 11:49
※ 编辑: jurian0101 来自: 218.164.12.81 (08/19 22:50)