S**I
发帖数: 15689 | 1 ☆─────────────────────────────────────☆
pore (坚持不懈) 于 (Tue May 15 00:11:28 2012, 美东) 提到:
利用电话按键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的按键组合?
☆─────────────────────────────────────☆
tradertobe (builder) 于 (Tue May 15 00:24:00 2012, 美东) 提到:
Look like DFS.
☆─────────────────────────────────────☆
realife (leda) 于 (Tue May 15 00:45:23 2012, 美东) 提到:
应该可以。从1和2分别出发，密码总数乘4，加上从5出发的密码数。
不知道思想对不对？
☆─────────────────────────────────────☆
pore (坚持不懈) 于 (Tue May 15 00:59:56 2012, 美东) 提到:
有点像，但是不完全一样。比如你用了147.....,你还可以再走157... 虽然7已经visit
过了。
1 2 3
4 5 6
7 8 9
☆─────────────────────────────────────☆
pore (坚持不懈) 于 (Tue May 15 01:01:20 2012, 美东) 提到:
我也是这么想的，但是从1出发的怎么计算呢？跟DFS还不一样，不同的path可以有重复
的节点。
☆─────────────────────────────────────☆
realife (leda) 于 (Tue May 15 01:07:06 2012, 美东) 提到:
我在想是不是可以用递归，比如计算从1出发时，对2,4,5递归，不用对节点
mark flag，只要确保没有重复数字就行了，比如用个set存一下已经访问的数字。
反正顺序不同的密码是不同的。
☆─────────────────────────────────────☆
pore (坚持不懈) 于 (Tue May 15 01:14:17 2012, 美东) 提到:
用递归的话，最大的问题，就是计算从3出发的时候，又会对2，5，6递归，其中2和5已
经在计算从1出发的时候递归过了，所以会有重复的节点。
☆─────────────────────────────────────☆
realife (leda) 于 (Tue May 15 01:16:43 2012, 美东) 提到:
所以说要用个set，来记录这条path经过的节点。
☆─────────────────────────────────────☆
pore (坚持不懈) 于 (Tue May 15 01:22:45 2012, 美东) 提到:
能具体说说吗？
我总觉得递归有点问题，
比如从1出发，递归2，4，5，
从3出发，递归2，5，6。
从3 出发，我们还需不需要递归2，5，如果不要的话，5－1显然是个新的节点。
☆─────────────────────────────────────☆
realife (leda) 于 (Tue May 15 01:38:49 2012, 美东) 提到:
一会有空的话写个code验证一下我的想法再来update。
不行就明天再写code吧，至少可以躺床上静想一下，呵呵。
☆─────────────────────────────────────☆
flier0 (flier) 于 (Tue May 15 01:48:24 2012, 美东) 提到:
感觉用DFS可以啊，不过是在每进入一层时把该点标记一下，然后退出这一层时再对该
点撤销标记。
☆─────────────────────────────────────☆
peking2 (myfacebook) 于 (Tue May 15 02:13:57 2012, 美东) 提到:
DFS不行吗？
☆─────────────────────────────────────☆
realife (leda) 于 (Tue May 15 03:24:29 2012, 美东) 提到:
从1开始共有132个密码，从2有146个，从5有96个，
所以总共应该有132*4+146*4+96，居然有这么多。
用的是递归，没有用纯粹的DFS。
☆─────────────────────────────────────☆
flier0 (flier) 于 (Tue May 15 14:07:45 2012, 美东) 提到:
从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
☆─────────────────────────────────────☆
flier0 (flier) 于 (Tue May 15 15:06:33 2012, 美东) 提到:
我的图建漏了一项。。结果貌似要更多
1开始1373，2开始1037，5开始665。。
☆─────────────────────────────────────☆
pore (坚持不懈) 于 (Tue May 15 17:36:19 2012, 美东) 提到:
能给个你说的递归的code吗？
☆─────────────────────────────────────☆
realife (leda) 于 (Tue May 15 18:50:08 2012, 美东) 提到:
我贴的结果是长度为5的密码，没有计算其他长度的。
我给你发个bbs mail吧，代码就不贴出来献丑了，呵呵。
☆─────────────────────────────────────☆
hammer9 (蛤蟆) 于 (Tue May 15 23:46:35 2012, 美东) 提到:
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]) |
|
