教学课件：《大学计算机—计算思维视角》.ppt

1、2 1.1.1 什么是计算机 计算机是一种能对各种信息进行存储和高速处理的电子机器(或工具、助手)。1.1 计算机概述 对上述定义要强调两点：对上述定义要强调两点：计算机不仅是一个计算工具，而且还计算机不仅是一个计算工具，而且还是一个信息处理机。是一个信息处理机。计算机不同于其它任何机器，它能存计算机不同于其它任何机器，它能存储程序，并按程序的引导自动存取和处理数储程序，并按程序的引导自动存取和处理数据，输出人们所期望的信息。据，输出人们所期望的信息。3 1.1.2 计算机的分类 1.按处理对象分类 数字计算机：处理非连续变化的数据，这些数据在时间上是离散的。其基本运算部件是数字逻辑电路。模拟

2、计算机：处理连续变化的数据，这些数据在时间上是连续的。其基本运算部件是由运算放大器构成的通用函数运算器等组成。混合计算机：可处理数字量和模拟量。1.1 计算机概述4 2.按用途分类 通用计算机：为了能够解决各种问题，具有较强的通用性而设计的计算机。它具有一定的运算速度和存储容量，带有通用的外设，配备各种系统软件和应用软件。专用计算机：为了解决一个或一类特定问题而专门设计的计算机。其软硬件的配置依据解决问题的需要而定。1.1 计算机概述5 3.按规模和处理能力分类(IEEE)巨型机：超级计算机,功能最强,价格最贵。小巨型机：与巨型机相比，价格大幅降低。大型机：主机，具有很强的管理和处理数据的能力

3、，在大企业、银行等单位使用。小型机：中小企业，VAX-II,DJS-2000。工作站：高档微机，具有很强的图形处理能力，应用于计算机辅助设计，Sun工作站。个人计算机：IBM PC，Apple1.1 计算机概述6 1.1.3 计算机的特点 1.运算速度快：每秒数万亿次，气象预报 2.计算精度高：理论上不受限制，圆周率 3.存储能力强：中等规模图书馆 4.具有逻辑判断能力：算术运算 逻辑运算 判断或比较 5.具有自动执行能力：无需人工干预1.1 计算机概述7 1.1.4 计算机的应用领域 1.科学计算或数值计算 利用计算机来完成科学研究和工程技术中提出的数学问题的计算。实际问题数学模型计算量大。

4、2.数据处理或信息处理 指对数据进行收集、存储、整理、分类、统计、加工、检索和传播等一系列活动的统称。信息时代海量数据的管理和有效利用。1.1 计算机概述8 3.过程控制或实时控制 利用计算机及时采集检测数据，按最优值迅速地对控制对象进行自动调节或自动控制。无人自动化工厂。4.计算机辅助技术 计算机辅助设计：CAD 计算机辅助制造：CAM 计算机集成制造系统-CIMS 计算机辅助教学：CAI1.1 计算机概述9 5.人工智能 利用计算机模拟或部分模拟人的智能活动，如感知、判断、理解、学习、图像识别等。实用技术：智能机器人、专家系统 6.通信网络 Internet网上银行、网上订票 网上教学、网

5、上医疗 网上税收、网上出版1.1 计算机概述10 1+1=10 6+3=11 9+9=121.2 计算机运算基础二进制数二进制数八进制数八进制数十六进制十六进制用来收集、传送、处理信息的计算用来收集、传送、处理信息的计算机，由于实现技术的原因，不能采机，由于实现技术的原因，不能采用十进制进行操作，因此人们采用用十进制进行操作，因此人们采用其他进制数。其他进制数。11 1.2.1 数制及其转换 1.数制的概念 数制是用一组固定的数码和一套统一的规则来表示数目的方法。进位记数制进位记数制非进位记数制非进位记数制表示数值大小的数码与表示数值大小的数码与它在数中的位置有关。它在数中的位置有关。如十进制

6、数：如十进制数：123.45123.45表示数值大小的数码与它在数表示数值大小的数码与它在数中的位置无关。中的位置无关。如罗马数如罗马数字字:,:,十进制数码：十进制数码：0 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 8 9 9十进制规则：逢十进一十进制规则：逢十进一1.2 计算机运算基础12 ：基数：指各种进位记数制中允许选用基本数码的个数。例如十进制的数码有：0,1,2,3,4,5,6,7,8,9基数是10 位权位权：每个数码所表示的数值等于该：每个数码所表示的数值等于该数码乘以一个与数码所在位置相关的常数，数码乘以一个与数码所在位置相关的常数，这个常数叫做权值。例如

7、：这个常数叫做权值。例如：123.4123.41 110102 2+2+210101 1+3+310100 0+4+41010-1-11.2 计算机运算基础13 2.常用的数制数制数制 十进制十进制 二进制二进制 八进制八进制 十六进制十六进制 数码个数数码个数 0,1,0,1,9,9 0 0,1,1 0,1,0,1,7,7 0,1,0,1,9,9,A,B,C,D,E,FA,B,C,D,E,F 基数基数 1010 2 2 8 8 1616 规则规则 逢十进一逢十进一 借一当十借一当十 逢二进一逢二进一 借一当二借一当二 逢八进一逢八进一 借一当八借一当八 逢十六进一逢十六进一 借一当十六借一当

8、十六 权权 1010i i 2 2i i 8 8i i 1616i i 形式表示形式表示 DecimalDecimal BinaryBinary OctalOctal HexadecimalHexadecimal 注：注：i i 为整数为整数 (N)(N)R R=a=an n-1 1R Rn n-1 1+a+an n-2 2R Rn n-2 2+a+a1 1R R1 1+a+a0 0R R0 0+a+a-1 1R R-1 1+a+a-m mR R-m m 其中：其中：R R 表示基数，表示基数，a a 表示某进制的数码表示某进制的数码 几种进位计数制的对应关系几种进位计数制的对应关系1.2 计

9、算机运算基础14几种进制数之间的对应关系几种进制数之间的对应关系十进制十进制二进制二进制八进制八进制十六进制十六进制0 01 12 23 34 45 56 67 78 89 9101011111212131314141515000000000001000100100010001100110100010001010101011001100111011110001000100110011010101010111011110011001101110111101110111111110 01 12 23 34 45 56 67 7101011111212131314141515161617170 01

10、 12 23 34 45 56 67 78 89 9A AB BC CD DE EF F1.2 计算机运算基础15 3.不同进制数的相互转换 二进制数与十进制数的互换 计算机二进制，人十进制 二进制数转换成十进制数二进制数转换成十进制数 按权展开，然后求和，就可把二进制数按权展开，然后求和，就可把二进制数转换成十进制数。例如：转换成十进制数。例如：(101.1)(101.1)2 21 12 22 2+0+02 21 1+1+12 20 0+1+12 2-1-1 (?)(?)10101.2 计算机运算基础16 十进制数转换成二进制数 十进制数有整数和小数两部分。在转换时，整数部分采用 小数部分采

11、用 然后通过小数点将转换后的二进制数连接起来即可。例如：(105.625)10=(?)21.2 计算机运算基础17 二进制数与八进制数的互换 二进制数转换成八进制数 ：以小数点为基准，整数部分从右到左，小数部分从左到右，每三位一组，不足三位添0补足,然后把每组的三位二进制数按权展开后相加，得到相应的一位八进制数码，再按权的顺序连接即得相应的八进制数。例如：例如：(1011100.00101011)(1011100.00101011)2 2=(?)=(?)8 8 (001,011,100.001,010,110)(001,011,100.001,010,110)2 2=(134.126)=(13

12、4.126)8 8 1 3 4.1 2 6 1 3 4.1 2 61.2 计算机运算基础18 八进制数转换成二进制数 ：将每一位八进制数写成对应的三位二进制数，然后按权连接即可。例如：(123.67)8=(?)2 1 2 3.6 7 (1 2 3.6 7 (八进制八进制)001,010,011.110111 (001,010,011.110111 (二进制二进制)(123.67)(123.67)8 8=(1010011.110111)=(1010011.110111)2 21.2 计算机运算基础19 二进制数与十六进制数的互换 二进制数转换成十六进制数 ：以小数点为基准，整数部分从右到左，小数

13、部分从左到右，每四位一组，不足四位添0补足,然后把每组的四位二进制数按权展开后相加，得到相应的一位十六进制数码，再按权的顺序连接即得相应的十六进制数。例如：例如：(1011110.00011)(1011110.00011)2 2=(?)=(?)1616 (0101,1110.0001,1000)(0101,1110.0001,1000)2 2=(?)=(?)1616 5 E.1 8 5 E.1 81.2 计算机运算基础20 十六进制数转换成二进制数 ：把一位十六进制数写成对应的四位二进制数，然后按权连接即可。例如：(123.EF)16=(?)2十进制数十进制数：512D512D或或512 51

14、2 二进制数二进制数：10111011B B八进制数：八进制数：127Q 127Q 十六进制十六进制：A8HA8H 1 2 3.E F (1 2 3.E F (十六进制十六进制)0001,0010,0011.1110,1111 (0001,0010,0011.1110,1111 (二进制二进制)(123.EF)(123.EF)1616=(100100011.11101111)=(100100011.11101111)2 21.2 计算机运算基础21 电路简单：计算机是由逻辑电路组成，而逻辑电路通常只有两个状态。可靠性高：两个状态表示的二进制两个数码，数字传输和处理不容易出错。运算简单：二进制运

15、算法则简单。逻辑性强：计算机工作原理是建立在逻辑运算基础上的，逻辑代数是逻辑运算的理论依据。4.4.计算机为什么采用二进制计算机为什么采用二进制1.2 计算机运算基础22 1.2.2 存储单位及地址 1.位(bit，b)位是计算机存储数据的最小单位，一个二进制位只能表示两种状态，如0、1。2.2.字节字节(Byte(Byte，B)B)字节是数据处理的基本单位，一个字节是数据处理的基本单位，一个字节是由八位二进制数组成。字节是由八位二进制数组成。1Byte=8bit1Byte=8bit 01000001 010000011.2 计算机运算基础23 存储器容量大小的单位：KB、MB、GB、TB 1

16、KB2101024B 1MB220102410241048576B 1GB230102410241024B 1TB2401024102410241024B存储体结构存储体结构：1.2 计算机运算基础24 3.字(Word)字是CPU通过数据总线一次存取、加工和传送数据的长度。一个字通常由一个或若干个字节组成。字长越长，计算机性能越强。常用的字长：8位、16位、32位、64位等。计算机数据计算机数据数值型数值型：整数、小数且有正负：整数、小数且有正负非数值型非数值型：数字、字母、汉字：数字、字母、汉字等等1.2 计算机运算基础25 1.2.3 数值型数据表示 1.机器数与真值 数值型数据(符号数

17、字)数码化 规定：0，1 例如：(+68)10(01000100)2 (-68)10(11000100)2 机器数：将符号和数字组合的二进制数 真值：由机器数所表示的实际值大小1.2 计算机运算基础26 2.原码、反码和补码 原码 规定：用符号位和数值位表示一个带符号数 正数符号0，负数符号1 例如：求二进制数+10011，-10011的原码。+10011原00010011 -10011原10010011 又如：求十进制数+65，-66的原码。1.2 计算机运算基础27 零的原码形式有两种：+0原00000000 -0原10000000 原码表示数的范围：8位：-127+127 16位：-32

18、767+32767 用原码表示一个数，与真值之间转换方便。对乘除法比较合适，但对加减法容易出错。1.2 计算机运算基础28 反码 规定：正数的反码与原码相同，负数的反码是对该数的原码除符号位外各位取反。例如：求二进制数+10011，-10011的反码。+10011反00010011 -10011反11101100 零的反码形式有两种：+0反00000000 -0反11111111任意数的任意数的反码的反反码的反码即是原码即是原码本身码本身1.2 计算机运算基础29 补码 规定：正数的补码与原码相同，负数的补码是对该数的原码除符号位外各位取反，末位加1.例如：求二进制数+10011，-10011

19、的反码。+10011补00010011 -10011补11101101 零的原码形式有两种：+0补00000000 -0补00000000任意数的任意数的补码的补补码的补码即是原码即是原码本身码本身1.2 计算机运算基础30 补码表示数的范围：8位：-128+127 16位：-32768+32767 引入补码后，减法运算可转换为加法运算。X+Y补X补+Y补 X-Y补X+(-Y)补X补+-Y补 例如：用补码计算十进制数 35-65?目前计算机中加减法基本采用补码运算。1.2 计算机运算基础31 一个正数的原码、反码和补码的表示形式相同，符号位置0，其它位是数的真值。负数的原负数的原码码符号位符号

20、位1 1其余位是该数的绝对值其余位是该数的绝对值负数的反负数的反码码符号位符号位1 1其余各位逐位取反其余各位逐位取反负数的补负数的补码码符号位符号位1 1其余各位逐位取反，末位加其余各位逐位取反，末位加1 1+0+0原原0000000000000000-0-0原原1000000010000000不唯一不唯一+0+0反反0000000000000000-0-0反反1111111111111111不唯一不唯一+0+0补补0000000000000000-0-0补补0000000000000000唯一唯一 真值零的表示：真值零的表示：1.2 计算机运算基础32 1.2.4 字符型数据编码 1.AS

21、CII码 American Standard Code for Information Interchange(ASCII，美国标准信息交换码)。国际通用的信息交换标准代码(ISO 646)。ASCII码是对数字、字母、通用符号和控制符号等字符进行编码。ASCIIASCII码：码：7 7位位128128种种 00000001111111 000000011111111.2 计算机运算基础3300000000100101001001101110010010110111011011111100000000NULNULDLEDLESPSP0 0 P P、p p00010001SOHSOHDC1DC1

22、!1 1A AQ Qa aq q00100010STXSTXDC2DC2“2 2B BR Rb br r00110011ETXETXDC3DC3#3 3C CS Sc cs s01000100EOTEOTDC4DC4$4 4D DT Td dt t01010101ENQENQNAKNAK%5 5E EU Ue eu u01100110ACKACKSYNSYN&6 6F FV Vf fv v01110111BELBELETBETB7 7G GW Wg gw w10001000BSBSCANCAN(8 8H HX Xh hx x10011001HTHTEMEM)9 9I IY Yi iy y101

23、01010LFLFSUBSUB*:J JZ Zj jz z10111011VTVTESCESC+;K K k k 11001100FFFFFSFS,N N n n 11111111SISIUSUS/?O O_ _o oDELDEL高三位高三位b b6 6b b5 5b b4 4低四位低四位b b3 3b b2 2b b1 1b b0 0341 10 00 00 00 01 11 1字字符符C C1 11 10 01 10 00 00 0字字符符h h1 11 10 01 10 00 01 1字字符符i i1 11 10 01 11 11 10 0字字符符n n1 11 10 00 00 00

24、01 1字字符符a a 例例 将将ChinaChina五个五个字字符的符的ASCIIASCII码查出码查出并并存放在内存中。存放在内存中。ASCIIASCII码的字符集码的字符集：1010个数字：个数字：0,1,2,3,4,5,6,7,8,90,1,2,3,4,5,6,7,8,9 5252个大、小写字母个大、小写字母 2525个特殊字符个特殊字符 比较大小比较大小：009A9AZaZazz1.2 计算机运算基础35 2.汉字编码 汉字处理技术：汉字输入、汉字输出、计算机内部的编码问题。根据汉字处理过程中的不同要求，有多种编码形式。汉字汉字输入输入码码汉字汉字交换交换码码汉字汉字机内机内码码汉字

25、汉字字形字形码码输入设输入设备备输出设输出设备备汉字库汉字库1.2 计算机运算基础36 汉字输入码 作用：让用户直接使用标准键盘输入汉字。特点：规则简单，重码率低，击键次数少。分类：数字编码电报码、区位码等 字音编码全拼、双拼等 字形编码五笔字型、郑码等 混合编码自然码、智能ABC等1.2 计算机运算基础37 汉字交换码 在汉字信息处理系统与通信处理系统之间进行汉字信息交换时所使用的编码。设计汉字交换码编码体系要考虑：被编码的汉字个数尽量多；编码的长度尽可能短；编码具有唯一性；码制的转换要方便。按照国家标准按照国家标准GB/T-2312-1980GB/T-2312-1980编码的汉编码的汉字交

26、换码字交换码国标码国标码.1.2 计算机运算基础38 国家标准GB/T 2312-1980：信息交换用汉字编码字符集-基本集 一级汉字3755个(按拼音排序)二级汉字3008个(按部首排序)字母、数字和特殊图形记号等 国标码规定：一个汉字采用两个字节来表示图形字符图形字符(7445(7445个个)0XXX XXXX0XXX XXXX0XXX XXXX0XXX XXXX第一字节第一字节第二字节第二字节例如例如：啊啊区位码区位码1 1601601 国标码区位码国标码区位码+32324833+323248331.2 计算机运算基础39 汉字机内码 汉字机内码是在设备和信息处理系统内部存储、处理、传输

27、汉字用的代码。目前我国使用的内码是国标码高位置1。汉字机内码汉字国标码汉字机内码汉字国标码8080H8080H 例如例如：啊啊机机内码内码30213021H+8080HH+8080H B0A1HB0A1H01XXX XXXX国标码国标码机内码机内码01XXX XXXX1.2 计算机运算基础40 又如：“中国”汉字机内码？汉字汉字区位码区位码汉字国标码汉字国标码汉字机内码汉字机内码中中544854488680=5650H8680=5650HD6D0HD6D0H国国2590259057122=397AH57122=397AHB9FAHB9FAH 通过通过DebugDebug查看汉字机内码查看汉字机

28、内码：1.2 计算机运算基础41 Debug的由来：1937年，美国青年霍德华.艾肯找到IBM公司为其投资200万美圆研制计算机，即马克1号，从这时起IBM公司正式跨进计算机领地。为马克1号编制程序的是一位女数学家雷斯.霍波。有一天她在调试程序时出现故障，拆开继电器后，发现有只飞蛾被夹扁在触点中间，从而卡住了机器的运行。于是霍波把程序故障统称为臭虫(BUG)，把排除程序故障叫DEBUG。1.2 计算机运算基础42 汉字字形码 字形码是一种用点阵表示汉字字形的编码，它主要用于汉字输出(打印、显示等)时产生的汉字字形。点阵大小类型：1616、2424 3232、4848以上 汉字库汉字库：一个汉字

29、系统所允许使用的：一个汉字系统所允许使用的全部汉字的汉字字形编码的集合。全部汉字的汉字字形编码的集合。1.2 计算机运算基础43 例如：把一个方块横向和纵向都分为16格。若用1表示黑点，用0表示白点，则1616的点阵汉字可用256位二进制数来表示，占用32B。02H 00H 01H 04H 7FH 02H 00H 01H 04H 7FH FEHFEH40H 04H 80H 08H 00H 40H 04H 80H 08H 00H 00H00H3FH F8H 01H 00H 01H 3FH F8H 01H 00H 01H 00H00H1FH F0H 01H 00H 01H 1FH F0H 01H

30、00H 01H 40H40H01H 20H 01H 20H 7FH 01H 20H 01H 20H 7FH FCHFCH00H 00H00H 00H汉字汉字“宝宝”的的16161616点阵数字化信息点阵数字化信息：1.2 计算机运算基础44 1.2.5 多媒体信息编码 1.图像的数字化 连续空间位置的离散和数字化 亮度值的离散和数字化1.2 计算机运算基础45 图像的主要参数：图像分辨率：指数字图像的实际像素数目，它反映图像在屏幕中显示的大小。颜色深度：指记录每个像素所使用的二进制位数。位数位数颜色数颜色数说明说明4 4位位1616种种Windows 3.xWindows 3.x中画笔支持中画

31、笔支持1616种颜色种颜色8 8位位256256种种多媒体应用中的最低颜色深度多媒体应用中的最低颜色深度1616位位3276832768种种RGB5:5:5,RGB5:5:5,剩余剩余1 1位表示其它属性位表示其它属性(透明透明度度)2424位位1616M M种种真彩色，超出人眼所能识别的颜色范围真彩色，超出人眼所能识别的颜色范围3232位位1616M M种种RGB8:8:8,RGB8:8:8,剩余剩余8 8位表示其它属性位表示其它属性(透明透明度度)1.2 计算机运算基础46 图像数据量的计算：图像文件的大小是指在磁盘上存储整幅图像所需的字节数。数据量图像分辨率颜色深度/8(B)例题一幅64

32、0480的真彩色图像，未压缩的图像数据量是多少？64048024/8921600B900KB1.2 计算机运算基础47 图像的文件格式 BMP：Windows标准图像文件格式 JPG：一种高效率压缩格式(1:1020)GIF：用于交换图片的，对灰度图像表现佳，但不超过256色的图像。PNGPNG：流式网络图形格式，它使用：流式网络图形格式，它使用LZ77LZ77派生的无损数据压缩算法。派生的无损数据压缩算法。PNGPNG存储灰度图像时图像深度达存储灰度图像时图像深度达1616位位PNGPNG存储彩色图像时图像深度达存储彩色图像时图像深度达4848位位1.2 计算机运算基础48 2.声音数字化

33、声音是通过一定介质传播的连续的波。t振幅周期A声波声波重要指标重要指标：振幅振幅音量的大小音量的大小周期周期重复出现的时间间重复出现的时间间隔隔频率频率信号每秒钟变化次信号每秒钟变化次数数1.2 计算机运算基础49 声音数字化过程：采样采样量化量化编码编码模拟信号模拟信号数字信号数字信号连续的模拟声音信号连续的模拟声音信号声音信号的采样声音信号的采样离散的音频信号离散的音频信号示意示意1.2 计算机运算基础50 声音数字化三要素采样频率采样频率量化位数量化位数声道数声道数每秒钟抽取声波每秒钟抽取声波幅度样本的次数幅度样本的次数每个采样点用多少二每个采样点用多少二进制位表示数据范围进制位表示数据

34、范围使用声音通道的使用声音通道的个数个数采样频率越高采样频率越高声音质量越好声音质量越好数据量也越大数据量也越大量化位数越多量化位数越多音质越好音质越好数据量也越大数据量也越大立体声比单声道立体声比单声道的表现力丰富，的表现力丰富，但数据量翻倍但数据量翻倍11.02511.025kHzkHz22.05 kHz22.05 kHz44.1 kHz44.1 kHz 8 8位位256 256 个值个值1616位位6553665536个值个值单声道单声道立体声立体声1.2 计算机运算基础51 数字音频数据的计算公式：数据量采样频率量化位数 声道数/8(字节/秒)采样频率采样频率(kHz)kHz)量化位数

35、量化位数(bit)bit)数据量数据量(KB/s)KB/s)单声道单声道立体声立体声11.02511.0258 810.7710.7721.5321.53161621.5321.5343.0743.0722.0522.058 821.5321.5343.0743.07161643.0743.0786.1386.1344.144.18 843.0743.0786.1386.13161686.1386.13172.27172.271.2 计算机运算基础52 音频的文件格式：WAV文件：WAV是Microsoft/IBM共同开发的PC波形文件。因未经压缩，文件数据量很大。声音层次丰富，还原音质好。W

36、MAWMA文件文件：WMA(Windows Media Audio)WMA(Windows Media Audio)是是Windows MediaWindows Media格式中的一个子集格式中的一个子集(音频格式音频格式)。压缩到压缩到MP3MP3一半。一半。MP3 MP3文件文件：MP3(MPEG Audio layer3)MP3(MPEG Audio layer3)是一是一种按种按MPEGMPEG标准的音频压缩技术制作的音频文件。标准的音频压缩技术制作的音频文件。高压缩比高压缩比(11:1)(11:1)，优美音质。，优美音质。1.2 计算机运算基础531.3 计算机工作原理 1.3.1

37、指令和指令系统 1.指令及其格式 指令：能被计算机识别的命令，它是硬件可执行的、完成一个基本操作所发出的命令。基本操作：加、减、乘、除、存数、取数等操作码操作码地址码或数据地址码或数据指令格式指令格式：54 2.指令分类与功能 指令系统：计算机能识别所有指令的集合。1.3 计算机工作原理程序程序：指用户根据某一问题的解决步骤，：指用户根据某一问题的解决步骤，选用一组指令进行有序排列的集合。选用一组指令进行有序排列的集合。数据传送指数据传送指令令将数据在存储器之间进行传送将数据在存储器之间进行传送数据处理指数据处理指令令对数据进行运算和变换对数据进行运算和变换控制转移指控制转移指令令控制程序中指

38、令的执行顺序控制程序中指令的执行顺序输入输出指输入输出指令令实现主机与外设间传输信息的指实现主机与外设间传输信息的指令令其他指令其他指令执行停机、空操作和等待的指令执行停机、空操作和等待的指令55 1.3.2 计算机程序设计 举例说明：计算 7+2=?1 1从存储器中取出从存储器中取出7 7到运算器的到运算器的0 0号寄存号寄存器中器中2 2从存储器中取出从存储器中取出2 2到运算器的到运算器的1 1号寄存号寄存器中器中3 3将将0 0号和号和1 1号寄存器中的数据相加，得号寄存器中的数据相加，得和和9 94 4将计算结果将计算结果9 9存入存储器中存入存储器中5 5在输出设备中打印计算结果在

39、输出设备中打印计算结果9 91.3 计算机工作原理文字描述的计算程序文字描述的计算程序56计算程序的简写形式计算程序的简写形式指令操作码指令操作码操作数存放单操作数存放单元元指令顺序指令顺序操作码操作码操作数操作数1 1取数取数7 72 2取数取数2 23 3加法加法7 7，2 24 4存数存数9 95 5打印打印9 96 6停机停机操作名称操作名称操作码操作码取数取数01000100加法加法01010101存数存数10101010打印打印10001000停机停机11111111数的操作地址数的操作地址存放的数存放的数000100010111(7)0111(7)001000100010(2)0

40、010(2)00110011计算结果计算结果57用二进制表示的计算程用二进制表示的计算程序序存储器布局存储器布局指令地指令地址址操作码操作码 地址码地址码所完成的操所完成的操作作010101010100010000010001 R R0 0(D(D1 1)011001100100010000100010 R R1 1(D(D2 2)011101110101010100010001 R R0 0(R(R0 0)+(R)+(R1 1)100010001010101000110011 D D3 3(R(R0 0)100110011000100000110011 打印机打印机(D(D3 3)10101

41、01011111111 停机停机单元地址单元地址 存储单元内存储单元内容容000100010000011100000111 7 7001000100000001000000010 2 200110011 计算结果计算结果01000100010101010100000101000001 取数指令取数指令011001100100001001000010 取数指令取数指令011101110101000101010001 加法指令加法指令100010001010001110100011 存数指令存数指令100110011000001110000011 打印指令打印指令1010101011111111

42、停机指令停机指令1011101158 1.3.3 计算机程序执行591.4 计算学科的典型问题 1.4.1 排序问题 排序是把给定数据集合中的元素按照一定的标准来安排先后次序的过程。选择排序算法选择排序算法：对给定的：对给定的一个数据表，算法从第一个元一个数据表，算法从第一个元素开始扫描整个列表，找到最素开始扫描整个列表，找到最小或最大的元素，并将其与第小或最大的元素，并将其与第一个位置的元素交换。然后算一个位置的元素交换。然后算法从第二个位置的元素开始扫法从第二个位置的元素开始扫描剩下的列表，找到次小或次描剩下的列表，找到次小或次大的元素，并将其与第二个位大的元素，并将其与第二个位置的元素交

43、换。如此循环，直置的元素交换。如此循环，直到所有的元素都被排好序为止。到所有的元素都被排好序为止。选择排序算法是由选择排序算法是由一个双层循环控制，一个双层循环控制，算法时间复杂度是算法时间复杂度是O(nO(n2 2)60 部分排序算法的时间效率比较(单位：毫秒)1.4 计算学科的典型问题每一种排序算法对时间的效率和空间的要求不尽相每一种排序算法对时间的效率和空间的要求不尽相同，没有哪一种是绝对最优的，在实用时需要根据同，没有哪一种是绝对最优的，在实用时需要根据不同情况适当选用，也可多种方法结合使用。不同情况适当选用，也可多种方法结合使用。排序算法排序算法10101001001K1K10K10

44、K100K100K1M1M插入排序插入排序0.0002580.0002580.0086190.0086190.7640.764565651455145515621515621冒泡排序冒泡排序0.0002760.0002760.0056430.0056430.5450.545616181748174549432549432选择排序选择排序0.0002370.0002370.0064380.0064380.4880.488474747174717478694478694快速排序快速排序0.0002910.0002910.0030510.0030510.0300.0300.3110.3113.634

45、3.6343939归并排序归并排序0.0007230.0007230.0062250.0062250.0660.0660.5610.5615.485.487070基数排序基数排序0.0051810.0051810.0210.0210.1650.1651.651.6511.42811.428117117哈希排序哈希排序0.0005220.0005220.0033720.0033720.0360.0360.5180.5184.1524.152616161 1.4.2 汉诺塔问题1.4 计算学科的典型问题印度古老传说印度古老传说：在世界中心贝拿勒斯的圣庙里，一块黄铜：在世界中心贝拿勒斯的圣庙里，一块

46、黄铜板上插着三根宝石针板上插着三根宝石针A A、B B和和C C。印度教的主神梵天在创造。印度教的主神梵天在创造世界时，在其中一根针上从下到上地穿好了由大到小的世界时，在其中一根针上从下到上地穿好了由大到小的6464片金片，这就是所谓的汉诺塔问题。片金片，这就是所谓的汉诺塔问题。不论白天黑夜，总有一个僧侣不论白天黑夜，总有一个僧侣在按下面的法则移动这些金片：在按下面的法则移动这些金片：一次只移动一片，不管在哪根一次只移动一片，不管在哪根针上，小片必须在大片上面。针上，小片必须在大片上面。僧侣们预言，当所有金片移到僧侣们预言，当所有金片移到另外一根针上时，世界将在一另外一根针上时，世界将在一声霹

47、雳中消灭，而梵塔、庙宇声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽。和众生也都将同归于尽。62 不管这个传说的可信度有多大，如果仅考虑把64片金片，由一根针上移到另一根针上，并且始终保持上小下大的顺序。这需要多少次移动呢？这里需要使用递归算法。1.4 计算学科的典型问题假设有假设有n n片，移动次数是片，移动次数是f(n)f(n)显然显然f(1)=1f(1)=1，f(2)=3f(2)=3，f(3)=7f(3)=7，且，且f(k+1)=2f(k+1)=2*f(k)+1f(k)+1不难证明不难证明：f(nf(n)=)=2 2n n-1-1当当n=64n=64时，时，f(64)=f(64)=2 2

48、6464-1=18446744073709551615-1=18446744073709551615次次如果如果每秒钟移动一次，共需多长时间呢？每秒钟移动一次，共需多长时间呢？一年一年有有3153600031536000秒，则秒，则18446744073709551615/3153600018446744073709551615/31536000584942417355584942417355年年63 1.4.3 国王的婚姻1.4 计算学科的典型问题国王：艾述国王：艾述(喜爱数学喜爱数学)宰相：孔唤石宰相：孔唤石(数学家数学家)公主：秋碧贞楠公主：秋碧贞楠(邻国邻国)公主：求出公主：求出487

49、7042864483689948770428644836899的一个真因子的一个真因子国王：国王：2,3,4,300002,3,4,30000多数据多数据(一天一天)公主：验证一下，公主：验证一下，223092871223092871宰相：将全国百姓按自然数的顺序编号，百姓用自己的编宰相：将全国百姓按自然数的顺序编号，百姓用自己的编号去除公主的数，谁除尽来领赏。号去除公主的数，谁除尽来领赏。童话说明童话说明：国王本人计算：国王本人计算(串行算法，时间复杂性串行算法，时间复杂性)全国百姓计算全国百姓计算(并行算法，空间复杂性并行算法，空间复杂性)64 1.4.4 旅行商问题 旅行商问题(TSP)

50、的描述：一位商人去n个城市推销货物，所有城市走一遍后，再回到起点，问如何事先确定好一条最短的路线，使其旅行的费用最少。1.4 计算学科的典型问题路径路径ABCDAABCDA的总距离是：的总距离是：4+2+4+2=124+2+4+2=12路径路径ABDCAABDCA的总距离是：的总距离是：4+6+4+6=204+6+4+6=20路径路径ACBDAACBDA的总距离是：的总距离是：6+2+6+2=166+2+6+2=16路径路径ACDBAACDBA的总距离是：的总距离是：6+4+6+4=206+4+6+4=20路径路径ADCBAADCBA的总距离是：的总距离是：2+4+2+4=122+4+2+4=