注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

互联网产品经理的窝

梦想社:一个人为了梦想,始终没有停下自己的脚步

 
 
 

日志

 
 

计算安卓手机的屏幕锁有多少种形状组合 (转)  

2012-05-07 14:39:06|  分类: python |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

原文

我前几天偶然想到一个组合数学/算法问题:安卓手机的屏幕锁是3*3的9点矩阵,相邻的点可以用一条直线连接,但每个点不可以重复连接。如果必须连接4个点(含4个点)以上才算一个有效的形状,一共有多少种形状组合?

我在网上查到“果壳”去年有篇相关文章,《智能手机的密码总共有多少种》用穷举法“傻”算出了一个结果(不过其结果可能有错,请对比后面我的源程序和计算结果)。我不欣赏缺乏思考的穷举法,所以试着自己动手编程序计算,结果发现这个问题并不像看起来那么难,程序的核心逻辑甚至不到10行代码(Python)。先看一下我的计算结果。

计算安卓手机的屏幕锁有多少种形状组合 (转) - 梦想社 - 梦想社

相邻的点细分有2类,以上图1号点为例:蓝色箭头所指的是直观的、大部分人用的近点,红色箭头所指的是不直观的、很少人用的远点。我分别计算了只用近点(下图蓝色方块)和用全部点(下图红色方块)、从1点到9点的各种长度下,一共能有多少种形状组合,汇总在下图中。
计算安卓手机的屏幕锁有多少种形状组合 (转) - 梦想社 - 梦想社

从图中可以看出来,只用近点的组合(我称为“懒惰”组合)远远少于用全部点的组合,如果再只用4个或5个点,这样的密码安全性并不高。为了密码安全,我推荐您使用8点全部组合方式。

再看一下我的程序结构,我用Python语言根据经典“图”算法(单向、无权重)来计算这个3*3的9点矩阵:9个点从1到9编号(源程序第5行);每个点预设相应的邻居点(源程序第8~18行);函数scan(源程序第44~52行)从任意一点起递归搜索所有可能的组合;函数log(源程序第37~41行)用文本树格式记录找到的组合;主程序(源程序第55~57行)针对9个不同的起点调用scan函数9次,最后打印计算结果。

我已经把这个小程序的Python源码和计算出来的全部组合上传到GitHub,请点这里查看、下载或修改。

计算安卓手机的屏幕锁有多少种形状组合 (转) - 梦想社 - 梦想社

最后还有个小遗憾:我的这个小程序算法复杂度有点高 O(n!),不知道组合数学有没有更好的办法来分析这个问题。
 
  评论这张
 
阅读(186)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017