一道笔试题!

kaios

一个5*5*5的立方体,要切成125个1*1*1的小立方体,最少切几刀?(切块可以随意叠放)
我写的是9刀,不过感觉这个答案太常规了!应该是更少!

gtkmm

常规想法，９确实是最小的值。

如果我们把切一刀，想像成把一个物体分成两半，这样的动作，
那么，把如下的形状，分为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刀是足够的。

mo_yuan_ming

2.5+2.5=6？

yecheng_110

我想到最少的是6刀

gtkmm

原帖由 kaios 于 2008-8-1 16:27 发表
一个5*5*5的立方体,要切成125个1*1*1的小立方体,最少切几刀?(切块可以随意叠放)
我写的是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步。

gtkmm

原帖由 yecheng_110 于 2008-8-1 17:57 发表
我想到最少的是6刀

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

kewenliang

这是几何题还是程序设计题啊？

blackuhlan

一刀最多分成两半
2^6=64<125<128=2^7,所以最少不能少于7刀,但最少是不是7刀没验证

action08

9刀，少不起吧？

blizzard213

原帖由 kaios 于 2008-8-1 16:27 发表
一个5*5*5的立方体,要切成125个1*1*1的小立方体,最少切几刀?(切块可以随意叠放)
我写的是9刀,不过感觉这个答案太常规了!应该是更少!

不要想得太神秘
average的智商加严谨好学可以胜任程序员