最多空间块
MC_dmAC
·
·
算法·理论
设 f_1(n) 为线中 n 个点最多可分隔出的线块。
设 f_2(n) 为面中 n 个线最多可分隔出的面块。
设 f_3(n)，意义形如上方，所有 n\in \mathbb{N}。
Final goal：计算 f_3(n) 的通项式。
Part1
计算 f_1(n) 的通项式。
初始没有点存在时，f_1(0)=1。
显然，每多一个点，原来的线必然有一条被分隔成两块，故 f_1(n)=f_1(n-1)+1。
综上可得，
\begin{cases}
f_1(0)=1\\
f_1(n)=f_1(n-1)+1\\
n\in\mathbb{N}
\end{cases}
解得 f_1(n)=n+1(n\in\mathbb{N})
Part2
计算 f_2(n) 的通项式。
同上，f_2(0)=1。
在平面中，第 n 条线最多可与 n-1 条线相交，最多有 n-1 个交点，因此这条线最多穿过 n 个平面并将它们分隔成两块，即新增的平面块为 n+1 个，故 f_2(n)=f_2(n-1)+n。
综上可得，
\begin{cases}
f_2(0)=1\\
f_2(n)=f_2(n-1)+n\\
n\in\mathbb{N}
\end{cases}
解得 f_2(n)=\frac{n(n+1)}{2}+1(n\in\mathbb{N})
Part3
计算 f_3(n) 的通项式。
同上，f_3(0)=1。
在空间中，第 n 个面最多可与 n-1 个面相交，最多有 n-1 条交线，各条交线都在第 n 个面上，这些交线在其上所分割出的平面块数量，即为第 n 个面经过的空间块的数量。
由此可知，新增的空间块数量为 f_2(n-1)，故 f_3(n)=f_3(n-1)+f_2(n-1)。
综上可得，
\begin{cases}
f_3(0)=1\\
f_3(n)=f_3(n-1)+f_2(n-1)\\
n\in\mathbb{N}
\end{cases}\\
\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}
解得 f_3(n)=\frac{n^3+5n}{6}+1(n\in\mathbb{N})
后记
由 f_1(n)，f_2(n) 和 f_3(n) 的推导过程中，我们可以发现一个规律
对于相同定义的 f_x(n)，它们都可以得到递推式并由 f_3(n) 继续向上迭代得出通项式。
\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]。
完结撒花