专栏文章

最多空间块

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

文章操作

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

当前评论
1 条
当前快照
1 份
快照标识符
@mipr9fjq
此快照首次捕获于
2025/12/03 16:38
3 个月前
此快照最后确认于
2025/12/03 16:38
3 个月前
查看原文
f1(n)f_1(n) 为线中 n 个点最多可分隔出的线块。
f2(n)f_2(n) 为面中 n 个线最多可分隔出的面块。
f3(n)f_3(n),意义形如上方,所有 nNn\in \mathbb{N}
Final goal:计算 f3(n)f_3(n) 的通项式。

Part1

计算 f1(n)f_1(n) 的通项式。
初始没有点存在时,f1(0)=1f_1(0)=1
显然,每多一个点,原来的线必然有一条被分隔成两块,故 f1(n)=f1(n1)+1f_1(n)=f_1(n-1)+1
综上可得,
{f1(0)=1f1(n)=f1(n1)+1nN\begin{cases} f_1(0)=1\\ f_1(n)=f_1(n-1)+1\\ n\in\mathbb{N} \end{cases}
解得 f1(n)=n+1(nN)f_1(n)=n+1(n\in\mathbb{N})

Part2

计算 f2(n)f_2(n) 的通项式。
同上,f2(0)=1f_2(0)=1
在平面中,第 nn 条线最多可与 n1n-1 条线相交,最多有 n1n-1 个交点,因此这条线最多穿过 nn 个平面并将它们分隔成两块,即新增的平面块为 n+1n+1 个,故 f2(n)=f2(n1)+nf_2(n)=f_2(n-1)+n
综上可得,
{f2(0)=1f2(n)=f2(n1)+nnN\begin{cases} f_2(0)=1\\ f_2(n)=f_2(n-1)+n\\ n\in\mathbb{N} \end{cases}
解得 f2(n)=n(n+1)2+1(nN)f_2(n)=\frac{n(n+1)}{2}+1(n\in\mathbb{N})

Part3

计算 f3(n)f_3(n) 的通项式。
同上,f3(0)=1f_3(0)=1
在空间中,第 nn 个面最多可与 n1n-1 个面相交,最多有 n1n-1 条交线,各条交线都在第 nn 个面上,这些交线在其上所分割出的平面块数量,即为第 nn 个面经过的空间块的数量。
由此可知,新增的空间块数量为 f2(n1)f_2(n-1),故 f3(n)=f3(n1)+f2(n1)f_3(n)=f_3(n-1)+f_2(n-1)
综上可得,
{f3(0)=1f3(n)=f3(n1)+f2(n1)nN\begin{cases} f_3(0)=1\\ f_3(n)=f_3(n-1)+f_2(n-1)\\ n\in\mathbb{N} \end{cases}\\ f3(n)=f3(n1)+f2(n1)=f3(n2)+f2(n2)+f2(n1)=f3(0)+f2(0)+f2(1)++f2(n1)=1+1+i=1n1(i(i+1)2+1)=2+i=1n1i22+i=1n1i2+n1=n+1+12i=1n1i2+12i=1n1i=n+1+(n1)n(2n1)12+n(n1)4=n+1+2n33n2+n+3n23n12=n+1+n3n6=n3+5n6+1 \begin{aligned} f_3(n)&=f_3(n-1)+f_2(n-1)\\ &=f_3(n-2)+f_2(n-2)+f_2(n-1)\\ &\vdots\\ &=f_3(0)+f_2(0)+f_2(1)+\ldots+f_2(n-1)\\ &=1+1+\sum_{i=1}^{n-1}(\frac{i(i+1)}{2}+1)\\ &=2+\sum_{i=1}^{n-1}\frac{i^2}{2}+\sum_{i=1}^{n-1}\frac{i}{2}+n-1\\ &=n+1+\frac{1}{2}\sum_{i=1}^{n-1}i^2+\frac{1}{2}\sum_{i=1}^{n-1}i\\ &=n+1+\frac{(n-1)n(2n-1)}{12}+\frac{n(n-1)}{4}\\ &=n+1+\frac{2n^3-3n^2+n+3n^2-3n}{12}\\ &=n+1+\frac{n^3-n}{6}\\ &=\frac{n^3+5n}{6}+1 \end{aligned}
解得 f3(n)=n3+5n6+1(nN)f_3(n)=\frac{n^3+5n}{6}+1(n\in\mathbb{N})

后记

f1(n)f_1(n)f2(n)f_2(n)f3(n)f_3(n) 的推导过程中,我们可以发现一个规律
对于相同定义的 fx(n)f_x(n),它们都可以得到递推式并由 f3(n)f_3(n) 继续向上迭代得出通项式。
{fx(0)=1fx(n)=fx(n1)+fx1(n1)nN\begin{cases} f_x(0)=1\\ f_x(n)=f_x(n-1)+f_{x-1}(n-1)\\ n\in\mathbb{N} \end{cases}
然而好像并没有什么用 [doge]。
完结撒花

评论

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

正在加载评论...