01_Intro

1 .第一讲 计算机基础 —— 信息的表示与存储 —— 算法

2 .2 主要内容 信息的表示与存储 算法基本概念 计算机的数字系统 常见的进制数及它们之间的转换 原码，反码与补码 非数值信息的表示

3 .3 计算机数字系统 计算机内部的信息的分类 信息 控制信息：指令和控制字 数据信息 数值信息：定点数与浮点数 非数值信息：字符数据与逻辑数据

4 .4 信息的存储单位 基本单位：位与字节 计算机的最小存储单元是字节（ Byte ） 一个字节由 8 个二进制位（ bit ）组成 其它单位 1 KB = 1024 B 1 MB = 1024 K 1 GB = 1024 M 1 TB = 1024 G 1 PB = 1024 T 1 EB = 1024 P … … 一个英文字符占一个字节，一个汉字占两个字节 计算机 的最小存储单元是字节（ Byte ），一个字节由 8 个二进制位（ bit ）组成。

5 .5 计算机数字系统 计算机的数字系统 计算机采用的是 二进制 数字系统 基本符号： 0 、 1 优点：易于物理实现、运算简单、可靠性高、通用性强 缺点：可读性差 程序设计中常用的数制 进 制 基数 进位原则 基本符号 二进制 2 逢 2 进 1 0 ， 1 八进制 8 逢 8 进 1 0 ~ 7 十进制 10 逢 10 进 1 0 ~ 9 十六进制 16 逢 16 进 1 0 ~ 9, A ~ F

6 .6 不同进制之间的转换 二进制、八进制、十六进制 转化为 十进制 各位数字与它的权相乘，然后相加 例如 ： (101.11) 2 = 1×2 2 + 0×2 1 + 1×2 0 + 1×2 -1 + 1×2 -2 = (5.75) 10 (506.2) 8 = 5×8 2 + 0×8 1 + 6×8 0 + 2×8 -1 = (326.25) 10 (10.C) 16 = 1 × 16 1 + 0× 16 0 + 12×16 -1 = (16.75) 10

7 .7 不同进制之间的转换 十进制 转化为 其他进制 整数：辗转相除法 34 余数 17 ┄┄┄┄┄┄┄┄┄┄┄ 0 8 ┄┄┄┄┄┄┄┄┄┄┄ 1 4 ┄┄┄┄┄┄┄┄┄┄┄ 0 2 ┄┄┄┄┄┄┄┄┄┄┄ 0 1 ┄┄┄┄┄┄┄┄┄┄┄ 0 0 ┄┄┄┄┄┄┄┄┄┄┄ 1 2 2 2 2 2 2 低位 高位 34 10 = 100010 2 十进制整数转化为其它进制的方法是类似的

8 .8 不同进制之间的转换 十进制的数转化为其他进制 纯 小数：与 2 相乘后取整数部分 例如 ： 0.3125×2 = 0 . 625 0.625 ×2 = 1 . 25 0.25 ×2 = 0 . 5 0.5 ×2 = 1 . 0 0.3125 10 = 0.0101 2 每次相乘后去掉整数部分，不断乘下去，直到 小数部分为 0 或 达到指定的精度 为止，然后取每次相乘后的整数部分即可。 绝大部分浮点数无法用二进制精确表示，如 0.1

9 .9 不同进制之间的转换 二进制与八进制、十六进制之间的关系 每位八进制数对应于一个三位二进制数 每位十六进制数对应于一个四位二进制数 0  000 1  001 2  010 3  011 4  100 5  101 6  110 7  111 0  0000 8  1000 1  0001 9  1001 2  0010 A  1010 3  0011 B  1011 4  0100 C  1100 5  0101 D  1101 6  0110 E  1110 7  0111 F  1111 例如 ： 11010.10 2 = 0001 1010 .1000 2 = 1A.8 16

10 .10 二进制数的编码表示 数在计算机内部的存储方式：原码、反码、补码 数的表示：符号 + 大小 - 符号：用“ 0 ”表示正，用“ 1 ”表示负，放在最高位 - 大小：二进制 34  0 0100010 -34  1 0100010 符号位 优点：直观 缺点：零的表示不唯一；四则运算要考虑符号位，规则复杂 注：这里假定用一个字节存放数据

11 .11 反码 反码一般不直接使用，通常是作为求补码的中间码 正数的反码：与原码相同； 负数的反码： 符号位不变 ，其它位取反（ 0 变 1 ， 1 变 0 ） 34  0 0100010  0 0100010 -34  1 0100010  1 1011101 原码 反码

12 .12 补码 0 的补码表示唯一，且可以多表示一个数 对补码再求补即得到原码 正数的补码：与原码相同； 负数的补码：反码的最末位加 1 计算机是以补码方式存放数据的！ 34  0 0100010  0 0100010  0 0100010 -34  1 0100010  1 1011101  1 1011110 原码 反码 补码

13 .13 补码运算规则 符号位可以作为数值参加运算 减法可以转化为加法运算 运算结果仍为补码 例： 用 8 位字长计算 67 - 10 67 10 = 01000011 2 [ 原 码 ]  01000011 [ 补码 ] -10 10 = 10001010 2 [ 原 码 ]  11110101 [ 反码 ]  11110110 [ 补码 ] 01000011 + 11110110 = 1 00111001  00111001 ( 注意： 符号位 加入正常运算，超出字长部分 自然丢失 ) 00111001 [ 补码 ]  00111001 2 [ 原 码 ] = 57 例： 用 8 位字长计算 85 + 44 ，会出现什么问题？

14 .14 非数值信息 西文字符： ASCII 码 中文汉字：一个汉字占两个字节，常见编码有 GB2312 、 GBK 、 GB18030 、 UTF-8 完整的 ASCII 码表见课程主页或教材 非数值信息的表示

15 .15 算法基本概念 什么是算法 算法的特征与评价 算法的描述方法与基本控制结构

16 .16 算法 程序 = 算法 + 数据结构 + 程序设计方法 + 语言工具和环境 算法： 为解决一个问题而采取的方法和具体步骤 —— 著名计算机科学家 Nikiklaus Wirth ， 1976 对数据组织的描述：数据的类型和组织形式，即 数据结构 对操作流程的描述：即操作步骤，也就是 算法 一个程序应该包括： 学习程序设计的目的不仅仅是学习一种特定的语言， 而是学习进行程序设计的 一般方法 。 掌握了算法就是掌握了 程序设计的灵魂 ，再配合有关的计算机语言， 就能顺利编写出程序，解决问题。 脱离了具体的语言去学习程序设计是困难的。

17 .17 算法 空间复杂度 时间复杂度 实现复杂度 算法性能的评测 输入： 有零个或多个输入量 输出： 通常有一个或以上输出量（计算结果） 明确性： 算法的描述必须无歧义，保证算法的正确执行 有限性： 有限个输入、有限个指令、有限个步骤、有限时间 有效性： 又称可行性，能够通过有限次基本运算来实现 算法的特征

18 .18 算法描述与基本结构 算法的描述方法： 自然语言、 流程图 、 NS 流程图、伪代码 流程图：简洁、直观、准确 算法的三种基本控制结构 顺序结构 选择结构 循环结构

19 .19 顺序结构 A B A A B A B A 顺序结构是最基本、也是最常用的程序设计结构，它按照程序语句行的自然顺序，一条一条地执行程序。

20 .20 选择结构 A B p Y N 当 p 为“真” 当 p 为“假” 选择结构，又称分支结构或条件结构，包括简单选择和多分支选择结构，可根据条件，判断应该选择哪一条分支来执行。

21 .21 循环结构 A p Y While 型循环 N 当 p 为“真” 当 p 为“假” 循环结构，可根据给定的条件，判断是否需要重复执行某一相同的程序段。

22 .22 循环结构 三种结构的共同点： 只有一个入口 只有一个出口 结构内每一部分都有机会被执行 结构内不存在“死循环”

23 .23 小结 算法的基本概念 算法的三种控制结构 了解以下内容 不同进制之间的转换 掌握以下内容

24 .24 课后练习 1 、将下列二进制数转化为十进制数 101, 100111, 11010.011 2 、将下列十进制数转化为二进制数 101, 0.5625, 93.328125 思考： 小数的补码如何计算？