基于linux的C++学习笔记4（算法 示例 优化）
算法：解决问题的方法和步骤
设计算法的目的：给出解决问题的逻辑描述，根据算法描述进行实际编程
算法特征：有穷性、确定性、输入、输出、有效性
有穷性——算法在每种情况下都可以在有限步后终止
确定性——算法步骤的顺序和内容没有二义性
输入——算法有零个或多个输入
输出——算个发至少具有一个输出
有效性——所有操作具有明确的含义，并在有限时间内完成
正确性不是算法的特征，算法的正确性数学证明
算法示例一：幻方(3*3)
9 2
8 1 6 8
3 5 7 3
4 9 2
省略了格子
找出规律，编写步骤：
步骤一：把1写在第一行中间一格
步骤二：在该格右上方的那一格写入下一个自然数（若该数超出3*3幻方范围，将该数写在其所在的那一排或列的另一端格子中，即相当于认为幻方外围仍然包含了同样的幻方，而该数卸载外围幻方的同样位置；每写完三个数，将第四个树写在第三个数下面格子中）
步骤三：重复步骤二，直到所有格子均填满
算法示例二：查英文单词
步骤一：翻开词典任意一页
步骤二：若所查的词汇按字母排列顺序在本页第一个单词之前，则往前翻开任意一页，重复步骤二；若所查单词在本页最后一个单词之后，则往后翻开任意一页，重复步骤二
步骤三：若上述两个条件都不满足，则该单词要么在本页上，要么词典中不存在（依次比较本页单词，或者查出该单词，或者得到该单词查不到的结论）
算法描述：伪代码、流程图
伪代码——混合自然语言与计算机语言、数学语言的算法描述方法
优点：方便，容易表达设计者思想，清洗描述算法流程，便于修改
缺点：不美观，复杂算法不容易理解
顺序结构、分支结构（if else）、循环结构（for while）
流程图（程序框图）——使用图形表示算法执行逻辑
优点：美观，算法表达清晰
缺点：绘制复杂，不易修改，占用过多篇幅
。
算法设计与实现
构造算法解决问题
按照自顶向下、逐步求精的方式进行
使用程序设计语言设计语言编程实现
典型示例：
素数判定问题——判定给定的某个自然数n（大于2是否为素数）
算法逻辑
输入：大于2的正整数n
输出：该数是否为素数，若为素数返回true，否则返回false
步骤一：设除数i为2
步骤二：判断除数i是否已为n，若为真返回true，否则继续
步骤三：判断n%i是否为0，若为0返回false，否则继续
步骤四：将除数i递增，重复步骤二
第一版
bool IsPrime(unsigned int n){
unsigned int i = 2;
while(i < n){
if(n%i == 0) return false;
i++;
}
return true;
}
第二版（优化用平方根以内数做除数）
bool IsPrime(unsigned int n){
unsigned int i = 2;
while(i <= (unsigned int)sqrt(n)){ //sqrt为标准库中的求平方根函数,返回值为浮点数
if(n%i == 0) return false;
i++;
}
return true;
}
第三版（优化首先判断是否是偶数）
bool IsPrime(unsigned int n){
unsigned int i = 3;
if(n%2 == 0) return false; //是偶数也就是合数
while(i <= (unsigned int)sqrt(n)){ //sqrt为标准库中的求平方根函数,返回值为浮点数
if(n%i == 0) return false;
i++;
}
return true;
}
第四版（优化防止平方根计算浮点数带来的误差导致错误，如：121的平方根被计算成10.999999强转unsigned int为10）
bool IsPrime(unsigned int n){
unsigned int i = 3;
if(n%2 == 0) return false; //是偶数也就是合数
while(i <= (unsigned int)sqrt(n) + 1){ //sqrt为标准库中的求平方根函数,返回值为浮点数
if(n%i == 0) return false;
i++;
}
return true;
}
第五版（优化防止求平方根操作在while循环中重复执行）
bool IsPrime(unsigned int n){
unsigned int i = 3, t = (unsigned int)sqrt(n) + 1;
if(n%2 == 0) return false; //是偶数也就是合数
while(i <= t){ //sqrt为标准库中的求平方根函数,返回值为浮点数
if(n%i == 0) return false;
i += 2;
}
return true;
}
算法选择的权衡指标
正确性：算法是否完全正确
效率：在某些场合，对程序效率的追求具有重要意义
可理解性：算法是否容易理解，也是必须要考虑的
算法评估：衡量算法的好坏，主要是效率
最大公约数问题——求两个整数x与y的最大公约数
第一版（穷举法）
unsigned int gcd(unsigned int x, unsigned int y){
unsigned int t;
t = x<y?x:y;
while(x%t != 0 || y%t != 0) t--;
return t;
}
第二版（欧式算法）
输入：正整数x、y
输出：最大公约数
步骤一：x整除以y，记余数为r
步骤二：若r为0，则最大公约数即为y，算法结束
步骤三：否则将y作为新x，将r作为新y，重复上述操作
unsigned int gcd(unsigned int x, unsigned int y){
unsigned int t;
while(true)
{
r = x%y;
if(r == 0) return y;
x = y;
y = r;
}
}
递归算法
递推公式：数学上很常见，阶乘函数（1！=1，n！=n*（n-1）！）、斐波那契数列（f（1）=f（2）=1，f(n)=f(n-1)+f(n-2)）
递推函数一定是分段函数，具有初始表达式
递推函数的计算逻辑：逐步简化问题规模
递归的工作步骤
递推过程：逐步分解问题，使其更简单
回归过程：根据简单情形组装最后的答案
阶乘函数
使用循环实现
unsigned int GetFactorial(unsigned int n){
unsigned int result = 1, i = 0;
while(++i <= n) result *= i;
return result;
}
使用递归实现
unsigned int GetFactorial(unsigned int n){
unsigned int result;
if(1 == n) result = 1;
else result = n*GetFactorial(n-1);
return result;
}
斐波那契数列函数
使用循环实现
unsigned int GetFibonacci(unsigned int n){
unsigned int i, f1, f2, f3;
if(2 == n || 1 == n) return 1;
f2 = 1;f1 = 1;
for(i = 3; i <= n; i++){
f3 = f2 + f1; f1 = f2; f2 = f3;
}
return f3;
}
使用递归实现
unsigned int GetFibonacci(unsigned int n){
if(2 == n || 1 == n) return 1;
else return GetFibonacci(n-1) + GetFibonacci(n-2);
}
循环和递归的比较：
循环使用显式的循环结构重复执行代码段，递归使用重复的函数调用执行代码段
循环在满足其终止条件时终止执行，而递归则在问题简化到最简单情形时终止执行
循环的重复是在当前迭代执行结束时进行，递归的重复则是在遇到对同名函数的调用时进行
循环和递归都可能隐藏程序错误，循环的条件测试可能永远为真，递归可能永远退化不到最简单情形
理论上任何递归程序都能使用循环迭代的办法解决（递归函数的代码短小精悍，掌握递归的思考方法，递归程序更容易理解）
汉诺塔问题——假设有三个分别命名为X、Y和Z的塔座，在塔座X上插有n个直径大小不同、依小到大分别编号为1，2，3......，n的圆盘，要求将塔座X上的n歌圆盘移动到塔座Z上并按相同顺序叠放，圆盘移动时必须遵循的规则：
每次只能移动一个圆盘；
圆盘可以插在X、Y、Z中的任意一个塔座上；
任何时刻都不能将较大的圆盘压在较小的圆盘上；
问题分析：
是否存在简单情形，问题很容易解决
是否将原始问题分解成性质相同但规模较小的子问题，且新问题的解答对原始问题有关键意义
解决方案（数学归纳法）
只有一个圆盘是最简单的情形
对于n-1，考虑n-1个圆盘，若将n-1个圆盘移动到某个塔座上，则可移动第n个圆盘
策略：先将n-1个圆盘移动到塔座Y上，然后将第n个圆盘移动到Z上，最后将n-1个圆盘从Y上移动到Z上
伪代码
void MoveHanoi(unsigned int n, HANOI from, HANOI tmp, HANOI to)
{
if(1 == n) 将一个圆盘从form移动到to
else{
将n-1个圆盘从from以to为中转移动到tmp
将圆盘n从from移动到to
将n-1个圆盘从tmp以from为中转移动到to
}
}
程序代码
#include<iostream>
using namespace std;
/* 枚举类型HANOI， 分别表示三个圆柱代号 */
unsigned int GetInteger();
void MoveHanoi(unsigned int n, HANOI from, HANOI tmp, HANOI to);
char ConverHanoiToChar(HANOI x);
void MovePlate(unsigned int n, HANOI from, HANOI to);
int main(){
unsigned int n;
n = GetInteger();
MoveHanoi(n, X, Y, Z);
return 0;
}
unsigned int GetInteger(){//获取输入值
unsigned int t;
cout << "Input number of plates:";
cin >> t;
return t;
}
void MoveHanoi(unsigned int n, HANOI from, HANOI tmp, HANOI to){
if(1 == n) MovePlate(n, from , to);
else{
MoveHanoi(n-1, from, to, tmp);
MovePlate(n, from, to);
MoveHanoi(n-1, tmp, from, to);
}
}
char ConverHanoiToChar(HANOI x){//将枚举文字转换成字符
switch(x){
case X:return 'X';
case Y:return 'Y';
case Z:return 'Z';
default:return '\0';
}
}
void MovePlate(unsigned int n, HANOI from, HANOI to){
char fc, tc;
fc = CovertHanoiToChar(from);
tc = CovertHanoiToChar(to);
cout << n << ":" << fc << "-->" << tc <<endl;
}
递归信任
递归实现是否检查了最简单的情形
在尝试将问题分解成子问题前，首先检查问题是否已足够简单
在大多数情况下，递归函数以if开头
如果不是这样，仔细检查源代码
是否解决了最简单情形
大量递归错误是由没有正确解决最简单情形导致的
最简单情形不能调用递归
递归分解是否使问题更简单
只有分解出子问题更简单，递归才能正确工作，否则将形成无限递归，算法无法终止
问题简化过程是否能够确实回归最简单情形，还是遗漏了某些情况
如汉诺塔问题需要调用两次递归过程，程序中如果遗漏了任意一个都会导致错误
子问题是否与原始问题完全一致
如果递归过程改变了问题实质，则整个过程肯定会得到错误结果
使用递归信任时，子问题的解是否正确组装为原始问题的解
将子问题的解正确组装以形成原始问题的解也是必不可少的步骤
容错：允许错误的发生
错误的处理
很少见的特殊情况或普通错误：忽略该错误不对程序运行结果产生影响
用户输入错误：通知用户错误性质，提醒用户更正输入
致命错误：通知用户错误的性质，停止执行
典型容错手段
数据有效性检查
程序流程的提前终止
数据有效性检查示例：
void GetUserInput(){
获取用户输入的数据
while(用户输入的数据无效){
通知用户输入数据有误，提醒用户重新输入数据
重新获取用户输入数据
}
}
素数判定函数第六版（添加参数检查及异常处理）
const int failed_in_testing_primality = 1;
bool IsPrime(unsigned int n){
unsigned int i = 3, t = (unsigned int)sqrt(n)+1;
if(1 => n){//越界处理，提示错误信息并返回错误码
cout << "IsPrime:Failed in testing the primality of" << n << endl;
exit(failed_in_testing_primality);
}
if(n == 2) return true;//2为素数
if(n%2 == 0) return false;
while( i <= t){
if(n%i == 0) return false;
i += 2;
}
return true;
}
算法复杂度
引入算法复杂度的目的——度量算法的效率和性能
大O表达式
算法效率与性能的近似表示（定性描述）
算法执行时间与问题规模的关系
表示原则
忽略所有对变化趋势影响较小的项，例如多项式忽略高阶项之外的所有项
忽略所有与问题规模无关的常数，例如多项式的系数
O(1)：常数级，表示算法执行时间与问题规模无关
O(log(n))：对数级，表示算法执行时间与问题规模的对数成正比
O(sprt(n))：平方根级，表示算法执行时间与问题规模的平方根成正比
O(n)：线性级，表示算法执行时间与问题规模成正比
O(n*log(n))：n*log(n)级，表示算法执行时间与问题规模的n*log(n)成正比
O(n2)：平方级，表示算法执行时间与问题规模的平方成正比
......
算法复杂度估计
for(i = 0; i < n; i++) //O(n)
;
for(i = 0; i < n; i++) //O(n2)
for(j = 0; j < n; j++)
;
for(i = 0; i < n; i++) //O(n2)
for(j = i; j < n; j++)
;
