计算机算法基础(第一章)第一章 导引与基本数据结构

第1章 算法基础
1.1 算法 1.2 算法分析 1.3 算法的运行时间
1.1.1 冒泡排序
1.1 算 法
冒泡排序(bubble sort)属于基于交换思想的排序方法。它将 相邻的两个元素加以比较，若左边元素值大于右边元素值，则 将这两个元素交换；若左边元素值小于等于右边元素值，则这 两个元素位置不变。右边元素继续和下一个元素进行比较，重 复这个过程，直到比较到最后一个元素为止。
3
do if A［j］ < A［j - 1
4
then exchange A［j］ A［j - 1
图1-1说明了输入实例为A = 〈5， 2， 4， 6， 1， 3〉时， 算法BUBBLE SORT的工作过程。对于外层for循环的每一次迭 代，则在A［i］位置产生当前元素比较范围A［i..n］内的一个 最小值。下标i从数组第一个元素开始， 从左向右直至数组中最 后一个元素。深色阴影部分表示数组元素A［1..i］构成已排好 的序列，浅色阴影部分表示外层循环开始时的下标i。数组元素 A［i +1..n］表示当前正在处理的序列。
下面， 我们考察这些性质是如何对冒泡排序成立的。 首先 证明内层for循环的不变式。
· 循环不变式：A［j］是A［j..length［A］］中的最小元素。
· 初始： 在内循环第一次开始迭代之前，j =length［A］， 因此，子数组A［length［A］..length［A］］ 中只包含一个元 素， 也即子数组中的最小元素， 此时， 循环不变式成立。
(9) “and”和“or”是布尔运算符。当对表达式“x and y”
求值时，首先计算x的值，
FALSE，则整个表达式
的值为FALSE，我们也无需计算y的值；如果x的值为TRUE，

知识点总结第一章算法初步
1.1算法的基本定义
算法(algorithm)定义为一组使机器可以达到特定目标的指令，它是计算机程序的一种基础。

它可以是通过演绎的过程创建出来的，也可以是通过纯粹的归纳的方法创建出来的。

一个典型的算法由不同步骤组成，每个步骤都有一定的功能和有效的设计思想。

1.2算法的实现
算法的实现通常需要使用一定的编程语言进行编程，比如C语言、Java等。

编程语言提供了许多有效的指令，可以用来实现不同的算法。

一般来说，实现算法的步骤有：设计，即把算法的概念写出来；编写，即把设计好的算法代码写出来；测试，即测试程序的正确性；调试，即改正程序中的缺陷。

1.3算法的分析
对于一个算法来说，它执行的时间和空间都是有限的，可以通过空间复杂度和时间复杂度来衡量一个算法的优劣。

一般来说，时间复杂度和空间复杂度可以分别衡量算法中计算和存储资源的消耗情况。

另外，为了使算法的运行效率更好，还可以使用存储技术、排序技术、技术等技术来改进算法的性能。

1.4实例
为了更好的理解算法，下面给出一个实例：输出1到100内的所有自然数。

解法一：使用循环语句，将1到100分别赋值给变量i。

第一章 数据结构与算法1.1 算法1描述。

算法规定了解决某类问题所需的操作语句以及执行顺序，使其能通过有限的指令语句，在一定时间内解决问题。

算法是一个操作序列、有限长度，目的是解决某类问题。

*：算法不等于程序，也不等于计算方法。

程序的编制不可能优于算法的设计。

2、算法的基本特征（1）可行性。

针对实际问题而设计的算法，执行后能够得到满意的结果。

（2）确定性。

每一条指令的含义明确，无二义性。

并且在任何条件下，算法只有唯一的一条执行路径，即相同的输入只能得出相同的输出。

（3）有穷性。

算法必须在有限的时间内完成。

有两重含义，一是算法中的操作步骤为有限个，二是每个步骤都能在有限时间内完成。

（4）拥有足够的情报。

指的是有足够的输入和输出。

*：综上所述，所谓算法，是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的，且是明确的，此顺序将在有限的次数下终止。

3、算法的基本要素一个算法通常由两种基本要素组成：一是对数据对象的运算和操作；二是算法的控制结构。

(1）算法中对数据的运算和操作每个算法实际上市按解题要求从环境能进行的所有操作中选择合适的操作所组成的一组指令序列。

因此，计算机算法就是计算机能处理的操作所组成的指令序列。

在一般的计算机系统中，基本的运算和操作有以下四类：①算术运算：主要包括加、减、乘、除等运算；②逻辑运算：主要包括与(AND)、或(OR)、非(NOT)等运算；③关系运算：主要包括大于、小于、等于、不等于等运算④数据传输：主要包括赋值、输入、输出等操作。

(2)算法的控制结构顺序、选择和循环。

4、算法的基本方法（计算机解题的过程实际上是在实施某种算法）（1）列举法（列举所有解决方案）根据提出的问题，列举所有可能的情况，并用问题中给定的条件检验哪些是需要的，哪些是不需要的。

（2）归纳法（特殊->一般）适合于列举量为无限的情况通过列举少量的特殊情况，经过分析，最后找出一般的关系。

（3）递推法（已知->未知）从已知的初始条件出发，逐次推出所要求的各中间结果和最后结果。

C++语言程序设计
第一章 计算机基础知识
•
授 课: 东南大学 郑雪清 E_mail: snow6789@
1
1.1 本章导读
本章所介绍的内容有： 计算机系统结构 计算机工作原理 计算机中数据的存储表示 算法的概念 软件开发的基本方法2ຫໍສະໝຸດ 1.2 计算机系统结构及原理
计算机的功能是以计算为基础的， 因此，计算机的基本结构首先应支持计 算能力的实现。目前绝大多数计算机都 采用冯•诺依曼体系结构。 计算机体系结构的统一带来的另一 个重要特点是使计算机具有通用性，即 运行不同程序就能实现不同的功能，因 此而称之为通用电子计算机。
进位规则：n进制逢n进一。十进制为逢十进 一；二进制为逢二进一等。 每一个数位上数码所具有的权：权为n的幂。 十进制数码各位的权是以10为底的幂，二进 制数码各位的权是以2为底的幂。
26
对于任何一个十进数N，都可以表示成按权展开的多项 式：
N=dn×10n+dn-1×10n-1+…+d1×101+d0×100+d-1×101+…+d ×10-m = di×10i -m 对于用R进制表示的数N（R为任意正整数），可以按权 展开为： N=Kn×Rn+Kn-1×Rn-1+…+K1×R1+K0×R0+K-1×R-1+…+K×R-m = Ki×Ri m
20
（3）执行指令 由操作控制线路发出完成该操 作所需要的一系列控制信号，机器执行该指 令所要求的操作，从而完成该指令的功能。
（4）一条指令执行完成后，将下一条要执行的 指令地址送入IP中，准备进入下一个指令执 行周期。这时可能有两种情况发生，若遇一 般指令则按顺序执行；若遇转移指令，则将 转移地址码送入IP中。