高中数学必修三 笔记与拓展

算法初步

算法是按照一定规则解决固定问题,通过对输入的某种变换产生结果.

素性测试

检验一个数是否为素数.

试除法

一个数是素数的充分必要条件是它因数个数为二.显然1和它本身都是它的因数.
receive int n
loop i from 2 to n-1
if n mod i equals 0 then exit(true)
exit(false)
然而一个数是合数必有一个小于等于sqrt(n)的素因子
receive int n
loop i from 2 cond i*i<=n
if n mod i equals 0 then exit(true)
exit(false)

筛法

就是用素数把它的倍数筛去.不详解了.

数值方法

二分法与牛顿迭代

高中数学必修1中介绍得比较详细.

Simpson

二次积分近似.
sf(x) on [a,b] ~ (f(a)+f(b)+4f((a+b)/2))(b-a)/6
可以用迭代自适应精度.

最大公约数

辗转相除

gcd(m,n)=gcd(n,m%n)
gcd(n,0)=n

Stein算法

gcd(2n,2m)=2gcd(m,n)
gcd(n,2m)=gcd(n,m)
gcd(n,m)=gcd(n-m,m)

秦九韶

多项式单点插值的一种方法.
\[f(x)=a_nx^n+a_{n-1}x^{n-1}+\dots =\left(\left(x+a_n\right)x+a_{n-1}\right)\dots\]