计算思维与计算机导论

计算思维导论

AnIntroductionofComputationalThinking1课程简介课程名称：计算思维导论课程编码：K100100220英文名称：AnIntroductionofComputationalThinking学时：32学分：2适用专业：全校理工类专业起点二课程类别：必修课程性质：公共基础课先修课程：教学目的教学目的：学生树立计算思维的理论体系，培养使用计算思维的方法解决实际问题的能力，为进一步学习其他课程打下坚实基础，与各学科的专业知识融合进行研究和创新。主要内容主要内容包括：计算思维和计算计算系统的基本思维计算机硬件的基本思维计算机软件的基本思维问题求解的基本思维计算机网络的基本思维信息安全的基本思维数据库的基本思维Word2010高级应用Visio2010高级应用Excel2010高级应用PowerPoint2010高级应用学时安排课程总学时32，（1）理论课讲授（20学时）（2）上机实践（12学时）（3）自主学习参考教材参考教材：[1]宁爱军，王淑敬等.计算思维与计算机导论[M].北京：人民邮电出版社，2018年8月，ISBN978-7-115-48812-1考核方式课程考试包括两部分：总成绩=期末考试（A）*0.7+课程平时成绩(B)*0.3（A）期末考试试卷（具体题型参考《计算思维导论样卷v2018》）（B）平时成绩，由任课教师根据平时学习记录评定，主要依据包括实验完成情况，平时签到记录，报告论文完成情况等。按照《大学生学籍管理规定》不符合要求的将取消考试资格或不予评定成绩；任课教师根据实际情况，可以自主安排，自主学习提交作品占适当平时分。小结通过本章的学习，了解课程的有关情况。81计算思维和计算天津科技大学

计算机公共基础系9目录1.1计算思维概述 1.2计算与自动计算 1.3计算工具的发展史 1.1计算思维概述计算思维是指计算机、软件以及计算相关学科的科学家和工程技术人员的思维方法。计算思维定义美国CMU大学周以真教授：

计算思维是运用计算科学的基础概念进行问题求解、系统设计以及人类行为理解等涵盖计算机科学之广度的一系列思维活动。

本质是抽象和自动化，即在不同层面进行抽象，以及将这些抽象机器化。

目的是希望所有人都能像计算机科学家一样思考，将计算技术与各学科理论、技术与艺术进行融合实现新的创新。计算思维的基本内容计算思维包括多项基本内容。二进制0和1的基础思维。指令和程序的思维递归的思维计算机系统发展的思维问题求解的思维网络化的思维1.1.2计算思维与各学科的关系1．应用计算手段促进各学科的研究和创新2．各学科创新自己的新型计算手段3．计算思维可以帮助培养各专业的人才1.2计算与自动计算计算是指数据在运算符的操作下，按照规则进行数据变换。有时候虽然人们知道了计算的规则，但是因为计算过于复杂，超过了人的计算能力，所以无法计算得到结果。两种解决方法：计算与自动计算两种解决方法（1）通过数学上的规则推导，获得等效的计算方法，从而完成计算。【例1.2】计算

通过数学推导可得

，人们可以轻松的完成计算计算与自动计算（2）另一种办法是设计简单的规则，让机器重复执行，进行自动计算。【例1.3】计算

可以转化为可以由机器重复执行的自动计算的计算规则step1:输入整数nStep2:s=0Step3:i=1Step4:s=s+iStep5:i=i+1Step6:如果i<=n，那么转入step4执行Step7:输出s，算法结束。计算与自动计算2．计算科学的基本问题计算科学的基本问题是“什么能够被有效地自动计算，什么不能被有效地自动计算？”(1)哪些问题可以在有限时间和有限空间内自动计算，计算的时间和空间复杂度怎样？(2)通过人类的各种思维模式，如何设计有效的计算方法，以减少计算的时间和空间复杂度。1.3计算工具的发展史计算和自动计算时需要考虑以下4个问题：（1）数据的表示。（2）数据的存储及自动存储。（3）计算规则的表示。（4）计算规则的执行与自动执行。提示：计算工具的发展过程就是人们不断追求计算的机械化、自动化和智能化，尝试各种计算工具，实现数据的表示、存储和自动存储数据、计算规则的表示、执行和自动执行计算规则的过程。1.3.1计算工具的发展计算工具的发展包括三个阶段:手动计算器机械计算器电子计算机1．手动计算器手动计算器是利用算法进行辅助数字计算过程的设备，操作者使用算法来进行计算。小石块和有刻痕的小棍算筹、算盘，珠算歌诀。纳皮尔筹，也称为纳皮尔计算尺滑动刻度尺2．计算机的雏形——机械式计算器机械式计算器可以自动完成计算，操作者不需要了解算法.1642年，帕斯卡加法器1673年，莱布尼兹乘法器1822年，差分机库塔（Curta）3．电子计算机电子计算机能够自动自动存储数据，能够理解和自动执行任意的复杂规则，能进行任意形式的计算。电子计算机在1937年到1942年间，阿塔纳索夫-贝瑞计算机（Atanasoff-BerryComputer，ABC）真空电子管代替机械式开关作为处理电路基于二进制数字系统的理念。ABC本身不可编程，仅用于求解线性方程组电子计算机1946年2月，ENIAC使用18

000个电子管，耗电150千瓦，总重量30吨每秒执行5

000次加法运算，是手工计算的20万倍造价为48万美元ENIAC成为世界公认的第一台电子计算机。1.3.2元器件的发展元器件发展中经历了电子管、晶体管、集成电路三个阶段电子管晶体管集成电路元器件的发展集成电路的构想：

通过在同一材料（硅）块上集成所有元件，并通过上方的金属化层连接各个部分，自动实现复杂的变换。这样，就不再需要分立的独立元件，避免了手工组装元件、导线的步骤。（1）1980年代，超大规模集成电路（VLSI），几十万个元件（2）1990年代，特大规模集成电路（ULSI），百万级（3）2012年，一块硅片上可以集成14亿个元件。元器件的发展摩尔定律：当价格不变时，集成电路上可容纳的晶体管书目约每18个月会增加1倍，其性能也提升1倍。提示：元器件的发展规律是：元件的尺寸越来越小，芯片体积越来越小，芯片上集成的器件越来越多，可靠性越来越高，运行速度越来越快，价格却越来越便宜。计算机的计算速度越来越快，功能越来越强大，能够完成的任务也越来越复杂。学习要求学生应掌握计算思维的基本概念。掌握计算的有关概念，计算工具的发展，元器件的发展等。阅读教材完成书后习题。2计算机系统的基本思维天津科技大学

计算机公共基础系30目录2.10和1的思维 2.2二进制与数据编码 2.3图灵机与冯•诺依曼计算机 2.10和1的思维计数制是指用一组固定的数码和一套统一的规则表示数值的方法。按进位的原则进行计数称为进位计数制。十进制、二进制、八进制、十六进制。进位计数制中表示一位数所能使用的数码符号个数称为基数。例如十进制数有0～9共10个数码，基数为10，逢10进1。进位计数制任何一个数，不同数位的数码表示的值的大小不同。例如，十进制中，323.4可以表示为进位计数制进位计数制1．十进制十进制中，K表示0～9的10个数码中的任意一个数码，则任何一个数（N）可以表示为：进位计数制2．二进制计算机中信息的存储和处理都采用二进制。二进制数只有0、1两个数码，基数为2，逢2进1。为了便于区分，在二进制数后加“B”，表示数为二进制数。进位计数制3．八进制八进制有0～7共8个数码，基数为8，逢8进1。为了便于区分，在八进制数后加“O”，表示数为八进制数。例如：进位计数制4．十六进制十六进制有0～9、A、B、C、D、E、F共16个数码，基数为16，逢16进1，用A～F表示十进制中10～15的6种状态。为了便于区分，在十六进制数后加“H”，表示数为十六进制数。例如：2.1.2不同进制数的转换1．不同进制数转换为十进制数【例2.1】将二进制数(110010100111.1)2、八进制数(6

247.4)8、十六进制数(CA7.8)16转换为对应的十进制数。不同进制数的转换2．十进制数转换为二进制、八进制、十六进制数将十进制数的整数部分转换为R进制数，通常采用“除R取余法”，即用十进制整数除以R取余数，将商反复除以R，直至商为零。得到的第一个余数为最低位，最后一个余数为最高位，将所得余数从高位到低位依次排列，就是对应R进制数。不同进制数的转换【例2.2】将十进制整数(167)10转换为对应的二进制、八进制、十六进制数。不同进制数的转换十进制转换为八进制不同进制数的转换十进制转换为十六进制不同进制数的转换3．二进制、八进制、十六进制数的相互转换每3位二进制数对应一位八进制数，每4位二进制数对应一位十六进制数【例2.3】将二进制数(10100111.1011)2转换成八进制、十六进制数。不同进制数的转换【例2.4】将(367.45)8、(E7B2.C8)16转换为二进制数。2.1.3二进制与易经易经是中国最古老的哲学思想，通过阴阳的组合来进行现实世界的语义符号化。语义符号化是指将现实世界的使用符号来表达，进而进行基于符号的计算的一种思维。

阴用两个短线（或六）来表示；

阳用一根长线（或九）来表示

阴对应二进制的0，阳对应二进制的1二进制与易经三画卦，8种组合，即八卦

天（乾）、地（坤）

雷（震）、风（巽）

水或月（坎）、

火或日（离）

山（艮）、泽（兑）二进制与易经六画的组合形成一卦，共有64种组合，即六十四卦。六画卦可以描述人从生到死的变化规律，或者描述一年二十四节气的演变规律。三画卦和六画卦的每一个阴和阳称为爻，则三画卦包括24爻，六画卦包括384爻。八卦和六十四卦从本质上来说是二进制数2.1.4二进制与逻辑运算逻辑指的是事物之间遵循的规律，是现实生活中普适的思维方式。逻辑的基本表现形式是命题和推理。命题是由语句表达的内容为真或假的一个判断。推理就是依据简单命题的判断结论推导出复杂命题的判断结论的过程。二进制与逻辑运算【例2.5】命题举例，现实生活中小明是一个男的小学生，变量A的值为10。命题1：小明是男生，结果为真。命题2：小明是小学生，结果为真。命题3：小明是男生，并且是个小学生，结果为真。命题4：A>3，结果为真。命题5：A<10，结果为假。命题6：A>3并且A<10，结果为假。二进制与逻辑运算【例2.6】将【例2.5】的命题的符号化。命题1用X表示。命题2用Y表示。命题3用Z表示，则“Z=XANDY”二进制与逻辑运算复杂命题的推理可以通过逻辑运算完成。逻辑运算符包括：（1）AND与：XANDY，X和Y都为真时，为真。（2）OR或：XORY，X和Y都为假，才为假。（3）NOT非：NOTX，X为真时值为假，X为假时值为真（4）XOR异或：XXORY，X和Y不同时为真。二进制与逻辑运算2.1.5二进制与元器件基本的逻辑运算可以由电子元器件及其电路实现。如高电平为1，低电平为0。电子计算机中，使用电子管来表示十进制的十种状态过于复杂，而使用电子管的开和关两种状态来表示二进制的0和1则非常容易实现。二进制与元器件【例2.7】使用8个电子管的一组开关状态表示二进制数10100110二进制与元器件硬盘也称为磁存储设备，通过电磁学原理读写数据，存储介质为磁盘或磁带，通过读写磁头改变存储介质中每个磁性粒子的磁极为两个状态，分别表示0和1二进制与元器件盘利用激光束在光盘表面存储信息，根据激光束和反射光的强弱不同，可以实现信息的读写。在写入光盘时会在光盘表面形成小凹坑，有坑的地方记录“1”，反之为“0”。二进制与元器件计算机中采用二进制数有以下优点。（1）可行性。（2）简易性。（3）适合逻辑运算。（4）易于转换。2.1.6存储单位关系（1）位（bit）。一“位”只能表示0和1中的一个。（2）字节（Byte）。每8个位称为字节（简写为B）。1张JPG图片，大约1MB，使用传统电子管存储需要220×8，约800万个。2.2二进制与数据编码在计算机中，数字、字符、图片、声音、视频等所有信息都要进行二进制编码才能存储和处理2.2.1二进制与数字的表示1．机器数在计算机中采用固定数目的二进制位数来表示数字，称为机器数。机器数的表示范围受计算机字长的限制，一般字长为8、16、32或64位数值超出机器数能表示的范围，就会出现“溢出”错误通常把一个二进制数的最高位作为符号位。机器数【例2.8】8位计算机中整数+11和-11对应的机器数。+11的机器数是00001011-11对应的机器数10001011原码原码原码是数字最简单的表示方法。用0表示正号、1表示负号。反码正数的反码与原码相同，负数的反码由原码的数值部分按位取反得到（即0变为1，1变为0）。0的反码有两种表示方法。补码正数的补码与原码、反码相同，负数的补码等于负数的反码加10有唯一的补码，[+0]补=[-0]补=00000000补码的算术运算补码可以将计算中的减法运算转变为加法运算，而原码和反码则不行。2.2.2计算机中的字符编码常用的西文字符有128个ASCII码存储和处理西文字符，是通用的国际标准编码7位ASCII采用7位二进制数表示一个字符，每个字符占用1Byte的空间，即8位二进制数，最高位设置为02.2.3计算机中的汉字编码1981年颁布了《信息交换用汉字编码字符集——基本集》，国家标准GB2312—80，简称国标码。基本集共收集汉字6

763个，常用一级汉字3

755，二级汉字3

008个。2个字节（16位）表示一个汉字，理论上可以表示256×256=65

536个汉字1．机内码为了区分汉字编码和ASCII字符，将国标码每个字节的最高位由0改为1，构成汉字的机内码，也称内码汉字在计算机内部存储、处理和传输时使用机内码汉字内码=汉字国标码+(8080)162．输入码通过键盘向计算机中输入汉字所使用的编码为输入码，也称外码。以拼音为基础的拼音类输入法以字形为基础的字形类输入法以拼音、字形混合为基础的混合类输入码3．输出码输出码也称汉字字型码，指汉字字库中存储的汉字字型的数字化信息，用于汉字在显示或打印输出。不同的汉字字库存放不同形状的汉字字型（即字体），如宋体、楷体、隶书等分为点阵和矢量两种表示方法（1）点阵字库用点阵表示字型时，将一个汉字放在一个多行多列的网格中，有笔画通过的网格用二进制位1表示，没有笔画通过的网格用二进制位0表示一般有16×16、24×24、48×48、64×64点阵汉字字型码以二进制数形式保存在存储器中，构成汉字字库48×48点阵需要288Byte（=48×48/8）空间存放一个汉字的字型码。（2）矢量字库矢量汉字字库存储的是描述汉字字型的轮廓特征，当要输出汉字时，通过计算机的计算由汉字字型描述生成所需大小和形状的汉字点阵。放大以后不影响输出效果2.2.4图像的数字化编码图像由许多像素组合而成，每个像素用若干二进制位来表示其颜色。每个像素所占二进制位数越多，则色彩越丰富，效果越逼真位图图像的色彩采用RGB模式，即红、绿、蓝。例如：24位颜色中从低位到高位分别用1字节表示蓝色、绿色和红色。

红色#FF0000 绿色#00FF00 蓝色#0000FF

白色#FFFFFF 黑色为#000000位图进行缩放时图像会失真图像的数字化图像的数字化过程主要包括：（1）采样（2）量化（3）编码量化计算机中的图像分为X行Y列的点阵，每个点用二进制数的编码表示其颜色，将所有点的二进制编码保存在一起成为一个图片文件。（1）一张24位色、640像素×480像素的照片 224=16777216种颜色，存储该照片大约需 640×480×24/8B=921600B=900KB（2）一张24位色、4288像素×2848像素的照片 4288×2848×24bit=35778KB=34.94MB

2.2.5声音的数字化编码声音又称音频。自然界的声音是模拟音频，是随时间连续变化的模拟量，信号体现为波形计算机中存储的音频为数字音频，它是随时间不连续或离散变化的数字量。声音的数字化编码将每1秒的采样次数称为采样频率，

如22.05kHz、44.1kHz、48kHz

编码可以用8bit、16bit、24bit表示声音的数字化编码例如44.1kHz的32位音频每秒有44.1×1024=45158.4个采用每个采样能描述232=4294967296种声音信号1分钟的44.1kHz的32位音频，需要存储空间 44.1×1024×60×32bit=5292KB=10.34MB2.2.6数据压缩技术数据压缩技术对数据重新编码，以减少所需的比特数，减少占用的存储空间，便于传输。数据压缩是可逆的，它的逆过程称为解压缩。数据之所以能被压缩，是因为数据中存在冗余。数据压缩技术1．压缩的指标

（1）压缩比。（2）压缩质量。（3）压缩和解压缩速度。数据压缩技术压缩的分类（1）有损压缩。

如图像、视频、声音

压缩比可以从几倍到上百倍（2）无损压缩。

如文本数据、程序代码和特殊应用场合的图像。

压缩比一般为2∶1～5∶1数据压缩技术图像和音频的压缩JPEG，有损压缩。（a）原始BMP文件

（b）30%压缩率的JPG文件2.3图灵机与冯•诺依曼计算机1．图灵阿兰·麦席森·图灵英国著名数学家、逻辑学家、密码学家被称为计算机科学之父、人工智能之父2．图灵机的基本思想图灵认为自动计算就是人或者机器对一条两端无限延长的纸带上的一串0和1，执行指令，一步步地改变纸带上的0和1，经过有限步骤得到结果的过程。指令由0和1表示，例如：00表示停止01表示转0为1,10表示翻转1为011表示移位2．图灵机模型图灵机（TuringMachine）是指一个抽象的计算模型。图灵机模型被认为是计算机的基本理论模型，它是一种离散的、有穷的、构造性的问题求解思路，一个问题的求解可以通过构造器图灵机来解决。著名的图灵可计算问题：凡是能用算法解决的问题，也一定能用图灵机解决；凡是图灵机解决不了的问题，任何算法也解决不了。3．图灵测试图灵测试，是图灵提出的一个关于机器人的著名判断原则，它是一种测试机器是否具备人类智能的方法。If电脑能在5分钟内回答问题，超过30%的回答让测试者误认为是人类所答，Then电脑通过测试，具有人类智能。3．图灵测试2014年6月7日在英国皇家学会举行的“2014图灵测试”大会，聊天程序“尤金·古斯特曼”（EugeneGoostman）首次通过了图灵测试。2.3.2冯·诺依曼计算机EDVAC：1946年，冯·诺依曼领导的研究小组发表了关于EDVAC计算机的论文。EDVAC是第一台具有现代意义的并行计算机，首次使用二进制。整台计算机使用了大约6000个电子管和12000个二极管，功率为56kW，占地面积45.5m2，重7850kg，2.3.2冯·诺依曼计算机冯·诺依曼体系结构计算机：（1）计算机由控制器、运算器、存储器、输入设备和输出设备5个部分构成（2）确定了计算机采用二进制，指令和数据均以二进制数形式存储在存储器中。（3）计算机按照程序规定的顺序将指令从存储器中取出，并逐条执行。冯·诺依曼计算机1．运算器运算器（ArithmeticLogicUnit，ALU）也称算术逻辑运算单元，主要完成算术运算和逻辑运算。冯·诺依曼计算机2．控制器控制器（ControlUnit）也称控制单元，负责读取指令、分析指令和执行指令，调度运算器完成计算。冯·诺依曼计算机3．存储器

存储器负责存储数据和指令。冯·诺依曼计算机4．输入设备输入设备负责将数据和指令从外部输入到计算中。5．输出设备输出设备将计算机中的二进制信息以用户能接受的形式呈现。2.3.3存储程序控制原理为了能够让计算机完成任务，需要为计算机提供一系列命令。指令：也称机器指令，是指计算机完成某个基本操作的命令，是计算机可以识别的二进制编码。包括操作码和操作数两部分。计算机的字长是指计算机能一次直接处理的二进制数据的位数。存储程序控制原理（2）指令系统：一台计算机所有机器指令的集合称为计算机的指令系统。（3）程序：由指令组成，是为解决某一特定问题而设计的有序指令的集合，是为了得到某种结果而由计算机等具有信息处理能力的装置执行的指令序列。存储程序控制原理2．指令执行过程：计算机按照程序的执行顺序逐条取出存储器中的指令，传输到CPU后执行。

（1）取指令阶段。

（2）分析指令阶段。

（3）执行指令阶段。

（4）写回结果阶段。提示：按照存储程序控制原理构造出来的计算机就是存储程序控制计算机，也称为冯·诺依曼计算机。半个多世纪以来，冯·诺依曼体系结构一直沿用至今，计算机一直遵循存储程序控制原理。学习要求阅读教材完成书后习题3计算机硬件的基本思维天津科技大学

计算机公共基础系100目录3.1现代计算机的结构 3.2计算机的应用领域 3.3单片机 3.4高性能计算与分布式计算 现代计算机的组成现代计算机系统由硬件、软件、网络和数据组成。（1）硬件（2）软件（3）网络（4）数据3.1现代计算机的结构现代计算机沿用冯·诺依曼体系结构，以微处理器为核心，配以内存、输入/输出接口和输入/输出设备等。CPU、内存和输入输出设备被称为计算机的三大核心部件现代计算机的结构总线是连接CPU、内存和各个I/O（Input/Output）接口模块的数据通路，是各模块之间传递数据的通道。总线分为以下三类。（1）地址总线（AB）（2）数据总线（DB）（3）控制总线（CB）3.1.2主板主板（Mainboard），是一块电路板，一般有BIOS芯片、I/O控制芯片、键和面板控制开关接口、指示灯插接件、扩充插槽、主板及插卡的直流电源供电接插件等元件。提示：通过在主板上设计电路和接口，连接各种设备的思维方法，目前广泛应用在计算机、手机以及家电等各种装备的设计中。3.1.3微处理器CPU微处理器是一块超大规模的集成电路，是计算机的核心，也称中央处理单元（CPU)。中央处理器主要包括控制器、运算器、寄存器以及高速缓冲存储器（Cache）CPUCPU的主要性能指标（1）主频。主频就是CPU时钟频率，也是CPU内核的工作频率，它标识CPU的运算速度，一般以MHz和GHz为单位。

目前的CPU主频已经达到4GHz或更高

因为工艺限制和功耗的原因，CPU的主频不能无限制增长，只能限制在4GHz或稍高（2）字长字长是计算机能直接处理的二进制位数。决定计算机的运算能力，字长越长，运算精度越高决定计算机的寻址能力，字长越长，寻址能力越强如32位，64位。（3）内核数。一台计算机中，采用多处理器并行处理的方法可以提高计算能力多核处理器在一个处理器中集成多个内核，通过并行处理提高计算能力如双核、四核、八核处理器（4）高速缓存CPU的高速缓存大小也是CPU的重要指标之一，缓存的大小对CPU速度的影响非常大。CPU中缓存的运行频率极高，一般与处理器同频运作，工作效率远远高于内存和硬盘。3．CPU的发展3.1.4计算机的存储体系随着CPU计算速度不断加快，计算机需要存储和处理的数据量越来越大，对存取速度的要求也越来越快。因此对存储的要求是容量足够大，越大越好；读取速度足够快，越快越好，以满足CPU运算速度的需要；价格要足够低，越便宜越好；存储的时间足够长，越久越好。因为制造工艺、精度、价格等因素影响，计算机的存储体系采用“速度、容量、价格的存储资源优化组合的思维模式”。包括寄存器、内存、高速缓存、外存，外存；用来永久存储程序和数据，断电时数据也不会丢失，包括硬盘、移动硬盘、光盘、软盘、U盘和存储卡等。1．寄存器寄存器是CPU中的高速存储器，如包括通用寄存器、专用寄存器和控制寄存器，可以用来暂存指令、数据和地址，寄存器的容量是有限的。寄存器与CPU采用相同制造工艺，速度可以与CPU完全匹配。2．内存内存是可按地址访问的存储器，又称为主存储器，它是一种半导体芯片。CPU可以直接读写内存内存分为RAM和ROM内存RAM可以按照地址访问，既可以读也可以写，断电后数据会丢失。内存容量反映了计算机运算和处理能力，内存容量越大，计算机性能越好。常有1GB、2GB、4GB、8GB、16GB等内存ROM可按地址访问，只能读不能写，断电后数据不丢失ROM具有永久存储的特点，其中的信息必须事先写入，其后只能读不能写，其容量非常小。3．高速缓存Cache由于CPU的处理速度远超过内存，使得CPU经常处于等待状态，影响系统的整体处理能力。据统计，CPU经常会读取同一块或者相邻数据块，如果将这些数据块提前读入高速缓冲存储器（Cache，简称高速缓存）中，在需要时微处理器可以直接读写高速缓存，从而提高数据的存取速度高速缓存Cache高速缓存可以制作在主板上、CPU上或者CPU的内核上，一般将高速缓存分为一级、二级、三级缓存。提示：缓存的思维模式，把即将要处理的数据和信息提前准备好，可以显著提高计算和处理速度。在生活中，提前准备好上学的书包、提前做好饭菜、提前买好火车票等，都可以提高效率。缓存的思想不仅应用在CPU和内存之间，还可以用在内存和硬盘之间，内存与其他外部设备之间。4．硬盘硬盘是一种采用磁性材料制作的大容量存储器，可以永久保存数据。（1）硬盘由若干个盘片和读写臂组成，读写臂上有读写磁头（2）一个盘片被划分为若干个同心圆，每个同心圆称为磁道（3）不同盘片的相同磁道构成一个柱面（4）每个磁道又被分为若干个扇形区域，称为扇区。一个扇区可以存储512Byte数据硬盘硬盘的读写时间包括寻道时间、旋转时间和传输时间。在硬盘中，一个大文件最好存储在连续的扇区中。在读写时可以连续读写，减少寻道时间和旋转时间，从而提高读写的速度。如果一个文件碎片较多，那么读写速度会显著减慢。硬盘1956年的IBM350硬盘它的尺寸很大但却只有5MB的空间硬盘硬盘的性能指标如下：（1）尺寸：3.5寸，2.5寸（2）容量：一般为几百GB，到几TB（3）转速：硬盘的转速越快，则读写的也越快。常见转速有5400r/min，7200r/min。硬盘固态硬盘（SolidStateDrives，SSD），用固态电子存储芯片阵列而制成的硬盘4．移动存储设备（1）移动硬盘（2）光盘（3）软盘（4）U盘和存储卡移动存储设备（5）写保护口用于控制软盘、U盘、存储卡等可移动设备的“只读/可改写”状态，当其处于写保护状态时，只能读取不能写入。写保护口可以防止误删除、误格式化以及病毒感染等。计算机的存储体系计算机的存储体系：CPU中寄存器的数量少，存取速度最快；内存的存储容量小，存取速度快，内存只能临时保存数据；硬盘的存储容量大，存取速度慢，硬盘可以永久保存数据。CPU可以直接存取内存中的数据，而不能读取硬盘数据；CPU通过高速缓存Cache，提高内存与CPU的数据传输速度，从而显著提高系统的整体性能；硬盘中的数据必须先读入内存中，才能被CPU读取和处理。而各种移动存储设备提供了转移数据的可能。3.1.5输入设备和输出设备输入设备用于使得计算机感知外部世界的信息；输出设备用于将计算机的处理结果呈现给外部世界。输入输出设备是计算机和外界交换信息的工具，也是人和计算机进行交互的工具1．输入设备-穿孔纸带穿孔纸带是早期计算机的输入和输出设备，带孔为1，无孔为0，经过光电扫描输入电脑。1725年，法国法制机械师布乔（B.Bouchon）提出“穿孔纸带”构想。。1805年，法国机械师杰卡德（J.Jacquard）完成了“自动提花编织机”设计。2．输入设备-键盘1868年，美国克里斯托夫.肖尔斯C.Sholes发明了沿用至今的QWERTY键盘，也称全键盘3．输入设备-鼠标鼠标是一种常用的计算机输入设备，它可以对当前屏幕上的游标进行定位，并通过按键和滚轮装置对游标所经过位置的屏幕元素进行操作1964年美国道格拉斯·恩格尔巴特（DouglasEngelbart）博士发明鼠标4．输入设备-扫描仪扫描仪是利用光电技术和数字处理技术，以扫描方式将纸质文档、图形或图像转换为数字的装置。5．输入设备-手写笔手写笔可以在手写识别软件的配合下输入中文和西文6．输入和输出设备-触摸屏触摸屏（TouchScreen），是一种可接收手指等输入讯号的感应式液晶显示装置。7．输出设备-显示器显示器（display）也称为监视器，是一种将信息通过特定传输设备显示到屏幕上再反射到人眼的显示工具显卡显卡（Videocard，Graphicscard）又称显示适配器，插在计算机主板的插槽上，将计算机的信息输出到显示器上显示，同时显卡还具有图像处理能力，可协助CPU工作，提高整体的运行速度。主要性能指标包括：（1）GPU（图形处理器）的核心频率（2）显存的容量（3）显存的位宽（4）显卡分为集成显卡和独立显卡。8．输出设备-打印机打印机（Printer)是输出设备，将计算机的运算结果果以人所能识别的数字、字母、符号、图形等，按照规定的格式印在纸上。9．输出设备-3D打印机3D打印机又称三维打印机，是一种快速成形技术的机器，它以数字模型文件为基础，运用特殊蜡材、粉末状金属或塑料等可粘合材料，通过打印一层层的粘合材料来制造三维物体。10．输入和输出设备-声卡声卡是实现声波/数字信号相互转换的一种硬件。基本功能：（1）把来自麦克风等设备的原始声音信号转换成数字音频；（2）将计算机中的各种数字声音转换为模拟声波输出到音箱、耳机等设备上，（3）通过音乐设备数字接口(MIDI)使乐器发出MIDI声音。提示：输入设备不断丰富，使用越来越简单，人们可以通过键盘输入文字，通过鼠标进行定位，通过扫描仪、手写笔、触摸屏等输入图形，通过声卡输入声音。输出设备的发展针对人类的感觉器官，如视觉、听觉、触觉等，输出文字、图形、声音和3D实体等。使得计算机与人的交互越来越简单，操作越来越方便，输出效果越来越好。3.1.6接口接口是计算机系统中两个独立的部件进行信息交换的共享边界。这种交换可以发生在计算机软件、硬件、外部设备或进行操作的人之间，也可以是它们的结合。提示：在现代计算机中，有很多种标准化的硬件接口，接口一般包括插槽和插头两部分，每一种接口标准都规定了相关参数，如尺寸规格、引脚数、电压、电流等，使得一种接口标准的插头不能插入另一种接口的插槽，从而避免出错和电器故障。接口主板的电源接口和插头，计算机主板上的各种输入输出设备的接口1．硬盘接口硬盘接口是硬盘与主机系统间的连接部件，在硬盘和主机内存之间传输数据。硬盘接口（1）IDE接口，也称为ATA接口,它使用一个40芯电缆与主板进行连接，硬盘接口（2）SATA（SerialAdvancedTechnologyAttachment）接口即串行硬件驱动器接口其特点是结构简单、支持热插拔、传输速度快、执行效率高硬盘接口（3）SCSI接口（小型计算机系统接口），是一种用于计算机和智能设备之间（硬盘、软驱、光驱、打印机、扫描仪等）的系统级接口的独立标准，它能与多种类型的外设进行通信。SCSI接口的硬盘可靠性高可以长期运转，速度快，支持多设备，支持热拔插，常用于服务器连接硬盘。硬盘接口（4）光纤通道(FiberChannel)，利用光纤形成高速通道，能提高多硬盘存储系统的速度和灵活性。光纤通道的主要特性有：热插拔性、高速带宽、远程连接、连接设备数量大等。光纤通道价格昂贵，一般只用在高端服务器。2．USB接口USB（UniversalSerialBus，通用串行总线）接口，连接计算机系统与外部设备的一种串口总线标准,支持即插即用。优点：支持热插拔、携带方便、标准统一、可以连接多个设备。3．PCI和PCI-E接口PCI（PeripheralComponentInterconnect）接口是个人计算机中广泛使用的接口，几乎所有的主板产品上都带有这种插槽PCI-E（PCIExpress）接口是英特尔公司推出的用于取代PCI接口的技术，称为第三代I/O总线技术4．图形显示接口VGA（VideoGraphicsArray）视频图形阵列是一个使用模拟信号的计算机输出数据的专用接口DVI（DigitalVisualInterface）即数字视频接口HDMI（HighDefinitionMultimediaInterface）接口即高清晰度多媒体接口3.1.7选购计算机策略1．准备工作（1）确定自己的预算。（2）明确计算机的主要用途和相关需求。（3）选择所需要的外设。选购计算机策略2．选择机型（1）台式计算机。（2）笔记本计算机。（3）平板电脑。选购计算机策略3．兼容机还是品牌机兼容机的优点。①灵活性好。②价格优势。③易于升级。兼容机的缺点：无售后服务、需自行安装操作系统，在后期需要自行维护和修理等。选购计算机策略3．兼容机还是品牌机品牌机的优点：①稳定性好。②售后服务好。③配件丰富。品牌机的缺点是比兼容机的价格贵、配置无法根据需要自行选择、很多具体配件的型号未知等。选购计算机策略4．操作系统的选择Mac系统Windows系统选购计算机策略5．主要性能指标购买台式机、笔记本、平板等计算机时，主要考虑以下性能指标（1）CPU：品牌，主频，内核数，高速缓存。（2）内存：容量。（3）硬盘：容量，机械硬盘还是SSD，机械硬盘的转速。（4）显示器：尺寸，集成显卡还是独立显卡，显存大小。（5）保修：保修时间，送修方式。3.2计算机的应用领域随着计算机的计算能力日益强大、计算范围广泛、计算内容丰富，输入输出设备更直观易用，计算机的应用领域日益广泛。1．科学计算科学计算是指为解决科学研究和工程设计过程中的数学问题而进行的计算，也称为数值计算。如导弹试验、火箭发射、灾情预测、天气预报、化学实验分析等如灾情预测。2．数据处理数据处理（或信息处理）是指对各种数据进行收集、存储、整理、分类、统计、加工、利用、传播等一系列活动的统称。数据处理广泛应用于办公自动化、企事业计算机辅助管理与决策、情报检索、图书管理、电影电视动画设计、会计电算化等行业。3．过程控制过程控制又称实时控制，是指利用计算机及时采集检测数据，按最优值自动调节和控制对象。4．计算机辅助工程（1）计算机辅助设计CAD（2）计算机辅助制造CAM（3）计算机辅助教学CAI（4）计算机辅助测试CAT5．人工智能人工智能（ArtificialIntelligence）是指研究用机器代替和模仿人脑的某些智能功能，通过编写程序模拟人类的思维活动，诸如感知、判断、理解、学习、问题求解、图像识别等。包括人机对弈、定理证明、翻译语言文字、诊断疾病、海底作业等。机器人技术是人工智能领域最伟大的发明之一，6．计算机网络计算机网络是现代计算机技术与通信技术紧密结合的产物。计算机网络解决了一个单位、一个地区、一个国家中计算机与计算机之间的通信，实现各种软、硬件资源的共享，大大促进了国际间的文字、图像、视频、声音等各类数据的传输与处理。3.3单片机单片机（MCU）又称为单片微控制器或单片微型计算机，是一种集成电路芯片，是采用超大规模集成电路技术把具有数据处理能力的中央处理器（CPU）、随机存储器（RAM）、只读存储器（ROM）、多种I/O接口和中断系统、定时器/计时器等功能集成到一块硅片上构成的一个小而完善的微型计算机系统。单片机提示：一块芯片就构成一台计算机，单片机和计算机相比只缺少I/O设备，它具有体积小、质量轻、价格便宜等优势，为学习、应用和开发提供了便利条件。3.4高性能计算与分布式计算发展高速度、大容量、功能强大的高性能计算，对科学研究、国家安全、提供经济竞争力具有重要意义。1.高性能计算高性能计算(Highperformancecomputing，缩写HPC)指使用很多处理器（作为单个机器的一部分）或者某一集群中组织的几台计算机（作为单个计算资源操作）组成的计算系统和环境。2．分布式计算分布式计算（也称网格计算），它研究如何把一个需要巨大计算能力的问题划分成许多小的部分，然后把它们分配给许多计算机进行处理，最后把这些计算结果综合起来得到最终结果。学习要求阅读教材完成书后习题4计算机软件的基本思维

天津科技大学

计算机公共基础系170目录4.1软件系统概述 4.2操作系统 4.3操作系统的其他基本思维

4.1.1软件与硬件计算机系统包括硬件和软件两部分。硬件通常由电子器件和机电装置组成，是看得见、摸得到的实体，是计算机系统中各种设备的总称。软件是为计算机运行服务的全部技术和各种程序、数据的集合，是计算机的灵魂。软件分为系统软件和应用软件。软件与硬件硬件和软件的关系如下所述。（1）硬件和软件互相依存，缺一不可。（2）硬件和软件无严格界限，有时侯功能是等效的。（3）硬件和软件协同发展。4.1.2系统软件系统软件是管理、监控计算机软硬件资源，维护计算机运行，支持应用软件开发和运行的软件总和。系统软件包括：（1）操作系统（2）语言处理程序（3）数据库管理系统（4）诊断程序（5）服务性程序操作系统操作系统（OperatingSystem）是管理和控制计算机所有软件、硬件资源的程序，是直接运行在“裸机”上的最基本的系统软件，任何其他软件都必须在操作系统的支持下才能运行。它是人和计算机之间的接口，是系统软件的核心和基础。主要功能包括进程管理、存储管理、磁盘和文件管理和设备管理。4.2.1进程管理进程是正在运行的程序实体，包括这个运行的程序占据的所有系统资源，比如CPU、输入输出设备、内存和网络资源等。同一个程序两次运行，会产生两个独立进程分时调度策略处理器是计算机系统中最重要的资源。由于CPU资源有限，为了避免同一进程长时间独占CPU，需要通过分配策略为每个申请CPU的进程分配CPU，让每个进程都能执行。分时调度策略系统将所有进程按先来先服务的原则排成一个队列。每个进程被分配一个时间段，称作它的时间片。如果在时间片结束时进程还在运行，则CPU将被剥夺并分配给另一个进程。如果进程在时间片结束前阻塞或结束，则CPU立即切换到下一个进程。当进程用完它的时间片后，它被移到队列的末尾。这样可以保证就绪队列中的所有进程，在一定时间内，都能获得一定的处理器执行时间。分时调度策略进程队列p1、p2、p3、……、pn，每个时间片长度为t，队列中的每个进程依次执行时间片。因为时间片t足够小，每个进程都感觉自己在独占CPU。多处理机调度策略当一个大任务的计算量很大，用单一CPU计算可能花费很长时间。此时可以采用多处理机协同工作缩短运算时间将大计算量的任务划分成若干可由单一CPU计算的小任务，分配给相应CPU来执行。小任务被相应CPU执行完成后，再将结果合并处理，形成最终结果，返回用户。4.2.2存储管理存储管理的主要任务是分配和回收主存空间、提高主存利用率、扩充主存、对主存信息实现有效保护，为系统进程和用户进程提供运行所需的内存空间，同时保证各用户进程之间互不干扰，保证用户进程不破坏系统进程。虚拟内存技术虚拟内存技术，使用部分硬盘空间作为虚拟内存，与实际内存一起构成一个远远大于实际内存空间的虚拟存储空间。当系统的实际内存空间耗尽时，将正在使用的数据存放在实际内存中，暂时不用的数据存放在虚拟内存中。在需要时，将虚拟内存中的数据交换回实际内存中，不用的数据交换到虚拟内存。如果没有虚拟内存，当系统实际内存耗尽时，将不能再运行新程序。当系统的内存较少时，经常使用虚拟内存，频繁地交换数据会使得系统的整体性能显著下降。虚拟内存技术4.2.3磁盘和文件管理文件是被赋予了名字的若干信息的集合。磁盘分为盘面、磁道和扇区扇区是磁盘的一次读写的最小单位。1.分区与格式化一个磁盘被划分成多个分区，如C:、D:、E:。格式化，为分区划分存储区域，包括保留扇区区域、文件分配表区域、根目录区域和数据区域，建立文件分配表和根目录。2.文件夹文件夹用来记录磁盘上文件的文件名、文件大小、更新时间等重要信息。完整的文件名包括：（1）文件名（2）分隔点（3）扩展名例如：基础.docx文件夹和文件的管理操作，包括新建、删除、重命名、移动、复制、搜索等。文件夹搜索文件和文件夹【例4.1】搜索文件名为“notepad.exe”，指定修改时间或者指定文件大小的文件。（1）搜索文件名（2）“修改日期”选项（3）“大小”选项3．路径路径（PATH），以分区符号开始，以“\”连接各级文件夹和文件名，可以指向一台计算机中的一个文件。C:\WINDOWS\Notepad.exe4．文件分配表为了提高磁盘的访问速度、便于管理，操作系统将磁盘组织成一个个的簇块，每个簇块为

个连续扇区，每个簇块可以一次连续读写。文件的信息分割成若干个簇块，写入磁盘的一个个簇块上。由于文件的变化和写入的先后次序不同，一个文件可能存放在连续或者不连续的簇块上。操作系统通过文件分配表（FileAllocationTable，FAT）管理和操作文件。文件分配表FAT文件分配表是记录文件存储的簇块之间衔接关系的区域5．磁盘查错和磁盘碎片整理磁盘查错功能，可以检查并修复磁盘中存在的文件系统错误，恢复损坏的扇区。磁盘碎片整理，将文件中不连续簇块整理为连续簇块存放，从而提高文件的存取速度磁盘和文件管理提示：磁盘和文件的管理采用化整为零的基本思维，将磁盘划分为多个分区，每个分区划分为大量簇块，通过文件分配表保存文件的簇块顺序。每个簇块都很小，每个文件仅浪费最后一个簇块中剩余的空间，从而减少空间的浪费。4.2.4设备管理设备管理是指计算机系统中除了CPU和内存以外的所有输入输出设备的管理，为用户分配和回收外部设备，控制外部设备按用户程序的要求进行操作等。设备驱动程序，是一种可以使计算机和设备通信的特殊程序，它相当于硬件的接口，操作系统只有通过这个接口，才能控制硬件设备的工作。分层的思维方法：将一个复杂的问题划分成若干个抽象层次，每个抽象层次都相对比较简单，易于求解。编制每一层相应的处理程序，实现相邻层之间的转换。操作系统在进行设备管理时，通过分层思维使得下一层向上一层屏蔽实现细节，上一层的开发不需要关心下一层的实现细节。操作系统设备分层管理高级语言层设备无关层设备相关层设备驱动程序4.3.1虚拟机虚拟机（VirtualMachine）指通过软件模拟的具有完整硬件系统功能的、运行在一个完全隔离环境中的完整计算机系统。虚拟机软件有VMWare、VirtualBox和VirtualPC等4.3.2虚拟主机将一台物理服务器分割成多个逻辑主机，每一个逻辑主机都能像一台物理主机一样在网络上工作，各个逻辑主机之间完全独立，从外部看就是多个服务器，所以称为虚拟主机。各个用户拥有自己的系统资源（IP地址、存储空间、内存、CPU等），每一台虚拟主机和一台单独的主机的表现完全相同。虚拟主机提示：多个远程用户从一台服务器主机上获得各自独立的虚拟主机，每个虚拟主机拥有单独IP地址（或共享的IP地址）、独立域名以及完整的Internet服务器，支持WWW、FTP、E-mail等功能。虚拟主机技术能够节省服务器硬件成本，充分利用服务器硬件资源。4.3.3单机多系统单机多系统，指的是在一台计算机上安装多个操作系统，每个操作系统安装在一个独立分区中，后安装的系统不会覆盖前一个系统，系统之间不会冲突。4.3.4备份和还原操作系统备份：在操作系统初装时系统速度快、性能好，此时将系统分区备份为一个备份文件，将系统分区的所有状态和数据保存下来。还原：当系统显著变慢时，使用Windows备份和还原工具或者Ghost将以前所作的系统备份还原到系统分区中。学习要求阅读教材完成书后习题。5问题求解的基本思维天津科技大学

计算机公共基础系204目录5.1计算机语言 5.2程序设计基础 5.3算法 5.4算法设计 5.5 函数与递归 5.6 程序设计

5.1计算机语言计算机语言是语法、语义与词汇的集合，它用来表达计算机程序。程序是指某种程序设计语言编制的、计算机能够执行的指令序列，表达的是让计算机求解问题的步骤和方法。计算机语言的发展过程经历了四个阶段：机器语言汇编语言高级语言构件化语言1．机器语言计算机的指令系统是指一组能够识别和执行的二进制和编码表达的指令集合。使用二进制编码的指令编写程序的语言被称为机器语言。2．汇编语言汇编语言使用助记符来代替机器语言的指令码，使机器语言符号化，从而提高编程效率。如加法表示为ADD，指令“ADDA,9”的含义是将A寄存器中的数与9相加，并将结果存入A中。使用汇编语言的助记符编写的程序称为汇编语言源程序。3．高级语言与编译器高级语言是类似于自然语言、以语句和函数为单位书写程序的编程语言。高级语言编写的程序称为高级语言源程序。编译器先使用其编译程序将高级语言源程序转换为汇编语言源程序，再由汇编程序将汇编语言源程序转换为机器可执行的二进制语言程序。4．构件化的语言构件化的语言的每一个构件都是由一系列语句完成的复杂程序，能够完成一定功能。构件化的语言，包括VisualBasic、VisualC++、Delphi，.Net等5．编程语言的分层结构编程语言的分层结构思维，以下层语言为基础，再定义一套能力更强的新语言和编译器。人们使用新语言高效率地编写程序，使用编译器将其编译成下层语言能识别的源程序。编译器将上级语言的源程序一层层向下翻译，直到最终得到机器语言程序，计算机就可以执行程序。6．Java虚拟机Java是一种面向对象的编程语言Java源程序，编译后会生成一种.class文件，称为字节码文件Java虚拟机（JavaVirtualMachine，简称JVM）负责将字节码文件翻译成特定平台下的机器码然后运行。只要在不同平台上安装对应的JVM，就可以运行JAVA字节码文件5.2程序设计基础程序设计的本质：程序设计与计算机的组成有密切关系，程序设计的本质是设计能够利用计算机的5个部件完成特定任务的指令序列。【例5.1】用键盘输入价格与斤数，计算樱桃的总价。PrivateSubCommand1_Click()DimpriceAsSingle,numberAsSingle,totalAsSingleprice=Val(Text1.Text)'输入樱桃价格number=Val(Text2.Text)'输入樱桃斤数total=price*number'计算总价钱Text3.Text=total'输出总价钱EndSub2．常量常量指在程序运行过程中值不能改变的量，通常是固定的数值或字符。（1）数值型：40,-40,0,123.456。（2）字符型："Hellowolrd!"。（3）逻辑型：真为True，假为False。3．变量在程序运行过程中，其值可以改变的量称为变量。变量占据内存中的一块存储单元，用来存放数据，存储单元中的数据可以改变。给存储单元起的名字，就是变量名4．算术运算符算术运算符的作用是进行算术运算，用算术运算符将运算对象连接起来的表达式称为算术表达式。算术运算符数学表达式编写成VisualBasic表达式为： (a+b)^4/(a*(b+c))5．关系运算符关系运算符用于比较两个操作数的关系，用关系运算符连接两个表达式称为关系表达式若关系成立，则表达式值为True，否则为False。6．逻辑运算符逻辑运算符用于对操作数进行逻辑运算，用逻辑运算符连接关系表达式或逻辑值称为逻辑表达式。逻辑表达式的结果为True或False5.3算法算法是解决一个问题所采取的一系列步骤。著名的计算机科学家NikiklausWirth提出如下公式：

程序

=

数据结构

+

算法算法给出了解决问题的方法和步骤，是程序的灵魂，决定如何操作数据，如何解决问题。5.3.2算法举例【例5.2】求1

+

2

+

3

+

4

+…+

100。（1）“1

+

2

+

3

+

4

+

5

+

6

+…+

100”，不可行（2）可行：

算法举例【例5.3】编写英里与公里转换程序，输入英里数，转换为千米数输出。step1:输入英里数milesstep2:kms=0.621*milesstep3:输出公里数kmsstep4:结束启发：判断算法是否正确的方法：跟踪上述算法的执行过程，理解变量的作用、程序设计时可用的部件和功能，验证算法的正确性。5.3.3算法的表示1．自然语言eg：求两个数的最大值如果A大于B，那么最大值为A，否则最大值为B自然语言表示算法时拖沓冗长，容易出现歧义，因此不常使用。2．伪代码伪代码用介于自然语言和计算机语言之间的文字和符号来描述算法。ifA大于Bthen最大值为Aelse最大值为B伪代码的描述方法比较灵活，修改方便，易于转变为程序，但是当情况比较复杂时，不够直观，而且容易出现逻辑错误。3．传统流程图流程图表示算法比较直观，它使用一些图框来表示各种操作，用箭头表示语句的执行顺序。4．N-S流程图N-S流程图又称盒图，其中所有结构都用方框表示。算法的特性算法应该具有以下特性才可以正确执行：（1）有穷性。（2）确定性。（3）输入。0个或者多个输入。（4）输出。（5）可行性。5.3.4算法类问题算法类问题是指那些可以由算法解决的问题。计算学科中有许多著名的算法类问题，如哥尼斯堡七桥问题、旅行商问题等。算法类问题算法类问题求解的第一步是数学建模。数学建模是一种基于数学的思维方式，运用数学的语言和方法，通过抽象和简化建立对实际问题的描述和定义数学模型。将现实世界的问题抽象成数学模型，可以发现其本质以及能否求解，找到求解问题的方法和算法。算法类问题【例5.4】哥尼斯堡七桥问题。寻找走遍这7座桥并最后返回原点且只允许每座桥走过一次的路径。哥尼斯堡七桥问题数学建模：去除哥尼斯堡七桥问题的无关语义，将其抽象成由节点和连接节点的边构成的图哥尼斯堡七桥问题的本质是从任一节点开始，经过每条边一次且仅一次的回路问题。哥尼斯堡七桥问题大数学家欧拉把它转化成“一笔画问题”，推断如下：除了起点以外，当一个人由一座桥（边）进入一块陆地（节点）时，他同时也由另一座桥离开此节点。所以每行经一点时，计算为两座桥（或线），从起点离开的线与最后回到开始点的线也计算两座桥，因此每一个陆地与其他陆地连接的桥数必为偶数。哥尼斯堡七桥问题七桥问题所构成的图中，没有一个节点含有偶数条边，所以哥尼斯堡七桥问题无解。旅行商问题【例5.5】旅行商问题（Travelingsalesmanproblem，TSP）：给定一系列城市和每对城市之间的距离，求解一条最短路径，使得一个旅行商从某个城市出发访问每个城市且只能在每个城市逗留一次，最后回到出发的城市。旅行商问题TSP抽象的数学模型如下：任意两个城市

和

之间的距离为TSP问题的本质是寻找城市的访问顺序旅行商问题采用遍历策略，求出TSP问题中所有可能路经及其总里程，从中选出总里程最短的路径。4个城市的遍历解：222222266655554444333路径：ABCDA距离：12路径：ABDCA距离：14路径：ACBDA距离：18路径：ACDBA距离：14路径：ADBCA距离：14路径：ADCBA距离：12旅行商问题解空间：共有3*2*1=6条可选路经，最短路径为

和

，最短距离为12。旅行商问题遍历策略对于小规模的TSP问题是有效的，但是对于大规模的TSP问题则不可行。n个城市的组合路径数为(n-1)!20个城市组合路径为随着城市数目的增长其组合路径数呈组合爆炸，即组合路径数以阶乘方式急剧增长，以至于无法计算。求解策略，包括贪心算法、分治法、动态规划、启发式算法等旅行商问题贪心算法策略的的基本思想是，一定做出当前状况的最好选择，以免将来后悔。求解TSP问题的贪心算法为：“从一个城市开始，每次选择下一个城市的时候，只考虑当前状况下最好的选择”根据贪心算法的策略，解为路径：

其总距离为14。贪心算法求得的并非最优解，而是可行解。可行解与最优解相比，差距不大，已经足够短。5.3.5算法分析1．算法的正确性算法的正确性是指问题求解的过程、方法是否正确，输出结果是否正确。算法分析2．算法的复杂性（1）算法的时间复杂性如果一个问题的规模为n，算法运行的时间记为T(n)O记法表示算法的时间复杂性求解TSP问题的贪心算法的时间复杂度为

算法分析（2）算法的空间复杂性算法的空间复杂性，指的是算法在执行过程中所占用的存储空间的大小，用S(n)表示。5.4算法设计1966年，Bohra和Jacopini提出：结构化程序设计方法的三种基本结构包括顺序结构、选择结构和循环结构已经证明，用三种基本结构可以组成解决所有编程问题的算法。5.4.1顺序结构顺序结构按照语句的先后顺序执行程序，它是程序设计中最简单的控制结构。顺序结构【例5.6】设计算法，输入三角形的3条边长a、b和c，求三角形的面积。1．分析根据数学知识，在已知三角形的3条边时可以使用海伦公式来求其面积，即顺序结构2．算法设计顺序结构【例5.7】求解鸡兔同笼问题。已知笼子中鸡和兔的头数总共为h，脚数总共为f，问鸡和兔各有多少只？（1）分析。5.4.2选择结构选择结构用于判断给定的条件，根据判断的结果来控制程序的流程。【例5.8】输入a、b值，输出其中较大的数。（1）输入变量a和b。（2）如果a＞b为真，则转入（3），否则转入（4）。（3）输出a，转入（5）。（4）输出b，转入（5）。（5）结束。选择结构【例5.9】输入x，求函数

的值。5.4.3循环结构循环结构是用于实现同一段程序多次执行的一种控制结构。【例5.10】求100!，即1

×

2

×

3

×…

×

100。step1:p=1step2:i=2step3:p=p×istep4:i=i+1step5:如果i<=100，那么转入step3执行step6:输出p，算法结束循环结构【例5.11】输入整数n，求1*2*3*…*n。step0:输入nstep1:p=1step2:i=2step3:p=p*istep4:i=i+1step5:如果i<=n，那么转入step3执行step6:输出p，算法结束循环结构ForNext循环ForNext循环是计数型循环，主要用于循环次数已知的情况，它的本质是当型循环。For<循环变量>=<初值>To<终值>[Step<步长>]<语句序列>[ExitFor]'退出循环Next[循环变量]穷举法穷举法又称枚举法，它的基本思路就是一一列举所有可能性，逐个进行排查。穷举法的核心是找出问题的所有可能，并针对每种可能逐个进行判断，最终找出问题的解。穷举法【例5.12】百钱买百鸡问题。假定公鸡每只2元，母鸡每只3元，小鸡每只0.5元。现有100元，要求买100只鸡，编程求出公鸡只数x、母鸡只数y和小鸡只数z。5.4.4数组数组，也称线性表（linearlist）是一种数据结构，一个数组是n个具有相同特性的数据元素的有限序列。数组的相邻元素之间存在着序偶关系每一个元素实际就是一个变量，可以赋值、输入、输出或参加各种运算。数组数组的处理实际上就是处理数组元素的过程，按顺序对每个数组元素进行处理的过程称为数组的遍历1．搜索在数组中，查找满足条件的所有元素，并求和、计数等。算法设计：遍历数组元素的过程中，判断每个元素是否满足条件，如满足条件则做出处理。【例5.13】一维数组中查找满足条件（元素能被4整除）的所有元素，统计个数、和及其平均值。2．求最大值【例5.14】求一维数组中100个元素的最大值。3．排序排序是最常见的问题，其本质是对一组对象按照某种规则进行有序排列的过程。在计算科学中，排序是许多复杂问题求解的基础。【例5.15】用“起泡法”把一维数组的n个元素按从小到大的顺序排列并输出。排序排序【例5.16】用选择法把一维数组的n个元素按从小到大的顺序排列并输出。排序排序算法的比较：冒泡法排序每轮依次比较两个相邻元素，如果前大后小则交换；而选择法排序则每轮次找到最小值，做一次交换。两种算法的时间复杂度都为。排序快速排序：从序列中任意取出一个元素作为中心，所有比它小的都放在左侧，比它大的都放在右侧，形成左右两个序列；再对各子序列重新选择中心元素依照规则；直到每个子序列只剩下一个元素排序问题的解决方法还有插入排序、桶排序、基数排序、堆排序等。5.5 函数与递归函数是由多条语句组成的能够实现特定功能的程序段，函数可以对程序进行模块化。函数一般包括函数名、参数、返回值和函数体四个部分。函数【例5.17】输入的两个变量，使用函数计算两个变量的和。intsum(intx,inty){ intz; z=x+y; returnz;}main(){ ints,m