程序设计与C语言第1章++预备知识.ppt

第1章预备知识 1 1计算机内的数据表示1 2数的定点和浮点表示1 3简单的逻辑运算1 4程序的概念1 5算法 1 1计算机内的数据表示 数据形态多种多样 凡是计算机能够处理的对象都称为数据 如文字数据 图形数据 声音数据等 但不管其表象多么复杂 多么千差万别 只要一归入计算机处理 都全部地统一为二进制数据 也就是说 数据在计算机内是以二进制 即用数字0和1 来表示的 在计算机中为什么要用二进制 采用二进制有哪些优点 以下就是问题的答案 1 二进制表示数字在物理上容易实现 计算机内部用电子器件的状态来表示数字信息 一种数制有多少种不同的数字 电子器件就需要多少种不同的状态 二进制只有数字0和1 因此它只需要由两个稳定状态的电子元件就可以表示了 而十进制则需要由10个不同稳定状态的电子元件来表示 2 二进制运算规则简单 二进制求和的规则有 0 0 00 1 1 0 11 1 10二进制求积的规则有 0 0 00 1 1 0 01 1 1 3 采用二进制可以用逻辑代数作为设计分析的工具 二进制中用0和1可以表示是与非 高与低等 这恰恰是逻辑代数中的内容 4 用二进制可以节约存储设备 比如要表示0 999这1000个数时 十进制要用三位数 需3 10 30个状态设备量 而用十位二进制数可表示1024个数 则只需2 10 20个状态设备量 1 1 1数的二进制 十进制 八进制和十六进制表示常用的数制有二进制 十进制 八进制和十六进制 它们有共性也有差别 1 数码及进位法则数码是构造一种数制所用的不同符号 各种进制的数码为 二进制 0 1十进制 0 1 2 3 4 5 6 7 8 9八进制 0 1 2 3 4 5 6 7十六进制 0 1 2 3 4 5 6 7 8 9 A a B b C c D d E e F f 2 位置计数法数据中各个数字所处的位置决定它的大小即权值 同样的数字在不同位置上代表的权值是不同的 比如 22 2 2 101 2 100 2 10 1 其中101 100 10 1就是该位置的权值 1 1 2数制转换我们日常习惯使用的是十进制 但在计算机中用的却是二进制 所以需要把十进制转换成二进制 但二进制书写麻烦 因此通常用八进制和十六进制表示 这样就存在各种数制之间的转换问题 1 将十进制转换成二进制把十进制的整数和小数转换成二进制时所用的方法不同 因此应该分别进行转换 1 用余数法将十进制整数转换成二进制整数 把十进制整数不断地用2去除 将所得到的余数0或1依次记为K0 K1 K2 直到商是0为止 将最后一次所得的余数记为Kn 则KnKn 1 K1K0即为该整数的二进制表示 在演算过程中可用竖式形式 也可用线图形式 例1 1 59 10 2 Kn K1K0 2 竖式演算如下 259余数1 K0229余数1 K1214余数0 K227余数1 K323余数1 K421余数1 K50 59 10 K5K4K3K2K1K0 2 111011 2 2 用进位法将十进制小数转换成二进制小数 把十进制小数不断地用2去乘 将所得乘积的整数部分0或1依次记为K1 K2 K3 一般情况下十进制小数并不一定都能用有限位的二进制小数表示 可根据精度要求 转换成一定位数即可 例1 2把0 47转换成二进制 用线图形式可演算如下 0 47 0 94 0 88 0 76 0 52 0 04 2 整数01111K 1K 2K 3K 4K 5在取5位小数时有 0 47 10 K 1K 2K 3K 4K 5 2 0 01111 2 3 在把十进制转换成二进制时 熟记一些2的幂次的十进制及二进制值能加快转换速度 表1 1中列出了一些2的幂次所对应的十进制和二进制数 表1 12的幂次所对应的二进制和十进制数 在转换时 可找出小于但最接近该十进制整数的某个2的幂次 减去这个幂次 再在减后的数中找小于且最接近该数的2的幂次 2的n次方的二进制数的特点是1后跟有n个0 利用这一点就能迅速地把二进制数的长度确定 然后在相应的位置上填上1或0即可 比如 1287 25 10 1024 256 4 2 1 0 25 210 28 22 21 20 2 2 10000000000 100000000 100 10 1 0 01 2 10100000111 01 2 例1 3 30000 10 2 计算30000除以1024得商29 余数为304 将商和余数分别用2的幂次之和的形式表示 商 29 16 8 4 1 24 23 22 20余数 304 256 32 16 28 25 24则 30000 10 1024 29 304 210 24 23 22 20 28 25 24 214 213 212 210 28 25 24 111010100110000 2 2 将二进制转换成十进制把二进制数按多项式展开求和即可 101 101 2 1 22 0 21 1 20 1 2 1 0 2 2 1 2 3 10 1 4 1 1 1 0 5 1 0 125 10 5 625 10 1 1 3原码 反码和补码在计算机中 位 bit 是最小的单位 通常用来表示由二进制位组成的信息长度 把8位二进制位定义为一个字节 Byte 计算机中的存储量就是按字节来计算的 计算机内部数据处理的基本单位称为字 word 它通常也是输入 输出设备和存储器之间传递数据的基本单位 每个字所包含的位数称为字长 在计算机中 不仅数值用0和1表示 而且正负号也用0和1表示 一般规定在一个存储单元的最高位 最左边的一位 为符号位 如该位是0表示正 该位是1表示负 在计算机中 带符号的数通常有三种表示方法 原码 反码和补码 为简单起见 下面我们只考虑用一个字节表示整数时的原码 反码和补码 1 原码原码是一种机器数 原码表示法就是在机器中最高位用0表示正数 用1表示负数 而其余位表示数本身 例如 15的原码为 00001111 代表正 15的原码为 10001111 代表负 0的原码为 00000000 0的原码为 10000000 2 反码在反码表示法中 正负数的表示是不同的 正数的反码和原码是一样的 如 15的反码仍然是00001111 负数的反码为 符号位为1 其他各位是对原码求反 如 15的反码为11110000数值0的反码有两种 0的反码为00000000 0的反码为11111111 即在反码表示法中 0的表示仍然不惟一 图1 1时钟示例 3 补码鉴于以上情况 计算机内部采用补码方法来表示数值 采用补码方法的好处是简化设计与计算 能把减运算转变为加运算来进行 我们以时钟为例来说明补码的原理 比如现在的标准时间是6点 而你的表停在11点的位置 如图1 1所示 要调准你的表可用两种方法 向前拨7格 向后拨5格 不管采用哪种方法 都能达到目的 可谓殊途同归 但从算式上来看 11 7 18 向前拨 11 5 6 向后拨 计算结果并不一样 那么操作结果为什么会一样呢 这是因为表盘的刻度是以12为周期的 超过12就又从头计数 因此上面的计算结果18因超过了12 再从头开始计数后也就得到了6 在计算机中是以一个有限长度的二进制位作为模 比如用一个字节表示一个数 则其模数为2 8 如运算结果超过2 8 就从中减去2 8 反映在内存中 其情况为 1即把8位以外的数舍掉 计算机中的补码是这样定义的 正数 其补码与其原码 反码相同 例如 15 补 15 原 15 反 00001111 127 补 127 原 127 反 01111111 00000000 负数 最高位为1 其余各位在原码的基础上取反 然后在最低位加1 简称 求反加1 可用如下关系式表示 x 补 x 反 1注意各位取反时不包括符号位 即符号位不求反 例如 15 原 10001111 127 原 11111111 0 原 10000000 15 反 11110000 127 反 10000000 0 反 11111111 15 补 11110001 127 补 10000001 0 补 00000000 表1 2补码的生成 1 2数的定点和浮点表示 1 2 1定点数的取值范围定点数的表示格式是 符号占1位 数值可有多位 小数点的位置在符号位之后 数值部分的最高位之前 但不占实际位数 例如 01011表示0 1011 是个正数11011表示1 1011 是个负数 符号 数值 设定点计算机的字长是9位 其中一位是符号位 另8位是数值位 则该计算机所能表示的数的绝对值范围是 0 00000001 0 11111111 或写成 2 8 1 2 8一般地 若定点计算机的字长是n位 其中一位是符号位 则它所能表示的数的绝对值范围是 2 n 1 1 2 n 1 数值位最低位为1 其余位皆为0 数值位各位全是1 1 2 2浮点数的取值范围在计算机中 浮点数由四部分表示 阶符 阶码 数符 尾符 和数码 尾数 其格式为 对浮点机来说 总是规定数码部分的最高位是1 也就是 例1 4对用32位表示的浮点数 设阶码部分为8位 尾数部分为24位 各含1位符号位 求它所能表示的数的绝对值范围和有效数字位数 先标出取最大 最小值时在内存中各位的表示 最小值 当阶码负最大 数码最小时 即 所表示的数值为 最大值 当阶码正最大 数码最大时 即 所表示的数值为 由此知其范围为 或 2 128 2127 1 2 23 这是以2为基数的表示 如何表示成以10为基数的呢 因为尾数部分不大于1 所以数的大小主要是由阶码部分决定的 令阶码2127等于十进制数10 x 即设2127 10 x 如能把x求出来 即可转换到十进制范围 对等式两边取对数 127 lg2 x 因为lg2 0 3 所以x 0 3 127 38 令2 128 10y 则 y 128 lg2 128 0 3 38 因此在十进制情况下 这种有7位阶码的浮点数的取值范围为 10 38 1038 浮点数的尾数部分决定数的精度 23位数码的最大值为224 1 224 令224 10 x 二进制的24位相当于十进制的x位 则 x 24 lg2 24 0 3 7一般情况下尾数达不到最大值 但也在223和224之间 对223 设有 223 10y 可求出 y 23 lg2 23 0 3 6 9 取y 6 即相当于十进制的6位 因此对尾数是24位的浮点数 其有效数字为6 7位 1 2 3整数的取值范围用一定位数表示整数 带符号位和不带符号位表示的数值范围是不同的 设用8位表示一个整数 其中最高位是符号位 则表示数值的位有7位 当7位全是1时绝对值最大 绝对值为27 1 一般地有 N 27 1 127对无符号数 最高位仍是数值位 则其最大值为8位全是1的时候 数值为28 1 一般地有0 N 28 1 255如有n 1位二进制数 则带符号时 它所表示的绝对值范围为 N 2n 1不带符号时 它所表示的数的范围为0 N 2n 1 1 1 3简单的逻辑运算 1 3 1 或 与 非 运算在逻辑演算中 逻辑连接词又称为逻辑运算符 它的运算对象都是真或假的命题 如果一个运算符需要两个运算对象 就称为双目运算符 如果只对一个运算对象进行运算 则称为单目运算符 逻辑运算符共有4个 逻辑 非 逻辑 与 逻辑 或 和逻辑 异或 其中第一个是单目运算符 后三个是双目运算符 我们这里只介绍前三个运算符 1 逻辑 或 加 运算符OR逻辑或运算的情况类似于一个并联开关 如图1 2所示 只要有一个开关接通 电路就接通 电灯就会发亮 若灯泡亮用 1 表示 暗用 0 表示 A B表示两个逻辑变量 接通用 1 表示 断开用 0 表示 结果用 F 表示 则可以写出如下函数关系 F AORB 结果F的值也可能是0或1 图1 2逻辑或运算的物理示意图 变量A B都可以取0或1中任一个值 这样当它们连接起来的时候就会有不同的组合 在各种组合情况下 结果值是什么呢 为了清楚地反映结果值与各变量取值间的关系 我们可以用一个表来显示 这样的表就称为 真值表 真值表反映了因变量与自变量之间的状态关系 逻辑或运算的真值表为 即 0OR0 01OR0 10OR1 11OR1 1 2 逻辑 与 乘 运算符AND与运算符的作用相当于一个串联开关 如图1 3所示 只有当两个开关同时连通时 电灯才会发亮 其关系式为 F AANDB其真值表为 即 0AND0 01AND0 00AND1 01AND1 1 图1 3逻辑与运算的物理示意图 3 逻辑 非 否定 运算符NOT逻辑 非 又称为逻辑否定 它把一个命题改换成相反的含义 其作用类似于反相开关电路 如图1 4所示 当开关接通时 电灯泡由亮变暗 断开时 电灯泡由暗变亮 其关系式为 F NOTA 即 NOT0 1NOT1 0 图1 4逻辑非运算的物理示意图 1 3 2真值表上面我们介绍了三种逻辑运算符 逻辑运算符和逻辑运算对象相结合构成的式子称为逻辑表达式 在程序设计中我们需要的是逻辑表达式而不是一个孤零零的命题 然而在实际应用中 我们却往往不知道其逻辑表达式 只知道一些具体的要求 这时我们可以首先根据具体要求列出其真值表 然后再根据真值表写出逻辑表达式 这就是真值表的重要意义所在 例1 5一个房间住了三个人 甲 乙 丙 求下列条件下房间内无人说话的表达式 1 甲从来不说话 2 当且仅当甲在场时乙才说话 3 丙在任何情况下都说话 编程思路 首先用三个变量A B C表示甲 乙 丙三人以便于书写 并且规定其值为1时表示在房间 为0时表示不在房间 结果F为1时表示房间内无人说话 为0时表示有人说话 第一步 根据条件 列出真值表 第二步 根据真值表列出逻辑表达式 关键是把F值为1的各种情况收集起来 用或运算符连接 表示只要有一种情况发生 就说明房间内无人说话 考虑F 1的各种取值 1 由真值表中第一行知 A B C 0时F 1 变量本身代表真 变量的否定代表假 则上述条件表示为 NOTA AND NOTB AND NOTC 解释为 A不在场并且B不在场并且C也不在场 此时房间内无人说话 2 由真值表第三行知 A C 0 B 1时F 1 这可以表示为 NOTA ANDBAND NOTC 解释为 A不在场但是B在场并且C不在场 此时房间内无人说话 3 由真值表第五行知 当A 1 B C 0时F 1 这可表示为 AAND NOTB AND NOTC 解释为 A在场但B不在场并且C不在场 此时房间内无人说话 逻辑运算符的优先级 NOT最高 AND次之 OR最低 把上面三个表达式用OR运算符连接起来 即为所求的逻表达式 F NOTA AND NOTB AND NOTC OR NOTA ANDBAND NOTC OR AAND NOTB AND NOTC 1 4程序的概念 一个程序是一个由指令组成的序列 指令就是行为或动作 从这个意义上说 程序在计算机发明以前很久就有了 比如弹奏乐曲的乐谱 厨师做菜的食谱 某项工程实施的计划等都可以说是程序 只是计算机的程序更复杂 更需要仔细而精细地进行编写而已 程序要由编程者来编写 并由执行者来实施 实现指令称为执行或运行程序 运行中的程序称为进程 程序是静态的概念 而进程是动态的概念 1 4 1程序的特性所有程序 包括计算机程序 都有一些共同的性质 这些性质主要包括以下几点 1 指令是顺序执行的 2 程序的执行都有一个结果 3 程序总是要对某些对象进行操作 4 有的程序要加入对操作对象的说明 5 有时指令要求执行者做出判断 6 一条或一组指令可能需要执行多次 1 4 2计算机程序的执行过程程序是一种手段 程序的编写者利用程序来和执行者进行通信 通信就需要语言 不同的场合可以用不同的语言来表示程序 比如用自然语言交待任务 下达命令 但大多数程序设计需要一种特殊的语言 对计算机下达任务的语言就是计算机语言 计算机语言有高级语言和低级语言之分 但这种高低之分并没有贵贱之别 有区分主要是因为它们对计算机硬件的接近程度不同 低级语言主要是指机器语言 二进制语言 和汇编语言 它们离计算机硬件最近 用机器语言写的指令都是由0和1组成的符号序列 计算机能直接识别和执行 因而速度很快 但这种指令写起来繁琐复杂 非专业人士不能为之 汇编语言是符号化的二进制语言 它用英文单词或其缩写来表达指令 执行速度也很快 但却受具体机器系统的制约 执行高级语言程序分为两个阶段 第一个阶段称为编译阶段 第二个阶段称为运行阶段 在程序执行的过程中可能会出现三种类型的错误 1 编译错误 这是在编译阶段发生的错误 主要是使用语言的语法不合规范所引起的错误 2 运行错误 这种错误在编译时发现不了 只在运行时才显现出来 如对负数开平方 除数为0 循环终止条件永远不能达到等 这种错误常会引起无限循环或死机 3 逻辑错误 这种错误即使在运行时也显示不出来 因程序能正常运行 但结果不对 图1 5高级语言源程序的执行过程 1 5算法 程序设计离不开算法 算法指导程序设计 算法是程序的灵魂 程序是语句的集合 但如何围绕所要解决的任务来安排这些语句的次序则是由算法决定的 因此程序设计的大致步骤如下 1 确定算法和数据结构 算法是和具体任务有关的 而数据结构则是程序要处理的数据的组织 2 把算法以明晰的方法表示出来 如用流程图 N S图 伪码等方法 3 在算法已明确表示出来的基础上用高级语言编制程序 1 5 1算法的特点算法 简单地讲 就是解决问题的流程安排 即先做什么 后做什么 精确地讲 算法是被精确定义的一系列规则 这些规则规定了解决特定问题的一系列操作顺序 以便在有限步骤内产生出所求问题的解答 尽管算法因求解问题的不同而千变万化 简繁各异 但它们都必须具备以下五个特性 1 确定性算法的每一步运算都必须有确切的定义 即每种运算所执行的操作都必须是确定的 无二义性的 2 能行性算法中有待实现的运算方法都必须是可执行的 即在执行者 计算机 能力范围之内并能在有限时间内完成 3 有穷性一个算法必须在执行了有穷的步骤之后结束 4 输入一个算法可以有0个或0个以上的输入 可提供算法操作的数据 5 输出一个算法总能产生一个或多个输出 即算法的计算结果 1 5 2算法的表示一个算法应该用明晰的方法展现在人们的面前 这样才易于用计算机语言写出体现算法的程序 表示一个算法 通常有以下四种方法 1 自然语言描述法比如求三个数的最大值问题 用自然语言可以描述为 先将两个数a和b进行比较 找出其最大者 然后再把它和第三个数c进行比较 如果它比第三个数大 则它就是最大数 否则第三个数c就是最大数 所谓伪码就是类似于程序设计语言的语句 但又不是任何一种真实的程序设计语言的语句 它不涉及程序设计的具体细节 比如求三个数的最大值问题 用伪码可表示为 ifa bthen把a交给maxelse把b交给maxifmax cthen输出最大值maxelse输出最大值c 3 N S图表示法这是一种图语言表示法 其特点是在一个矩形框内完成算法的流程说明 比如求三个数最大值的问题 用N S图可描述为如图1 6所示的形式 图1 6求三个数的最大值问题 4 流程图表示法这也是一种图语言表示法 它用一些不同的图例来表示算法的流程 常用的图例主要有如图1 7中所示的几种 图1 7流程图表示法常用图例 图1 8求三个数的最大值问题的流程图表示 1 5 3结构化程序设计的三种基本结构20世纪60年代 在开发大型软件的过程中出现了所谓的 软件危机 其主要表现是 开发进度被推迟 成本超出预算 软件产品不可靠 人们认识到软件开发要比想象的复杂得多 在如何克服 软件危机 的讨论和研究中 诞生了 结构化程序设计 的概念 这是编写出清晰 正确和容易理解的程序的一种指导方针和严格方法 结构化程序设计的基本方法是 在设计程序时 本着从上到下 逐步求精的原则 将一个大的原始问题分解为多个可独立进行编程的小问题 即小模块 如果某个模块还未精细到能直接进行编程的程度 则继续对它进行分解 直至能直接编程为止 每个模块只有一个入口和一个出口 这样不管编多大的程序 不管有多少人参加编写 都可以把他们的模块很自然地连接起来 在结构化程序设计方法中 有三种基本的控制结构 这三种基本结构是 顺序结构 选择结构和循环结构 顺序结构是指语句的执行顺序和它在程序中出现的次序是一致的 即一条语句执行完后紧接着执行它下面的那条语句 选择结构是根据一定的条件 把语句分成不同的分支 程序只执行其中一个分支 而不执行其他分支 循环结构是根据一定的条件 对某些语句重复执行 被重复执行的语句称为循环体 重复执行的次数可以预指定 也可以不指定 而由循环体中的变化所决定 这三种基本结构 可以用图表示法说明 1 用N S图表示 1 顺序结构 A执行完后接着执行B 2 选择结构 P T F A B 3 循环结构 循环结构有下面两种图示 只要P为真就执行A P A P为条件 执行A直到P为真为止 A P 2 用流程图表示 1 顺序结构 如图1 9所示 2 选择结构 这里又有如下三种形式 if结构 单路选择结构 如图1 10所示 if else结构 双路选择结构 如图1 11所示 switch结构 多路选择结构 如图1 12所示 图1 12的意思是 当某个Pi为真时 执行相应的语句Ai 然后退出选择语句 通过break语句实现 图1 9顺序结构的流程图 图1 10if结构的流程图表示 图1 11if else结构的流程图表示 图1 12switch结构的流程图表示 3 循环结构 循环结构也有三种形式 while结构 如图1 13所示 do while结构 如图1 14所示 和 的区别在于 这里是先执行语句A 然后再判断条件P for结构 如图1 15所示 图1 13while结构的流程图表示 图1 14do while结构的流程图表示 图1 15for结构的流程图表示 从上面各图中可以看出 每一个结构只有一个入口和一个出口 按顺序来组织各种控制结构就能设计出结构化的程序 即只要把一个控制结构的出口点和另一个控制结构的入口点连接起来即可 结构化程序设计的规则有4条 1 从最简单的流程图开始 2 任何矩形框都可以被两个按顺序放置的矩形框取代 3 任何矩形框都可以被任何结构取代 4 规则 2 和规则 3 可按任何顺序运用多次 图1 16从最简结构出发反复使用规则 2 和规则 4 图1 17中的虚线框就是对图1 16中一个矩形框的细化 用规则 4 可以产生更大的 包含内容更丰富的 层次更深的嵌套式结构 运用规则所生成的流程图可以构造所有可能的结构化流程图 因而能够建立所有可能的结构化程序 图1 17对最简结构使用规则 3 和规则 4 注意 如果不按上面的基本结构来绘制流程图 就有可能产生非结构化的流程图 如图1 18所示 上面介绍了表示算法的四种方法 即 自然语言 伪码 N S图和流程图 下面举个例子 用四种不同的方法来表示其算法 以比较各方法的使用和方便程度 图1 18非结构化流程图 例1 6用辗转相除法求两个正整数的最大公约数 用自然语言描述 S1 输入两个正整数m和n S2 比较m和n 如m小于n 则交换它们的值以保证m是最大数 m作相除时的分子 S3 求m除以n的余数rS4 如余数r 0 转S6 S5 把除数n作为新的分子m 余数r作为新的分母n 然后转S3 S6 打印除数n 即为最大公约数 用伪码描述 inputm nifm nthenswapmandnr mod m n Whiler 0dom n n rr mod m n enddoprintn其中 符号mod m n 代表m除以n的余数 图1 19例1 6的N S图描述 图1 20例1 6的流程图描述 从上面的描述可以看出 四种方法各有特色 读者可以根据自己的爱好和熟悉程度来决定使用哪一种方法 说明 在按确定的算法编制程序前 并不一定非要把算法以某种形式写出来或画出来 根据求解问题的难易程度及程序员的编程经验 有时可以画一些简图 甚至什么图都不画 而由算法直接编写程序 1 5 4程序设计中的几种常用算法算法是解决问题的方法 在不同领域中都有各自的算法 但从算法所采用的方法或思路上来看 算法还是有一定的共性的 算法按其共性可以分成几大类 下面主要介绍穷举法 迭代法和递归法 1 穷举法穷举法又称枚举法 试探法 如果问题解的值域是有限的 确定的和有序的 则可以把其中每一个值都拿来试一下 看是否符合所给条件 如果由人来采用该方法进行求解 则极为繁琐 尤其是当值域很大时 但该方法却特别适合于由计算机求解 对那些尚未找到或不易找到用解析方法求解的问题 穷举法不失为一种行之有效的方法 例1 7百鸡问题 用100元钱买100只鸡 已知一只公鸡5元 一只母鸡3元 3只小鸡1元 问能买的公鸡 母鸡和小鸡各是多少只 设能买公鸡x只 母鸡y只 小鸡z只 按题意可列出下列方程组 100 总钱数100 总只数100 这个方程组有两个方程 3个未知数 因而是不定方程的求解问题 可用穷举法把每一种可能的组合方案都试一下 由题意可知 公鸡x的取值范围是0到20 可以一只公鸡都不买 也可以全买成公鸡 但最多买20只 当然这里