[中譯] PuzzleUp 2009 (5) Pattern

看板puzzle作者 ((short)(-15074))時間15年前 (2009/08/19 20:31), 編輯推噓53(53推 0噓 35→)
留言88則, 12人參與, 最新討論串1/1
首頁：http://www.puzzleup.com/2009/?home 時限：2009/08/20（四）19:00～08/26（三）18:59 答案可上傳５次，但每改１次扣２０分（基本分為１００分） 在比賽期間內可隨時回答，但只有在時限內回答者有額外加分 ◆Pattern 在一個５Ｘ５的格子裡任意塗黑三格共有幾種塗法？ 注意：若一個塗法可以由另一個塗法經旋轉(且不鏡射)而得到， 則兩者就認為是相同的塗法。 -- '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
哇嗚~這樣就不能玩帕索了ＱＱ。。。
08/20 20:29, 13F
推
08/20 20:40, , 14F
他故意的
08/20 20:40, 14F
推
08/20 20:49, , 15F
帕索大真殘忍...唯一的樂趣也被硬生生地剝奪ＱＱ。。。
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
‣ 更多 LPH66 的文章
文章代碼(AID): #1AY_2x_R (puzzle)