1.算法是什么
算法是指解题方案的准确而完整的描述,是一系列解决问题的清晰指令,算法代表着用系统的方法描述解决问题的策略机制。
2.算法的特点
2.1 有穷性
能在有限的指令中终止。
2.2 确切性
每一个指令有确切的定义,没有歧义。
2.3 输入项
有0个或多个输入,以刻画运算对象的初始情况,0个输入是指算法本身定出了初始条件。
2.4 输出项
有1个或多个输出,,以反映输入数据加工后的结果,没有输出的算法是毫无意义的。
2.5 可行性
每个指令本身是可执行的,或者可分解为可执行的基本指令。
3.算法的一个实例
3.1 欧几里得算法
欧几里得算法的作用是求最大公约数。
3.2 伪代码描述
Euclid(m,n)
//输入:两个不全为0的非负整数m,n
//输出:m,n的最大公约数
while n != 0 do
r = m mod n
m = n
n = r
return m
3.3 为什么它是一个算法
3.3.1 有穷性
每执行一次循环体,n = m mod n,n比原值小,所以总有n = 0的时候,此时算法终止。
3.3.2 确切性
算法中涉及的有while循环、不等式判断、求余和赋值,每一项都是确切的指令,没有歧义。
3.3.3 输入项
算法中有m,n两个明面输入项,m和n是非负整数且不全为0。
3.3.4 输出项
算法有一个输出项,那就是m和n的最大公约数。
3.3.5 可行性
算法中涉及的while循环、不等式判断、求余和赋值这几种指令都是简单的操作,从数学角度和计算机角度都是可行的。
3.4 C++实现
unsigned int Euclid(unsigned int m, unsigned int n) {
unsigned int r;
while (n != 0) {
r = m % n;
m = n;
n = r;
}
return m;
}