作者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)