魔方吧·中文魔方俱乐部

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

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

Rank: 1

积分
11
帖子
8
精华
0
UID
23927
性别
保密
发表于 2008-3-4 02:24:03 |显示全部楼层
<P>密码是1-9的话。太简单了9个里任取2个:9×8/2×1=36</P>
<P>密码是0-9的话。太简单了10个里任取2个:10×9/2×1=45</P>

使用道具 举报

Rank: 1

积分
38
帖子
36
精华
0
UID
19129
发表于 2008-3-7 23:47:03 |显示全部楼层
最少试一次,恰好蒙对了,楼主说呢?

使用道具 举报

积分
2
帖子
2
精华
0
UID
24532
性别
保密
发表于 2008-3-8 23:06:28 |显示全部楼层
从000-099总共100次

使用道具 举报

Rank: 4

积分
1393
帖子
228
精华
0
UID
142
性别
发表于 2008-4-9 18:03:13 |显示全部楼层
<P>
原帖由 <I>dragonpig</I> 于 2007-1-4 23:00 发表 <A href="http://bbs.mf8-china.com/redirect.php?goto=findpost&amp;pid=37672&amp;ptid=813" target=_blank><IMG alt="" src="http://bbs.mf8-china.com/images/common/back.gif" border=0></A> " 上面所说的36个格点至多覆盖36*10+36*4*2=648个格点"请问这个×4×2怎么出来的?
</P>
<P>&nbsp;</P>
<P>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 这个要联系前面的来看,底层放4个点后,上面的36个点要补充完底层的空缺,要不然底层就无法完全覆盖。然后算这36个点覆盖范围的时候,从垂直上看可以覆盖36*10个格点,<FONT color=red>那么剩下的空全部在横4竖4的8个立面上</FONT>,那么这36个点每个点和这8个面最多只能有8个交点(垂直的36*10已经算过了),所以是36*4*2,也就是36*8。</P>
<P>&nbsp;</P>
<P>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 这个问题提的不错,说明你确实认真思考了</P>
<P>&nbsp;</P>
<P>&nbsp;</P>

使用道具 举报

积分
2
帖子
2
精华
0
UID
41076
性别
保密
发表于 2008-8-24 19:21:44 |显示全部楼层
假如密码锁有N个元素的话,那么不失一般性,题目要求的密码应该是在00——NN之间的一位,即我们如果放弃第三位的话,至少要试(N+1)×(N+1)次,不过由于还有一位,则我们可以这样设置:00N,01(N-1),02(N-2).......此时若N为奇数时,以9为例,要10×10%2=50,N为偶数时,以8为例,8×8%2+9=41~

使用道具 举报

Rank: 7Rank: 7Rank: 7

积分
1298
帖子
925
精华
0
UID
37321
性别
保密
发表于 2008-8-24 22:21:16 |显示全部楼层
题目的问题是,至少多少步能保证开锁。这么考虑,题目也就是把不能开锁的所有都算出来,然后再试一次就可以了。所以应该是1.只对一个密码:3*9*9;2.一个都不对:9*9*9;一共是9*9*9+9*9*3+1=973次

使用道具 举报

Rank: 7Rank: 7Rank: 7

积分
1298
帖子
925
精华
0
UID
37321
性别
保密
发表于 2008-8-24 22:25:02 |显示全部楼层
cube-master考虑错了啊,在试的过程是没有得考虑的,所以你不能说第三个键盘不转的,一定要考虑所有打不开的情况。

使用道具 举报

Rank: 2

积分
421
帖子
233
精华
2
UID
25681
性别
保密
发表于 2008-8-25 10:54:01 |显示全部楼层
<P>答案已经有了,如下:</P>
<P>(0,0,0)(0,1,4)(0,2,3)(0,3,2)(0,4,1)</P>
<P>(1,0,1)(1,1,0)(1,2,4)(1,3,3)(1,4,2)</P>
<P>(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)</P>
<P>(4,0,4)(4,1,3)(4,2,2)(4,3,1)(4,4,0)<BR>(5,5,5)(5,6,9)(5,7,8)(5,8,7)(5,9,6)</P>
<P>(6,5,6)(6,6,5)(6,7,9)(6,8,8)(6,9,7)</P>
<P>(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)</P>
<P>(9,5,9)(9,6,8)(9,7,7)(9,8,6)(9,9,5)<BR>但答案不是唯一的,给出得到答案的一个思路吧,<IMG alt="" src="http://bbs.mf8-china.com/images/smilies/default/loveliness.gif" border=0 smilieid="28"> </P>
<P>&nbsp;</P>
<P>采用的数学原理是抽屉原理,因为密码有三位,所以要设置两个抽屉,也就是随机把0~9的数字分为两组,例如:0~5和6~9两组,则密码中的三位数字一定有两位落在同一个组内,我们就利用这两个同组数字来开锁。这两个数字的变化情况为5*5=25种,位置变化为ab*,a*b,*ab三种,共25*3=75种,如果加入第三位每一种可以代替三种,所以可以构造75/3=25种来代替全部变化。同理如果落入第二个抽屉,还需要25种情况,所以一共需要25*2=50种情况。</P>
<P>&nbsp;</P>
<P>看看上面的答案,可以发现就是两个抽屉的各25种情况。在每一种情况当中,先固定一位(上面的答案固定的是第二位),然后让另一位在固定位的基础上轮换(即第一位在第二位基础上轮换),最后一位在前两位的基础上进行轮换(即第三位在第一、二位的基础上轮换)。</P>
<P>&nbsp;</P>
<P>如果有人对此问题的数值解法感兴趣,可以参考<A href="http://lab.ntsec.gov.tw/activity/race-2/International2004/pdf/0104.pdf"><FONT color=blue>http://lab.ntsec.gov.tw/activity/race-2/International2004/pdf/0104.pdf</FONT></A></P>
<P>关于此问题,其中有详细的结论。<FONT color=red>N为偶数时,F(N)=(N/2)^2+(N/2)^2=N^2/2;N为奇数时,F(N)=(N^2+1)/2</FONT>。</P>
<P>&nbsp;</P>
<P>PS:55#的构造能不能多写点,看不出构造的规律。如果后面只是改变第一个数,第二个数总是小于第三个数且不变(如果不小于就100种了),那么类似054这种组合怎么能试出来呢?也许是我理解得不对,o(∩_∩)o...</P>

[ 本帖最后由 金眼睛 于 2008-8-25 10:57 编辑 ]

使用道具 举报

积分
3
帖子
3
精华
0
UID
41601
性别
发表于 2008-8-27 13:11:36 |显示全部楼层

1000次.因为不知道第几位坏了

123的锁,12*,13*,*23.首先要知道是哪个位置错了吧.个人觉得这和锁没坏一个样.
所以个人认为答案是10*10*10=1000.
前提,开锁数字是0-9这十个数

使用道具 举报

积分
4
帖子
4
精华
0
UID
37862
性别
保密
发表于 2008-9-4 21:32:22 |显示全部楼层
覆盖的问题没有介绍清楚,大家也都没有理解好!不是吗?你自己也搞清楚了吗?

使用道具 举报

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

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

GMT+8, 2019-1-19 15:05

Powered by Discuz! X2

© 2001-2011 Comsenz Inc.

回顶部