Re: [問題] 踩地雷的數字

看板puzzle作者jurian0101 (Hysterisis)時間13年前 (2011/08/14 21:40)推噓1(1推 0噓 3→)

留言4則, 3人參與討論串2/2 (看更多)

※ 引述《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

→

jurian0101

08/14 22:06, , 1^F

08/14 22:06, 1^F

→

jurian0101

08/14 22:09, , 2^F

08/14 22:09, 2^F

→

EIORU

08/15 11:48, , 3^F

08/15 11:48, 3^F