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