为了更好体现数学在计算机算法中的重要作用，我来介绍一些数学知识以及它们的应用。
Contens
1. 秦九韶算法 9. 最小二乘法
2. 斯特林公式 10. 自守数
3. 外观数列
4. 整数拆分问题
5. 阿贝尔变换
6. 二项式反演
7. 马青公式
8. 艾森斯坦判别法
1. 秦九韶算法
秦九韶算法是中国南宋时期数学家秦九韶提出的一种计算多项式的优化算法。在西方又被称为
Horner算法
。
给定一个多项式
，计算这个多项式的值。
可以对这个多项式进行如下改写
那么由内到外就是
时间复杂度为
。
代码：
int Horner(int a[], int n, int x)
{
int v1 = a[n];
for(int i = n - 1; i >= 0; i--)
{
int v2 = v1 * x + a[i];
v1 = v2;
}
return v1;
}
2. 斯特林公式
斯特林公式是用来取阶乘近似值的数学公式。尤其是在
比较大的时候，用斯特林公式非常高效。公式如下
在
维基百科
上有关于斯特林数更详细的介绍，如下
链接：
http://zh.wikipedia.org/wiki/%E6%96%AF%E7%89%B9%E9%9D%88%E5%85%AC%E5%BC%8F
题目：
http://acm.hdu.edu.cn/showproblem.php?pid=1018
分析：
题意就是求阶乘的位数，由于给定数比较大，直接做很容易TLE，采用斯特林数易过之。
拓展：
给定一个正整数
，
比较大，求如下表达式结果的位数。
分析：
作如下变换，然后取对数即可。
3. 外观数列
外观数列是这样一个数列，首项为
1
，以后的每一项都是对前一项的描述，数列如下
比如
312211
是对
111221
的描述，即
3
个
1
，
2
个
2
，
1
个
1
。
1987年，康威（John Conway）发现，在这个数列中，相邻两数的长度之比越来越接近一个固定的常数，当数
列
项数趋近无穷大的时候，该比值约为
1.303577
，此
常数叫做
康威常数
。外观数列还有一个性质，
4
永远不出现。
更多有关康威常数的了解请关注
Matrix 67
的博客，如下
链接：
http://www.matrix67.com/blog/archives/3870
题目：
http://acm.hdu.edu.cn/showproblem.php?pid=4148
题意：
求外观数列指定某一项的长度。
分析：
我们只需考虑前一项与后一项的关系，然后递推即可。
代码：
#include <iostream>
#include <string.h>
#include <stdio.h>
using namespace std;
char list[32][10005];
void Init()
{
for(int i = 0; i < 32; i++)
memset(list, 0, sizeof(list));
list[1][0] = '1';
for(int i = 2; i < 32; i++)
{
int k = 0;
int cnt = 1;
int len = strlen(list[i - 1]);
for(int j = 0; j < len; j++)
{
if(list[i - 1][j] == list[i - 1][j + 1]) cnt++;
else
{
list[i][k++] = cnt + '0';
list[i][k++] = list[i - 1][j];
cnt = 1;
}
}
}
}
int main()
{
int n;
Init();
while(cin>>n && n)
cout<<strlen(list[n])<<endl;
return 0;
}
4. 整数拆分问题
问题：
给定一个自然数
，把它拆分为若干个数的和，记这若干个数的积为
，求
的最大值。
分析：
假设把
拆分为
个数之和，那么有
和
，由不等式
进一步得到如下结论
我们需要求
的最大值，等价于求如下函数的最大值
求导后得到
那么函数
在
处取得最大值，因为
与
3
最接近，所以可得到如下结论
结论：
，使乘积最大的拆分方案是，先拆分出尽多可能的
3
，如果剩余
的
数为
2
或
0
，则拆分结束。如果剩余的数为
1
，则将拆分好的
3
拿一个和剩余的
1
组合拆分为两个
2
，
拆
分
结束。
而本题也可以用
dp
的思路做，只不过时间复杂度比较高，仅适合比较小的
。状态转移方程如下
其中
表示把自然数
拆分为若干数之和，得到的最大乘积。
5. 阿贝尔变换
给定两个数列
和
，并记
并且
，那么有如下结论
则称上式为
阿贝尔变换
或者
阿贝尔部分求和公式
。证明步骤如下
由于
，则进一步有
证明完毕！
应用
阿贝尔变换
可以解决一些比较复杂的数学问题，接下来看看一个经典例题。
例题：
已知
，且满足如下两个条件
证明如下不等式
证明：
记
中全体非负实数之和为
，全体负数之和为
，由条件可知
且
。所以
得到
记
，并且
很明显，对于所有的
，都有
所以根据
阿贝尔变换
得到
证明完毕！
6. 二项式反演
设
和
是定义在非负整数集上的两个函数，并且满足
那么得到
这就是
二项式反演
的主要内容。
证明：
首先我们要知道
有了这个，就很容易证明了，步骤如下
证明完毕！
接下来，我会用二项式反演来求
错排公式
。
个不同的元素排列的方法数为
，那么恰有
个元素错排的方法数为
，那么有
根据
二项式反演
，进而得到
7. 马青公式
马青公式
是英国天文学教授
约翰·马青于1706年发现的，用它来计算圆周率
的值非常高效。公式内容如下
关于这个公式的推导参考
WiKi
，链接如下
链接：
http://zh.wikipedia.org/wiki/%E6%A2%85%E6%AC%BD%E9%A1%9E%E5%85%AC%E5%BC%8F
对于
的幂级数展开式推导步骤如下
设
，那么有
两边分别积分，最终得到
也就是说
然后得到
的计算方法如下
通过这个公式，可以很容易计算出
小数点后精确到某一位的值。当然这里计算
有技巧，
由于
设
，并且
对于
可以用
秦九韶算法
求之，最终得到
，为了提高效率，乘法运算可用
FFT
。
代码：
#include <iostream>
#include <string.h>
#include <stdio.h>
using namespace std;
typedef long long LL;
const int BASE = 10000;
const int DIGIT = 10000;
const int NUM = DIGIT >> 2;
int res[NUM], A[NUM], B[NUM], C[NUM];
void set(int res[], int x)
{
for(int i = 0; i < NUM; i++)
res[i] = 0;
res[0] = x;
}
void copy(int res[], int x[])
{
for(int i = 0; i < NUM; i++)
res[i] = x[i];
}
bool zero(int res[])
{
for(int i = 0; i < NUM; i++)
if(res[i]) return false;
return true;
}
void add(int res[], int x[])
{
for(int i = NUM - 1; i >= 0; i--)
{
res[i] += x[i];
if(res[i] >= BASE && i > 0)
{
res[i] -= BASE;
res[i - 1]++;
}
}
}
void sub(int res[], int x[])
{
for(int i = NUM - 1; i >= 0; i--)
{
res[i] -= x[i];
if(res[i] < 0 && i > 0)
{
res[i] += BASE;
res[i - 1]--;
}
}
}
void multi(int res[], int x)
{
int t = 0;
for(int i = NUM - 1; i >= 0; i--)
{
res[i] *= x;
res[i] += t;
t = res[i] / BASE;
res[i] %= BASE;
}
}
void div(int res[], int x)
{
int t = 0;
for(int i = 0; i < NUM; i++)
{
res[i] += t * BASE;
t = res[i] % x;
res[i] /= x;
}
}
void arctan(int res[], int A[], int B[], int x)
{
int m = x * x;
int cnt = 1;
set(res, 1);
div(res, x);
copy(A, res);
do{
div(A, m);
copy(B, A);
div(B, 2 * cnt + 1);
if(cnt & 1)
sub(res, B);
else
add(res, B);
cnt++;
}while(!zero(B));
}
void print(int res[])
{
printf("%d.\n", res[0]);
for(int i = 1; i < NUM; i++)
{
printf("%04d", res[i]);
if(i % 15 == 0) puts("");
}
puts("");
}
void Machin()
{
arctan(res, A, B, 5);
multi(res, 4);
arctan(C, A, B, 239);
sub(res, C);
multi(res, 4);
print(res);
}
int main()
{
Machin();
return 0;
}
8. 艾森斯坦判别法
艾森斯坦判别法
是目前为止用来判断
内一个多项式可约与否的最好的方法。内容如下
给定一个
次
本原多项式
，并且这是一个整系数多项式，若存在一
个素数
，使得下面
3
个条件都成立
那么
为
不可约多项式
。
上面提到了
本原多项式
，其实本原多项式就是满足多项式所有系数的最大公约数为
1
的多项式。
9. 最小二乘法
最小二乘法
又叫
最小平方法
，是一种数学优化技术，它通过最小化误差的平方和寻找数据的最佳函数匹配。
通常情况，最小二乘法用于求回归问题。以简单的线性最小二乘为例，在二维平面上给定
个点的坐标，确定
一条直线，要求尽量吻合这
个点的走向。
首先设要找的直线方程为
，这
个点的坐标为
，那么现在要
确定
和
的值，使得
最小，根据这种方法来求
和
的值就是典型的最小二乘法。
可以看出
是关于
和
的一个二元函数，要求
的最小值，先求偏导，并且偏导值均为零，即
进一步得到
然后联立两式可以解出
和
，如果方程个数比较多，可以通过
高斯消元
来做，最小二乘法的解是唯一的。
问题：
在一个平面直角坐标系中给定
个点，找出一条直线
，要求这些点到这条直线距离
的平方和最小，求出这条直线的方程。
问题：
在一个三维空间中给定
个点，求一过原点的平面
，使得这些点到这个平面的距
离的平方和最小，求出这个平面的方程。
（2014年编程之美复赛）
10. 自守数
一个
位的自然数
，如果它的平方后得到的最后
位跟原数相同，那么称
为
自守数
。其数学表达式为
一位的自守数有3个，即1，5，6。一位数以上的自守数分为两类
（1）个位数为5，形式为
（2）个位数为6，形式为
可以看出两个位数相同的自守数之和为
。自守数还有两个重要的性质
（1）一个数为自守数当且仅当它为另一个自守数的后缀
（2）
位（1位数除外）的自守数仅有两个，其位数包括前导零
自守数的计算方法，一个
位的自然数
可以由
求得，具体如下
（1）对于个位数为
5
的自守数
求
的平方，取最后
位，如果第
位为零，则取最后
位。例如
（2）对于个位数为
6
的自守数
求
的平方，取最后
位，把最后第
位的数用
10
减之代替，若第
位是零，则取最后
第
位来减，第
位保持为零。例如
题目：
http://acm.timus.ru/problem.aspx?space=1&num=1698
题意：
求位数不大于
的自守数的个数。
代码：
#include <iostream>
#include <string.h>
#include <stdio.h>
using namespace std;
typedef long long LL;
const int N = 2005;
int a[N], b[N];
int ans, n;
bool check(int k)
{
b[k] = 0;
for(int i = 0; i <= k; i++)
b[k] += a[i] * a[k-i];
if(k) b[k] += b[k-1] / 10;
return b[k] % 10 == a[k];
}
void dfs(int k)
{
if(k >= n) return;
for(int i=9; i >= 0; i--)
{
a[k] = i;
if(check(k))
{
if(a[k]) ans++;
dfs(k+1);
}
}
}
int main()
{
while(cin>>n)
{
ans = 0;
dfs(0);
cout<<ans<<endl;
}
return 0;
}