信息的表示与存储——算法 /~jypan 目录页 Contents 华东师范大学数学科学学院SchoolofMathematicalSciences,ECNU 1信息的表示与存储2算法基本概念 /~jypan 目录页 Contents 华东师范大学数学科学学院SchoolofMathematicalSciences,ECNU 1信息的表示与存储 1信息的表示与存储2算法基本概念 计算机的数字系统常见的进制数及它们之间的转换原码，反码与补码非数值信息的表示 /~jypan 计算机信息分类 计算机内部的信息分类 信息 控制信息：指令和控制字 数据信息 数值信息：定点数与浮点数非数值信息：字符数据与逻辑数据 信息的存储单位 基本单位：位（bit）与字节（Byte）计算机最小存储单元是字节，一个字节由8个bit组成 其它单位：KB，1MB，1GB，1TB，1PB，1EB… †一个英文字符占一个字节，一个汉字字符占两个字节。
/~jypan
4 计算机数字系统 计算机数字系统 计算机采用的是二进制数字系统基本符号：0、
1 -优点：易于物理实现、运算简单、可靠性高、通用性强-缺点：可读性差 程序设计中常用的数制 进制二进制八进制十进制十六进制 基数281016 进位原则逢2进1逢8进1逢10进1逢16进
1 /~jypan 基本符号0，10~70~90~
9,A~F
5 不同进制之间的转换 二进制、八进制、十六进制十进制 各位数字与它的权相乘，然后相加 例： (101.11)2=1×22+0×21+1×20+1×2-1+1×2-2=(5.75)10(506.2)8=5×82+0×81+6×80+2×8-1=(326.25)10(10.C)16=1×161+0×160+12×16-1=(16.75)10 /~jypan
6 不同进制之间的转换 十进制二进制 整数：辗转相除法纯小数：与2相乘后取整数部分 23421728 242221
0 余数 ┄┄┄┄┄┄┄┄┄┄┄0┄┄┄┄┄┄┄┄┄┄┄1┄┄┄┄┄┄┄┄┄┄┄0┄┄┄┄┄┄┄┄┄┄┄0┄┄┄┄┄┄┄┄┄┄┄0┄┄┄┄┄┄┄┄┄┄┄
1 低位高位 3410=1000102 /~jypan †十进制整数转化为其它进制的方法类似
7 不同进制之间的转换 十进制二进制 整数：辗转相除法纯小数：与2相乘后取整数部分 0.3125×2=0.6250.625×2=1.250.25×2=0.50.5×2=1.0 0.312510=0.01012 每次相乘后去掉整数部分，不断乘下去，直到小数部分为0或达到指定的精度为止，然后取每次相乘后的整数部分即可。
†绝大部分浮点数无法用二进制精确表示，如0.1,0.2,0.3,... /~jypan
8 不同进制之间的转换 八进制、十六进制二进制 每个八进制数对应于一个三位二进制数每个十六进制数对应于一个四位二进制数 0↔000 1↔0012↔0103↔0114↔1005↔1016↔1107↔111 0↔0000 1↔00012↔00103↔00114↔01005↔01016↔01107↔0111 8↔1000 9↔1001A↔1010B↔1011C↔1100D↔1101E↔1110F↔1111 例：11010.102=00011010.10002=1A.816 /~jypan
9 计算机数字系统 数在计算机内部的存储方式 原码、反码、补码二进制数的原码：符号+大小 -符号位：用“0”表示正，用“1”表示负，放在最高位（最左边） 例：用1个字节表示正整数3400100010 符号位 -34↔10100010 †原码的优点：直观†缺点：
(1)四则运算要考虑符号位，规则复杂；
(2)零的表示不唯
一 /~jypan 10 反码与补码 反码与补码正数的反码和补码：与原码相同；负数的反码：符号位不变，其它位取反（0变1，1变0）负数的补码：反码的最末位加
1 原码34↔00100010-34↔10100010 反码↔00100010↔11011101 补码↔00100010↔11011110 计算机是以补码方式存放数据的！ †注1：反码一般不直接使用，通常是作为求补码的中间码†注2：补码的补就是原码†注3：可通过特定设置，使0的表示方法唯
一，且可以多表示一个数 /~jypan11 补码运算 补码运算 符号位可以作为数值参加运算减法可以转化为加法运算运算结果仍为补码 例：用8位字长计算67-10 6710=010000112[原码]↔01000011[补码]-1010=100010102[原码]↔11110101[反码]↔11110110[补码]01000011+11110110=100111001↔00111001[补码]↔001110012[原码]=5710 符号位加入正常运算，超出字长部分自然丢失 思考：用8位字长计算85+44，会出现什么问题？ /~jypan 12 非数值信息非数值信息的表示 西文字符：ASCII码完整的ASCII码表见课程主页 中文字符：一个汉字（含标点符号）占两个字节常见编码有GB2312、GBK、GB18030、UTF-
8 /~jypan 13 目录页 Contents 华东师范大学数学科学学院SchoolofMathematicalSciences,ECNU 2算法基本概念 1信息的表示与存储2算法基本概念 什么是算法算法的特征与评价算法的描述方法基本控制结构 /~jypan 算法 程序=算法+数据结构+程序设计方法+语言工具和环境 ——著名计算机科学家NikiklausWirth，1976 一个程序应该包括：对数据组织的描述：数据的类型和组织形式，即数据结构对操作流程的描述：即操作步骤，也就是算法 算法：为解决一个问题而采取的方法和具体步骤 †学习程序设计的目的不仅仅是学习一种特定的语言，而是学习进行程序设计的一般方法。
†掌握了算法就是掌握了程序设计的灵魂，再配合有关的计算机语言，就能顺利编写出程序，解决问题。
†但是，脱离了具体的语言去学习程序设计是困难的。
/~jypan 15 算法 算法的特征 输入：有零个或多个输入量输出：通常有一个或以上输出量（计算结果）明确性：算法的描述必须无歧义，保证算法的正确执行有限性：有限个输入、有限个指令、有限个步骤、有限时间有效性：又称可行性，能够通过有限次基本运算来实现 算法性能的评测 空间复杂度：所占用的内存 时间复杂度：所需的运算量/执行时间 实现复杂度：编程实现和后期升级维护等 /~jypan 16 算法描述 算法的描述方法：自然语言、流程图、伪代码、…… 流程图：简洁直观 /~jypan 伪代码：易于编程 17 算法基本结构 算法的三种基本控制结构顺序结构、选择结构、循环结构 顺序结构 是最基本、也是最常用的程序设计结构，它按照程序语句行的自然顺序，一条一条地执行代码。
/~jypan AB 18 选择结构 选择结构 也称分支结构或条件结构，根据条件，判断应该选择哪一条分支来执行，包括简单选择和多分支选择。
Yesp No
A B /~jypan 19 循环结构 循环结构 根据给定的条件，判断是否需要重复执行某一相同的程序段。
三种结构的共同点 只有一个入口只有一个出口结构内每一部分都有机会被执行结构内不能存在“死循环” /~jypan ApYesNo （以while循环为例） 20 课后练习
1.将下列二进制数转化为十进制数101,100111,11010.011
2.将下列十进制数转化为二进制数101,0.5625,93.328125 思考小数的补码如何计算？ /~jypan 21