当前课程知识点:大学计算机基础 > 第六章 算法与程序设计 > 6-1 算法基础 > 6-1 算法基础
要使计算机能完成预定的工作
首先必须为如何完成预定的工作
设计一个软件算法
然后再根据软件算法编写程序
本节我们介绍软件算法的基础知识
首先我们看算法的概念
算法就是解决问题的方法和步骤
当我们需要解决一类问题的时候
解决这类问题的一系列步骤
就确定了解决这类问题的一个运算
序列
对于这类问题的任何的初始的数值
都能按照算法一步步执行计算
经过有限的步骤后产生计算的结果
运算的序列就是资本问题的一个算法
我们计算机程序设计
软件开发在算法的基础上
使用程序设计语言设计程序
下面我们看一个具体问题的算法的
例子
假设我们要求任意两个正整数A和B
的最大公约数
那么相应的算法我们设计如下
第1步比较A和B的大小
将较大的数设为A较小的数设为B第
2步
A÷B得到余数C第3步
如果C为0
则最大公约数就是B否则的话将B
赋值给A,C赋值给B
重复进行上述第2步
第3步
以上三步就构成了我们求最大公约数
这一类问题的算法
此算法被称为辗转相除法或欧几里得
算法
利用上述算法
假设我们要求12和8的最大公约数
那么算法的执行步骤比较12和8的
大小
将12赋值给A,8
负责给B计算A÷B
求A÷B的余数
得余数为4
四
赋值给C由于此时C不等于0
故而我们将B的值赋值给A即A=8
将C的值赋值给B级B=4
再次计算新的A除以B求其余数
此时8÷4
余数为0
由于余数C得0
因此此时B的值4即为12和8的最
大公约数
这就是我们利用上述欧几里得算法来
计算具体的12和8的最大公约数的
步骤
对于一个完整的算法
应该具有一些基本的性质
首先要有一个算法的名称
为了便于描述和交流
对于经典的算法都会有一个名称
比如我们刚刚讲的求最大公约数的
算法
就被命名为欧几里得算法
输入算法一般应有一些输入的数据
或者初始条件
比如欧几里得算法里面必须输入A和
B的值
才能求出两个具体数的最大公约数
输出
对于输入数据进行运算处理后
应该有一个或多个运算结果作为输出
比如我们上述例子当中
输入A和B的值分别为12和8
那么算法的输出为4
有效性
算法的每一步都是可执行的
假设人们用纸和笔做有些字的计算后
应该也能得到正确的计算结果
正确性
算法的输出结果必须是正确的
比如上例欧几里得算法当中
如果按照算法求得
12和8的最大公约数是为4
这才是一个正确的算法
有穷性
一个算法必须在执行有限操作步骤后
终止
例如我们上述算法当中算法执行五步
后终止
算法的表示
为了方便表达和交流算法
需要用合适的载体把算法表达出来
常用的表示自然语言
伪代码
流程图等等
比如我们例61当中的欧几里得算法
用自然语言的方式表达了算法
下面我们再介绍其他两种常用的方法
第1种伪代码
伪代码通常采用自然语言
数学公式和字母符号来描述算法
是一种接近于计算机编程语言的算法
描述方法
便于像计算机程序过渡
所以人们在实际当中通常都采用伪
代码来描述算法
例如欧几里得算法的每代码描述如下
算法开始
数目A和B的值
如果A小于B则交换A和B的值
我们交换的目的是为了保证较大的数
始终是赋值给A的
然后求A除以B的余数
将于数赋值给C当C>0
也就是C不等于0的时候
执行下面的循环语句
反复的将B赋值给AC负责给BA÷
B的余数赋值给C多次执行之后
直到C>0不满足
也就是C=0的时候
这个循环已经结束
我们输出B的值,即为我们求得的A和
B的最大公约数
此时算法结束
第2种方法
流程图的方法
流程图是用图形表示算法的工具
它有一些图形框和带箭头的线条组成
欧几里得算法用流程图表示如下
我们在开始和结束部分所用的符号为
起止框
表示算法的开始和结束
输入B的值和输出B的值
所用的符号为输入输出框
表示算法的输入
输出
操作
A小于B和C不等于0
所用的为判断框
表示算法当中的条件判断
交换AB的值
等用的符号为处理框
表示算法当中的各种处理操作
框内填写各种指令和指令的序列
连接各种符号的流程线
符号
表示算法的一个执行流程
箭头指向流程的方向
算法的评价
解决一个问题
通常有多种不同的方法
从而可以设计���多个不同的算法
虽然这些算法都能正确地执行
但是肯定存在一定的差异
我们一般从算法执行所占用计算机的
执行时间和重组空间两个方面来评价
一个算法
很显然执行时间短
占用存储空间少的算法
是好的算法
算法的优劣
通常用算法的复杂度来衡量
一般与算法所解决问题的规模有关
包括时间复杂度和空间复杂度
比如我们对N个学生某门课程的成绩
要从高到低排序
那么学生人数N就是这个问题的问题
规模问题规模一般用字母N表示
表示算法所处理的数据范围的大象
时间复杂度
时间复杂度
并不关心某个算法的具体执行时间
因为精确的执行时间不仅与算法本身
有关
还有所计算的计算机硬件
操作系统等有关
所以算法的时间复杂度
关心的是算法当中最耗费时间的指令
它的执行次数
人们关心随着问题规模的增长
时间增长率的情况
所以一般我们表示为时间复杂度为F(n)
即问题规模N的函数
空间复杂度
空间复杂度通常指执行算法所需要的
存储开销
比如用到了多少个变量
一般我们空间复杂度表示为SN等于
FN级问题规模N的函数
例如对N个学生进行排序
需要把N个学生的成绩都放入存储器
当中
那么该问题算法的空间复杂度
函数为SN=N与时间复杂度一样
我们一般只关心随问题
规模的增长
空间复杂度的增长率
在评价算法的时候
空间复杂度和时间复杂度较低的算法
我们就称之为是较优的算法
在本节当中我们简单的介绍了算法的
概念
算法的性质
以及算法的表示和算法的评价
等关于算法的基础知识
谢谢观看
行
-1-1 计算机的诞生
--第一章 习题1
--计算机的诞生1
--计算机的诞生2
-1-2 计算机的分类
--第一章 习题2
--计算机的分类
-1-3 计算机的应用领域
--第一章 习题3
-1-4 计算机系统组成
--第一章 习题4
--计算机系统组成1
--计算机系统组成2
-1-5 计算机思维的定义
--第一章 习题5
--计算思维1
-1-6 计算思维的特点
--第一章 习题6
--计算思维2
-1-7 计算思维的应用案例
--第一章 习题7
--计算思维3
-第一章 章测试
-2-1 进位计数制表示方法
--第二章 习题1
-2-2 进位计数制的相互转换
--第二章 习题2
--进位计数制2
-2-3 整数的表示方法
--第二章 习题3
--整数的表示1
-2-4 浮点数表示方法
--第二章 习题4
--浮点数的表示1
-2-5 BCD格式表示法
--第二章 习题5
--BCD码
-2-6 算术运算
--2-6 算术运算
--第二章 习题6
-2-7 运算溢出及判断
--第二章 习题7
--运算的溢出
-2-8 逻辑运算
--2-8 逻辑运算
--第二章 习题8
--逻辑运算
-2-9 ASCII编码
--第二章 习题9
-2-10 Unicode编码
--第二章 习题10
-2-11汉字编码
--2-11汉字编码
--第二章 习题11
--汉字编码
-2-12数据校验编码
--第二章 习题12
--数据校验编码
-第二章 章测试
-3-1中央处理器
--3-1中央处理器
--第三章 习题1
--中央处理器
-3-2 存储器
--3-2 存储器
--第三章 习题2
--存储器1
--存储器2
--存储器3
-3-3 总线和接口
--第三章 习题3
--总线
-3-4 外部设备
--3-4 外部设备
--第三章 习题4
--外部设备
-3-5 冯.诺依曼体系结构
--第三章 习题5
-3-6 计算机常用性能指标
--第三章 习题6
--性能指标1
--性能指标2
-3-7嵌入式系统
--第三章 习题7
--嵌入式系统
-3-8哈佛体系结构
--第三章 习题8
--哈佛体系结构
-3-9 DSP简介
--3-9DSP简介
--第三章 习题9
--DSP
-3-10 虚拟台式计算机模拟器
--虚拟桌面架构
-3-11 4位计算机模拟器
-第三章 章测试
-4-1计算机软件分类
--第四章 习题1
--软件分类
-4-2软件的工作模式
--第四章 习题2
--软件的工作模式
-4-3软件的安装方法
--第四章 习题3
--软件安装
-4-4计算机软件生命周期
--第四章 习题4
--生命周期1
--生命周期2
--生命周期3
--软件测试1
--软件测试2
-4-5计算机软件开发过程模型
--第四章 习题5
- 4-6 常用软件介绍-办公软件
--第四章 习题6
-办公软件实例1 文字处理软件
-办公软件实例2 电子表格软件
-办公软件实例3 演示文稿软件
-4-7 常用软件介绍-多媒体创作软件
--第四章 习题7
-多媒体创作软件实例1 音频处理软件
-多媒体创作软件实例2 图像处理软件
-多媒体创作软件实例3 动画制作软件
-多媒体创作软件实例4 视频处理软件
-4-8 常用软件介绍-网页制作软件
--第四章 习题8
-第四章 章测试
-5-1 操作系统概述
--第五章 习题1
--操作系统
--操作系统分类
--操作系统管理
-5-2 Windows 7基本操作
--第五章 习题2
-5-3 Windows 7文件管理
--第五章 习题3
-5-4 Windows 7程序管理
--第五章 习题4
-5-5 Windows 7系统安全
--第五章 习题5
--操作系统安全
-5-6 Windows 7计算机管理
--第五章 习题6
-5-7 Dos命令
--第五章 习题7
--dos
-5-8 Windows 7常用软件
--第五章 习题8
-5-9 Linux操作系统
--第五章 习题9
--Linux
-5-10 手机操作系统
--第五章 习题10
-5-11 虚拟机及Vmware介绍
--第五章 习题11
--虚拟机
--虚拟机使用
-第五章 章测试
-6-1 算法基础
--6-1 算法基础
--第六章 习题1
-6-2 程序设计语言分类
--第六章 习题2
-6-3 程序设计过程
--第六章 习题3
-6-4 程序设计方法
--第六章 习题4
-6-5 程序设计语言基本要素(一)
--第六章 习题5
-6-6 程序设计语言基本要素(二)
--第六章 习题6
-6-7 Python简介及编程环境配置
--第六章 习题7
-6-8 程序设计应用举例
--第六章 习题8
-第六章 章测验
-7-1 数据库技术概述
--第七章 习题1
--信息和数据
-7-2 数据库管理系统
--第七章 习题2
--数据库管理系统
-7-3 数据库系统的组成与功能
--第七章 习题3
--独立性
--数据库系统分类
-7-4 关系模型的数据结构
--第七章 习题4
--E-R图
--三级模式结构
-7-5 关系模型的数据操作及完整性约束
--第七章 习题5
--关系模型
--数据库范式
--完整性约束
-7-6 Access数据库的建立
--第七章 习题6
--Access
-7-7 Access的数据查询
--第七章 习题7
-第七章 章测试
-8-1计算机网络概述
--第八章 习题1
--定义
-8-2网络分类
--8-2网络分类
--第八章 习题2
--分类
-8-3数据传输
--8-3数据传输
--第八章 习题3
--数据传输
-8-4网络拓扑结构
--第八章 习题4
--网络拓扑结构
-8-5网络体系结构
--第八章 习题5
--网络体系结构
-8-6网络互连
--8-6网络互连
--第八章 习题6
--网络互连
-8-7Internet基础:TCP╱IP协议结构
--第八章 习题7
--TCP/IP模型
--IP协议
-8-8Internet基础:IP地址
--第八章 习题8
--IP地址
-8-9Internet基础:域名系统
--第八章 习题9
--域名
-8-10Internet基础:Internet的基本服务
--8-10Internet基础:Internet的基本服务
--第八章 习题10
--Internet
-8-11Internet基础:Internet的接入
--第八章 习题11
-第八章 章测试
-9-1信息安全的基本概念
--第九章 习题1
--信息安全的CIA
--攻击与防御
-9-2 密码技术及应用
--第九章 习题2
--数字签名
-9-3防火墙技术
--9-3防火墙技术
--第九章 习题3
--防火墙的分类
--防火墙的基本特性
-9-4恶意软件
--9-4恶意软件
--第九章 习题4
--恶意软件类型
-9-5入侵检测技术
--第九章 习题5
--入侵检测概念原理
--入侵检测分类
-第九章 章测试
-10-1 云计算
--10-1 云计算
--第十章 习题1
-10-2大数据
--10-2大数据
--第十章 习题2
-10-3物联网
--10-3物联网
--第十章 习题3
-10-4机器学习
--10-4机器学习
--第十章 习题4
-10-5人工智能
--10-5人工智能
--第十章 习题5
-10-6物联网应用
-第十章 章测验
-1-0 准备步骤
--1-0 准备步骤
-1-1 台式机组装
-1-2 笔记本电脑组装
-3-1 启动和退出Word
-3-2 创建、编辑和保存Word文档
-3-3 封面的制作
--封面的制作-1
--封面的制作-2
--封面的制作-3
--封面的制作-4
-3-4 长文档编辑
--长文档编辑
-3-5 页面插入与目录
-3-6 页眉页脚与页码
-3-7 完成文档
-4-1 创建和编辑Excel表格
-4-2 简单公式和函数
-4-3 插入图表
--4-3 插入图表
-4-4 电子表格中数据的管理
-5-1 创建演示文稿与添加幻灯片
-5-2 编辑演示文稿
-5-3 设置演示文稿外观
-5-4 交互式演示文稿的设置
-5-5 设置演示文稿动画和音乐
-5-6 演示文稿放映
-6-1 图像的修饰
-6-2 淡黄色的记忆
-6-3 心形贺卡
--6-3 心形贺卡
-6-4 燃烧字
--6-4 燃烧字
-6-5 闻味的小狗狗
-6-6 换脸
--6-6 换脸
-7-1 逐帧动画的制作
-7-2 动作补间动画的制作
-7-3 形状补间动画的制作
-8-1 网站制作前期工作
-8-2 在Dreamweaver中建立和管理站点
-8-3设计制作网站主页
-8-4 制作网站导航栏
-8-5 修饰美化页面
-8-6 填写页面内容
-8-7 设计制作次级页面并建立链接
-9-1 Python的下载
-9-2 Python的安装
-9-3 IDLE的使用
-9-4 求矩形的周长和面积
-9-5 求三角形的面积
-9-6 求素数
--9-6 求素数
-10-1 数据库的建立
-10-2 SQL的应用
-11-1 Packet Tracer简介及下载方法
-11-2 有线网络的组网与配置
-11-3 无线网络的组网及无线路由配置
-12 无线网络安全配置