专栏文章

论如何n等分一条线段

算法·理论参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性,并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miq4m3us
此快照首次捕获于
2025/12/03 22:52
3 个月前
此快照最后确认于
2025/12/03 22:52
3 个月前
查看原文
众所周知,想要二等分一条线段是比较容易的,只需要做一条中垂线即可,那么三等分、四等分甚至 nn 等分,要怎么办呢?我们先从三等分看起。

观察

如图,有一条线段 ABAB 让我们在它的上面随意点上两个点 MMNN , 就长这样: 那么我们接下来就进行如下操作:
  1. 将点 MM 移至 ANAN 中点;
  2. 将点 NN 移至 MBMB 中点; 重复执行以上操作,我们会发现,MM 和点 NN 竟然在一直靠近线段 ABAB 的三等分点,下图就是执行 55 次以后的状况:

猜想

那么我们于是就生发出猜想:
是不是只要执行的次数够多是不是只要执行的次数够多
就可以得到更为准确的三等分点就可以得到更为准确的三等分点

证明

条件

我们不妨假设上面所分的三条线段 AMAMMNMNNBNB 的长度分别是 xxyyzz
我们这时,将一次点的移动看做一次操作,那么在第一次执行完之后的线段长度(刚刚更新的)就是 x+y2\frac{x + y}{2},再执行一次操作后,则为 12(x+y)+z2\frac{\frac{1}{2}{(x + y)} + z}{2}
在我们手动枚举五次后得到的结果如下( a0a_0 表示第一次,以此类推): a0=x+y2a_0 = \frac{x+y}{2} a1=12(x+y)+z2a_1 = \frac{\frac{1}{2}{(x + y)} + z}{2} a2=32(x+y)+z22a_2 = \frac{\frac{3}{2}{(x + y)} + z}{2^2} a3=52(x+y)+3z23a_3 = \frac{\frac{5}{2}{(x + y)} + 3z}{2^3} a4=112(x+y)+5z24a_4 = \frac{\frac{11}{2}{(x + y)} + 5z}{2^4} 接着,我们发现:
aa 的式子中,变了的只有 (x+y)(x + y) 前的系数、zz 的系数和分母。
那么我们接下来开始严格的证明。

代数证明

an=bn2(x+y)+cnz2na_n = \frac{\frac{b_n}{2}(x + y) + c_n z}{2^n}b1=1,b2=3,c1=1,c2=1b_1 = 1, b_2 = 3, c_1 = 1, c_2 = 1
an1=bn12(x+y)+cn1z2n=bn1(x+y)+2cn1z2na_{n - 1} = \frac{\frac{b_{n - 1}}{2}(x + y) + c_{n - 1} z}{2^n} = \frac{b_{n - 1}(x + y) + 2 c_{n - 1} z}{2^n},
由此可得: an+1=an+an12a_{n + 1} = \frac{a_n + a_{n - 1}}{2} =bn2(x+y)+cnz2n+bn1(x+y)+2cn1z2n2 = \frac{\frac{\frac{b_n}{2}(x + y) + c_n z}{2^n} + \frac{b_{n - 1}(x + y) + 2 c_{n - 1} z}{2^n}}{2} =bn+2bn12(x+y)+(cn+2cn1)z2n+1=\frac{\frac{b_n + 2 b_{n-1}}{2}(x + y) + (c_n + 2 c_{n - 1})z}{2^{n + 1}} 这时,我们发现
bn=bn1+bn2b_n = b_{n - 1} + b_{n - 2} cn=cn1+cn2c_n = c_{n - 1} + c_{n - 2}
又因为 c2=b1,c3=b2c_2 = b_1, c_3 = b_2,所以, cn=bn1c_n = b_{n - 1}
所以原式化为: an=bn2(x+y)+bn1z2na_n = \frac{\frac{b_n}{2}(x + y) + b_{n - 1} z}{2^n} 化到这时,我们先求一下 bnb_n 的通项式:
bn=bn1+bn2b_n = b_{n- 1} + b_{n - 2}
使用特征根
x2=x+2x^2 = x + 2
解得 x=1x=2x = -1 或 x = 2
bnb_n 通项为 α2n+β(1)n\alpha 2^n + \beta (-1)^n
带入 b1b_1b2b_2 得,

评论

0 条评论,欢迎与作者交流。

正在加载评论...