关于九宫格解锁的可能种数。

不知道有多少蛋疼如我的人每天在解锁手机的时候都忍不住想,这锁到底能有多少种呢?

这个问题并不像表面上看起来那么简单,至少不是9个点全部排列的9+9*8+9*8*7+9*8*7*6+9*8*7*6*5+9*8*7*6*5*4+9*8*7*6*5*4*3+9*8*7*6*5*4*3*2+9*8*7*6*5*4*3*2*1=986409。为什么不是呢?因为有些组合是无法达到的。对于一个九宫格解锁来说

1 2 3
4 5 6
7 8 9

像1->3->2这样的路径是不行的,但是反过来说,2->1>3这样的路径是可以的,也就是说,如果把一种锁当成是一串数字,那么每横每竖每斜两端的数如果相邻,就必须位于中间的数之后。

接下来的问题就简单了,穷举呗(谁用组合数学解出来了请务必和我联系)。判断的程序很好写(虽然挺多行,总之就是在一个数组里搜索13,17,19,46,28,37,79,39的组合,看它们是否在2,4,5,5,5,5,8,6之后)。排列穷举起来还是有点麻烦的,我是用链表+迭代解决的。

另外经提醒,由于4个点以下的密码是不允许的。总之,得出的结果是 382069。对这个结果我还是比较有信心的(之前那个迭代部分有误)。如果有兴趣的话,源程序在这里

发表评论

电子邮件地址不会被公开。 必填项已用*标注