y*********e
发帖数: 576 | 1 版上牛人多，我问一个不知道算智力题还是算法题。
最近在研究android的九宫解锁，突然想算出到底有多少种可能的密码组合。
简单的说，就是3*3的点阵，有多少种一笔画的可能？
要求：
1.每个点最多被经过一次;
2.笔画数大于等于1;
3.必须是直线;
4.每个点被经过后就相当于在图上被抹去了;
5.从任意一点可以连到非相临的点，前提是这条连线上不能存在未被经过点，否则算作
两条连线消去两个点；
有android手机的实验一下就知道到底是怎么个规则了，向各位求一个答案和计算过程;
相应的，如果扩展到m*n的均匀点阵，有大侠能给个通项么，如果不能，给个算法和算
法复杂度也行。
谢谢！ |
r*********n
发帖数: 4553 | 2 Google面馆正愁没有新题，你这倒是帮人家出了一道 :) |
c********t
发帖数: 5706 | 3 你捡到手机了？
不是屌丝，没用过adroid手机。
2.笔画数大于等于1 （等于就是1个点也可以做密码？）
3.必须是直线 （啥意思？直线最多不就三个点？）
你给个最长的路线例子吧。
这道题肯定是 dfs or bfs可解，但也许数学高手直接算出结果来给你。
【在 y*********e 的大作中提到】
: 版上牛人多，我问一个不知道算智力题还是算法题。
: 最近在研究android的九宫解锁，突然想算出到底有多少种可能的密码组合。
: 简单的说，就是3*3的点阵，有多少种一笔画的可能？
: 要求：
: 1.每个点最多被经过一次;
: 2.笔画数大于等于1;
: 3.必须是直线;
: 4.每个点被经过后就相当于在图上被抹去了;
: 5.从任意一点可以连到非相临的点，前提是这条连线上不能存在未被经过点，否则算作
: 两条连线消去两个点；
|
y*********e
发帖数: 576 | 4 保守估计也有1/2 个9!个解。。忘记这个pattern了还是可以通过google账户登入的。
1.用android ！= 屌丝。。
2.就是最少要连一笔，也就是两个点
3.连线必须是直线，也就是说如果三点在一直线上，不能跨过中间的点连上两边的，要
连就一起连上了
4.求的是可能解的个数而不是最长路线，最长路线估计是画斜对角线
【在 c********t 的大作中提到】
: 你捡到手机了？
: 不是屌丝，没用过adroid手机。
: 2.笔画数大于等于1 （等于就是1个点也可以做密码？）
: 3.必须是直线 （啥意思？直线最多不就三个点？）
: 你给个最长的路线例子吧。
: 这道题肯定是 dfs or bfs可解，但也许数学高手直接算出结果来给你。
|
y*********e
发帖数: 576 | 5 我google过，没找到类似的题。。
【在 r*********n 的大作中提到】
: Google面馆正愁没有新题，你这倒是帮人家出了一道 :)
|
c********t
发帖数: 5706 | 6 必须要连续吗？ 比如X可以不？
经过的点还能再经过吗？ 比如（又）可以不？
【在 y*********e 的大作中提到】
: 保守估计也有1/2 个9!个解。。忘记这个pattern了还是可以通过google账户登入的。
: 1.用android ！= 屌丝。。
: 2.就是最少要连一笔，也就是两个点
: 3.连线必须是直线，也就是说如果三点在一直线上，不能跨过中间的点连上两边的，要
: 连就一起连上了
: 4.求的是可能解的个数而不是最长路线，最长路线估计是画斜对角线
|
l******n
发帖数: 9344 | 7 我觉得就是9!个解，相当于9个不同位置的排列
【在 y*********e 的大作中提到】
: 保守估计也有1/2 个9!个解。。忘记这个pattern了还是可以通过google账户登入的。
: 1.用android ！= 屌丝。。
: 2.就是最少要连一笔，也就是两个点
: 3.连线必须是直线，也就是说如果三点在一直线上，不能跨过中间的点连上两边的，要
: 连就一起连上了
: 4.求的是可能解的个数而不是最长路线，最长路线估计是画斜对角线
|
c******h
发帖数: 71 | 8 补充一条规则，至少要连4个点
最终总共389112种组合，没有什么通项，就是用brute force穷算
这个结果在一篇论文里有支持
【在 y*********e 的大作中提到】
: 版上牛人多，我问一个不知道算智力题还是算法题。
: 最近在研究android的九宫解锁，突然想算出到底有多少种可能的密码组合。
: 简单的说，就是3*3的点阵，有多少种一笔画的可能？
: 要求：
: 1.每个点最多被经过一次;
: 2.笔画数大于等于1;
: 3.必须是直线;
: 4.每个点被经过后就相当于在图上被抹去了;
: 5.从任意一点可以连到非相临的点，前提是这条连线上不能存在未被经过点，否则算作
: 两条连线消去两个点；
|
d**********x
发帖数: 4083 | 9 没用过android手机，不知道什么规则
但是确实看起来像是np...
算作
【在 c******h 的大作中提到】
: 补充一条规则，至少要连4个点
: 最终总共389112种组合，没有什么通项，就是用brute force穷算
: 这个结果在一篇论文里有支持
|
b*****o
发帖数: 715 | 10 9! = 362880 < 389112...
【在 c******h 的大作中提到】
: 补充一条规则，至少要连4个点
: 最终总共389112种组合，没有什么通项，就是用brute force穷算
: 这个结果在一篇论文里有支持
|
|
|
c******h
发帖数: 71 | 11 不一定要把9个点都连上，还可以是只连8个点，7个点，...,直到最少4个点
9! + 8! + ... + 4! > 389112
【在 b*****o 的大作中提到】
: 9! = 362880 < 389112...
|
b*****o
发帖数: 715 | 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 的大作中提到】
: 版上牛人多，我问一个不知道算智力题还是算法题。
: 最近在研究android的九宫解锁，突然想算出到底有多少种可能的密码组合。
: 简单的说，就是3*3的点阵，有多少种一笔画的可能？
: 要求：
: 1.每个点最多被经过一次;
: 2.笔画数大于等于1;
: 3.必须是直线;
: 4.每个点被经过后就相当于在图上被抹去了;
: 5.从任意一点可以连到非相临的点，前提是这条连线上不能存在未被经过点，否则算作
: 两条连线消去两个点；
|
y*********e
发帖数: 576 | 13 X不行，必须连续，又可以，因为一个点被连过一次以后就被抹去了
【在 c********t 的大作中提到】
: 必须要连续吗？ 比如X可以不？
: 经过的点还能再经过吗？ 比如（又）可以不？
|
y*********e
发帖数: 576 | 14 这篇论文就是针对google这个unlock pattern的规则么
【在 c******h 的大作中提到】
: 补充一条规则，至少要连4个点
: 最终总共389112种组合，没有什么通项，就是用brute force穷算
: 这个结果在一篇论文里有支持
|
y*********e
发帖数: 576 | 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**********e
发帖数: 1145 | |
