计算机算法基础(第二章)

2．二进制数的逻辑运算
逻辑运算也是以二进制数为基础。基本的逻辑运算有三种： 逻辑乘、逻辑加和取反。
① 逻辑“与” (AND) 也称逻辑乘，用运算符 “∧”或 “·” 表示
0·0＝0 0·1＝0 1·0＝0 1·1＝1
0∧0＝0 0∧1＝0 1∧0＝0 1∧1＝1
逻辑或（OR运算）又称逻辑加，用运算符 “＋”或者“∨”表示。
2．4．1 西文字符的编码 1. ASCII码（American Standard Code for
Information Interchange） 如，数字0~9用ASCII编码表示为30H~39H，H所指
示的是十六进制形式。30H转化成二进制为 0110000，这就是计算机内数字0的ASCII码表示。 如：大写英文字母A~Z的ASCII编码为41H~5AH。
一条指令通常是由操作码和地址码两部分组成，如图2-9所 示
计算机之所以采用二进制，主要是基于下面的 原因。
1.二进制在技术上容易实现 2.二进制数的运算规则特别简单 3.二进制可以使计算机方便地进行逻辑
运算 4. 机器可靠性高 5. 通用性强
2．1．2 二进制数的运算
1．二进制数的算术运算 二进制数的算术运算与十进制数的算术运算方法
是一样的，也有加、减、乘、除四则运算，只是 比十进制数的算术运算更简单。
如图所示。一般规定0表示“＋”（正数），1表 示“－”（负数）。
符号位
数值部分



有符号整数
① 原码表示法 X=＋0101011 X=－0101011
[X]原=00101011 [X]原=10101011
② 反码表示法 X=＋0101011 [X]原=00101011 X=－0101011 [X]原=10101011

算法的输入规模
算法的执行时间随问题规模的增长而增长，增长的速 度随不同的算法而不同
没有一个方法可以准确的计算算法的具体执行时间 语言、编译系统、计算机
实际上，在评估算法的性能时，并不需要对算法的执 行时间作出准确的统计，人们希望算法与实现的语言 无关、与执行的计算机无关
所关心的是：算法的执行时间，随着输入规模的增长 而增长的情况
1）事前分析
目的：试图得出关于算法执行特性的一种形式描 述，以“理论上”衡量算法的“好坏”。
如何给出反映算法执行特性的描述？
最直接方法：统计算法中各种运算的执行情况，包括：
➢
运用了哪些运算
➢
每种运算被执行的次数
➢
该种运算执行一次所花费的时间等。
算法的执行时间 = ∑Fi * ti
频率计数
例： x←x+y
f(n)的增长至少像g(n)的增长那样快 试图求出“最大”的g(n)，使得f(n) = Ω(g(n))。
3）“平均情况”限界函数
定义1.3 如果存在正常数c1，c2和n0，对于所有的n≥n0，有 c1|g(n)| ≤|f(n)| ≤ c2|g(n)|
则记作
含义：
f (n) (g(n))
算法在最好和最坏情况下的计算时间就一个常数因子范围内而言是相同的。 可看作：
3）工作数据集的选择
编制能够反映算法在最好、平均、最坏情况下工作的数据 配置。然后使用这些数据配置运行算法，以了解算法的性 能。
测试数据集的生成在目前算法证明与程序正确性证明没有 取得理论上的突破性进展的情况下，是程序测试与算法分 析中的关键技术之一。
·作为算法分析的数据集：典型特征 ·作为程序性能测试的数据集：对执行指标产生影响的性质

1 →t 2 →i while i≤5 { t*i →t i+1 →i } print t end /*算法结束*/
C程序设计（第四版）
用计算机语言表示算法 P32
• 计算机无法识别流 程图和伪代码，还 需转换成计算机语 言程序。
• 用计算机语言表示 算法必须严格遵守 所用的语言的语法 规则。
例2.18 求5！
例2.1 求1×2×3×4×5如。何求1×3×5×7×9×11？
原始方法
通用算法:设变量P为被乘数，i为乘数
S1:使P=1
S2:使i=23
S3:使P*i,乘积仍放在变量P中，表示为： P*i→ P
S4:使i的值加1，即i＋12→ i 。 S5:若i≤51，1返回S3,否则结束。
问题：见P18
（若i>51，1 结束，否则，返回S3）
具有通用性、灵活性。（S3~S5组成一个循环）
C程序设计（第四版）
例 2.2 有50个学生，要求将他们中成绩在80分以上的
学号和成绩输出。用n表示学生学号，n1代表第一个学 生学号， ni代表第i个学生学号。用g代表学生成绩， gi代表第i个学生成绩。
算法：
归纳：
S1: 1 → i
P19
S2：如果gi≥80，则输出ni 和gi，否则不输出
（4）结构内不存在“死循环”（无终止的循环） 。
基本结构不一定只限于上面三种，只要具有上 述4个特点的都可以作为基本结构。
用N-S流程图表示见P29 图2-24、图2-25、图2-26 、图2-27
C程序设计（第四版）
2.4.5 用伪代码表示算法
伪代码是介于自然语言和计算机之间的文字和符号来描 述算法。 例2.16 求5！ begin /*算法开始*/

计算机算法基础第三版答案余祥宣《计算机算法基础第三版（余祥宣著）课后习题答案详解》。

要是你正在学习计算机算法，那余祥宣老师编写的《计算机算法基础第三版》肯定不陌生吧。

这本书可是算法学习路上的好帮手呢，不过课后习题有时候会让人有点头疼。

别担心，下面我就来给大家详细讲讲这本书的部分课后习题答案，还会说说为啥是这样解，让咱们一起把算法知识学个透！第一章：算法概述。

习题1：什么是算法？请举例说明。

答案：算法呢，简单说就是解决问题的步骤和方法。

就好比你要做一顿饭，得先买菜、洗菜、切菜，然后再炒菜，这一系列的步骤就是做饭的“算法”。

再比如说，计算两个整数相加，你先把两个数对齐，从个位开始相加，满十进一，这就是加法运算的算法。

原因：算法得有明确的步骤，就像做饭和做加法一样，每一步都清楚该做什么，这样才能得到正确的结果。

而且算法还得是有限的步骤，不能没完没了，不然问题永远解决不了。

习题2：算法有哪些特性？请分别举例解释。

答案：算法有五个特性，分别是有穷性、确定性、可行性、输入和输出。

- 有穷性：就是说算法在执行有限的步骤之后必须结束。

比如说计算1到100的整数和，通过一个循环，从1加到100，加完100就结束了，不会一直加下去。

- 确定性：算法的每一步都必须有明确的定义，不能模糊不清。

例如在一个判断奇数偶数的算法中，规定如果一个数除以2余数为0就是偶数，余数为1就是奇数，这个规则是明确的。

- 可行性：算法的每一步都能够通过有限次的基本运算来实现。

就像你要计算两个数的乘积，通过乘法运算就可以实现，这是可行的操作。

- 输入：算法可以有零个或多个输入。

比如计算圆的面积，需要输入圆的半径这个数据。

- 输出：算法至少有一个输出。

还是计算圆的面积这个例子，输出就是计算得到的圆的面积数值。

原因：这五个特性是算法的基本要求。

有穷性保证了算法不会无限循环下去；确定性让算法的执行结果是可预测的；可行性确保算法能够在实际中实现；输入和输出则明确了算法的处理对象和结果呈现。