微距生活 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>Joke - 肚皮舞运动

微距生活

微距生活# Joke - 肚皮舞运动

p*e2012-03-01 08:03

1 楼

利用电话按键1－9产生password，必须swipe产生password，跟android很像，密码没有
重复的数字。
比如
1 2 3
4 5 6
7 8 9
可以从1出发到5，到9，到6，到3，产生密码15963.
但是不可以从1直接到9，因为1跟9不相连。
也不可以是1421，因为任何数字在一个密码中只能用一次。
问题是：用这种方法一共可以产生多少个passwords？
如果是nxn square，能够有多少个swipable的按键组合?

G*r2012-03-01 08:03

2 楼

蚂蚁王国

t*e2012-03-01 08:03

3 楼

Look like DFS.

r*e2012-03-01 08:03

4 楼

nice!

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

: 蚂蚁王国

r*e2012-03-01 08:03

5 楼

应该可以。从1和2分别出发，密码总数乘4，加上从5出发的密码数。
不知道思想对不对？

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

: Look like DFS.

c*72012-03-01 08:03

6 楼

wow漂亮！

p*e2012-03-01 08:03

7 楼

有点像，但是不完全一样。比如你用了147.....,你还可以再走157... 虽然7已经visit
过了。
1 2 3
4 5 6
7 8 9

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

: Look like DFS.

p*e2012-03-01 08:03

8 楼

我也是这么想的，但是从1出发的怎么计算呢？跟DFS还不一样，不同的path可以有重复
的节点。

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

: 应该可以。从1和2分别出发，密码总数乘4，加上从5出发的密码数。
: 不知道思想对不对？

r*e2012-03-01 08:03

9 楼

我在想是不是可以用递归，比如计算从1出发时，对2,4,5递归，不用对节点
mark flag，只要确保没有重复数字就行了，比如用个set存一下已经访问的数字。
反正顺序不同的密码是不同的。

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

: 我也是这么想的，但是从1出发的怎么计算呢？跟DFS还不一样，不同的path可以有重复
: 的节点。

p*e2012-03-01 08:03

10 楼

用递归的话，最大的问题，就是计算从3出发的时候，又会对2，5，6递归，其中2和5已
经在计算从1出发的时候递归过了，所以会有重复的节点。

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

: 我在想是不是可以用递归，比如计算从1出发时，对2,4,5递归，不用对节点
: mark flag，只要确保没有重复数字就行了，比如用个set存一下已经访问的数字。
: 反正顺序不同的密码是不同的。

r*e2012-03-01 08:03

11 楼

所以说要用个set，来记录这条path经过的节点。

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

: 用递归的话，最大的问题，就是计算从3出发的时候，又会对2，5，6递归，其中2和5已
: 经在计算从1出发的时候递归过了，所以会有重复的节点。

p*e2012-03-01 08:03

12 楼

能具体说说吗？
我总觉得递归有点问题，
比如从1出发，递归2，4，5，
从3出发，递归2，5，6。
从3 出发，我们还需不需要递归2，5，如果不要的话，5－1显然是个新的节点。

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

: 所以说要用个set，来记录这条path经过的节点。

r*e2012-03-01 08:03

13 楼

一会有空的话写个code验证一下我的想法再来update。
不行就明天再写code吧，至少可以躺床上静想一下，呵呵。

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

: 能具体说说吗？
: 我总觉得递归有点问题，
: 比如从1出发，递归2，4，5，
: 从3出发，递归2，5，6。
: 从3 出发，我们还需不需要递归2，5，如果不要的话，5－1显然是个新的节点。

f*02012-03-01 08:03

14 楼

感觉用DFS可以啊，不过是在每进入一层时把该点标记一下，然后退出这一层时再对该
点撤销标记。

p*22012-03-01 08:03

15 楼

DFS不行吗？

r*e2012-03-01 08:03

16 楼

从1开始共有132个密码，从2有146个，从5有96个，
所以总共应该有132*4+146*4+96，居然有这么多。
用的是递归，没有用纯粹的DFS。

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

: 一会有空的话写个code验证一下我的想法再来update。
: 不行就明天再写code吧，至少可以躺床上静想一下，呵呵。

f*02012-03-01 08:03

17 楼

从1开始我算出来是1047条。。2开始886条。。5开始665条。。
你是把哪些当作重复了
这是我的code:
void print(int* set, int size) {
for (int i = 0; i < size && set[i] > 0; i++)
cout << set[i];
cout << endl;
}
int PadPathNum(int** graph, int num, int first) {
static int path_num = 0;
static int visit[9] = {0};
static int set[9] = {0};
static int index = 0;
visit[first] = 1;
set[index++] = first + 1;
print(set, num);
path_num++;
for (int i = 0; i < num; i++)
if (graph[first][i] == 1 && visit[i] == 0)
PadPathNum(graph, num, i);
visit[first] = 0;
set[--index] = 0;
return path_num;
}
以下是以1开头的密码的前面一部输出结果：
1
12
123
1235
12354
123547
1235478
12354786
123547869
12354789
123547896
123548
1235486
12354869
1235487
1235489
12354896
12356
123568
1235684
12356847
1235687

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

: 从1开始共有132个密码，从2有146个，从5有96个，
: 所以总共应该有132*4+146*4+96，居然有这么多。
: 用的是递归，没有用纯粹的DFS。

f*02012-03-01 08:03

18 楼

我的图建漏了一项。。结果貌似要更多
1开始1373，2开始1037，5开始665。。

【在 f****0 的大作中提到】

: 从1开始我算出来是1047条。。2开始886条。。5开始665条。。
: 你是把哪些当作重复了
: 这是我的code:
: void print(int* set, int size) {
: for (int i = 0; i < size && set[i] > 0; i++)
: cout << set[i];
: cout << endl;
: }
: int PadPathNum(int** graph, int num, int first) {
: static int path_num = 0;

p*e2012-03-01 08:03

19 楼

能给个你说的递归的code吗？

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

: 从1开始共有132个密码，从2有146个，从5有96个，
: 所以总共应该有132*4+146*4+96，居然有这么多。
: 用的是递归，没有用纯粹的DFS。

r*e2012-03-01 08:03

20 楼

我贴的结果是长度为5的密码，没有计算其他长度的。
我给你发个bbs mail吧，代码就不贴出来献丑了，呵呵。

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

: 能给个你说的递归的code吗？

h*92012-03-01 08:03

21 楼

next = {1:[2,4,5],2:[1,3,4,5,6],3:[2,5,6],4:[1,2,5,7,8],5:[1,2,3,4,6,7,8,9],
6:[2,3,5,8,9],
7:[4,5,8],8:[4,5,6,7,9],9:[5,6,8]}
def genpass(now):
if not now: return 0
ret = 1
for n in next[now[-1]]:
if n in now: continue
ret += genpass(now+[n])
return ret
for i in range(1,10):
print i,genpass([i])

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

: 我贴的结果是长度为5的密码，没有计算其他长度的。
: 我给你发个bbs mail吧，代码就不贴出来献丑了，呵呵。