当前课程知识点：基于Linux的C++ > 第四讲 算法 > 4.4 算法设计与实现 > LinuxCPP0404
好 我们接下来讨论算法的设计与实现
所谓算法的设计和实现
就是要构造算法来解决实际的问题
就像原来讲的
你一定要按照自顶向下
逐步求精的方式来进行才行
为啥要这么去写呢
因为几十年来的程序设计经验表明
如果你不按照这个方式来书写
你写的算法花的时间就多
就是说效率不高
最典型的一个特点就是
我要解决这个问题
总是要搞清楚我这个算法的执行逻辑
我第一步应该做什么
第二步应该做什么
第三步应该做什么
想清楚了才能写程序
这就叫自顶向下
你从顶层开始思考问题
然后一点点地向细节进发
这是一个非常重要的设计思路
如果你倒过来写
先从细节开始 然后再去顶层
原来主框架的逻辑都没有搞清楚
你就开始写细节
写了半天了最后发现主框架不对
那不白做吗
这是最重要的地方
一定要自顶向下逐步求精
这里面就会通过两个例子
一个是素性判定的例子
一个是最大公约数的例子
给同学们展示
我们怎么设计一个优良的算法
通过这几个例子的不同实现
你也能够看出来
同样一个问题 换了一个解决思路
对于最终程序执行来讲
它的执行效率是千差万别的
先看第一个 就是素性判定的问题
判定某个给定的自然数n
n大于2 先不考虑2的问题
先说说大于2是不是素数
按照定义 很容易写出对应的伪代码
注意在此之前 严格的算法书写模式
应该在前面写上输入部分
输出部分是什么
输入是个大于2的正整数n
输出 就是n值 是素数还是不是素数
如果是 返回true
否则返回false 这样把它写上
有什么好处呢
这就很容易地
决定这个函数的原型是什么样子
有了输入和输出
函数的原型基本上就呼之欲出了
写伪代码的时候同学们一定要注意
接下来就是步骤
步骤1、步骤2、步骤3和步骤4
就按照它的定义来 写出来就行了
伪代码我们就不解释了
看我们的实现
给出素性判定函数的第一版的实现
bool IsPrime(unsigned int n)传过来的是一个n值
然后unsigned int i初始化成2
从2开始除起 2、3、4 一直到n-1
如果全部都不能整除
那就说明它就是素数了
所以while(i
if(n % I == 0)
除了以后取余数
如果它的余数为0 就return false
它是合数不是素数
如果不成 怎么办呢
它没有return false 就i++
2除不尽
然后试着用3去除 看看能不能除尽
3不行看4、4不行看5
按照这个方式一点点地除 一直到n-1
这个循环做完 它也没有返回false
那没辙了 只能return true
这就是算法的第一版的实现
你可以验证一下是不是算法
对照算法的五个特征
有穷性、确定性、输入、输出、有效性
看它是不是满足要求 是的
那么它就是算法
然后我们就要证明这个算法
这个算法吻合我们的素数定义
所以它实际上也是算法
然后你会测试 就写一个主程序
然后调用这个函数 运行一下
有的放矢地给一些特定的数
看一看满不满足要求
最后得到结论是不是正确的
一测试发现算法是对的
刚才那个算法效率不高
那么现在就可以考虑做一个更快一点的
怎么样让算法做得更快呢
那就有一个很重要的观察
就是如果一个数是合数
那么它一定会有两个因子
假设这两个因子是p、q
p、q的乘积是n
那p、q肯定有一个大一个小
假设较小那个是p
那p肯定是小于等于q
在这种情况下p一定是小于等于根号n的
这意味着是什么呢
如果这个数n是一个合数
那么它一定有一个小于根号n的因子
如果2到根号n之间
都找不到它的任何一个因子
比根号n还大的那个整数
我们就不用找了
那个因子肯定不存在
有了这个方案的话
那就说while循环
我压根都不需要到i
我只到i<=sqrt(n)就可以
这样的话 我的测试就从2到n-1
一口气降低到了2到根号n这个级别
程序比原来快多了
你想原来如果n是10000的话
那我原来要比较2到9999
要比较这么多个数
这是多少个数 这是9998个数
你才能得到结论
现在呢 我只要比较2到100就行了
我只要比较99个数
刚才是多少啊 刚才9998
现在是多少 接近原来1%
速度立马就快了还跟多
非常非常明确
但是同学们要记住
sqrt这个函数 是C标准库里面的函数
那个函数写在“math.h”头文件里面
你要想用它 你必须包含数学库
数学库的名字叫什么呢
在C里面叫“math.h”
在C++里面呢 你可以用“math.h”包含它
也可以使用“cmath”去包含它
这两种包含策略都可以
但是你在Linux下面写程序的时候
要特别记住
Linux缺省情况下 是不把数学库
库代码装载进去的
你要装载它
应该在链接的时候g++后面写上“-lm”
把数学库 链接进去
才能够编译通过
这是第一个地方需要特别解释的
第二个地方呢 就是sqrt函数
它接受的实际上是一个
double类型的浮点数
返回值还是一个double类型的浮点数
比较这个浮点数没有意义
对于我们来说实际上是一个整数
所以我们要把sqrt得到的结果
转型成一个unsigned int
所以我们的程序代码
是按照这样方式写的
这就是素性判定的第二版
明显比第一版的效率实际上就要高的
接下来就要想
这个程序能不能做得更快
我们还有一个招
什么招呢 就是说如果这个数是个偶数
那它一定不是素数 它是个合数
刚才讲了吧 我们是大于2的数嘛
那就很明确了
if(n%2==0) 那说明它是合数 return false
再此之后 从3开始除
还除4吗 不用除 我们除5
我们只需要除奇数就行了
所以每次我不再i++ 我i+=2
整个程序运行效率
比刚才第二版又快了一倍
几乎所有的偶数被跳过
只不过前面多了一个If
后面的偶数就全眺过了
所以效率显然比刚才又快了
这是我们第三版
但是我们现在要注意到一个地方就是
这两个版本实现
实际上隐含着一个问题
这个问题一般人注意不到
早期的计算机上面
这是有可能存在的一个隐含的bug
现在新式的计算机
这个问题一般就不太突出
问题在哪里呢
就是sqrt这个求平方根这个函数
最后得到的结果它是一个浮点数
如果这个数是完全平方数
假设一个数字121
它是完全平方数 是11的平方
那么它要求根号
理论上应该等于11.00000
但是因为它表示的问题
计算机内部表示我们以前讲过
浮点数它是有误差的
存在误差的情况下面
这个11.00000
有可能被表示成了11.00001
它也可能被你表示成10.99999
可能会存在这样一种情况
如果很不幸
计算机把11这个整数
作为浮点数保存的时候
会保存成10.99999的话
那这个程序就崩掉了
为啥呀 当它转化成unsigned int的时候
它的小数部分会被砍掉
它不会四舍五入的
它一砍掉以后结果就是10
也就是说会漏过一些完全平方数
实际上是合数 但是被你误认为是素数
怎么解决这个问题呢 简单
就把这个地方加1
把sqrt取出平方根以后转换成整数
然后把它加1 多判断一次
就把这个隐含的bug消灭掉了
我自己在现代计算机上做了测试
我一直测试到100万
所有完全平方数
它最终求平方根以后得到结果
都是完全精确的
后面小数点部分全是0
所以说在现在计算机上
一般看不见它的误差
那么现在我就要问
从第二版一直到第四版
我们的程序真得很快吗
理论应该比我们第一版快
但是它真得很快吗 还真不一定
为啥不一定呢 很重要一条
你注意看我原来代码是怎么写的
我把那个求平方根的函数写在
while循环条件表达式里
这就意味着每做一次循环迭代
我就要求一次平方根 没必要
对于我们这一道题来讲
n的值在我们的函数内部是不变的
取它的平方根
只需要取一次就够了
我没必要反复计算它的平方根
所以我们最好的方案
是将这个求平方根的函数
从while循环条件表达式里面
给它提取出来 放到循环之前
这意味着我们做while循环的时候
再也不会去算根号n了
根号n在我们进入while循环之前
就已经算好了 只算一遍就够了
那么整个程序效率提升
就会非常非常明显
我们给出了五版的素性判定函数
你就看得很清楚
当我解决一个问题 设计算法的时候
应该怎么去做
第一个 必须保证你这个算法
写出来是正确的
第二个 衡量一个算法的好坏
它实际上有两个主要的出发点
一个我们称它为效率
一个称它为可理解性
算法写得好坏与否
那第一个就体现你算法做得快不快
能够迅速地准确地得到答案
这就要迅速
这就叫效率 效率要高 这是一个
第二个就是可理解性
你这个算法写出来
别人能不能够很容易看懂
这就叫可理解性好
如果可理解性不好
那么别人来维护你这个算法
想对你这个算法进行修改、更新、升级
怎么去处理呢
你的代码读都读不懂 可理解性太差
那根本没有办法维护
涉及到效率和可理解性
你设计这样一个算法就必须综合考虑
在设计一个算法的时候
效率和可理解性 有的时候是属于
鱼与熊掌不可得兼的一个东西——
你不可能既要求效率又高
可理解性又好
这种情况往往很难出现
经常出现一个场合就是
一个算法效率很高
但是很难读懂
如果这个算法很简单 一眼就能懂
它效率往往就不高
所以当我们进行算法评估的时候
衡量这个算法的好坏
必须在效率和可理解性下面
做一个折中
虽然我们说算法的好坏主要是效率
但是对于初学者来讲
可理解性其实更重要
同学们写算法的时候要特别去注意
要尽可能用一种简单的方式来实现
哪怕效率低一点也能接受
这是我们算法选择 效率和可理解性
两者要进行一次折中 注意这一点
我们来看第二个例子
这就是最大公约数这个例子
求两个正整数x和y最大公约数
直接给出函数原型
gcd 后面跟着俩整数
然后返回值就是它的最大公约数
还是一个整数 我们不考虑负数
最大公约数我给出两种设计方案
一种设计方案就是穷举法
就是我们来个最笨的方案 那就除呗
x和y两个数
一直从大往小找共同的因子
一直递减到1 如果互素的话
1就是它的最大公约数 肯定能找到
所以我们就按照它的定义
很容易就写出这个代码
我定义个临时变量t
设成x、y较小的那一个
然后用while循环
看x%t!==0 或者y%t!==0
只要有一个不等于0 就说明什么
就不能整除 我就要t--
最终就能够得到一个值t
返回这个t就行了
因为这个循环 不管怎么样
当t递减到1的时候
它就一定能够整除了
就是说这个循环是能够结束的
t就是最大公约数 这就是穷举法
当两个数互素的时候
比如说1000和1001
这两个数是互素的
所以你要按照这个方式除
先除1000 除999 除998 一直除到1
你要除1000遍
才能够得到它们的最大公约数是1
这个穷举法效率显然是低的
看第二个解决方案
这个第二种解决方案叫欧几里得算法
在中国古代称之为辗转相除法
它的基本意思就是什么
两个正整数x和y
用x整除以y 设它的余数是r
如果r是0
那么y就是它的最大公约数
如果不是的话
那我们就把y作为新的x
把r作为新的y 然后重复
就按照这个重复的模式去计算
我们三两下
就能够把它的最大公约数给除出来
明显比刚才那个算法的效率快很多
但是同学们要知道
这样一个算法别看它代码很短
它很容易就能够发现吗
不那么容易
你别觉得 中国古代很久很久之前
就有这样一个算法
如果你以前没有学过数论方面知识
让你现在自己凭空去想这个算法的实现
你就会发现这个算法真不那么容易发现
-1.1 提纲
-1.2 程序设计的基本概念
-1.3 简单C/C++程序介绍
-1.4 程序设计的基本流程
-1.5 基本语法元素
-1.6 程序设计风格
-1.7 编程实践
-第一讲 C/C++基本语法元素--编程实践提交入口
-2.1 提纲
-2.2 结构化程序设计基础
-2.3 布尔数据
-2.4 分支结构
-2.5 break语句
-2.6 循环结构
-2.7 编程实践
-第二讲 程序控制结构--编程实践提交入口
-3.1 提纲
-3.2 函数声明、调用与定义
-3.3 函数调用栈框架
-3.4 编程实践
-第三讲 函数--编程实践提交入口
-4.1 提纲
-4.2 算法概念与特征
-4.3 算法描述
-4.4 算法设计与实现
-4.5 递归算法（一）
-4.6 递归算法（二）
-4.7 容错与计算复杂度
-4.8 编程实践
-第四讲 算法--编程实践提交入口
-5.1 提纲
-5.2 库与接口
-5.3 随机数库（一）
-5.4 随机数库（二）
-5.5 作用域与生存期
-5.6 典型软件开发流程（一）
-5.7 典型软件开发流程（二）
-5.8 编程实践
-第五讲 程序组织与开发方法--编程实践提交入口
-6.1 提纲
-6.2 字符
-6.3 数组（一）
-6.4 数组（二）
-6.5 结构体
-6.6 编程实践
-第六讲 复合数据类型--编程实践提交入口
-7.1 提纲
-7.2 指针基本概念
-7.3 指针与函数
-7.4 指针与复合数据类型（一）
-7.5 指针与复合数据类型（二）
-7.6 字符串
-7.7 动态存储管理（一）
-7.8 动态存储管理（二）
-7.9 引用
-7.10 编程实践
-第七讲 指针与引用--编程实践提交入口
-8.1 提纲
-8.2 数据抽象（一）
-8.3 数据抽象（二）
-8.4 链表（一）
-8.5 链表（二）
-8.6 链表（三）
-8.7 链表（四）
-8.8 函数指针（一）
-8.9 函数指针（二）
-8.10 抽象链表（一）
-8.11 抽象链表（二）
-8.12 编程实践
-第八讲 链表与程序抽象--编程实践提交入口
-9.1 提纲
-9.2 程序抽象与面向对象
-9.3 类类型
-9.4 对象（一）
-9.5 对象（二）
-9.6 类与对象的成员（一）
-9.7 类与对象的成员（二）
-9.8 类与对象的成员（三）
-9.9 继承（一）
-9.10 继承（二）
-9.11 继承（三）
-9.12 多态（一）
-9.13 多态（二）
-9.14 编程实践
-第九讲 类与对象--编程实践提交入口
-10.1 提纲
-10.2 四则运算符重载（一）
-10.3 四则运算符重载（二）
-10.4 关系与下标操作符重载
-10.5 赋值操作符重载（一）
-10.6 赋值操作符重载（二）
-10.7 赋值操作符重载（三）
-10.8 赋值操作符重载（四）
-10.9 赋值操作符重载（五）
-10.10 流操作符重载（一）
-10.11 流操作符重载（二）
-10.12 流操作符重载（三）
-10.13 操作符重载总结
-10.14 编程实践
-第十讲 操作符重载--编程实践提交入口
-11.1 提纲
-11.2 泛型编程概览
-11.3 异常处理机制（一）
-11.4 异常处理机制（二）
-11.5 运行期型式信息（一）
-11.6 运行期型式信息（二）
-11.7 模板与型式参数化
-11.8 题外话：术语翻译
-11.9 泛型编程实践（一）
-11.10 泛型编程实践（二）
-11.11 泛型编程实践（三）
-11.12 泛型编程实践（四）
-11.13 泛型编程实践（五）
-11.14 泛型编程实践（六）
-11.15 泛型编程实践（七）
-11.16 泛型编程实践（八）
-11.17 泛型编程实践（九）
-11.18 泛型编程实践（十）
-11.19 编程实践
-第十一讲 泛型编程--编程实践提交入口
-12.1 提纲
-12.2 程序执行环境（一）
-12.3 程序执行环境（二）
-12.4 程序执行环境（三）
-12.5 程序执行环境（四）
-12.6 输入输出（一）
-12.7 输入输出（二）
-12.8 文件系统
-12.9 设备
-12.10 库（一）
-12.11 库（二）
-12.12 makefile文件（一）
-12.13 makefile文件（二）
-12.14 makefile文件（三）
-12.15 编程实践
-第十二讲 Linux系统编程基础--编程实践提交入口
-13.01 提纲
-13.02 进程基本概念
-13.03 信号
-13.04 进程管理（一）
-13.05 进程管理（二）
-13.06 进程管理（三）
-13.07 进程间通信（一）
-13.08 进程间通信（二）
-13.09 进程间通信（三）
-13.10 进程间通信（四）
-13.11 进程池
-13.12 编程实践
-第十三讲 进程编程--编程实践提交入口
-14.1 提纲
-14.2 线程基本概念
-14.3 线程管理（一）
-14.4 线程管理（二）
-14.5 线程管理（三）
-14.6 线程管理（四）
-14.7 线程同步机制（一）
-14.8 线程同步机制（二）
-14.9 C++11线程库（一）
-14.10 C++11线程库（二）
-14.11 C++11线程库（三）
-14.12 C++11线程库（四）
-14.13 C++11线程库（五）
-14.14 编程实践
-第十四讲 线程编程--编程实践提交入口
-15.1 提纲
-15.2 Internet网络协议
-15.3 套接字（一）
-15.4 套接字（二）
-15.5 编程实践
-第十五讲 网络编程--编程实践提交入口
