作者jurian0101 (Hysterisis)
看板puzzle
標題[問題] 手機螢幕鎖
時間Thu Aug 18 15:32:49 2011
◎ ◎ ◎
◎ ◎ ◎
◎ ◎ ◎
我的moto手機有種圖形螢幕鎖，它的設計是使用者劃過螢幕連接起九宮格中的若干點
作為密碼。
>> 例如
◎→◎→◎ ◎→◎ ◎
↓ ↓
◎ ◎ ◎ 或 ◎ ◎→◎
↖↓ ↓↖ ↓
◎ ◎ ◎ ◎ ◎←◎
都是有效的密碼
它還允許Ａ－Ｂ（還有Ｂ－Ｃ）這樣的連線
◎ ◎ Ｂ
┌----┘
Ａ ◎ ◎
◎ Ｃ ◎
然而如下圖，ａ到ｃ中間一定要經過ｂ不能跳過
ａ ◎ ◎
◎ ｂ ◎
◎ ◎ ｃ
請問至少包含四個點的密碼有幾種？1.旋/翻轉視為不同
2.旋/翻轉視為相同
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 218.164.9.243
1F：推 JimAbbott: Android @.@ 08/18 15:45
2F：→ jurian0101:所以所有Android手機都有囉 08/18 16:14
3F：推 pphhxx:如果經過的點不同 但是產生的圖形相同 算同or不同? 08/18 18:53
4F：→ puzzlez:從密碼的角度來看，當然不同 08/18 19:10
5F：推 Favonia:所以不能重複經過同一點對不對？ 08/18 23:52
6F：→ puzzlez:樓上問得好！我都沒有想到... 08/19 05:49
7F：推 RichardHan:我不會算，但我想聽結果~有人算出來了嗎 08/19 11:07
8F：推 LPH66:能重覆的話就算不完啦... 08/19 18:09
9F：→ jurian0101:不能經過同一點 可以在點以外的地方交叉 只能在點轉彎 08/19 20:44
10F：→ jurian0101:轉到數學板廣招英雄試試看XD 08/19 21:08
※ jurian0101:轉錄至看板 Math 08/19 21:09
11F：推 LPH66:話說你在 Math 版給出的 182944 好像不太對... 08/20 12:15
12F：→ LPH66:我的程式跑出來是至少四點的共 139880 種 08/20 12:16
13F：→ LPH66:而不管點數全部算進去的話是 140249 種 08/20 12:16
14F：→ jurian0101:我自勘就發現有錯了 08/20 15:58
15F：推 Favonia:140250,140249,140240,140184,139880,138480,133152, 08/21 02:01
16F：→ Favonia:117120,81792,32256 08/21 02:01
17F：→ jurian0101:Mathmatica驗證出來了，兩位答案140249 (不限點數)和 08/22 03:10
18F：→ jurian0101:139880(限4~9點) 正確!! ...起碼和四色定理一樣正確XD 08/22 03:12
19F：→ Favonia:樓上介意讓我看程式碼多短嗎xD 我對簡潔的程式很有興趣xD 08/22 04:55
１ ２ ３
４ ５ ６
７ ８ ９
話說Math板有人提醒，我才發現Android的正版螢幕鎖允許2-5-8-
6---4這樣的連結
不想改了直接無視。搞操煩啦!!
這裡就當作禁止出現 13/17/19/31/37/39/71/73/79/91/93/97/46/64/82/28 這16個
"規則"好了
LPH66和Favonia一定同意 :D
- - -
Mathematica: 以下為Input
set = Permutations[{"1", "2", "3", "4", "5", "6", "7", "8", "9"}, {4, 9}];
(*生出排列*)
stringset = Array[StringJoin[set[[#]]] &, Length[set]];
(*更改一下形式*)
S[x_, y_] := StringMatchQ[x, y];
(*只是嫌函數太長的代換*)
rule = Not[#] & /@ (S[#, ___ ~~ "13" ~~ ___] ||
S[#, ___ ~~ "17" ~~ ___] || S[#, ___ ~~ "19" ~~ ___] ||
S[#, ___ ~~ "31" ~~ ___] || S[#, ___ ~~ "37" ~~ ___] ||
S[#, ___ ~~ "39" ~~ ___] || S[#, ___ ~~ "71" ~~ ___] ||
S[#, ___ ~~ "73" ~~ ___] || S[#, ___ ~~ "79" ~~ ___] ||
S[#, ___ ~~ "91" ~~ ___] || S[#, ___ ~~ "93" ~~ ___] ||
S[#, ___ ~~ "97" ~~ ___] || S[#, ___ ~~ "28" ~~ ___] ||
S[#, ___ ~~ "82" ~~ ___] || S[#, ___ ~~ "46" ~~ ___] ||
S[#, ___ ~~ "64" ~~ ___] & /@ stringset);
(*將16個規則map到stringset，再取Not*)
Length[Pick[stringset, rule]]
(*Pick根據rule把stringset裡所有「不犯規」的組合挑出來，以利萬一要揪錯所用，
輸出挑出來集合的大小*)
※ 編輯: jurian0101 來自: 218.164.5.102 (08/22 19:07)
20F：推 Favonia:了解，謝謝提供！ 08/22 23:26