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