当前课程知识点:C语言程序设计 > 第2章 算法 > 2.1 算法的概念与描述 > 2.1 算法的概念与描述 .mp4
大家好
我是云南大学信息学院的丁海燕老师
欢迎走进C语言程序设计课堂
今天我们讲解算法的概念和算法的描述
通过上一章的学习
我们知道通过编写正确的程序
并上机运行可以给出问题的求解结果
那么如何编写程序
利用计算机进行求解
才能实现解决问题的要求呢
下面介绍算法的概念
Pascal之父
结构化程序设计的先驱沃思提出了一个公式
程序 = 算法 + 数据结构
算法是贯穿在所有计算机程序设计中的一个基本概念
算法是程序设计的核心
是程序设计的灵魂
算法的好坏直接影响了程序的通用性和有效性
影响着解决问题的效率
那么,什么是算法
下面我们先看一个例子
一名学生要上大学
需经历一系列的步骤:
1.填高考报名表
2.拿到准考证
3.参加考试
4.填志愿
5.获得录取通知书
6.到大学报名注册
这里考入大学的1→6步骤也是算法的体现
算法是为解决一个问题而采取的方法和步骤
人们解决问题的一般过程为
明确问题→分析问题→脑中收集信息
→根据已有的知识、经验判断
推理→采用方法和设计步骤→解决问题
算法必须通过程序运行来实现
算法的好坏直接影响程序的通用性和运行效率
下面通过一个案例进一步说明解决问题的步骤
例2.1 农夫过河问题
有一农夫带着一条狼
一只羊和一筐菜
想从河的左岸乘船到右岸
但由于船太小
农夫每次只能带一样东西过河
而且如果没有农夫看管,狼会吃羊,羊会吃菜
请问:农夫怎样过河才能把每个东西安全地送过河
分析思考:要使农夫能安全地将这三样东西带过河
只需避免农夫与狼和羊
农夫与羊和菜不在同岸的情况发生
农夫即可把每样东西安全地送过河
解决方案1
第一步:人和羊过河,人返回,留下羊
第二步:人和狼过河,人和羊返回,留下狼
第三步:人和菜过河,人返回,留下菜
第四步:人和羊过河
在这个案例中
算法就是解决方案而且步骤是有限的
农夫只要按照上述四个步骤
可把每样东西安全地送过河
当然,解决方案不是唯一的
下面来看解决方案2
步骤1:人和羊过河,人返回,留下羊
第二步:人和菜过河,人和羊返回,留下菜
第三步:人和狼过河,人返回,留下狼
第四步:人和羊过河
可见,对同一个问题
可以有不同的解决方法和步骤
对照人们解决问题的一般过程
计算机解题过程可简单地概括为
分析问题→设计算法→编写程序→运行程序/验证结果
图灵奖得主 克努特给出算法的定义
一个算法就是一组有穷规则
这些规则给出求解特定类型问题的操作序列
算法的特征
1.输入:一个算法有零个或多个输入
2.输出:一个算法有一个或多个输出
3.确定性:一个算法的每个步骤都必须精确地定义
4.有限性:一个算法应包括有限的操作步骤
能在执行有穷的操作步骤之后结束
5.可行性:一个算法一般认为是可行的
在实际的算法设计中还要注意算法的通用性
当针对一个问题设计出算法后
该问题的多个实例都能被求解
对算法的评价从五个方面进行
算法的正确性、可读性、健壮性、效率、存储量需求
有三种常见的方法描述算法
(1)自然语言描述算法
例2.2 用自然语言描述解决下列问题的算法
已知圆的半径,求圆面积
算法描述:
开始
1.输入半径r 的值
2.计算面积area=3.14*r*r
3.输出面积area 的值
结束
例2.3 用自然语言描述解决下列问题
求任意两个数a 和b 中的较大数,并输出这个数
算法描述
开始
1.输入a 的值和b 的值
2.如果a≥b,则 输出a; 否则 输出b
结束
例2.4 用自然语言描述解决下列问题的算法
求出从1 开始的连续n个自然数的和
算法描述
第一步输入n 的值
第二步 设sum 的初始值为0,i 的初始值为1
第三步 如果i≤n 时
顺序执行S4,否则执行S7
第四步 计算sum 加上i 的值后
重新赋值给sum
第五步 计算i 加1
然后将值重新赋值给i
第六步 转去执行S3
第七步 输出sum 的值
结束
第二种描述方法是流程图
使用流程图描述算法
就是用一组标准的图形符号来描述算法
常用的流程图符号有
圆角矩形表示一个算法的开始、结束
平行四边形表示算法过程中
从外部获取信息或将处理过的信息输出
矩形表示算法过程中
需要处理的信息
只有一个入口和一个出口
菱形表示算法过程中的分支结构
在菱形框中标明判断条件
箭头在算法过程中指示流程的方向
例2.2 已知圆的半径,求圆面积
下面用流程图描述的算法如图所示
输入r,计算area,输出area的值
例2.3 求任意两个数a和b中的较大数
并输出这个数
用流程图描述的算法如图所示
输入a,b,若a>=b成立,输出a,否则输出b
例2.4 求出从1 开始的连续n个自然数的和
用流程图描述的算法如图所示
用伪代码描述算法
请大家课后自学完成
好了,同学们
算法的概念和描述我们就学习到这儿
下节课再见
-1.1 C语言的发展和特点
--1.1自测题
-1.2 一个简单的C语言程序
--讨论单元
--源程序 例1.1 输出一行文字Hello,world!”
--源程序 例1.2 多个函数构成的程序,求两个整数中较大者
--1.2自测题
-1.3 程序、程序设计语言及C程序运行步骤
--讨论单元
--1.3 自测题
-第1章 自测题
-2.1 算法的概念与描述
--讨论单元
--2.1自测题
-2.2 简单算法举例、计算思维与结构化程序设计方法
--2.2 简单算法举例、计算思维与结构化程序设计方法.mp4
--讨论单元
--2.2 自测题
-第2章 自测题
-3.1 C语言程序的简单结构和标识符
--3.1自测题
-3.2 常量、变量与赋值
--讨论单元
--3.2 自测题
-3.3 算术、赋值、自增自减运算符
--3.3 自测题
-3.4 条件、逗号、取地址、求字节运算符以及各类数值型数据间的混合运算
--3.4 条件、逗号、取地址、求字节运算符以及各类数值型数据间的混合运算.mp4
--3.4 自测题
-3.5 输入输出举例与字符的输入输出
--源程序 例求一元二次方程的根。a、b、c由键盘输入。设b2-4ac>0
--源程序 例2. 从键盘输入BOY三个字符,然后把它们输出到屏幕
--3.5 自测题
-3.6 格式化输出printf函数
--3.6自测题
-3.7 格式化输入scanf函数
--讨论单元
--3.7 自测题
-3.8 C语言基本数据类型
--3.8 自测题
-C语言运算符与表达式自测题
-第3章 自测题
-4.1 关系、逻辑运算符和if语句
--讨论单元
--源程序 例4.2 输入两个实数,按代数值由小到大的顺序输出这两个数。
--4.1自测题
-4.2 switch语句
--讨论单元
--4.2自测题
-4.3 选择结构程序举例
--4.3 自测题
-第4章 自测题
-5.1 while和do…while语句
--讨论单元
--源程序 例5.1 用while语句求1+2+3+…+100
--源程序 例5.2 用do…while语句求1+2+3+…+100
--5.1自测题
-5.2 for语句
--5.2 自测题
-5.3 改变循环执行的状态及嵌套循环
--源程序 例5.5 输出100~200之间的不能被3整除的数。
--5.3 自测题
-5.4 循环结构程序举例1
--源程序 例1 按每行输出5个数的形式输出Fibonacci数列的前20项 。
--源程序 例2 判断输入的某个数m是否为素数。若是素数,输出“YES”,若不是,输出“NO”。
--源程序 例3 用牛顿迭代法求方程 2x3+4x2-7x-6=0 在x=1.5附近的根。
--源程序 例4. 求2~10000以内的完全数(一个数的因子(除了这个数本身)之和等于该数本身。)
--5.4 自测题
-5.5 循环结构程序举例2
--5.5自测题
-第5章 自测题
-6.1 一维数组的定义和引用
--讨论单元
--6.1自测题
-6.2 一维数组编程
--6.2 自测题
-6.3 二维数组的定义和引用
--6.3 自测题
-6.4 二维数组编程
--源程序 例2 将一个二维数组行和列的元素互换,存到另一个二维数组中。
--6.4 自测题
-6.5 字符数组的定义、初始化和输入输出
--讨论单元
--6.5 自测题
-6.6 字符串处理函数
--6.6 自测题
-6.7 字符数组编程
--6.7 自测题
-第6章 自测题
-7.1 函数概念以及怎样定义和调用函数
--源程序 例7.1
--7.1自测题
-7.2 函数调用时的数据传递、调用过程及函数返回值
--7.2 函数调用时的数据传递、调用过程及函数返回值.mp4
--讨论单元
--源程序 例7.2
--7.2 自测题
-7.3 对被调函数的声明和函数的嵌套调用
--源程序 例7.4
--7.3 自测题
-7.4 函数的递归调用
--源程序 例7.6
--源程序 例7.7
--7.4 自测题
-7.5 数组作为函数参数1
--讨论单元
--7.5 自测题
-7.6 数组作为函数参数2
--7.6 自测题
-7.7 局部与全局变量,内部与外部函数
--7.7 自测题
-7.8 变量的生存期与局部变量的存储方式
--7.8 自测题
-7.9 全局变量的存储类别
--7.9 自测题
-第7章 自测题
-8.1 指针概念、指针变量的定义和引用
--源程序 例8.1
--讨论单元
--8.1自测题
-8.2 指针变量作为函数参数
--讨论单元
--8.2 自测题
-8.3 数组元素的指针的运算以及通过指针引用数组元素
--8.3 数组元素的指针的运算以及通过指针引用数组元素.mp4
--8.3 自测题
-8.4 用数组名作函数参数
--8.4 自测题
-8.5 通过指针引用多维数组
--8.5 自测题
-8.6 通过指针引用字符串
--8.6 自测题
-8.7 字符指针作函数参数
--8.7 自测题
-8.8 指向函数的指针
--8.8 自测题
-8.9 返回指针值的函数
--源程序 截取子串
--8.9 自测题
-8.10 指针函数和多重指针
--8.10 自测题
-8.11 动态内存分配与指向它的指针变量
--讨论单元
--8.11 自测题
-第8章 自测题
-9.1 定义和使用结构体变量
--9.1自测题
-9.2 使用结构体数组
--讨论单元
--9.2 自测题
-9.3 结构体指针
--9.3 自测题
-第9章 自测题