免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
最近访问板块 发新帖
查看: 17132 | 回复: 65

[算法] 一道笔试题! [复制链接]

论坛徽章:
0
发表于 2008-08-01 16:27 |显示全部楼层
一个5*5*5的立方体,要切成125个1*1*1的小立方体,最少切几刀?(切块可以随意叠放)
我写的是9刀,不过感觉这个答案太常规了!应该是更少!

论坛徽章:
0
发表于 2008-08-01 17:30 |显示全部楼层
常规想法,9确实是最小的值。

如果我们把切一刀,想像成把一个物体分成两半,这样的动作,
那么,把如下的形状,分为1*1*1的需要的刀数为:
1*1*1=2^0    0刀     
2*1*1=2^1   1刀
2*2*2=2^3    3刀
8*8*8=2^9    9刀

5*5*5明显没有8*8*8复杂,因此,9刀是足够的。

论坛徽章:
0
发表于 2008-08-01 17:45 |显示全部楼层
2.5+2.5=6?

论坛徽章:
1
双子座
日期:2015-01-04 14:25:06
发表于 2008-08-01 17:57 |显示全部楼层
我想到最少的是6刀

论坛徽章:
0
发表于 2008-08-01 18:13 |显示全部楼层
原帖由 kaios 于 2008-8-1 16:27 发表
一个5*5*5的立方体,要切成125个1*1*1的小立方体,最少切几刀?(切块可以随意叠放)
我写的是9刀,不过感觉这个答案太常规了!应该是更少!

我可以试式证明一下,9是最小值。

假设有长方体A0,是a0*b0*c0大小的,我们用刀装备把这个物品分成1*1*1的。
把A0切一刀,所得两块,我们记体积较大的为A1。
同理,把An切一刀,所得到的,体积最大的那个物体为An+1

我们记An的长宽高为:( an,bn,cn)

随便切一刀,不妨切在an的边上了,则切成了两半:

( x, bn,cn)和( y,bn,cn)   x+y=an
x和y中较大的值,不会比an/2小。

因此,我们看出来,如下的变化:
(  a0,b0,c0)
(  a1,b1,c1)
(  a2,b2,c2)
.....
.....
(  an,bn,cn)
.....
.....
(   1,  1,  1)
就是保持两个数不变,把其中一个变小。变小,但不能小于上一个数的1/2.  (因为是两半中取大的)。
然而,不论怎么变,最终结果都是把每一列的数都变为1.

这么一来,
2^n变成1,要经过n步。  2^(n+1)要变成1,要经过n+1步,他们之间的值,经过的步数要大于n,而不能超过n+1,于是为n+1.
如此:

则:
( X,Y,Z),   的长方体,若:
2^a<=X<2^A
2^b<=Y<2^B
2^c<=Z<2^C
则需a+b+c步。
令X=Y=Z=5.
2^2<5<2^3
则a=b=c=3
需要3+3+3=9步。

论坛徽章:
0
发表于 2008-08-01 18:14 |显示全部楼层
原帖由 yecheng_110 于 2008-8-1 17:57 发表
我想到最少的是6刀

6刀最多能把物体分为2^6=64块。明显不符。

论坛徽章:
0
发表于 2008-08-01 18:22 |显示全部楼层
这是几何题还是程序设计题啊?

论坛徽章:
0
发表于 2008-08-01 19:14 |显示全部楼层
一刀最多分成两半
2^6=64<125<128=2^7,所以最少不能少于7刀,但最少是不是7刀没验证

论坛徽章:
223
2022北京冬奥会纪念版徽章
日期:2015-08-10 16:30:32操作系统版块每日发帖之星
日期:2016-05-10 19:22:58操作系统版块每日发帖之星
日期:2016-02-18 06:20:00操作系统版块每日发帖之星
日期:2016-03-01 06:20:00操作系统版块每日发帖之星
日期:2016-03-02 06:20:0015-16赛季CBA联赛之上海
日期:2019-09-20 12:29:3219周年集字徽章-周
日期:2019-10-01 20:47:4815-16赛季CBA联赛之八一
日期:2020-10-23 18:30:5320周年集字徽章-20	
日期:2020-10-28 14:14:2615-16赛季CBA联赛之广夏
日期:2023-02-25 16:26:26CU十四周年纪念徽章
日期:2023-04-13 12:23:10操作系统版块每日发帖之星
日期:2016-05-10 19:22:58
发表于 2008-08-01 21:00 |显示全部楼层
9刀,少不起吧?

论坛徽章:
0
发表于 2008-08-01 21:07 |显示全部楼层
原帖由 kaios 于 2008-8-1 16:27 发表
一个5*5*5的立方体,要切成125个1*1*1的小立方体,最少切几刀?(切块可以随意叠放)
我写的是9刀,不过感觉这个答案太常规了!应该是更少!


不要想得太神秘
average的智商加严谨好学可以胜任程序员
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122 niuxiaotong@pcpop.com 17352615567
未成年举报专区
中国互联网协会会员  联系我们:huangweiwei@itpub.net
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP