V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
这是一个专门讨论 idea 的地方。

每个人的时间,资源是有限的,有的时候你或许能够想到很多 idea,但是由于现实的限制,却并不是所有的 idea 都能够成为现实。

那这个时候,不妨可以把那些 idea 分享出来,启发别人。
sennes
V2EX  ›  奇思妙想

From 我的房门锁 To 算法题?

  •  
  •   sennes · 2015-11-26 23:52:08 +08:00 · 2860 次点击
    这是一个创建于 3266 天前的主题,其中的信息可能已经有所发展或是发生改变。

    http://senneszi.com/post/article/2015-11-26

    我不是搞算法的,然后这个题,不知道从哪里开始想。

    到底怎样才能没冗余的去破解这样一个串行序列检测。

    是不是有什么算法能得到这个最优解序列呢?

    12 条回复    2015-11-29 17:03:47 +08:00
    sennes
        1
    sennes  
    OP
       2015-11-26 23:53:48 +08:00
    是不是应该 move 到"程序员"那边会比较好?
    ybao
        2
    ybao  
       2015-11-27 10:36:14 +08:00
    这个题目有太多不明细的地方了,比如:有多少扇门需要设置的,或者说,密码的最短多少,最长多少等等。。
    sennes
        3
    sennes  
    OP
       2015-11-27 12:18:00 +08:00
    @ybao hi ,我觉得应该挺清楚的。
    有多少扇门需要设置的 → "使得任意房门都能打开"
    密码的最短多少,最长多少 → "用户设定的房门密码不超过 16 位数字"
    mathcoder23
        4
    mathcoder23  
       2015-11-27 13:11:46 +08:00
    真心脑洞大开啊。我假设最高是二位依然没有思路,感觉和动态规划,代数系统那方面有点儿关系啊。。。如果有解,希望通知哇。
    popo233
        5
    popo233  
       2015-11-27 17:44:30 +08:00   ❤️ 3
    想了一下两位密码的情况,想到了以前看过的七桥问题。于是这个问题可以转化为:

    一个圆上 10 个点,从某点出发不间断地画有向的线(起点终点都在点上),要求最后每两个点之间都有来回两条,每个点还得有个返回自身的,求画出这个图形的最短线段数

    如果能保证每种线段都只画一次,肯定最少了。假设可以,那么因为每个点上都有 10 条进入的, 10 条出去的,也就是“奇点”个数为 0 。根据七桥问题的那个结论,应该是可以一笔画下来的。

    列一下 4 个数的:
    11213142233244341 ,共 4*4+1 位
    6 个数的:
    1121314151662636465545352232443342561 ,共 6*6+1 位
    10 个数应该需要 101 位,不列了,套路一样。


    密码位数更多的情况暂时不考虑了.. 有勇士可以试试。
    exch4nge
        6
    exch4nge  
       2015-11-27 18:29:43 +08:00 via iPhone
    @popo233 感谢思路!自己想半天也没想出来。

    具体位数的话我来补充下,假设有 m 个字符集 n 位密码的话,在 m 为偶数的情况下,需要 pow(m, n) + n - 1 位。奇数情况的话肯定比这更多……
    exch4nge
        7
    exch4nge  
       2015-11-27 18:35:10 +08:00 via iPhone
    额,再想了想好像没法把问题映射到七桥问题吧…… 上述回复先无视掉吧……
    ryrubyy
        8
    ryrubyy  
       2015-11-28 13:18:33 +08:00
    话说 MIUI 锁屏解锁是不是也是串行序列检测呢?
    zhly
        9
    zhly  
       2015-11-28 13:48:08 +08:00   ❤️ 3
    wy315700
        10
    wy315700  
       2015-11-28 13:52:10 +08:00
    @popo233
    不对吧,你这个 4 位数的 不包含 1234 这个序列啊
    skydiver
        11
    skydiver  
       2015-11-28 14:02:46 +08:00
    @zhly 哈哈哈原来问题早就有解了……
    Pan940425
        12
    Pan940425  
       2015-11-29 17:03:47 +08:00   ❤️ 1
    @wy315700 认真看嘛,人家说的“ 4 位数”是指数字只有“ 1,2,3,4 ”四个数,而最大的位数 @popo233 在回复的第一句就说了,“两位密码的情况”,所以需要有的组合只有 11,12,13,14,21,22,23,24,31,32,33,34,41,42,43,44 共计 16 种,而 @popo233 提供的答案“ 11213142233244341 ”中,以上组合均包含。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   5516 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 30ms · UTC 08:38 · PVG 16:38 · LAX 00:38 · JFK 03:38
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.