计算思维与计算机导论 课件 04-计算机软件的基本思维、05-问题求解、06-计算机网络技术

4计算机软件的基本思维

天津科技大学

计算机基础与信息技术教研部1目录4.1软件系统概述 4.2操作系统

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

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

计算机基础与新技术教研部34目录5.1计算机语言 5.2程序设计基础 5.3算法 5.4算法设计与程序设计5.5函数与递归

5.1计算机语言计算机语言是语法、语义与词汇的集合，它用来表达计算机程序。程序是指某种程序设计语言编制的、计算机能够执行的指令序列，表达的是让计算机求解问题的步骤和方法。计算机语言的发展过程经历了四个阶段：（1）机器语言（2）汇编语言（3）高级语言（4）构件化语言1．机器语言计算机的指令系统是指一组能够识别和执行的二进制和编码表达的指令集合。使用二进制编码的指令编写程序的语言被称为机器语言。2．汇编语言汇编语言使用助记符来代替机器语言的指令码，使机器语言符号化，从而提高编程效率。使用汇编语言的助记符编写的程序称为汇编语言源程序。ADDA,93．高级语言与编译器高级语言是类似于自然语言、以语句和函数为单位书写程序的编程语言。高级语言编写的程序称为高级语言源程序。编译器先使用其编译程序将高级语言源程序转换为汇编语言源程序，再由汇编程序将汇编语言源程序转换为机器可执行的二进制语言程序。4．构件化的语言构件化的语言的每一个构件都是由一系列语句完成的复杂程序，能够完成一定功能。构件化的语言，包括VisualBasic、VisualC++、Delphi，.Net等5．编程语言的分层结构编程语言的分层结构思维，以下层语言为基础，再定义一套能力更强的新语言和编译器。人们使用新语言高效率地编写程序，使用编译器将其编译成下层语言能识别的源程序。编译器将上级语言的源程序一层层向下翻译，直到最终得到机器语言程序，计算机就可以执行程序。6．Java虚拟机Java是一种面向对象的编程语言Java源程序，编译后会生成一种.class文件，称为字节码文件Java虚拟机（JavaVirtualMachine，简称JVM）负责将字节码文件翻译成特定平台下的机器码然后运行。只要在不同平台上安装对应的JVM，就可以运行JAVA字节码文件5.2程序设计基础程序设计的本质：程序设计与计算机的组成有密切关系，程序设计的本质是设计能够利用计算机的5个部件完成特定任务的指令序列。【例5.1】用键盘输入价格与斤数，计算樱桃的总价。price=float(input("输入樱桃价格："))number=float(input("输入樱桃斤数："))total=price*numberprint("总价为",total)2．常量常量指在程序运行过程中值不能改变的量，通常是固定的数值或字符。（1）数值型：40，-40，0，123.456。（2）字符型："Helloworld!"。

3．变量在程序运行过程中，其值可以改变的量称为变量。变量占据内存中的一块存储单元，用来存放数据，存储单元中的数据可以改变。给存储单元起的名字，就是变量名a=84．算术运算符算术运算符的作用是进行算术运算，用算术运算符将运算对象连接起来的表达式称为算术表达式。运算符含义举例a=3，b=4+加a+b值为7-减a-b值为-1*乘a*b值为12/除a/b值为0.75//整除，返回商的整数部分b//a值为1，a//b值为0%求余数（模）a%b值为3**幂，a**b表示a的b次方a**b值为81表5-1Python算术运算符算术运算符数学表达式编写成Python语言表达式

(a+b)**4/(a*(b+c))5．关系运算符关系运算符用于比较两个操作数的关系，用关系运算符连接两个表达式称为关系表达式若关系成立，则表达式值为True，否则为False。运算符运算举例a=3，b=4==当左数与右数相等时，值为True，否则为Falsea==b值False!=当左数与右数不相等时，值为True，否则为Falsea!=b值True>当左数大于右数时，值为True，否则为Falsea>b值False<当左数小于右数时，值为True，否则为Falsea<b值True>=当左数大于或等于右数时，值为True，否则为Falsea>=b值False<=当左数小于或等于右数时，值为True，否则为Falsea<=b值True表5-2Python关系运算符6．逻辑运算符逻辑运算符用于对操作数进行逻辑运算，用逻辑运算符连接关系表达式或逻辑值称为逻辑表达式。逻辑表达式的结果为True或False运算符含义说明举例（a=10）and与（并且）两个操作数都为True时，结果才为True1<=aanda<15值为Trueor或（或者）两个操作数都为False时，结果才为Falsea<=1ora>=20值为Falsenot非（取反）操作数为True，结果为False操作数为False，结果为Truenot(a<4)值为True表5-3Python逻辑运算符7．标准输入Python内置函数input()，接受用户通过键盘输入的字符串input([prompt])【例5.2】标准输入函数。

a=input("请输入字符串：")b=int(input("请输入整数："))c=float(input("请输入浮点数："))print(a,b,c)

8．标准输出Python，标准输出函数print()用于向屏幕输出数据print(value1,value2,...)【例5.3】标准输出函数。

a=123b=456print("a=",a,"b=",b)print("实施科教兴国战略，强化现代化建设人才支撑：")print("办好人民满意的教育；","完善科技创新体系；","加快实施创新驱动发展战略；","深入实施人才强国战略。")5.3算法算法是解决一个问题所采取的一系列步骤。著名的计算机科学家NikiklausWirth提出如下公式：

程序

=

数据结构

+

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

+

2

+

3

+

4

+…+

100。第一种算法是书写“1

+

2

+

3

+

4

+

5

+

6

+…+

100”，不可行第二种算法是利用数学公式，可行

算法举例【例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.7】哥尼斯堡七桥问题。寻找走遍这7座桥并最后返回原点且只允许每座桥走过一次的路径。哥尼斯堡七桥问题数学建模：去除哥尼斯堡七桥问题的无关语义，将其抽象成由节点和连接节点的边构成的图哥尼斯堡七桥问题的本质是从任一节点开始，经过每条边一次且仅一次的回路问题。大数学家欧拉把它转化成“一笔画问题”。哥尼斯堡七桥问题除了起点以外，当一个人由一座桥（边）进入一块陆地（节点）时，他同时也由另一座桥离开此节点。所以每行经一点时，计算为两座桥（或线），从起点离开的线与最后回到开始点的线也计算两座桥，因此每一个陆地与其他陆地连接的桥数必为偶数。哥尼斯堡七桥问题七桥问题所构成的图中，没有一个节点含有偶数条边，所以哥尼斯堡七桥问题无解。旅行商问题【例5.8】旅行商问题（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．算法的正确性算法的正确性是指问题求解的过程、方法是否正确，输出结果是否正确。TSP的贪心算法在可以接受的有限的时间内可以求得可行解，说明算法是正确可行的。算法分析2．算法的复杂性（1）算法的时间复杂性如果一个问题的规模为n，算法运行的时间记为T(n)O记法表示算法的时间复杂性求解TSP问题的贪心算法的时间复杂度为

算法分析（2）算法的空间复杂性算法的空间复杂性，指的是算法在执行过程中所占用的存储空间的大小，用S(n)表示。5.4算法设计与程序设计1966年，Bohra和Jacopini提出：结构化程序设计方法的三种基本结构包括顺序结构、选择结构和循环结构已经证明，用三种基本结构可以组成解决所有编程问题的算法。Python语言是一种跨平台、面向对象的高级程序设计语言5.4.1顺序结构顺序结构按照语句的先后顺序执行程序，它是程序设计中最简单的控制结构。顺序结构【例5.9】设计算法，输入三角形的3条边长a、b和c，求三角形的面积。1．分析根据数学知识，在已知三角形的3条边时可以使用海伦公式来求其面积，即顺序结构2．算法设计顺序结构打开Python的IDLEShell窗口执行“File→NewFile”命令，打开编辑器窗口a=float(input("请输入a："))#输入边长b=float(input("请输入b："))c=float(input("请输入c："))s=(a+b+c)/2

#计算周长的一半sarea=(s*(s-a)*(s-b)*(s-c))**0.5

#计算三角形面积areaprint("三角形面积为",area)#输出面积area单步调试单步调试：（1）在PythonIdle中，执行“Debug→Debugger”菜单命令，打开Debugger调试器（2）程序编辑器“Run→RunModule”命令（3）调试器按下“Over”按钮逐行运行程序，观察变量的变化过程。顺序结构【例5.10】求解鸡兔同笼问题。已知笼子中鸡和兔的头数总共为h，脚数总共为f，问鸡和兔各有多少只？（1）分析。输入h，fx+y=h2x+4y=f输出x,y顺序结构【例5.10】求解鸡兔同笼问题。已知笼子中鸡和兔的头数总共为h，脚数总共为f，问鸡和兔各有多少只？（1）分析。5.4.2选择结构选择结构用于判断给定的条件，根据判断的结果来控制程序的流程。。5.4.2选择结构【例5.11】输入x，求函数的值。选择结构【例5.9】输入x，求函数

的值。分析：（1）首先判定x＜1条件，如果为真则结果为x；否则判定1≤x＜10条件，如果为真则结果为2x

−1；否则结果为。（2）如果x＜1为假，那么在判断第二个条件1≤x<10时，并不需要判断条件1≤x。（3）如果前两个条件都为假，那么第三个条件x>10就一定为真，因此第三个条件可以不做判断。选择结构选择结构【例5.12】输入学生课程成绩mark，给出评分等级。选择结构程序设计if语句结构if条件表达式1:

语句块1[elif条件表达式2:

语句块2

…elif条件表达式n:

语句块n][else:

执行语句块n+1]if语句的运行流程为：（1）先判断表达式1，如果为真则执行语句块1；（2）否则判断下一个表达式，如果为真则执行对应语句块；（3）如果前边的条件都为假，则执行else的语句块。注意：（1）if、elif和else左对齐，不可以缺少冒号。（2）各分支的语句块可以包括一条或多条语句，语句向右缩进左对齐。选择结构程序设计【例5.13】使用Python语言，编写和运行例5.12程序。x=float(input("请输入x:"))ifx<1:

y=xelifx<10:

y=2*x-1else:

y=x**2+2*x+1print("y=",y)提示读者在调试选择结构程序时，需要使用调试器进行单步调试，多次运行程序并输入各分支的数值，观察程序的运行情况，从而分析和判断程序是否正确。5.4.3循环结构循环结构是用于实现同一段程序多次执行的一种控制结构。5.4.3循环结构循环结构是用于实现同一段程序多次执行的一种控制结构。【例5.10】求100!，即1

×

2

×

3

×…

×

100。Step1：p=1。Step2：i=1。Step3：如果i<=100，那么转入Step4执行，否则转入Step7。Step4：p=p×i。Step5：i=i+1。Step6：转到Step3。Step7：输出p，算法结束。循环结构循环结构【例5.11】输入整数n，求1*2*3*…*n。Step0：输入n。Step1：p=1。Step2：i=1。Step3：如果i<=n，那么转入Step4执行，否则转入Step7。Step4：p=p*i。Step5：i=i+1。Step6：转到Step3。Step7：输出p，算法结束。循环结构循环结构while语句用于描述循环结构，书写格式如下：while表达式p:

<循环体语句块>（3）循环体语句如果有多条语句，需要向右缩进左对齐。（4）循环体内的语句块可以是顺序结构、选择结构，也可以是循环结构。

循环结构【例5.16】使用Python语言，编写和运行例5.15程序。n=int(input("请输入n："))i=1s=1whilei<=n:

s=s*i

i=i+1print(n,"!=",s)提示读者在调试循环结构程序时，需要使用调试器进行单步调试，观察程序的循环过程，分析和判断程序是否正确。穷举法穷举法又称枚举法，它的基本思路就是一一列举所有可能性，逐个进行排查。穷举法的核心是找出问题的所有可能，并针对每种可能逐个进行判断，最终找出问题的解。穷举法在算法设计中，如果是已知循环次数的计数型循环，那么可以使用for语句来描述。foriinrange(1,n+1):

<语句序列>

函数range(1,n+1)生成1、2、3、…、n的数字序列。for语句在每次循环时，变量i依次取得数字序列的一个值。穷举法求解n!的问题也可以的算法描述。穷举法【例5.12】百钱买百鸡问题。假定公鸡每只2元，母鸡每只3元，小鸡每只0.5元。现有100元，要求买100只鸡，编程求出公鸡只数x、母鸡只数y和小鸡只数z。穷举法print("公鸡母鸡小鸡")forxinrange(0,51):foryinrange(0,34):forzinrange(0,100):ifx+y+z==100and2*x+3*y+0.5*z==100:print("{:6}{:6}{:6}".format(x,y,z))5.5 函数与递归函数是由多条语句组成的能够实现特定功能的程序段，函数可以对程序进行模块化。函数一般包括函数名、参数、返回值和函数体四个部分def<函数名>([形式参数]):

函数体语句

return[表达式]（1）[形式参数]也称为形参，放在小括号中，可以有0个、1个或多个，形参之间用小括号隔开。（2）函数体语句需要向右缩进左对齐。（3）return语句返回函数的值。函数调用函数定义后就可以被调用。如果函数定义中有形参，在调用时，应该传递实际参数（实参）。<函数名>([<实参表>])函数【例5.18】编写函数计算两个参数之和，输入两个变量，计算并输出其和。defsum(x,y):#函数头部定义

z=x+y#注意缩进

return(z)#函数的返回值a=float(input("输入a:"))b=float(input("输入b:"))c=sum(a,b)

#调用,有实参、返回值print("和为：",c)

5.5.2递归递归是一种重要的计算思维模式，既是抽象表达的一种手段，也是问题求解的重要方法。递归故事：“从前有座山，山里有座庙，庙里有个老和尚在讲故事，故事是（从前有座山，山里有座庙，庙里有个老和尚在讲故事，故事是（从前有座山，山里有座庙，庙里有个老和尚在讲故事，故事是(…）））”递归使用递归的方法绘制的图形递归递归的基本思想：

将一个大规模的复杂问题，层层转换为一个与原问题相同但是规模较小问题来求解，函数调用函数本身、高阶调用低阶。使用递归的方法进行问题求解的基础是构造递归函数。递归【例5.19】用递归算法求n!。分析：观察可知：n!=

n*(n-1)!，(n-1)!=

(n-1)*(n-2)!，…，3!=3*2!，2!=2*1!，1!=1。递归过程两个阶段。（1）回推阶段：n!→(n-1)!→(n-2)!→(n-3)!→…→3!→2!→1!要计算n!，从左向右依次回推，直到求1!=1（2）递推阶段：n!←(n-1)!←(n-2)!←(n-3)!←…←3!←2!←1!求得1!，再从右向左，依次递推，直到求出n!递归（3）假设fact(n)用于计算n的阶乘，则递归函数fact(n)表示为递归deffact(n): #递归函数ifn==0orn==1:return1else:returnn*fact(n-1) #递归调用n=int(input("输入整数n："))t=fact(n)print(n,"!=",t)递归递归调试递归【例5.19】汉诺塔（Hanoi）问题是这样的问题，有3根柱子A、B和C，开始A柱上有64个盘子，从上到下，依次大一点，把所有盘子移到C柱上，要求：盘子必须放在A、B或C柱上，一次只能移动一个盘子，大盘子不能放在小盘子上边。递归分析：3个盘子

7次4个盘子

15次5个盘子

31次6个盘子

63次64个盘子…。经过实验可知，当盘子为n个时，需要2n-1次移动盘子。递归递归过程归纳如下。（1）如果将n个盘子从a，通过b移动到c，计作函数Hanoi(n，a，b，c)。（2）递归函数过程：ifn

=

1then直接从a移动到c，Move(a，c)。ifn>1then将n-1个盘子从a通过c移到b，Hanoi(n-1，a，c，b)，第n个盘子从a移到c，Move(a，c)，再将n-1个盘子从b通过a移到c，Hanoi(n-1，b，a，c)。递归total=0 #移动次数计数defPlateMove(a,c):#盘子从A移动到C

globaltotal

total=total+1#总次数加1

print(total,a,"->",c)#输出移动过程：A移动到C#递归函数，将n个盘子借助B,从A移动到CdefHanoi(n,a,b,c):ifn==1:PlateMove(a,c)#一个盘子时，直接从A移动到Celse:Hanoi(n-1,a,c,b) #将n-1个盘子借助C从A移动到BPlateMove(a,c) #将最后一个盘子从A移动到CHanoi(n-1,b,a,c) #将n-1个盘子借助A从B移动到Cn=int(input("请输入盘子数n:"))Hanoi(n,'A','B','C'); #调用函数，将n个盘子借助B从A移动到C6计算机网络技术天津科技大学计算机基础与新技术教研部116主要内容网络概述网络分类网络体系结构和协议TCP/IP的网络访问层、网络层、传输层、应用层局域网接入Internet信息检索117网络的定义利用通信设备和传输介质，将具有独立功能的计算机连接起来，在软件（操作系统、协议等）的支持下，实现计算机之间的资源共享、信息交换和分布式处理的系统，称为计算机网络（简称网络）118网络的主要功能（1）资源共享：包括软件、硬件和数据资源119网络的主要功能（2）信息交换：指网络节点之间的通信网络的主要功能（3）分布式处理：将一个规模大的任务分配给网络中的若干台计算机并行处理，均衡各计算机的负载，以便人们能在规定的时间内完成任务。网络的发展历史发展历史包括：终端联机系统ARPAnet标准化的网络Internet122半自动地面防空系统（SAGE）网络的发展历史（1）终端联机系统一台主机中安装多用户分时操作系统，按照时间片将CPU分配给各个终端，执行各终端的程序。不是真正意义上的计算机网络。123美国航空公司与IBM公司合作开发的航空订票处理系统SABRE-1，全美范围的2

000多个终端连接网络的发展历史（2）ARPAnet1969年美国国防部高级研究计划管理局（AdvancedResearchProjectsAgency，ARPA）建立的ARPAnet把美国的几个军事及研究用计算机主机连接起来124网络的发展历史（3）标准化的网络在网络通信市场上各自为战的现象不利于网络之间互连互通，也不利于网络的发展和推广ISO成立TC97，制定开放系统互联参考模型（OpenSystemInterconnection，OSI），实现各种计算机网络之间的互连。125网络的发展历史（4）Internet。20世纪80年代开始，Internet将世界各地的各种类型的网络连接起来。126网络分类计算机网络分类方法：网络地理范围网络使用范围网络拓扑结构127从网络地理范围分类1．局域网（LAN）地理范围在几千米之内的网络，如一栋建筑、一所学校、一个厂区等。128特点：（1）覆盖地理范围较小，在相对独立的范围内组网。（2）组网简单，灵活性高，使用方便。从网络地理范围分类2．城域网（MAN）地理范围在几千米到上百千米之内的网络，可以覆盖一个城市或地区，介于局域网和广域网之间129城域网经常作为城市的骨干网，用于连接城市中不同地点的主机、局域网等从网络地理范围分类3．广域网（WAN）地理范围在几百千米到几千千米之内的网络，可以覆盖多个城市，一个或多个国家，通信线路一般由电信运营商提供的网络130特点：（1）覆盖范围广、通信距离远。（2）广域网一般由电信部门或公司负责组建、管理和维护，向社会提供通信服务。从网络使用范围分类公用网（PublicNetwork）由网络服务提供商组建、管理，供公共用户使用的通信网络。如电信、移动、联通、广电等通信网络131从网络使用范围分类2．专用网（PrivateNetwork）由用户部门自己组建、管理的网络，这种网络不向本部门以外的部门和个人提供服务，如军队、铁路、银行、政府等系统网络132虚拟专网VPN用户也可以租用公共通信网络，使用虚拟专用网络技术（VirtualPrivateNetwork，VPN），在VPN管道中进行加密通信，形成专用网，实现安全的远程访问133网络的拓扑结构网络拓扑结构就是指将服务器、工作站等具体设备看成点，将通信线路看成线，将网络抽象成以点和线组成的几何图形结构。网络的拓扑结构，包括：星形结构、总线结构、树形结构、环形结构、全互连结构和不规则形结构134网络的拓扑结构1．星形结构星形结构的网络由一个中心节点S通过点对点链路连接所有从节点组成，任意两个节点之间的通信都必须通过中心节点S完成135优点：组网容易，控制相对简单，单个节点故障影响小，故障容易检测和隔离；缺点：对中心节点的依赖性大网络的拓扑结构2．总线结构总线结构的网络是以一条高速的公共传输介质连接若干节点组成的网络，总线结构的网络结构简单、容易实现、易于扩展。136网络的拓扑结构3．树形结构树形结构的网络采用分层结构将各个节点连接成树形137网络的拓扑结构4．环形结构环形结构的网络中每个节点仅与两侧节点相连，通过通信线路将各节点连接成一个闭合的环路，数据在环路中单向流通时，每个节点都要转发信息。138网络的拓扑结构5．全互连结构全互连结构的网络中每个节点与网络中的其他节点都可通过线路连接5个节点的网络，每个节点都需要4条线路，该网络总共需要10条（即n×(n-1)/2）线路139网络的拓扑结构6．不规则形结构在广域网中，根据节点间的距离、信息的流量，决定在节点间是否建立连接。140网络的拓扑结构141网络体系结构和协议网络协议是指为了使网络中的计算机之间能够正确传输信息而制定的关于信息传输的规则、约定与标准。通信双方必须按照同样的协议发送和接收信息，才能正确地进行数据通信。142网络体系结构网络协议的设计相当复杂，在设计协议时普遍采用层次结构模型，把复杂问题分解为若干简单、易于处理的问题。网络协议设计采用层次结构网络层次结构模型与各层协议的集合称为网络体系结构。国际标准化组织（ISO）制定了OSI参考模型。143OSI开放式系统互联7层结构的模型144OSI网络中各节点（如主机A和主机B）具有相同的层次结构；不同节点的同一层功能相同；同一节点内相邻层之间通过接口通信；每一层均可使用下层提供的服务，并向其上层提供服务；不同节点的同等层通过协议来实现对等层之间的通信。145TCP/IP协议集TCP/IP是Internet的基本协议集，它的两个核心协议是TCP（传输控制协议）和IP（互联网协议）146TCP/IP的网络访问层网络访问层（NetworkAccessLayer）对应OSI的物理层和数据链路层，负责通过网络传输介质发送和接收数据。该层没有定义任何协议，只定义了与不同网络进行连接的接口等。涉及：网络传输介质数据传输与控制硬件设备147网络传输介质传输介质是指在通信中数据传输的载体，是网络中数据发送者和接收者之间的物理路径分为有：有线传输介质无线传输介质148传输速率波特率：在单位时间传输了多少码元，单位时间内载波调制状态改变的次数来表示，单位为波特（Baud）用时间间隔相同的符号来表示数字，这个符号称为码元，每个码元可以表示一个二、八、十或十六进制数149传输速率电磁光谱图，按照从左到右的顺序，低频波、无线电、微波、红外线、可见光，频率越来越高，可以调制的波特率也就越来越高150传输速率比特率：线路中每秒传输的有效二进制位数，称为比特率，其单位是bit/skbit/s、Mbit/s、Gbit/s文件的下载速度MB/S。1MB/s=8Mbit/s100M宽带，指的是100Mbit/s，宽带最大下载速率约为12.5MB/s151有线传输介质有线传输介质包括：双绞线同轴电缆光纤152双绞线由两根具有绝缘保护层的铜导线按一定密度互相绞在一起；一般将多对双绞线一起包在一个绝缘电缆套管里。最大传输速率：4类线10Mbit/s/、100Mbit/s、5类线100Mbit/s、超5类线1000Mbit/s、6类线10

000Mbit/s153双绞线使用双绞线连接交换设备，组建星形网络同轴电缆内芯是单股实心铜线（内导体），外包一层绝缘材料（绝缘层），再外层是由金属屏蔽线组成的网状导体（外导体），具有屏蔽作用，最外层是外部保护层两类：基带同轴电缆（屏蔽层-铜，阻抗50Ω，数字信号）宽带同轴电缆（屏蔽层-铝，阻抗75Ω，模拟信号）。155同轴电缆在网络发展的早期它被广泛用于组建总线结构局域网光纤光纤的中心为一根玻璃或透明塑料制成的光导纤维，周围包裹保护材料根据需要可以将多根光纤合并在一根光缆中家用普通光纤的速率可达10Gbit/s实验室环境中极限速度可达26Tbit/s157无线传输介质无线传输不受固定地理位置限制，可以用于实现移动通信和无线网络。无线传输的介质包括：无线电波红外线激光158无线电波无线电波是指在自由空间（包括空气和真空）中传播的电磁波。两种传播方式：一是电波沿着地表面向四周直接传播；二是靠大气层中的电离层折射进行传播159无线局域网WLAN在室内或室外空间中使用无线电波作为通信介质，使各种可移动的计算机和设备能随时随地接入网络，不需要连接有线介质，从而满足人们移动上网的需要。WLAN主要使用WiFi（WirelessFidelity无线保真）技术2.4GHz的WiFi理论最高带宽为300Mbit/s5GHz的WiFi入门速度433Mbit/s5GHz最高可达1Gbit/s以上160蓝牙蓝牙是一种支持设备间短距离通信（一般10m内）的无线电通信技术，工作在2.4GHz主要用在汽车、移动电话、无线耳机、计算机之间进行短距离通信161蓝牙蓝牙实现手机A和B之间连接的过程①手机A开启蓝牙功能，设定为“对其他蓝牙设备可见”②手机B开启蓝牙功能，设定为“对其他蓝牙设备可见”，搜索到手机A。③手机A和手机B确认配对的密钥，选择配对对方的手机。④手机A和手机B通过蓝牙连接传输文件、照片、音频、视频、电话簿等数据。162红外线红外线是波长介于微波与可见光之间的电磁波，它不能穿透障碍物（如墙壁）红外线通信使用不可见的红外线光源传输数据，广泛用于室内短距离通信。如各种遥控器两种标准：SIR-115.2kbit/sFIR-4Mbit/s。163激光激光在空气或真空中传输数据。激光通信系统的两端都需要发送端和接收端优点：带宽高、容量大、不受电磁干扰、不怕窃听，设备的结构轻便、价格经济。缺点：在空气中的传播衰减快，受天气影响大；激光束有极高的方向性，瞄准困难164激光激光通信主要用于：地面间短距离高速率通信，短距离内传送高清视频信号导弹引导的数据传输，地面间的多路通信卫星进行全球通信和星际通信。TCP/IP协议集166数据传输与控制数据是有意义的实体，涉及事物的形式。如数字、日期。如1234，1981年9月16日

如字符、文字、图表、图像、声音等。信息是数据的内容或解释。如文字、照片描述的内容167信号信号是数据在传输介质上传输时的表示形式，也称为数据的电子编码、电磁编码模拟信号是在一定的数值范围内可以连续取值的信号，是一种连续变化的电信号数字信号是一种离散的脉冲序列，如，以恒定的正电平和0电平分别表示二进制的1和0168数据

编码在数据传输时，发送方需要将数据编码为适合在信道中传输的信号，接收方接收到信号后将其还原为数据。分为：数字信号编码模拟信号编码169数据编码数字信号编码：将二进制数据用不同电平或电压极性表示，形成矩形脉冲信号170数据编码模拟信号编码：将二进制数据转换为模拟信号进行传输的编码方式171差错控制在数据传输过程中，受信道内外的干扰，不可避免地会发生接收数据与发送数据不一致的现象，称为差错。通信系统必须具有检测差错和纠正差错的差错控制功能。172差错控制差错控制的核心是在发送的数据中加入能够在目的地检查或纠正传输差错的冗余编码能自动检测出错误的编码是检错码。常用的有：奇偶校验码循环冗余校验（CRC）码能自动检测并纠正差错的编码是纠错码，数据冗余太高，较少使用。173差错控制奇偶校验码的原理：在7位数据后增加1位，使1的个数为奇数（奇校验）或偶数（偶校验）在目的地，根据1的数目为奇数或偶数，判断传输有无差错。174发送方：数据1001011，奇校验，8位信号是11001011接收方：8位信号是11001010，错1位，确定错误8位信号是11000010，错2位，会误判循环冗余校验码CRC发送方：数据f(x)，r(x)=f(x)/g(x)，发送f(x)+r(x)接收方：接收f2(x)+r2(x)，r‘x=f2(x)/g(x)。如果r2(x)=r‘(x)，则正确，否则出错。175硬件设备TCP/IP的网络访问层（NetworkAccessLayer）工作的常用硬件设备包括：网络适配器交换机176网络适配器网络适配器（NetworkInterfaceCard，NIC）也叫网卡，承担计算机与网络之间交换数据的任务包括：有线网卡无线网卡177网络适配器有线网卡：一般有RJ45、BNC、AUI和光纤接口无线网卡用于连接无线局域网178网络适配器物理地址（MAC地址）是保存在网卡中的全球唯一地址，通常由生产厂烧入网卡的EPROM中。由48bit（6字节）十六进制数组成，如：179E8-9A-8F-F3-20-2D网络适配器在局域网中，可使用广播方式发送数据，通过物理地址来识别主机180交换机交换机能根据发送数据包的源地址和目的地址，接通源端口与目的端口电路，为接入交换机的任意两个网络节点提供独享的信号通路。交换机常见的有10Mbit/s、100Mbit/s、自适应10/100Mbit/s、1000Mbit/s等。181交换机纵横式交换机原理182交换机交换机用于组建星形网络TCP/IP的网络层184TCP/IP的网络层网络层的主要功能是寻址、路由选择和重组，它的核心协议是IPIP是一个无连接协议，在IP数据分组中包括目的地址，IP负责将数据分组从源转发到目的地，主要功能包括寻址、路由选择及重组185

IP地址IP地址是标识计算机在Internet中位置的唯一地址在Internet中，不允许有两台计算机的IP地址相同。IP地址长32bit，分为4字节，每个字节均对应0～255的十进制整数，数字间用“．”隔开例如：正确的：09错误的：2186IP地址的分层结构IP地址采用分层结构管理，包含网络地址：表明主机所在网络的Internet地址，如主机地址：网络中的每一台主机都获得一个主机地址:209187IP地址【例6.2】主机1向主机4发送数据包的传输过程。188特殊IP地址是本机地址，别名：Localhost私有网络地址，如：10.x.x.x172.16.x.x～172.31.x.x192.168.x.x

（解决IP地址资源不足的问题）189Ping命令检测本机到目的IP主机之间的网络是否连通，以及主机之间的连接速率Ping目的主机IP地址或域名190Ping命令Ping命令用于检测本机到目的IP主机之间的网络是否连通，以及主机之间的连接速率。191Ping目的主机IP地址或域名Ping命令向目的主机发送32字节的消息，并计算目的主机的响应时间默认情况下，重复4次，响应时间低于400ms为正常如果返回“RequestTimeout”信息，则说明连接不到目的主机。Ping命令【例6.3】使用Ping命令，测试本计算机的网络连接的TCP/IP配置是否正常。路由器在广域网中进行数据包转发的设备，工作在OSI参考模型的网络层在广域网中，路由器接收并存储数据包，根据信道速率、拥塞等情况自动选择路由，以最佳路径将数据包从源IP地址向目的IP地址转发数据包。193传输层传输层提供源节点到目的节点的两个进程之间可靠的端到端的数据传输TCP/IP的传输层传输层包括：TCP传输控制协议UDP用户数据报协议195TCPTCP是一个可靠的、面向连接的传输层协议，它将源主机的数据以字节流的形式无差错地传送到目的主机。面向有连接一对一数据传输可靠差错控制、超时重传流量控制196TCP建立和断开连接建立连接：三次握手TCP建立和断开连接断开连接：四次挥手TCP常用于要求准确、可靠数据传输的场合：HTTP：网页SMTP：邮件FTP：文件传输Telnet：远程登录UDPUDP是一个不可靠的、无连接的传输层协议不建立连接，不提供端到端的确认重传，接收方不验证不重传单播、多播、广播200UDP常用于高速、可靠性要求不高、网络延迟较小的场合，如：

视频会议、视频直播、流媒体、IP电话等常用于请求/应答式的应用，如：

QQ聊天等TCP/IP的应用层TCP/IP的应用层提供应用程序使用其他层服务的能力，定义了应用程序交换数据的协议（1）HTTP：超文本传输协议（2）SMTP：简单邮件传输协议（3）FTP：文件传输协议（4）DNS：域名系统（5）Telnet：终端仿真远程登录202客户机/服务器工作模式Internet中，几乎所有的服务和功能都以客户机/服务器（Client/Server，C/S）模式。以下过程:（1）客户机向服务器发出服务请求。（2）服务器收到请求后，对请求进行处理（3）服务器将处理结果传送给客户机。203客户机/服务器工作模式【例6.4】QQ登录过程。（1）客户端输入账号和密码，登录，信息传输到服务器。（2）服务器接收登录请求信息，验证账号和密码（3）如果正确，则向客户端返回结果，进入QQ；

否则返回错误结果，提示“密码错误”。204端口号在Internet中，一台拥有IP地址的主机可以提供许多服务，这些服务不能通过同一个IP地址区分。在TCP/IP中，通过“IP地址+端口号”区分不同服务

端口号的范围是：0～65535205端口号知名端口号范围：0～1

023，注册端口号范围：1

024～49

151例如：（1）80：HTTP（TCP）（2）20、21：FTP（TCP）（3）23：Telnet（TCP）（4）25：SMTP（TCP）（5）135：RPC（TCP）（6）4000：QQ端口（UDP）206在实际工作中，可以通过封闭某设备的某些端口号，从而禁止某些服务。端口号一个服务在使用默认的端口号时可以省略端口号，也可以指定其他端口号:80:8080:80207DNS域名数字格式的IP地址难以记忆和识别，DNS使用域名来指向IP地址。域名采用层次型树状结构：

主机域名.机构域名.地理域名

208DNS域名域名层次型树状结构中文域名，如：.中国，.集团，.在线，.政务，.公益209DNS域名顶级域名210域名含义

域名含义com商业机构org非商业或教育的其他机构net网络机构int国际组织gov政府机构cn中国edu教育机构ca加拿大mil非保密军事机构au澳大利亚域名的解析一个域名指向一个IP地址，域名系统（DNS）负责管理域名与IP地址之间的对应关系。对应域名的分层结构，每一级域名都有对应的DNS服务器，保存域名与IP地址的映射表211DNS域名【例6.5】使用Ping命令，测试域名对应的IP地址212WWW服务WorldWideWeb（WWW），万维网，是Internet的一种信息服务方式，WWW服务的资源由许多Web页构成基础协议：超文本传输协议（HypertextTransferProtocol，HTTP）213超文本标记语言HTML超文本文件是指在文本文件中加入图片、声音等多媒体信息，通过超级链接指向其他资源。HTML（HyperTextMarkupLanguage，超文本标记语言）通过标记符号来标记网页的各个部分214HTML常用标记标记意义举例<html>…</html>定义HTML文档

<head>…</head>定义HTML头部

<body>…</body>HTML主体标记

<p>…</p>分段

<br>换行

<hr>画水平线

<b>…</b>粗体字显示<b>第一个网页</b><hn>…</hn>n级标题显示<h2>第一个网页</h2><font>…</font>字体<fontface="楷体_GB2312"size=6color="red"><imgsrc="…">加载图片<imgsrc="ABC.jpeg"><ahref="…">超级链接<ahref=""><table>…</table>用于定义表格

<tr>…</tr>定义表格行

<td>…</td>定义单元格

215HTML举例【例6.6】使用文本编辑器编写代码，保存为eg0607.htm216<html><head><title>例子网页</title></head><body><h3>第一个网页</h2><hr><p><font

face="楷体_GB2312"

size=4

color="red">第一个例子</font></p><table

border="1"

width="100%"><tr><td>链接</td><td>内容</td></tr><tr><td>文字</td><td><a

href="02.htm">超级链接</a></td></tr><tr><td>图片</td><td><img

border="0"

src="ding.jpg"

width="84"

height="84"></td></tr></table></body></html>网页访问过程网页保存在Web服务器上安装的Web服务程序（如IIS、Apache）指定的文件夹下217URL地址全球统一资源定位（URL）是Internet上所有资源统一且唯一的地址定位方法。URL地址包括：资源类型（http、Telnet、mailto、E-mail、News）存放资源的主机域名或IP地址资源文件名三部分组成218电子邮件（E-Mail）电子邮件（E-mail）是一种快捷、简单、廉价的通信手段，它是应用广泛的Internet基本服务发信人将电子邮件发送到邮件服务器，放在收信人的邮箱中，收信人可以随时上网读取电子邮件。电子邮件不仅可以传输文字，还可以附上图像、声音、程序等附件。219电子邮件电子信箱是在邮件服务器中申请的账号，它是电子邮件地址的唯一标志。电子信箱格式：naj@ccbs2011@使用电子信箱时还需要拥有密码220用户名@邮件服务器域名电子邮件电子邮件的工作过程221电子邮件查看和发送邮件通过Web浏览器邮件客户端，如foxmail，邮箱大师、Outlook等222FTP文件传输协议（FileTransferProtocol，FTP）用于在Internet中进行文件传输。