魔方吧·中文魔方俱乐部

 找回密码
 注册
搜索
热搜: 魔方
楼主: hw294

开锁问题 --- 魔方最少覆盖问题 [复制链接]

Rank: 3Rank: 3

积分
831
帖子
110
精华
0
UID
429
性别
发表于 2005-5-13 14:40:35 |显示全部楼层
我要看[em02][em02][em02]
...缠缠绵绵...柴米油盐...缠缠绵绵...柴米油盐...

使用道具 举报

Rank: 7Rank: 7Rank: 7

积分
3306
帖子
1333
精华
1
UID
489
性别

十四年元老

发表于 2005-5-13 15:32:07 |显示全部楼层
頂一下~~~

使用道具 举报

Rank: 8Rank: 8

积分
4787
帖子
1876
精华
12
UID
93
性别

魔方理论探索者 十年元老

发表于 2005-5-15 09:25:49 |显示全部楼层

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

一把密码锁,有n位数字( 0 - 9 ),现已损坏,只要k位数字对,就能打开。 现在,密码忘记了,问:最少试多少次,就肯定能打开锁?( k < n )

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

~~ 宇宙在旋转运动 ~~ 魔方在循环变换 ~~

使用道具 举报

银魔

宇宙起源

Rank: 7Rank: 7Rank: 7

积分
3197
帖子
1034
精华
12
UID
564
性别

魔方理论探索者 魔方破解达人 论坛建设奖 六年元老

发表于 2005-5-15 23:55:15 |显示全部楼层

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

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

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编辑过]

The Answer to the Ultimate Question of Life, the Universe, and Everything 

使用道具 举报

Rank: 8Rank: 8

积分
5032
帖子
251
精华
1
UID
118
性别
居住地
广州市
兴趣爱好
速度

十年元老

发表于 2005-5-17 21:19:44 |显示全部楼层
足球彩票中的缩水(不是指条件过滤,而是纯粹的缩水)技术解决的就是这种问题。由于足球彩票的特殊性,每场结果只能是胜平负中的一个,也就是每一位有3个数字可选。这类问题是比较复杂的,基本没有通用的求最有优的方法

使用道具 举报

银魔

宇宙起源

Rank: 7Rank: 7Rank: 7

积分
3197
帖子
1034
精华
12
UID
564
性别

魔方理论探索者 魔方破解达人 论坛建设奖 六年元老

发表于 2005-5-18 08:59:07 |显示全部楼层
以下是引用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编辑过]

The Answer to the Ultimate Question of Life, the Universe, and Everything 

使用道具 举报

Rank: 10Rank: 10Rank: 10

积分
16322
帖子
6926
精华
47
UID
68
性别
兴趣爱好
结构

收藏爱好者 魔方破解达人 魔方结构大师 十年元老

发表于 2005-5-18 09:29:59 |显示全部楼层
以下是引用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) 的锁头,用上面数据好象不行吧。

使用道具 举报

积分
1393
帖子
228
精华
0
UID
142
性别
发表于 2005-5-18 19:08:12 |显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽

使用道具 举报

Rank: 10Rank: 10Rank: 10

积分
16322
帖子
6926
精华
47
UID
68
性别
兴趣爱好
结构

收藏爱好者 魔方破解达人 魔方结构大师 十年元老

发表于 2005-5-18 19:44:34 |显示全部楼层

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

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

使用道具 举报

银魔

宇宙起源

Rank: 7Rank: 7Rank: 7

积分
3197
帖子
1034
精华
12
UID
564
性别

魔方理论探索者 魔方破解达人 论坛建设奖 六年元老

发表于 2005-5-19 07:44:44 |显示全部楼层

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

(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)

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

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

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

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

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

The Answer to the Ultimate Question of Life, the Universe, and Everything 

使用道具 举报

您需要登录后才可以回帖 登录 | 注册

Archiver|手机版|魔方吧·中文魔方俱乐部

GMT+8, 2024-3-29 04:09

Powered by Discuz! X2

© 2001-2011 Comsenz Inc.

回顶部