V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
• 请不要在回答技术问题时复制粘贴 AI 生成的内容
yasonyyx
V2EX  ›  程序员

一道有意思的手机九宫格手势密码的算法题,大家看看有好的思路吗

  •  1
     
  •   yasonyyx · 2014-12-31 11:39:45 +08:00 · 6012 次点击
    这是一个创建于 3645 天前的主题,其中的信息可能已经有所发展或是发生改变。

    今天看到一道九宫格,就是手机手势密码的题,题目大概是这样的:
    1、如果只设置2位密码,有多少种满足的密码,密码不能穿越,比如1 3之间穿过2,这是不允许的;2、如果变成N*M格,判断一个2位密码是否是满足要求的密码(要求同1),
    3、如果设置密码位数为9位,有多少种合适的密码,给出算法思路,并给出伪代码。

    我的想法是这样的:
    先检测当前位置在哪,再穷举所有移动记录次数。
    1、3*4+5*4+1*8=40.
    2、可以用一个N*M的数组保存1~N*M的值,然后看两位密码是否接触...
    3、实在没想到什么让自己觉得很好的思路...

    各位大神看看除了我这个思路外还有什么更高效的方法吗?

    6 条回复    2015-01-01 12:08:43 +08:00
    sam12321
        1
    sam12321  
       2014-12-31 11:46:08 +08:00
    已经按过的点貌似不能再按了
    gooffer
        2
    gooffer  
       2014-12-31 11:53:16 +08:00
    穷举吧,这个没方法的吧?
    deljuven
        3
    deljuven  
       2014-12-31 17:07:11 +08:00 via Android
    类似n皇后问题,回溯吧。。。还没有想到更好的思路。。。
    xylophone21
        4
    xylophone21  
       2014-12-31 18:21:28 +08:00
    歪个楼吧,为什么要计算密码是否满足要求?为什么要计算有多少种情况?

    密码保存模块校验? 这不是把密码保存和输入耦合吗?
    密码输入模块校验?人都能输进去了你担心这个干啥?怕UI bug?万一UI Bug了用更高级的密码重置一下不就OK了?不会没有吧?
    计算密码的安全性? 那就不需要在板子上计算了,找台服务器慢慢算就是,一次性的工作,为什么要高效?
    pheyer
        5
    pheyer  
       2015-01-01 12:05:17 +08:00
    第1题,九宫格从左上角顶点开始,从左到右从上到下分别命令为A, B, ..., I, J。统计规则:每个点只统计右方,右下方,下方,左下方的连接点。则A点的连接点个数为3个,B点的连接点为4个,C点的连接点为2个,D、E、F与A、B、C一致,H和I分别为一个。
    这样就能找到规律了吧:(n-1)*(3+(m-2)*4+2) + m-1

    第2题,如果是4宫格,合适的密码为3^9吗?感觉有点难度
    pheyer
        6
    pheyer  
       2015-01-01 12:08:43 +08:00
    点过的好像不能再点吧,那就不是3^9了。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   5355 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 27ms · UTC 09:11 · PVG 17:11 · LAX 01:11 · JFK 04:11
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.