- 注册时间
- 2011-3-2
- 最后登录
- 1970-1-1
- 威望
- 星
- 金币
- 枚
- 贡献
- 分
- 经验
- 点
- 鲜花
- 朵
- 魅力
- 点
- 上传
- 次
- 下载
- 次
- 积分
- 836
- 在线时间
- 小时
|
发表于 2014-3-18 04:50:01
|
显示全部楼层
用\(x_i\)表示线段长度,将线段长度排序,即
\(1 < \cdots \leq x_i \leq \cdots \leq x_j \leq \cdots \leq x_k \leq \cdots <55 \)
假设没有任何三条线段能构成三角形,
那么对于任意的\(i < j < k \),有\(x_i+x_j \leq x_k\),只需\(x_k \ge x_{k-2}+x_{k-1}\)即可
即任意给定\((x_i,x_j)\),那么\(x_k\)不能位于禁止区间\([x_{k-1},x_{k-2}+x_{k-1})\)内,否则构成三角形
而\(x_k\)影响的禁止区间为\([x_{k+1},x_{k}+x_{k+1})\)
所以最小化每个\(x_k\),能最小化禁止区间的总长度
现在用贪婪法,求出\(x_k\)的禁止区间总长度所能达到的最小值
先取\((x_1,x_2)\),那么产生的禁止区间为\([x_2,x_1+x_2)\)
要使禁止区间的总长度最小化,那么\((x_1,x_2) \to (1,1)\)
因为若\((x_1,x_2)\)不位于\((1,1) \)处,
那么总是可以唯一的将\((x_1,x_2)\)调整到区间的左边端点\((1,1)\)处,使得禁止区间\([x_2,x_1+x_2)\)的长度不变或减小,
接着,选择\(x_3\),应使得\(x_3 \ge x_2+x_1\),要使得\(x_3\)影响的禁止区间\([x_4,x_3+x_4)\)长度最小,只能取\(x_3=x_2+x_1\)
同理,选择\(x_k\),应使得\(x_k \ge x_{k-2}+x_{k-1}\),要使得\(x_k\)影响的禁止区间\([x_{k+1},x_{k}+x_{k+1})\)长度最小化,
只能取:
\(x_k = x_{k-2}+x_{k-1}\)
上式为斐波那契数列,由此得:
\[\begin{align*}x_1&=1,&x_2&=1,&x_3&=2,&x_4&=3,&x_5&=5, \\
x_6&=8,&x_7&=13,&x_8&=21,&x_9&=34,&x_{10}&=55.\end{align*}\]
产生的禁止区间为\([1,55]\),其总长度能取到的最小值为\(55-1=54\)
即不会构成三角形的必要条件是线段长度区间长度\(\ge 54\),
而题目条件中给出的线段长度区间为\((1,55)\),其区间长度\(<54 \)
所以存在一条线段,其长度在禁止区间中,能找到解 |
|