$$writebyLJX$$

转载请附上：https://www.luogu.org/blog/xiaopangfeiyu/shu-lie

目录

目录

引入

第一种解法

1.数学推导

2.代码实现

第二种解法

小总结

拓展内容

1.函数化

2.矩阵

3.特殊的通项公式

第二种解法的优化

总结

---

引入

OI中很多题目同于数列有联系，数学中它也是十分关键的。

而数列中最重要的东西之一就是通项公式了。

那么我们是否能用程序算出一个数列的通项公式呢？

看完后你因该就知道了。

第一种解法

到底如何解决这个问题呢？

数学推导

这里插入一个定理：

凡是一个长度为n的数列，都可以用一个不超过n-1次的式子表示出来

什么意思？

就是例如

$ a= \begin{Bmatrix}1,2,4\end{Bmatrix}$

$a_1=1$

$a_2=2$

$a_3=4$

设$ f(x)=a_{x} $

$ f(x) $就是$a$的通项公式

定理的意思就是

$f(x)=t1\ast x^2+t2\ast x+t3$

根据这个神奇的定理我们就可以求解了

还是刚刚的例子：

我们得出$f(x)=t1\ast x^2+t2\ast x+t3$

所以

$f(1)=t1+t2+t3=1$

$f(2)=4\ast t1+2\ast t2+t3=2$

$f(3)=9\ast t1+3\ast t2+t3=4$

$ \begin{cases} t1=\frac{1}{2} \ t2=-\frac{1}{2} \ t3=1 \end{cases} $

就这样我们大致推出了解决思路：

先利用待定系数法列出式子

再将数值带进去列出方程

求解方程

代码实现

关于代码实现，我们就按上面的解决思路来

待定系数法求出式子：编程中不存在的将数值带进去列出方程：带入过程就是将x的几次幂算出来求解方程：很显然要使用高斯消元

代码部分：

#include <iostream> using namespace std; int main() { //暂时没有代码 }

第二种解法

第二种方法和第一种有本质上的区别请做好准备。

依旧是刚才的例子

不用往上翻了，我帮你搬下来了

$ a= \begin{Bmatrix}1,2,4\end{Bmatrix}$

$a_1=1$

$a_2=2$

$a_3=4$

设$ f(x)=a_{x} $

现在我们要对他进行一顿操作

在f(x)中

当$x=1$时，$f(x)=1$

当$x=2$时，$f(x)=2$

当$x=3$时，$f(x)=4$

即

当$ x \neq 2,3$时，$f(x)=1$

当$ x \neq 1,3$时，$f(x)=2$

当$ x \neq 1,2$时，$f(x)=4$

不过这有什么用呢？

接下来这波操作绝对闪瞎你的狗眼眼睛

设$f(x)=t1+t2+t3$

其中

当$x=2,3$时,$t1=0$

当$x=1$时,$t1=1$

当$x=1,3$时,$t2=0$

当$x=2$时,$t2=2$

当$x=1,2$时,$t3=0$

当$x=3$时,$t3=4$

接下来我们只需分别求解即可

$\because$当$x=2,3$时,$t1=0$

$\therefore t1=(x-2)(x-3)* $一坨东东

原因很简单让式子中含$(x-2)$就是为了$x=2$时式子值为0

$\because$当$x=1$时,$t1=1$

$\therefore x=1$时 ,$t1=(x-2)(x-3)* $一坨东东$=1$

$\therefore $一坨东东$=\frac{1}{2}$

$\therefore t1=\frac{(x-2)(x-3)}{2}$

$\because$同理可得

$ \therefore\begin{cases} t1=\frac{(x-2)(x-3)}{2} \ t2=-2(x-1)(x-3) \ t3=2(x-1)(x-2) \end{cases} $

$\therefore f(x)=\frac{(x-2)(x-3)}{2}-2(x-1)(x-3)+2(x-1)(x-2)$

$\therefore f(x)=\frac{1}{2}{x}^2-\frac{1}{2}x+1$

和刚刚得出的结果一样

就这样我们大致推出了解决思路：

口算出结果

额……

确实是的这种方法熟练后确实可以口算出结果

只不过没有化简

关于代码：

这种方法不适合写编程！

Q:这种方法为什么不适合编程?

A:因为都可以口算了，还编程干嘛。

Q:不是还有化简吗？

A:化简的复杂度太高了！

Q:比$O(N^3)$高吗？

A:$O(N\ast 2^N)$！

Q:额……

A:……

不过这种算法在后面有惊喜……

剧透一下：也许有解决办法

小总结

程序数学第一种时间复杂度较低暴力解方程第二种巨大无比的暴力口算出答案

拓展内容

关于通项他还有许多好玩的

函数化

其实你因该已经注意到了，上面的式子

$f(x)=t1\ast x^2+t2\ast x+t3$

其实和我们学的函数很像

$y=a{x}^2+bx+c$

对吧，所以上面那个定理可以变成

凡是坐标系上任意n个点，都可以在一个不超过n-1次的函数上

这个定理似乎学过吧！

矩阵

可能有人会想：数列有通项，矩阵和数列那么像因该也有吧！

例如矩阵：

y\x12112224

可以表示成$xy$

因此我们猜想：凡是一个为nm的矩阵，都可以用一个不超过（n-1）（m-1）次的式子表示出来，且只有两个元，一个的最高此不超过n-1，另一个不超过m-1

并且如果通项公式是对称式，矩阵沿对角线对称，如上图。

求通项的办法仍然可以使用上述两种办法。

能想到这里，脑洞已经够大了，但看到上面 函数化。

是不是这个柿子式子也能函数化

先把四次式子写出来：

$f(x,y)=t1\ast x+t2+t3\ast y+t4\ast xy$

转化为

$z=a\ast xy+b\ast x+c\ast y+d$

哇！这是！什么东西？

喔对！这是三维函数

原来如此！

维度\性质通项函数一维数列一元两元二维矩阵两元三元………………

到此你的脑洞和想象已经到达最高点。

放张图片缓解一下心情

特殊的通项公式

我们先来解决一下上面的问题：

我们是否能用程序算出一个数列的通项公式呢？

奇怪了,上面不是给出两种方法了吗？

注意！上面给出的是给你一个长度为n的数列，让你求一个不超过n-1次的通项公式。

其实任意数列都有无穷多中通项公式！

也就是说找规律题目你写什么数都是对的

回到正题

找规律中，以前有这么一类题目：

$1,2,4,4,9,6,16,8,25,10,(?)$

方法就是奇偶拆开：

甲：$1,4,9,16,25$

乙：$2,4,6,8,10$

抛开之前说的通项公式求法

甲数列的通项公式最简单不过的就是：$x^2$

乙数列的通项公式最简单不过的就是：$2x$

那么合体的数列通项公式是什么？

答案是：

$\frac{[(-1{)}^x-1]}{-2}\ast x^2+\frac{[(-1{)}^x+1]}{2}\ast 2x$

这中合并方法利用了$(-1{)}^x$的特性：

$2|x$时，$(-1{)}^x=1$

$2|x+1$时，$(-1{)}^x=-1$

同时再结合第二种方法的思想即可

这种方法有归并的影子里面

第二种解法的优化

第二种方法是不是也能用归并实现，而不用打又长又恶心的代码？

确实可以，举个例子：

$1,2,4,8$

一次合并:

$\frac{(x-2)}{-1}+2(x-1),\frac{(x-4)}{-4}+8(x-3)$

拆开：

$x,\frac{31}{32}x-23$

这种用归并的方法写第二种方法代码技术含量提高了许多

不过时间复杂度仍然十分高

但是优化的方法却变得多了

举一个例子，上面的式子合并过后形式都为：

$\frac{(x-a)}{-b}+c(x-d)$

根据这个就可以很简单的拆开它

优化他的办法还有很多，接下来的就由你自己探索吧！

总结

关于求数列，矩阵，三维数据，……求通项公式

介绍了两种方法

一种数学上很暴力，程序用到高斯消元，很有技巧性

另一种数学上有技巧性，程序暴力，但可以用归并优化

并且每个通项公式对应一个函数，每个维度数据里的数字对应内个维度上的一个点

到此我们讲完了关于数列与通项的许多内容

也许哪一道关键的题目能够用上呢？

$$end$$