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

dragonpig

" 上面所说的36个格点至多覆盖36*10+36*4*2=648个格点"
请问这个×4×2怎么出来的？

bawanglb

按照题目说的，比如密码是“123”则须“12”“13”“23”就可以了，当然“21”“32”“31”也可以，那么就是说3个密码数字，只要猜队2个就好了，而我们也只试两个数字，用组合知，要10乘10再除以2，即50下就可以了，因为题目说的是与数字顺序没关系的。

小楼

1000组合中。只有30个组打开锁

魔方初心者

感觉题目出得不太好~题目说到有一条件是“肯定能开锁”但解答那里是有选择的去试的，这里密码位数少就当然能用这种方法，如果位数多了就不一样了~！就假设变成6位吧，那时候作出筛选来试比一个一个试可能更慢，以楼主在14楼的发言作例子，楼主用这个简单例子说明未必要N*N次，但实际上题目说了是“肯定能开”做了选择性的当然了，倒不如直接选了正确密码就一次OK了~~只有两位当然可以知道001和110覆盖了其他，但假设你不知道这两个数是覆盖了所谓其他数呢？就好像6位密码一样，知道那些数合起来覆盖所有其他数吗？这太麻烦了吧，如果在不知道的情况下就只能慢慢试，如果试两次，从000开始，那试了000，001是不是能开密码为101的呢？不能吧。

所以能符合“肯定能开”这个条件的尝试方法应该是N*N-1的

kaitoKID

QUOTE:

以下是引用bawanglb在2007-1-22 10:58:27的发言：
按照题目说的，比如密码是“123”则须“12”“13”“23”就可以了，当然“21”“32”“31”也可以，那么就是说3个密码数字，只要猜队2个就好了，而我们也只试两个数字，用组合知，要10乘10再除以2，即50下就可以了，因为题目说的是与数字顺序没关系的。

我新手哈，但觉得照题目的意思，显然是有关系的，不仅数字对，位置也要对，好像和某些彩票中奖规则一样，还和文曲星里的猜数字游戏一样：）

“123”的话，当然“21*”“*32”“31*”都是开不了的……

另外，如果照bawanglb所想的，只要有任意两个数字对，而不管位置的话，也要花点时间算算的哈：

共10*9*8/6+10*9*3/3+10=220种组合，其中100种是有重复数字的

001 112 223 334 445 556 667 778 889 990

就把所有重复数字的（100种），以及有相邻数字的不重复组合（70种）全覆盖了

剩下50种（前两位数省略写啦）

024、5、6、7、8
035、6、7、8
046、7、8
057、8
068

135、6、7、8、9
146、7、8、9
157、8、9
168、9
179

246、7、8、9
257、8、9
268、9
279

357、8、9
368、9
379

468、9
479

579

然后就是我头痛的地方了——我不知道怎么算，用感觉凑出来的：

024 135 036 147 257 369 068

这7组数字，可以完全覆盖这些

所以我至多需要17次，有大侠帮我看看，可不可能再少点啊！或者有完备的算法，而不是感觉！！！谢谢啦

kaitoKID

QUOTE:

以下是引用魔方初心者在2007-2-23 0:57:03的发言：

感觉题目出得不太好~题目说到有一条件是“肯定能开锁”但解答那里是有选择的去试的，这里密码位数少就当然能用这种方法，如果位数多了就不一样了~！就假设变成6位吧，那时候作出筛选来试比一个一个试可能更慢，以楼主在14楼的发言作例子，楼主用这个简单例子说明未必要N*N次，但实际上题目说了是“肯定能开”做了选择性的当然了，倒不如直接选了正确密码就一次OK了~~只有两位当然可以知道001和110覆盖了其他，但假设你不知道这两个数是覆盖了所谓其他数呢？就好像6位密码一样，知道那些数合起来覆盖所有其他数吗？这太麻烦了吧，如果在不知道的情况下就只能慢慢试，如果试两次，从000开始，那试了000，001是不是能开密码为101的呢？不能吧。

所以能符合“肯定能开”这个条件的尝试方法应该是N*N-1的

数学题就是这样哈，追求极致的最优化，而不是应用时的最快：）当然，你算过一次了，以后再有坏掉的锁试起来就快啦，哈哈——

就像魔方，要算出最少步数来翻，速度绝对比不过以自己最习惯的公式来翻，即使要多翻的次数是最少步数的几倍，也不会比研究最少步数的时间来得多。是吧？哈哈，我魔方新手

kaitoKID

楼主hw294的题目真有意思，就算是理解错了方向，也都是有趣的难题哦……

noski的三维图很让人豁然开朗啊！……

只是，如果要求：

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

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

 岂不是要用到多维空间？

[em06][em06]

123455

[em01][em01][em01][em01]

haohmaru

最少.......
应该是一次吧

汕头=老沙

不错不错不错不错不错不错不错不错不错不错不错不错不错不错不错不错