rosebud 发表于 2005-5-13 14:40:35

我要看

lok 发表于 2005-5-13 15:32:07

頂一下~~~

ggglgq 发表于 2005-5-15 09:25:49

<P>
  
    好主题，固顶。原来“开锁问题”就是“魔方最少覆盖问题”呀，楼主厉害！
建议大家再进一步研究一下以下两个问题：</P><P>
    一把密码锁，有n位数字（ 0 - 9 ），现已损坏，只要k位数字对，就能打开。
现在，密码忘记了，问：最少试多少次，就肯定能打开锁？（ k &lt; n ）</P><P>    一把密码锁，有n位数字（ 0 - P ），现已损坏，只要k位数字对，就能打开。
现在，密码忘记了，问：最少试多少次，就肯定能打开锁？（ P &gt; 0， k &lt; n ）</P>

noski 发表于 2005-5-15 23:55:15

<P>最少的还在考虑中, 我算个试最多的次数:</P>
<P>试最多的次数就是把所有打不开的都试个遍, 再加一次.</P>
<P>0~9一共十个数, 在三个位置上排列的情况有10*10*10=1000种;</P>
<P>"对对错"的情况有10种, "对错对"的情况有10种, "错对对"的情况有10种;</P>
<P>在这三种能开锁的情况中, "对对对"的情况计算了3次;</P>
<P>能开锁的情况有(3*10-2)种;</P>
<P>所以最多试1000-(3*10-2)+1 次就开了.</P>
<P>锁有3位数字, 每一位有N个数字可选的话, 比如题中是N=10, 则公式为:</P>
<P>N^3-3*N+3</P>
<P>想看看和魔方的关系~</P>
[此贴子已经被作者于2005-5-16 12:47:37编辑过]

还猪哥哥 发表于 2005-5-17 21:19:44

足球彩票中的缩水（不是指条件过滤，而是纯粹的缩水）技术解决的就是这种问题。由于足球彩票的特殊性，每场结果只能是胜平负中的一个，也就是每一位有3个数字可选。这类问题是比较复杂的，基本没有通用的求最有优的方法

noski 发表于 2005-5-18 08:59:07

<DIV class=quote><B>以下是引用<I>hw294</I>在2005-4-28 13:56:04的发言：</B><br>
<P>    先从最简单的考虑，比如说每个转盘只有0和1两个数字，那么密码共有以下8种可能：000，001，010，011，100，101，110，111。而只用001和110，只试两次就可打开，因为001管000，001，011，101这4种可能，而110管010，100，110，111剩下的这4种可能，所以只试两次就已打开锁了，而并非2*2=4次。</P></DIV>对的! 答案也是这样
[此贴子已经被作者于2005-5-18 9:11:01编辑过]

大烟头 发表于 2005-5-18 09:29:59

<DIV class=quote><B>以下是引用<I>hw294</I>在2005-5-13 13:44:25的发言：</B><BR>
<P>只试下面的50次，就一定打开锁了。做小偷也要想着办法省力点嘛！</P>
<P>(0,0,0)(0,1,4)(0,2,3)(0,3,2)(0,4,1)<BR>(1,0,1)(1,1,0)(1,2,4)(1,3,3)(1,4,2)<BR>(2,0,2)(2,1,1)(2,2,0)(2,3,4)(2,4,3)<BR>(3,0,3)(3,1,2)(3,2,1)(3,3,0)(3,4,4)<BR>(4,0,4)(4,1,3)(4,2,2)(4,3,1)(4,4,0)</P>
<P>(5,5,5)(5,6,9)(5,7,8)(5,8,7)(5,9,6)<BR>(6,5,6)(6,6,5)(6,7,9)(6,8,8)(6,9,7)<BR>(7,5,7)(7,6,6)(7,7,5)(7,8,9)(7,9,8)<BR>(8,5,8)(8,6,7)(8,7,6)(8,8,5)(8,9,9)<BR>(9,5,9)(9,6,8)(9,7,7)(9,8,6)(9,9,5)</P></DIV>
<P>不可能。
<P>如：密码为（0、5、X) 的锁头，用上面数据好象不行吧。

hw294 发表于 2005-5-18 19:08:12

大烟头 发表于 2005-5-18 19:44:34

<P>哦，是我题目没看清楚，我以为是其中一个密码坏了，现在明白了。</P><P>独酌你心情不好可以理解，可惜我在论坛里找不到回收站，可能权限不够，我己建议恢复你的贴子:《笨人的天真——傻瓜转法》</P>

noski 发表于 2005-5-19 07:44:44

<P>我把这五十个点画到一个立方体里面，这样可能更直观一些。</P>
<P>(0,0,0)(0,1,4)(0,2,3)(0,3,2)(0,4,1)<BR>(1,0,1)(1,1,0)(1,2,4)(1,3,3)(1,4,2)<BR>(2,0,2)(2,1,1)(2,2,0)(2,3,4)(2,4,3)<BR>(3,0,3)(3,1,2)(3,2,1)(3,3,0)(3,4,4)<BR>(4,0,4)(4,1,3)(4,2,2)(4,3,1)(4,4,0)</P>
<P>(5,5,5)(5,6,9)(5,7,8)(5,8,7)(5,9,6)<BR>(6,5,6)(6,6,5)(6,7,9)(6,8,8)(6,9,7)<BR>(7,5,7)(7,6,6)(7,7,5)(7,8,9)(7,9,8)<BR>(8,5,8)(8,6,7)(8,7,6)(8,8,5)(8,9,9)<BR>(9,5,9)(9,6,8)(9,7,7)(9,8,6)(9,9,5)</P>
<P></P>
<P>由各个方向的视图可见，这些点并不是完全覆盖整个立方体，而是只覆盖了一半。如图：</P>
<P><BR></P>
页: 1 2 [3] 4 5 6 7 8
查看完整版本: 开锁问题 --- 魔方最少覆盖问题