算法1
2018-10-23 本文已影响0人
无端飞溅
前言：重新复习算法相关内容，随便找了本算法书，记录一下心得，书名是《算法设计与分析——C++语言描述》，陈慧南编著。
算法是什么？
- 在计算机科学中，算法用于描述一个可用于计算机实现的问题求解（problem-solving）方法。
- 广义的算法（algorithm）是求解一类问题的任意一种特殊的方法；即一个算法是对特定问题求解步骤的一种描述。
算法的5个特征
- 输入（input）
- 输出（output）
- 确定性（definiteness）
- 能行性（effectiveness）
- 有穷性（finiteness）
算法的起源
- 算法概念不是计算机诞生之后才有的概念，最早可以追溯到古希腊欧几里得（约公元前330——275年）在他的《几何原本》（Euclid's Elements）中提出的计算两个整数的最大公约数的辗转相除法。直到1950年左右，算法一词还经常与欧几里得算法（Euclid's algorithm）联系在一起。
欧几里得算法又叫辗转相除法
- 计算两个整数m和n（0≤m<n）的最大公约数，记为gcd(m,n)
- 计算过程为：gcd(m,n)=gcd(n mod m, m)，对于m>0
- 算法使用了递归！高端吧:-D
欧几里得算法实现（C++）
- 递归实现
https://github.com/terrellhu/algorithm/blob/master/20181023/euclid_recursion.cpp - 迭代实现https://github.com/terrellhu/algorithm/blob/master/20181023/euclid.cpp
- 连续整数检测法https://github.com/terrellhu/algorithm/blob/master/20181023/noeuclid.cpp
为什么学习算法？
- 算法是计算机科学的基础，更是程序的基石。
