当前课程知识点：C语言程序设计（上） > 从问题到C语言程序设计 > 1.1 计算机的问题求解方法 > 1.1.3-3关于算法——算法的优化

返回《C语言程序设计（上）》慕课在线视频课程列表

1.1.3-3关于算法——算法的优化在线视频

1.1.3-3关于算法——算法的优化

下一节:1.1.4-1-程序设计方法

返回《C语言程序设计（上）》慕课在线视频列表

1.1.3-3关于算法——算法的优化课程教案、知识点、字幕

接下来大家已经有欲望

要讨论一个问题

算法的优化

什么是优化

我们刚才已经体会到了

三个数的排序

我们已经选择选择再选择

使这个选择的这个分支

非常的庞大

所以　

感觉上对一个简单问题复杂化

就说　

让计算机做这件事情

反而把它复杂了

由我们人去看的话　它非常简单

如何使它优化

我们来看一下

对开始　结束　输入　输出

是同样的

我们　这个问题

我们把它界定成什么

说　我输入的是a b c

a b c的是任意数

可能a大　也可能a最小

是任意数

这个大小分布　不是顺序的a b c

我希望经过这个

选择　判断以后

你就给我用一句输出

让a最大　b是中间　c最小

可不可以这样做

这个思路就调整成了　说

你不是有6个输出

你就有1个输出

至于你输入的abc

如果不是

真正的a最大　c最小的话

不是这样一个顺序

这中间可不可以交换

你把它交换成

a最大c最小

b在中间

我们说

我们下面讨论这个算法　大家看看

是不是可以实现这样

这样　就使问题简化

输出只有一句

我输出的就是abc

只不过这个abc和你输入的abc

可能对应　不是一一对应的

它已经是

a里边一定是最大的数

c里边一定是最小的数

大家看　怎么实现它

我们先拿这个

a小于b

大家看　最前边看见了　我们说

a并不是判断小于b　是说

a大于b吗

我们原来是这样判断的

是因为它的分支是这样走的

a大于b吗

如果大于怎么样　如果小于怎么样

是这样子

我们现在是说

我们想让a大于b

我现在问的　方法是说

你不大于b吗

a不大于b吗

也就是说a小于b吗

如果你是小于b　你就做一件事

把a和b交换

如果不是小于b　那就是a大于b

正好符合我们的要求　什么事都不做

如果不符合a大于b

你把它俩交换

好了　通过

这一次判断　一次交换

做到了什么

ab这个组合是固定的

a一定在b前边

我们接下来要做什么

大家考虑一下　需要做什么

就是需要判断c放在哪里合适

c到底放在哪里合适

大家先来考虑一下

c是有两个选择

还是三个选择

这是通常在这件事情上

大家容易有问题的

我们刚才认为

a大于b是这样的一个组合

我们现在判断c

c肯定是说　你比b还小吗

如果小就是abc　对的

那你不比b小吗

没有比　也就是b比你大吗

如果b大于c的话

c是不是一定放在中间

大家考虑一下

这时候　是不是还有一个选择

c不是在最后

c比b大

是不是还有一种可能

c也比现在的a大

所以　c有三个选择

三个位置选择

可能是最后　可能是中间

也可能是放在第一个位置

也就是说

至少还有两个选择

两次判断

我们第一次的判断是说

b小于c吗

也就是说　我需要交换吗

我实际上　希望是b大于c的

和刚才a小于b吗　是一样的道理

b小于c吗

如果是

那你把它俩先交换

先让b和c这两个数是固定的

一个组合bc

如果走过了交换

无论交换了还是没交换

这时候　一定是

做到了什么

最小的数在后边

只是现在中间这个数

并没有确定

没有确定它和第一个数之间的关系

就是中间这个数和第一个数

如果交换了

不管交换了还是没交换

第二个数现在都是b

最后那个数是c

现在第二个这个b　新的这个b

和a之间到底谁最大

并不确定

所以　大家这时候

不能把脑子的思路

放在了说　a与b已经交换过一次了

是因为到这

可能产生的情况　b已经改变了

所以我们在下边　需要在做一次什么

a小于b吗

和第一次的判断一模一样

a小于b吗　那此刻的a小于b吗

实际上这个b

不一定是第一次的那个b

a小于b吗

如果是

我还让这个组合是固定的

a与b交换

通过第三次的交换或者没交换

总之　流程到了这个地方的时候

这时候　abc里边一定是大中小

这样的一个位置

我们把判断的这个过程

放在这个流程图里边

这个流程是开始

提供一个任意组合的

abc　然后进行了这里边的判断

通过了这个粉颜色框里的判断之后

abc一定是大中小的位置

直接把它输出　流程结束

大家考虑一下

我们比较一下这两个算法

我们再做　刚才直接

就是没有优化这个算法的时候

我们判断的次数是5次判断

在这里边　我们是1 2 3

做了3次判断

大家说　你很计较这两次判断吗

很计较　为什么　5次和3次

差了将近一半

而判断一次比做一次交换

计算机付出的代价

我们所谓的代价是时间的代价

就是　在cpu里工作的时间的代价

要比交换要慢的多

它执行的指令是不同的

它是一个判断　选择

转移的这么一个指令

我们再看　输出

我们在第一种算法里边　

输出是6个输出

而这里边是一个输出

大家这块　有一个地方不能混

6个输出它都执行了吗

是把6个语句都执行了

对　没有

它执行的数　只执行一次　

因为你的组合只能有一种可能

只执行一次　那这里的麻烦

不是计算机的执行的问题

是人写它的问题

是你把输出这个printf函数

写了6次

程序的简洁的程度

就会看上去会啰嗦一些　这个出口

就有6个

就有6个出口

而我们这个里边　看上去就会

这个流程就会整齐一些

出口只有一个　一个输出

所以　从程序的可估性上

也是这样要好一些

但是　我们

大家会说

每个交换里有三个赋值语句

三次交换就有九个赋值语句

这个程序也会拖的长

但是

对赋值来说　计算机执行它

是简单的　用的时间的代价是小的

所以　这个算法

这样优化起来

从可读性上　还是可执行性上

都会要　比刚才

我们上边的那个算法要优化一些

关于算法　我们最后也是给几个

结论

是什么　就是步骤

算法的设计

不是取决于机器而是取决于人的创造

这是由于机器的

基本工作原理所决定的

而优化

更体现了人的聪明才智

而不是机器的聪明才智

C语言程序设计（上）课程列表：

从问题到C语言程序设计

-1.1 计算机的问题求解方法

--1.1.1--程序设计面向的问题

--1.1.2--关于计算

--1.1.3-1关于算法-算法的特征

--1.1.3-2关于算法——算法的表示

--1.1.3-3关于算法——算法的优化

--1.1.4-1-程序设计方法

--1.1.4-2-程序设计方法

--讨论题：数学模型

-1.1 计算机的问题求解方法--作业

-1.2 C语言与C程序

--1.2.1-1-C概述

--1.2.1-2-C概述

--1.2.2-C初步

--讨论题：运算符

-1.3 C语言处理系统与程序调试运行

--1.3.1C程序如何调试运行

--1.3.2常用C语言处理系统

--1.3.3DEVC++的使用-v1

--1.3.4C语言概貌小程序

-1.4 程序中的人机交互

--1.4 printf用法

--1.4.2 scanf的用法

--作业讨论区

数据计算实现与顺序结构程序设计（一）

-2.1 算术运算的C程序实现

--2.1.1 第二章

--2.1.2 C语言算术表达式概念

--2.1.3 算术运算的实现

--2.1.4 整数相除

--2.1.5 输入格式造成的计算错误

--2.1.6 求余运算

--2.1.7 自增自减运算

--2.1.8 复合运算

--fangcheng-1.c

--fangcheng-2.c

--fangcheng-3.c

--fangcheng-4.c

--算术混合运算.c

--讨论题：自增自减符

--讨论题：程序输出结果

--讨论题：程序运行结果

-2.1 算术运算的C程序实现--作业

-2.2 关系运算的C程序实现

--2.2.1 关系比较问题

--2.2.2 C语言关系表达式

--2.2.3关系运算优先级

--2.2.4 用关系运算做判断条件

--2.2.5 程序实例

--2.2.6 字符比较

--pingshifen-1.c

--panduanzhengshu.c

--pingshifen-2.c

--字符比较.c

--讨论题：比较大小

--讨论题：程序的运行

-2.2 关系运算的C程序实现--作业

-第二周作业--作业

数据计算实现与顺序结构程序设计（二）

-2.3 逻辑运算的C程序实现

--2.3.1 逻辑运算问题~1

--2.3.2 逻辑运算表达式

--2.3.3 如何判断闰年

--2.3.4 逻辑运算优先级

--2.3.5 条件运算符

--计算结合性

--2.3.7 一个简单实例

--自动购票问题.c

--讨论题：逻辑表达式

-2.3 逻辑运算的C程序实现--作业

-2.4 位运算的C程序实现

--2.4.1 什么是位运算

--2.4.2 位运算有哪些

--2.4.3 位运算怎么用

--讨论题：位运算

-2.5 几种很个别的运算

--2.5 几个很个别的运算

-2.5 几种很个别的运算--作业

-2.6 混合运算及数据类型转换

--2.6 混合运算及数据类型转换

--讨论题：数据类型

-2.7 顺序结构程序实例

--2.7.1 第一个程序：三角形

--三角形面积.c

--讨论题：工业产值

--讨论题：程序无效结果

-2.7 顺序结构程序实例--作业

选择结构的程序设计

-3.1 程序中的路径选择实现

--3.1.1_1 第三章

--3.1.1_2 神奇的if_else

--打印学生成绩.c

--一元二次方程.c

-3.1 程序中的路径选择实现--作业

-3.2 路径中的再选择——嵌套判断

--3.2.1_1 if语句的嵌套

--3.2.1_2三个数排序1029

--3.2.2 用户登录检查

--三个数排序_未优化.c

--三个数排序_优化.c

--讨论题：程序改错

-3.2 路径中的再选择——嵌套判断--作业

-3.3 复杂判断问题的C程序设计

--3.3 多级选择

--银行存款.c

--讨论题：多级选择

-3.4 多分支问题的C程序设计

--3.4.1 switch语句表达式

--3.4.2 加减乘除计算

--3.4.3 几类说明

--加减乘除运算.c

--讨论题：关于switch

-3.4 多分支问题的C程序设计--作业

-3.5 GOTO的适当使用

--3.5 GOTO的适当使用

-3.6 选择结构的程序实例

--3.6 程序展示

--计算第几天.c

--存款利息__switch实现.c

--讨论题：输出奇数

--讨论题：计算税金

-3.6 选择结构的程序实例--作业

-第四周作业--作业

循环结构的程序设计（一）

-4.1 需要重复执行的程序

--4.1.1----第四章~1

--4.1.2---while实现先判断后循环~1

--4.1.3----while循环的应用-录入速度~1

--打印学生成绩.c

--统计录入速度.c

--求平均数.c

-4.1 需要重复执行的程序--作业

-4.2 至少要执行一次的循环

--4.2.1至少要执行一次的循环

--4.2.2-do-while循环应用

--成绩录入_do while实现.c

--字符分类统计.c

--讨论题：关于while

-4.2 至少要执行一次的循环--作业

-4.3 已知循环次数用for语句

--4.3.1--用for语句控制循环次数

--4.3.2--循环的应用-求和

--求和问题.c

--斐波那契数列问题.c

--数列求和.c

--讨论题：循环语句的不同

--讨论题：循环语句

-4.3 已知循环次数用for语句--作业

-4.4 循环控制——简单循环应用

--4.4.1-循环的应用-找数-水仙花数

--4.4.2--循环的应用-求素数

--水仙花数.c

--讨论题：死循环

--讨论题：continue和break

--讨论题：猜数字

-循环结构的程序设计（一）--4.4 循环控制——简单循环应用

循环结构的程序设计（二）

-4.5 循环的嵌套

--4.5.1 循环的嵌套——九九乘法表

--4.5.2 循环的嵌套——打印三角形

--打印九九乘法表.c

--打印实心三角图案.c

--打印空心三角图案.c

--讨论题：程序运行

-4.5 循环的嵌套--作业

-4.6 break与continue

--4.6 循环中断与继续循环——break再讨论

--最大素数.c

--求正数个数及平均数.c

-4.6 break与continue--作业

-4.7 循环的综合应用

--4.7.1 数的排列组合问题

--4.7.2 循环综合应用——穷举算法

--4.7.3 循环综合应用——满足条件的数

--4.7.4 循环综合应用——求最后三位数

--4.7.5 循环综合应用——打印空心图案

--数的排列组合.c

--数的排列组合优化.c

--鸡兔同笼.c

--找满足条件的数.c

--输出14的13次方的最后三位数.c

--打印空心字符.c

--讨论题：打印图形

--讨论题：打印空心图形

--讨论题：计算闰年

-第六周作业

--虚拟实验：循环程序设计实验

-第六周作业--作业

数组（一）

-5.1 同类有序数据处理问题

--5.1.0 数组开篇

--5.1.1 同类有序数据存储问题

--讨论题：下标变量与下标

-5.2 一维数组的定义和引用

--5.2.1_1 数组的定义~1

--5.2.1_2 数组的初始化

--5.2.2 一维数组的输入输出

--5.2.3 一维数组的应用1--成绩排序(选择法)~2

--5.2.4 一维数组的应用2--Fibonacci数列

--数组定义.c

--数组初始化.c

--输出大于平均值的数.c

--反向输出.c

--选择法_成绩排序.c

--求斐波那契数列前n项.c

--讨论题：对称数

--讨论题：关于'\0'

-5.2 一维数组的定义和引用--作业

-5.3 一维字符串数组

--5.3 一维字符串数组11.24~1

--用函数测试字符串长度.c

--讨论题：编程

-5.4 字符串处理函数

--5.4 字符数组的输入与输出

--字符串反向.c

--字符串函数

--讨论题：程序如何运行

--讨论题：黑色星期五

数组（二）

-5.5 二维数组的定义与使用

--5.5 二维数组定义

--二维数组的定义与初始化.c

-5.6 二维数组的输入输出

--5.6 二维数组的输入与输出

--二位数组输出_矩阵输出.c

--讨论题：随机数据存储

-5.6 二维数组的输入输出--作业

-5.7 二维数组的应用‍

--5.7.1二维数组的应用-转置矩阵

--5.7.2 用一维数组方式引用二维数组元素

--转置矩阵.c

--找二维数组最大数.c

--讨论题：修改程序

--讨论题：关于随机数函数 rand()

-5.8 二维字符数组

--5.8 单词排序

--单词排序.c

--讨论题：回文字符串

-5.8 二维字符数组--作业

-5.9 数组综合应用

--5.9.1 应用1——学生成绩统计

--统计成绩.c

--5.9.2 应用2——删除重复字符

--删除串中的重复字符串

--5.9.3 应用3——统计字符

--5.9_4数组的应用4--矩阵相乘

--统计字符次数.c

--讨论题：洗牌

-本期课程结束语

-第八周编程作业

--虚拟实验：冒泡排序算法程序设计实验

期末复习

-《C语言程序设计（上）》期末复习参考

期末复习答案

-《C语言程序设计（上）》期末复习参考答案

1.1.3-3关于算法——算法的优化笔记与讨论

也许你还感兴趣的课程:

© 柠檬大学-慕课导航课程版权归原始院校所有，
本网站仅通过互联网进行慕课课程索引，不提供在线课程学习和视频，请同学们点击报名到课程提供网站进行学习。