种树

flash

一个农夫有一块 100 x 100 公尺的正方形土地。他打算在那块地种树。为了将来可令每棵树有生长的空间，在种植时每棵小树之间的距离必须至少10公尺。假设每棵小树的树干直径等于零，小树可以种植在土地的交界处；请问那个农夫可最多可种几棵小树？

pipi

答案是：121 棵小树。
做法：在 100 x 100 公尺的正方形土地画上11条＂横＂线，11条＂直＂线，且让最邻近的两条＂横＂线（或＂直＂线）相距10公尺。（所以，11条＂横＂线 及 11条＂直＂线 是最 optimal 了）
由此，我们可得121交界点。在每个交界点处种上 1 棵小树，便行。

flash

pipi 于 25-3-2004 09:14  说 :
答案是：121 棵小树。
做法：在 100 x 100 公尺的正方形土地画上11条＂横＂线，11条＂直＂线，且让最邻近的两条＂横＂线（或＂直＂线）相距10公尺。（所以，11条＂横＂线 及 11条＂直＂线 是最 optimal 了）
由 ...

抱歉 pipi网友，这还不是最optimal。

提示：须改进排法。

pipi

暂时改进的答案是：126 棵小树。

做法：
画上7条相距10*3^(1/2)公尺＂直＂线，11条相距10公尺＂横＂线.
(note: 第一条＂直＂线画在土地的交界处，
       最后一条＂直＂线画在土地的＂外边＂)
在每个直横的交界点处种上 1 棵小树， 可得 66 棵小树。

然后，在这60个 10*3^(1/2)公尺 乘 10公尺 长方形的＂中心＂各别种上 1 棵小树，可得 60 棵小树。

所以共有126 棵小树。

flash网友，多多指教。在此谢过。

flash

答案还是不对，不过你的做法已经朝向正确的方向。pipi 网友加油！

pipi

再次改进的答案是：127 棵小树。

做法：
画上7条相距10*3^(1/2)公尺＂直＂线，11条相距10公尺＂横＂线.
(note: 第一条＂直＂线画在土地的交界处，
       最后一条＂直＂线画在土地的＂外边＂)
在每个直横的交界点处种上 1 棵小树， 可得 66 棵小树。

然后，在这50个（除了最后 10个）
10*3^(1/2)公尺 乘 10公尺 长方形的＂中心＂各别种上 1 棵小树，可得 50 棵小树。

再然后， 最边沿的土地的交界处可种 11 棵小树。

所以共有127 棵小树。

flash网友，多多指教。再次谢过。

無聊人

不知道pipi网友解法如何？我都看不懂的？

我拿的答案是221。奇怪了……

flash网友的正解又是什么呢？

pipi

無聊人 于 25-3-2004 07:28 PM  说 :
不知道pipi网友解法如何？我都看不懂的？

我拿的答案是221。奇怪了……

flash网友的正解又是什么呢？

how to get 221??

無聊人

乱乱猜的。你能解释一下你的答案吗？

斷羽鳥

哟! 楼上的你酱乱乱猜那行哦! ...
想说你们怎么都用四方的grid啊? ... 我猜想(猜吧了啊, 我也不知答案的), 如果要最密的排法, 应该和regular三角形grid有关, 楼主我的方向对了吗?????

flash

pipi网友和無聊人网友，答案不是１２７ 或 ２２１。

斷羽鳥网友，排法牵涉到等边三角形和正方形配合。

先让大家尝试，过几天我会把正解贴上来。

情~風

126?
用等邊三角形頂點的分佈考慮

flash

情~風网友,答案不是 126。排法牵涉到等边三角形和正方形配合。明天我会把正解贴上来。

pipi

强烈期待！

flash

正确的答案是 128。排法如下：

0    A    B    A    B    A    B    A    B    A    B    A

        C    C    C    C    C    C    C    C    C    C

     A    B    A    B    A    B    A    B    A    B    A

        C    C    C    C    C    C    C    C    C    C

     A    B    A    B    A    B    A    B    A    B    A

        C    C    C    C    C    C    C    C    C    C

     A    B    A    B    A    B    A    B    A    B    A

        C    C    C    C    C    C    C    C    C    C

70   A    B    A    B    A    B    A    B    A    B    A   

80   A    B    A    B    A    B    A    B    A    B    A   

90   A    B    A    B    A    B    A    B    A    B    A   

100  A    B    A    B    A    B    A    B    A    B    A   

把 A 种植在土地的交界处，A和B的距离是 10 公尺；所以第一排有 11 棵小树。把 A，B，C 排成等边三角形，A和B，A和C, B和C的距离是 10 公尺;如此一来第二排便有 10 棵小树；重复这样的排法４次，在７０，８０，９０和１００公尺的地方，每排种植 11 棵小树。

pipi

终于等到答案了...
不错的排法...
不过，我有个问题：
如何证明 128 是最 optimal??
就这个排列法，我们只能说 >=128
(也就是说它的下限(lower bound))
如何证明 128 是它的上限(upper bound)呢？

flyingfish

让x为正方排的数量,y为三角排的数量.

依题意:
10x + 5(3^0.5)y <=100
maximise  11*(x+1+floor(y/2))+10*ceiling(y/2)

x, y,  11*(x+1+floor(y/2))+10*ceiling(y/2)
1,10,127
2,9,127
3,8,128
4,6,118
5,5,118
6,4,119
7,3,119
8,2,120
9,1,120
10,0,121

一些解释:
1.正方排高=10,三角排高=5*(3^0.5)

2.第一排能排11.

3.三角排有两种排法,V(倒三角)和^(直三角)
V(倒三角)排底部能排10.
^(直三角)排底部能排11.

4.假设有n个三角排,会是先排V(倒三角)排,然后是^(直三角)排,
所以V(倒三角)排有ceiling(n/2)排,
^(直三角)排有floor(n/2)排..
例:5个三角排,会有3个V(倒三角)排,2个^(直三角)排.

麻烦网友们看看有无漏洞...