不知道发到哪个版，发这里试一下 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

不知道发到哪个版，发这里试一下

不知道发到哪个版，发这里试一下# JobHunting - 待字闺中

y*e2013-02-23 08:02

1 楼

版上牛人多，我问一个不知道算智力题还是算法题。
最近在研究android的九宫解锁，突然想算出到底有多少种可能的密码组合。
简单的说，就是3*3的点阵，有多少种一笔画的可能？
要求：
1.每个点最多被经过一次;
2.笔画数大于等于1;
3.必须是直线;
4.每个点被经过后就相当于在图上被抹去了;
5.从任意一点可以连到非相临的点，前提是这条连线上不能存在未被经过点，否则算作
两条连线消去两个点；
有android手机的实验一下就知道到底是怎么个规则了，向各位求一个答案和计算过程;
相应的，如果扩展到m*n的均匀点阵，有大侠能给个通项么，如果不能，给个算法和算
法复杂度也行。
谢谢！

r*n2013-02-23 08:02

2 楼

Google面馆正愁没有新题，你这倒是帮人家出了一道 :)

c*t2013-02-23 08:02

3 楼

你捡到手机了？
不是屌丝，没用过adroid手机。
2.笔画数大于等于1 （等于就是1个点也可以做密码？）
3.必须是直线（啥意思？直线最多不就三个点？）
你给个最长的路线例子吧。
这道题肯定是 dfs or bfs可解，但也许数学高手直接算出结果来给你。

【在 y*********e 的大作中提到】

: 版上牛人多，我问一个不知道算智力题还是算法题。
: 最近在研究android的九宫解锁，突然想算出到底有多少种可能的密码组合。
: 简单的说，就是3*3的点阵，有多少种一笔画的可能？
: 要求：
: 1.每个点最多被经过一次;
: 2.笔画数大于等于1;
: 3.必须是直线;
: 4.每个点被经过后就相当于在图上被抹去了;
: 5.从任意一点可以连到非相临的点，前提是这条连线上不能存在未被经过点，否则算作
: 两条连线消去两个点；

y*e2013-02-23 08:02

4 楼

保守估计也有1/2 个9!个解。。忘记这个pattern了还是可以通过google账户登入的。
1.用android ！= 屌丝。。
2.就是最少要连一笔，也就是两个点
3.连线必须是直线，也就是说如果三点在一直线上，不能跨过中间的点连上两边的，要
连就一起连上了
4.求的是可能解的个数而不是最长路线，最长路线估计是画斜对角线

【在 c********t 的大作中提到】

: 你捡到手机了？
: 不是屌丝，没用过adroid手机。
: 2.笔画数大于等于1 （等于就是1个点也可以做密码？）
: 3.必须是直线（啥意思？直线最多不就三个点？）
: 你给个最长的路线例子吧。
: 这道题肯定是 dfs or bfs可解，但也许数学高手直接算出结果来给你。

y*e2013-02-23 08:02

5 楼

我google过，没找到类似的题。。

【在 r*********n 的大作中提到】

: Google面馆正愁没有新题，你这倒是帮人家出了一道 :)

c*t2013-02-23 08:02

6 楼

必须要连续吗？比如X可以不？
经过的点还能再经过吗？比如（又）可以不？

【在 y*********e 的大作中提到】

: 保守估计也有1/2 个9!个解。。忘记这个pattern了还是可以通过google账户登入的。
: 1.用android ！= 屌丝。。
: 2.就是最少要连一笔，也就是两个点
: 3.连线必须是直线，也就是说如果三点在一直线上，不能跨过中间的点连上两边的，要
: 连就一起连上了
: 4.求的是可能解的个数而不是最长路线，最长路线估计是画斜对角线

l*n2013-02-23 08:02

7 楼

我觉得就是9!个解，相当于9个不同位置的排列

【在 y*********e 的大作中提到】

c*h2013-02-23 08:02

8 楼

补充一条规则，至少要连4个点
最终总共389112种组合，没有什么通项，就是用brute force穷算
这个结果在一篇论文里有支持

【在 y*********e 的大作中提到】

d*x2013-02-23 08:02

9 楼

没用过android手机，不知道什么规则
但是确实看起来像是np...

算作

【在 c******h 的大作中提到】

: 补充一条规则，至少要连4个点
: 最终总共389112种组合，没有什么通项，就是用brute force穷算
: 这个结果在一篇论文里有支持

b*o2013-02-23 08:02

10 楼

9! = 362880 < 389112...

【在 c******h 的大作中提到】

: 补充一条规则，至少要连4个点
: 最终总共389112种组合，没有什么通项，就是用brute force穷算
: 这个结果在一篇论文里有支持

c*h2013-02-23 08:02

11 楼

不一定要把9个点都连上，还可以是只连8个点，7个点，...,直到最少4个点
9! + 8! + ... + 4! > 389112

【在 b*****o 的大作中提到】

: 9! = 362880 < 389112...

b*o2013-02-23 08:02

12 楼

那还是贴code吧，我算出来是140240。 code很没有效率，要算半分钟～
//////////////////////////////////
import fractions
import time
N = 3
M = 3
def notCollinear(i, j):
a, b = map(lambda x: (x / N, x % N), (i,j))
if abs(fractions.gcd(a[0] - b[0], a[1] - b[1])) > 1:
return False
return True
def adjoin(S):
return reduce(lambda x, y: x + y, S)
def nextRound(pw):
return adjoin(map(lambda x: [x + [i] for i in xrange(N * M)
if not i in x and notCollinear(i,x[-1])], pw))
def findAll():
pw = [[[i] for i in xrange(N * M)]]
for i in xrange(N * M - 1):
pw.append(nextRound(pw[i]))
return adjoin(pw[1:])
start = time.clock()
a = findAll()
print "Elapsed time(s): " + str(time.clock() - start)
print "Total number of passwords: " + str(len(a))

【在 y*********e 的大作中提到】

y*e2013-02-23 08:02

13 楼

X不行，必须连续，又可以，因为一个点被连过一次以后就被抹去了

【在 c********t 的大作中提到】

: 必须要连续吗？比如X可以不？
: 经过的点还能再经过吗？比如（又）可以不？

y*e2013-02-23 08:02

14 楼

这篇论文就是针对google这个unlock pattern的规则么

【在 c******h 的大作中提到】

: 补充一条规则，至少要连4个点
: 最终总共389112种组合，没有什么通项，就是用brute force穷算
: 这个结果在一篇论文里有支持

y*e2013-02-23 08:02

15 楼

感觉这个结果不太对啊， 9！+8！+...4!=409104,
然后第一个点选在四个角的话第二个点只有5种可能性，选在边上四个点的话第二个点
只有7种可能
所以upper bound 是
4/9 * 5/8 + 4/9 * 7/8 +1/9 = 7/9
409104 * （7/9） = 318192

【在 c******h 的大作中提到】

: 补充一条规则，至少要连4个点
: 最终总共389112种组合，没有什么通项，就是用brute force穷算
: 这个结果在一篇论文里有支持

i*e2013-02-23 08:02

16 楼

有人解答过了吧。里面还有googler 给了解答的。
http://www.quora.com/How-many-combinations-does-Android-9-point