[中譯] PuzzleUp 2009 (5) Pattern

看板puzzle (益智遊戲 - 數獨,拼圖,推理,西洋棋)作者 ((short)(-15074))時間15年前 (2009/08/19 20:31), 編輯推噓53(53035)
留言88則, 12人參與, 最新討論串1/1
首頁:http://www.puzzleup.com/2009/?home 時限:2009/08/20(四)19:00~08/26(三)18:59 答案可上傳次,但每改1次扣20(基本分為100分) 在比賽期間內可隨時回答,但只有在時限內回答者有額外加分 ◆Pattern 在一個5X5的格子裡任意塗黑三格共有幾種塗法? 注意:若一個塗法可以由另一個塗法經旋轉(且不鏡射)而得到, 則兩者就認為是相同的塗法。 -- 'Oh, Harry, dont't you see?' Hermione breathed. 'If she could have done one thing to make absolutely sure that every single person in this school will read your interview, it was banning it!' ---'Harry Potter and the order of the phoenix', P513 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.112.30.84

08/19 20:32, , 1F
就不等帕索大了 自己先貼 XD (其實是解的差不多了...(逃
08/19 20:32, 1F
※ 編輯: LPH66 來自: 140.112.30.84 (08/19 20:33)

08/19 20:57, , 2F
如果題目是 4x4 或 6x6 的格子會比較簡單...
08/19 20:57, 2F

08/19 20:58, , 3F
題目長得就是一付有陷阱的臉...
08/19 20:58, 3F

08/19 21:09, , 4F
只用乘跟除的答案會對嗎
08/19 21:09, 4F

08/19 21:17, , 5F
不曉得耶, 我在想有沒有解法是可以用到開根號的....:P
08/19 21:17, 5F

08/19 21:27, , 6F
5*5的關鍵就是中間這格
08/19 21:27, 6F

08/19 21:30, , 7F
沒錯, 陷阱臉....
08/19 21:30, 7F

08/19 23:34, , 8F
同意,掌握關鍵後剩下的就是排列組合啦
08/19 23:34, 8F

08/19 23:35, , 9F
怎麼用根號解我也想不到… :P
08/19 23:35, 9F

08/20 08:25, , 10F
算完之後,我得到一個驚人的結果……
08/20 08:25, 10F

08/20 08:39, , 11F
什麼!! Σ(⊙▽⊙"a
08/20 08:39, 11F

08/20 08:42, , 12F
咦!閒聊區不見了
08/20 08:42, 12F

08/20 20:29, , 13F
哇嗚~這樣就不能玩帕索了QQ。。。
08/20 20:29, 13F

08/20 20:40, , 14F
他故意的
08/20 20:40, 14F

08/20 20:49, , 15F
帕索大真殘忍...唯一的樂趣也被硬生生地剝奪QQ。。。
08/20 20:49, 15F

08/20 20:50, , 16F
為了這題 我翻出了塵封以久的五子棋來排
08/20 20:50, 16F

08/20 21:01, , 17F
要牌很久喔
08/20 21:01, 17F

08/20 21:36, , 18F
只排三階就很快...而且會發現一件奇怪的事...
08/20 21:36, 18F

08/20 21:42, , 19F
也是只排3 冥冥中有個巧合....難不成...
08/20 21:42, 19F

08/20 21:43, , 20F
只要確定是21或22 我就能確定5階的答案了...
08/20 21:43, 20F

08/20 21:55, , 21F
嗯 是22種 我能確定5階的答案了!
08/20 21:55, 21F

08/20 21:56, , 22F
22種是3階的答案...別誤會了.......
08/20 21:56, 22F

08/20 22:03, , 23F
我可以確定1階的答案是0種....
08/20 22:03, 23F

08/20 22:03, , 24F
提供大家做參考..
08/20 22:03, 24F

08/20 22:10, , 25F
2階是1種 肯定!
08/20 22:10, 25F

08/20 22:13, , 26F
我經過2天不眠不休,再用微積分,終於算出4階有140種...
08/20 22:13, 26F

08/20 22:15, , 27F
解數列 0, 1, 22, 140, ? 天啊...這個提示真大.....
08/20 22:15, 27F

08/20 22:23, , 28F
不眠不休 0口0""
08/20 22:23, 28F

08/20 22:34, , 29F
這不是應該用5x5格子中塗1個格子有幾種、塗兩個格子有幾種
08/20 22:34, 29F

08/20 22:35, , 30F
進而算出塗三個格子有幾種?
08/20 22:35, 30F

08/20 23:14, , 31F
樓上一語驚醒夢中人!我本來還想用線性迴歸法去分析說....
08/20 23:14, 31F

08/21 01:12, , 32F
有尾數@@
08/21 01:12, 32F

08/21 01:41, , 33F
帕索不眠不休,那來的夢中人 = =
08/21 01:41, 33F

08/21 06:40, , 34F
啊我就不能做白日夢哦-.- 真愛計較...
08/21 06:40, 34F

08/21 06:42, , 35F
TO werul: 什麼尾數來著?你之前是算 XXX0 嗎?
08/21 06:42, 35F

08/21 16:28, , 36F
我算的是有尾數 而且沒超過1000@@ 尾數就是不是5或0的數字
08/21 16:28, 36F

08/21 17:28, , 37F
愛做白日夢的帕索大
08/21 17:28, 37F

08/21 18:24, , 38F
我是故意打四位數說 被你破梗XDDDD 我的尾數也不是5或0...
08/21 18:24, 38F

08/21 20:51, , 39F
答案個位數是8嗎? 想確認一下 講個位數應該不算洩露答案!
08/21 20:51, 39F

08/21 20:53, , 40F
寫了2個小時的程式 讓程式去跑出答案 哈哈! 我真懶惰
08/21 20:53, 40F

08/21 20:54, , 41F
但不知道答案對不對? 但4X4的話 我的程式跑出來是140種
08/21 20:54, 41F

08/21 21:34, , 42F
6x6跑來出是1785種
08/21 21:34, 42F

08/21 23:18, , 43F
我算出來尾數是3..
08/21 23:18, 43F

08/21 23:22, , 44F
應該是奇數格才要考慮對稱情形 如3X3 5X5 7X7
08/21 23:22, 44F

08/21 23:24, , 45F
我算出來是5X3...Q口Q
08/21 23:24, 45F

08/21 23:24, , 46F
偶數格沒有對稱情形 直接除以四 ex: C(2^2,3)/4 =1
08/21 23:24, 46F

08/21 23:25, , 47F
c(4^2,3)/4 = 140 C(6^2,3)/4 = 1785
08/21 23:25, 47F

08/21 23:26, , 48F
除以4的原因是因為可以旋轉4個角度 都視為一種
08/21 23:26, 48F

08/21 23:27, , 49F
08/21 23:27, 49F

08/21 23:28, , 50F
奇數格則會圖形對稱的情況 需另外考慮 不能直接除以4
08/21 23:28, 50F

08/21 23:29, , 51F
直接除答案是575..不過當然不對XD
08/21 23:29, 51F

08/21 23:32, , 52F
想知道程式怎麼寫的
08/21 23:32, 52F

08/22 10:32, , 53F
我也想知道QQ...我最近好像變笨了...
08/22 10:32, 53F

08/23 21:59, , 54F
就是把三格數字化 例如(1,1),(4,1),(5,5)記為114155
08/23 21:59, 54F

08/23 22:00, , 55F
然後開始排列,把每一個三格翻轉4次得到的數字丟到陣列去
08/23 22:00, 55F

08/23 22:01, , 56F
然後下一個排列的三格,看看數字有沒有已經在陣列裡?
08/23 22:01, 56F

08/23 22:03, , 57F
有的話 不予計數,免得得到同樣的圖形而重覆計數了!
08/23 22:03, 57F

08/23 22:13, , 58F
我的程式沒有很長 大概200行左右 用c++寫的
08/23 22:13, 58F

08/24 22:05, , 59F
借用utomaya的想法,如果我以中間(3,3)的格子當作原點。
08/24 22:05, 59F

08/24 22:06, , 60F
向右為實數1,2;向左為-1,-2;向上為虛數i,2i向下為-i,-2i
08/24 22:06, 60F

08/24 22:07, , 61F
則(1,1)以數字表示為-2+2i;(4,1)=1+2i;(5,5)=2-2i
08/24 22:07, 61F

08/24 22:09, , 62F
逆時針旋轉90度,相當於數字乘上i。
08/24 22:09, 62F

08/24 22:10, , 63F
例如 (1,1)=-2+2i 乘上i = -2-2i = (1,5)
08/24 22:10, 63F

08/24 22:12, , 64F
經過這樣轉換,是否有什麼定理可以用原題的解題上?
08/24 22:12, 64F

08/25 10:06, , 65F
還滿有創意,但至今我還想不出有什麼應用解題的方式....
08/25 10:06, 65F

08/25 11:20, , 66F
在旋轉的時候把中間的格子當做(0,0),
08/25 11:20, 66F

08/25 11:20, , 67F
在做運算的時候把左上角的格子當做(0,0),
08/25 11:20, 67F

08/25 11:21, , 68F
如果可以,就代表重覆,否則計數器加一
08/25 11:21, 68F

08/25 11:21, , 69F
唔...連推失敗
08/25 11:21, 69F

08/25 11:21, , 70F
在旋轉的時候把中間的格子當做(0,0),
08/25 11:21, 70F

08/25 11:21, , 71F
在做運算的時候把左上角的格子當做(0,0),
08/25 11:21, 71F

08/25 11:22, , 72F
整個盤面有25個格子,一個integer佔32個bit
08/25 11:22, 72F

08/25 11:22, , 73F
所以用右邊的25個bit來代表那些格子,
08/25 11:22, 73F

08/25 11:22, , 74F
(x,y)用第(x*5+y)個bit來表示,如果有放東西
08/25 11:22, 74F

08/25 11:22, , 75F
就是1,否則是0,
08/25 11:22, 75F

08/25 11:22, , 76F
所以每一個盤面會有三個bit不為零,可用一個整數代表
08/25 11:22, 76F

08/25 11:22, , 77F
,假設為k,對於每一個k,檢查是否可以轉換成一個更小的k'
08/25 11:22, 77F

08/25 11:22, , 78F
如果可以,就代表重覆,否則計數器加一
08/25 11:22, 78F

08/25 11:23, , 79F
這樣枚舉完所有可能之後就可以算出有幾種方法
08/25 11:23, 79F

08/25 11:24, , 80F
這樣寫的話大概50行就夠了
08/25 11:24, 80F

08/25 14:38, , 81F
嗯,看懂了...好像真的不難耶......
08/25 14:38, 81F

08/25 14:39, , 82F
這麼一來就不用把查過的位置,記錄下來了.....
08/25 14:39, 82F

08/25 21:05, , 83F
找到奇數項的公式了,可是不知道為什麼長這樣 >.<
08/25 21:05, 83F

08/25 21:35, , 84F
哇,我知道為什麼耶~突然覺得自己好優秀~XDDDDD
08/25 21:35, 84F

08/25 21:40, , 85F
哇!!!我懂了,原來我忘了某一項~XDD
08/25 21:40, 85F

08/26 06:51, , 86F
結果我只優秀了35分鐘....=.="
08/26 06:51, 86F

08/27 14:00, , 87F
我3X3的只排出19個 = =
08/27 14:00, 87F

08/27 14:05, , 88F
對不起我錯了 <(_ _)> 重算後是21,不知道少哪一個 ^^"
08/27 14:05, 88F
文章代碼(AID): #1AY_2x_R (puzzle)
文章代碼(AID): #1AY_2x_R (puzzle)