当前课程知识点：基于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 编程实践
-第十五讲 网络编程--编程实践提交入口
