2.2 简单算法举例、计算思维与结构化程序设计方法.mp4在线视频

大家好

我是云南大学信息学院的丁海燕老师

欢迎走进C语言程序设计课堂

今天我们讲解的是

简单算法举例

计算思维与结构化程序设计

简单算法举例如下

例2.5

求一元二次方程

ax2+bx+c=0的根

由求根公式可知

一元二次方程的根

是由系数a、b、c的值决定的

利用判别式

b2-4ac

可以判断方程的根的情况

一元二次方程

ax2+bx+c=0的根

与判别式b2-4ac有如下关系

当∆≥0的时候

方程有两个实数根

x1=-b+√∆/2a

x2=-b-√∆/2a

二

当∆<0的时候

方程无实数根

根据分析

分别用自然语言和流程图

描述的算法

如图所示

例2.6

找出一组任意的正整数中

值最大的数

以-1为结束标志

现有一组任意的正整数

希望从中找到值最大的数

如果将随机数中的每一个数字

看成是一颗豆子的大小

可以将问题转化成“捡豆子”

即

依次从一个口袋中

取出一颗豆子

与杯子中的豆子进行比较

杯子中总是保留每次比较后

较大的那颗豆子

直到取出并比较完最后一颗豆子

杯子中的豆子

就是最大的一颗豆子

针对原问题

我们可以用dat

表示每一个数字

类似于一颗豆子

每次比较后

将大的数都保留在max

类似于杯子中

依次对每一个data

与max进行比较判断

由于在算法设计时

事先不知道任意数究竟有多少

我们可在任意数的最后

增设一个不参加比较的数

假设最后一个数是-1

由于问题中的任意数

均为正整数

-1

远离可能出现的正确数据

起到了终止运行的作用

因此也称为终止标志

当然

也可选择其它的数作为终止标志

如-2

-999等

当data的值为-1时

说明已判断完所有的数

这时可停止比较

max中的数即为最大数

根据分析

分别用自然语言和流程图

表示的算法

如图所示

下面介绍计算思维

可以看出

在利用计算机求解问题的一系列过程中

包括了思维过程

设计过程和计算过程

对于给定的问题

首先

必须对提出的问题进行分析思考

即为

思维过程

其次用规范的形式对算法进行描述

即设计过程

最终通过计算机程序实现算法

使问题得到解决

即为计算过程

显然

计算性的思维

已贯穿了计算机求解问题的全过程

无论是形成解题思路

还是编写程序

其思维的目标都是围绕可计算性

或可操作性

即计算思维

美国卡内基梅隆大学计算机系

系主任周以真教授

提出了 计算思维的概念

所谓计算思维

就是用计算的基础

概念去求解问题

设计系统

理解人类行为

她认为

计算思维

是每个人都渴望具有的

能够学习

和实际运用的

具有普适性的思维方式和应用技巧

表2.3给出计算思维

在日常生活事例中的体现

例如1

出门前

把所需要的东西放进背包

体现了计算思维的缓存算法

二

弄丢手套时

沿走过的路寻找

体现了计算思维的回溯算法

三

停电时电话仍然可用

体现了算法的健壮性

表现为失败无关性

和设计冗余性

四

在什么时候需要进货

体现了在线算法

五

到银行排队办理业务

体现了多服务器系统的模型算法

六

尽可能多的购买商品带回家

体现了贪心算法

七

天气预报

体现了数据挖掘算法

八

拍电报

体现了编码算法

九

下棋

体现了人工智能算法

例2.7

计算思维过程

我国古代数学家张丘建

在《算经》中提出了著名的

“百钱百鸡问题”

鸡翁一

值钱五

鸡母一

值钱三

鸡雏三

值钱一

百钱买百鸡

翁

母

雏

各几何

题目的意思是

一只公鸡卖5枚钱

一只母鸡卖3枚钱

三只小鸡卖1枚钱

用100枚钱买100只鸡

能买到公鸡

母鸡

小鸡各多少只

这是一个不定方程问题

有3个未知数

2个方程

设公鸡

母鸡

小鸡数分别为x、y、z

则有x+y+z=100

5*x+3*y+z/3=100

需要让计算机去一一测试是否符合条件

找出所有可能的答案

这里采用穷举算法

穷举算法的基本思想是

对问题的所有可能答案一一测试

直到找到正确答案

或测试完全可能的答案

采用伪代码来描述算法

算法描述一

for( x=1;x<=100;x++)

/*控制公鸡数x在1~100变化*/

二

for(y=1;y<=100;y++)

/*控制母鸡数x在1~100变化*/

三

for( z=1;z<=100;z++)

/*控制小鸡数x在1~100变化*/

if ( (x+y+z=100)

&& (5*x+3*y+z/3=100) )

then 输出x,y,z的值

/*验证是否同时满足2个条件

可得到一组解*/

将算法转化为程序后

运行结果为

x=4

y=18, z=78

x=8

y=11

z=81

x=12

y=4

z=84

要给出可行的解

三重循环的运行次数

达到了一百万次

时间效率较低

能否对算法进行改进

由于数量的限制

一旦购买公鸡和母鸡的数量确定

则由x+y+z=100

可直接得到购买小鸡的数量z=100-x-y

这样就将算法一的三重循环

降为二重循环

算法描述二

for( x=1;x<=100;x++)

for(y=1;y<=100;y++)

z=100-x-y；

/*在二重循环控制下

小鸡的数量z受x、y的制约*/

if ( (x+y+z=100) && (5*x+3*y+z/3=100))

then输出x,y,z的值

二重循环的运行次数为一万次

减少了

九万九千次的运行次数

算法的一个简单循环优化

效率就提升了99%

能否继续简化算法二

由于价格的限制

如果只是一种鸡

公鸡数量不可能超过20

就可以在循环中

把公鸡数量的变化限制在1~20

同理

母鸡数量的变化限制在1~33

得到算法描述三

for( x=1;x<=20;x++)

/*控制公鸡数x在1~20变化*/

for(y=1;y<=33;y++)

/*控制母鸡数x在1~33变化*/

z=100-x-y

如果这两个条件成立

那么则输出x,y,z的值

算法三的循环次数又减少了1万

-20×33=9340次

比算法二的效率又提升了93%

上述一系列的简化和优化处理

体现了计算思维的思维过程

通过设置循环控制条件

来减少穷举和组合的次数

从而提高算法的时间效率

能否对算法再做改进

进一步减少循环次数

请同学们自己思考

计算思维有哪些特征呢

计算思维是信息思维

它不同于传统的数学思维

不关注逻辑关系

推理演算的严谨程度

而是强调问题解决的操作过程

和应用实践

计算思维的本质是抽象

和自动化

计算思维的抽象

指的是用抽象的方法

表达实际的问题

计算思维的自动化

则体现在程序的机械式执行

C语言是一种结构化程序设计语言

那么什么是结构化程序设计方法呢

结构化程序设计

是1965年

由荷兰计算机科学家

狄克斯特拉提出来的

“结构化程序设计”的主要观点是

采用自顶向下

逐步求精的程序设计方法

使用顺序

选择

循环

三种基本控制结构构造程序

以模块化设计为中心

将待开发的软件系统

划分为若干个相互独立的模块

使得完成每一个模块的工作

变得简单而明确

为设计一些较大的软件

打下良好的基础

我们来看例2.8

开发一个简易图书管理系统

要求满足以下功能需求

一

能够进行新书入库

现有图书信息修改

以及删除管理

二

能够实现对用户信息的查询

和编辑管理

三

能够进行借书

还书及超期罚款管理

四

能够进行查询管理

按自顶向下

逐步求精的方法

将图书管理系统划分为三个模块

借还管理

查询管理

和系统维护

每一个模块

又可进一步划分

借还管理模块包括借书管理

还书管理

及超期管理等模块

查询管理模块包括图书查询

用户查询和借阅查询等管理模块

系统维护模块包括

系统登录

权限设置

图书资料维护和用户维护等

管理模块

图书管理系统模块化设计如图所示

本章小结

算法是用计算机

来解决某一类问题的步骤

计算思维的本质

是抽象和自动化

就是用计算机的计算方法思考问题

和表达行为

算法必须通过程序运行来实现

算法的好坏

直接影响程序的通用性和运行效率

掌握算法的概念

及算法的描述方法

从问题出发

抽象成解决问题的算法描述

然后用程序设计语言

实现问题求解的自动化

通过这样一条主线

将计算思维的本质

抽象和自动化

贯穿于程序设计的过程中

结构化的程序设计采用

自顶向下

逐步求精

模块化的设计

结构化编程思想

好了

同学们

简单算法举例

计算思维与结构化程序设计

我们就学到这儿

下节课再见