p**e 发帖数: 533 | 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的按键组合? | t********e 发帖数: 143 | | r*****e 发帖数: 792 | 3 应该可以。从1和2分别出发,密码总数乘4,加上从5出发的密码数。
不知道思想对不对?
【在 t********e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : Look like DFS.
| p**e 发帖数: 533 | 4 有点像,但是不完全一样。比如你用了147.....,你还可以再走157... 虽然7已经visit
过了。
1 2 3
4 5 6
7 8 9
【在 t********e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : Look like DFS.
| p**e 发帖数: 533 | 5 我也是这么想的,但是从1出发的怎么计算呢?跟DFS还不一样,不同的path可以有重复
的节点。
【在 r*****e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 应该可以。从1和2分别出发,密码总数乘4,加上从5出发的密码数。 : 不知道思想对不对?
| r*****e 发帖数: 792 | 6 我在想是不是可以用递归,比如计算从1出发时,对2,4,5递归,不用对节点
mark flag,只要确保没有重复数字就行了,比如用个set存一下已经访问的数字。
反正顺序不同的密码是不同的。
【在 p**e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我也是这么想的,但是从1出发的怎么计算呢?跟DFS还不一样,不同的path可以有重复 : 的节点。
| p**e 发帖数: 533 | 7 用递归的话,最大的问题,就是计算从3出发的时候,又会对2,5,6递归,其中2和5已
经在计算从1出发的时候递归过了,所以会有重复的节点。
【在 r*****e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我在想是不是可以用递归,比如计算从1出发时,对2,4,5递归,不用对节点 : mark flag,只要确保没有重复数字就行了,比如用个set存一下已经访问的数字。 : 反正顺序不同的密码是不同的。
| r*****e 发帖数: 792 | 8 所以说要用个set,来记录这条path经过的节点。
【在 p**e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 用递归的话,最大的问题,就是计算从3出发的时候,又会对2,5,6递归,其中2和5已 : 经在计算从1出发的时候递归过了,所以会有重复的节点。
|
| p**e 发帖数: 533 | 9 能具体说说吗?
我总觉得递归有点问题,
比如从1出发,递归2,4,5,
从3出发,递归2,5,6。
从3 出发,我们还需不需要递归2,5,如果不要的话,5-1显然是个新的节点。
【在 r*****e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 所以说要用个set,来记录这条path经过的节点。
| r*****e 发帖数: 792 | 10 一会有空的话写个code验证一下我的想法再来update。
不行就明天再写code吧,至少可以躺床上静想一下,呵呵。
【在 p**e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 能具体说说吗? : 我总觉得递归有点问题, : 比如从1出发,递归2,4,5, : 从3出发,递归2,5,6。 : 从3 出发,我们还需不需要递归2,5,如果不要的话,5-1显然是个新的节点。
| | | f****0 发帖数: 151 | 11 感觉用DFS可以啊,不过是在每进入一层时把该点标记一下,然后退出这一层时再对该
点撤销标记。 | p*****2 发帖数: 21240 | | r*****e 发帖数: 792 | 13 从1开始共有132个密码,从2有146个,从5有96个,
所以总共应该有132*4+146*4+96,居然有这么多。
用的是递归,没有用纯粹的DFS。
【在 r*****e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 一会有空的话写个code验证一下我的想法再来update。 : 不行就明天再写code吧,至少可以躺床上静想一下,呵呵。
| f****0 发帖数: 151 | 14 从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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 从1开始共有132个密码,从2有146个,从5有96个, : 所以总共应该有132*4+146*4+96,居然有这么多。 : 用的是递归,没有用纯粹的DFS。
| f****0 发帖数: 151 | 15 我的图建漏了一项。。结果貌似要更多
1开始1373,2开始1037,5开始665。。
【在 f****0 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 从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**e 发帖数: 533 | 16 能给个你说的递归的code吗?
【在 r*****e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 从1开始共有132个密码,从2有146个,从5有96个, : 所以总共应该有132*4+146*4+96,居然有这么多。 : 用的是递归,没有用纯粹的DFS。
| r*****e 发帖数: 792 | 17 我贴的结果是长度为5的密码,没有计算其他长度的。
我给你发个bbs mail吧,代码就不贴出来献丑了,呵呵。
【在 p**e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 能给个你说的递归的code吗?
| h*****9 发帖数: 26 | 18 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我贴的结果是长度为5的密码,没有计算其他长度的。 : 我给你发个bbs mail吧,代码就不贴出来献丑了,呵呵。
|
|