开锁问题 --- 魔方最少覆盖问题

rosebud

我要看[em02][em02][em02]

lok

頂一下~~~

ggglgq

好主题，固顶。原来“开锁问题”就是“魔方最少覆盖问题”呀，楼主厉害！[em17] 建议大家再进一步研究一下以下两个问题：

一把密码锁，有n位数字（ 0 - 9 ），现已损坏，只要k位数字对，就能打开。 现在，密码忘记了，问：最少试多少次，就肯定能打开锁？（ k < n ）

一把密码锁，有n位数字（ 0 - P ），现已损坏，只要k位数字对，就能打开。 现在，密码忘记了，问：最少试多少次，就肯定能打开锁？（ P > 0， k < n ）

noski

最少的还在考虑中, 我算个试最多的次数:

试最多的次数就是把所有打不开的都试个遍, 再加一次.

0~9一共十个数, 在三个位置上排列的情况有10*10*10=1000种;

"对对错"的情况有10种, "对错对"的情况有10种, "错对对"的情况有10种;

在这三种能开锁的情况中, "对对对"的情况计算了3次;

能开锁的情况有(3*10-2)种;

所以最多试1000-(3*10-2)+1 次就开了.

锁有3位数字, 每一位有N个数字可选的话, 比如题中是N=10, 则公式为:

N^3-3*N+3

想看看和魔方的关系~[em01]

[此贴子已经被作者于2005-5-16 12:47:37编辑过]

还猪哥哥

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

noski

以下是引用hw294在2005-4-28 13:56:04的发言：

先从最简单的考虑，比如说每个转盘只有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次。[em05][em05]

对的! 答案也是这样

[此贴子已经被作者于2005-5-18 9:11:01编辑过]

大烟头

以下是引用hw294在2005-5-13 13:44:25的发言：

只试下面的50次，就一定打开锁了。做小偷也要想着办法省力点嘛！[em07]

(0,0,0)(0,1,4)(0,2,3)(0,3,2)(0,4,1)
(1,0,1)(1,1,0)(1,2,4)(1,3,3)(1,4,2)
(2,0,2)(2,1,1)(2,2,0)(2,3,4)(2,4,3)
(3,0,3)(3,1,2)(3,2,1)(3,3,0)(3,4,4)
(4,0,4)(4,1,3)(4,2,2)(4,3,1)(4,4,0)

(5,5,5)(5,6,9)(5,7,8)(5,8,7)(5,9,6)
(6,5,6)(6,6,5)(6,7,9)(6,8,8)(6,9,7)
(7,5,7)(7,6,6)(7,7,5)(7,8,9)(7,9,8)
(8,5,8)(8,6,7)(8,7,6)(8,8,5)(8,9,9)
(9,5,9)(9,6,8)(9,7,7)(9,8,6)(9,9,5)

不可能。

如：密码为（0、5、X) 的锁头，用上面数据好象不行吧。

大烟头

哦，是我题目没看清楚，我以为是其中一个密码坏了[em06]，现在明白了。

独酌你心情不好可以理解，可惜我在论坛里找不到回收站，可能权限不够，我己建议恢复你的贴子:《笨人的天真——傻瓜转法》

noski

我把这五十个点画到一个立方体里面，这样可能更直观一些。

(0,0,0)(0,1,4)(0,2,3)(0,3,2)(0,4,1)
(1,0,1)(1,1,0)(1,2,4)(1,3,3)(1,4,2)
(2,0,2)(2,1,1)(2,2,0)(2,3,4)(2,4,3)
(3,0,3)(3,1,2)(3,2,1)(3,3,0)(3,4,4)
(4,0,4)(4,1,3)(4,2,2)(4,3,1)(4,4,0)

(5,5,5)(5,6,9)(5,7,8)(5,8,7)(5,9,6)
(6,5,6)(6,6,5)(6,7,9)(6,8,8)(6,9,7)
(7,5,7)(7,6,6)(7,7,5)(7,8,9)(7,9,8)
(8,5,8)(8,6,7)(8,7,6)(8,8,5)(8,9,9)
(9,5,9)(9,6,8)(9,7,7)(9,8,6)(9,9,5)

由各个方向的视图可见，这些点并不是完全覆盖整个立方体，而是只覆盖了一半。如图：