计算思维案例及平时成绩讨论题.doc

《计算思维案例及平时成绩讨论题.doc》由会员分享，可在线阅读，更多相关《计算思维案例及平时成绩讨论题.doc（17页珍藏版）》请在三一办公上搜索。

1、1.5本章计算思维的典型案例案例1：计算作为人类文明的开端，从最远古的手指计数到中国古代的算盘计算到近代西方的纳皮尔算筹及帕斯卡机械式计算机，至当前的电子计算机的高速度计算，不管是计算方法还是计算工具都有了变革性的创新，计算也作为一种思维方式存在，并成为人类科学思维的重要一员。从算盘到计算机的发展过程是计算思维内容不断拓展的过程。现今，我们面临着一个问题：计算机能不能再快些？我们还能不能依靠单一的电子器件加快我们的“大脑”？从历史来看，机械到电子不但是材料的进步，也是思维方式的进步。计算机发展，归根结底是计算思维的传承和发扬光大。计算机的历史就像一个孩子的成长史，它已经经历了少年时期的疯长，进

2、入了青年时期。它还会有下一轮的飞速成长，但是要靠人类的智慧作为营养哺育它。在不久的将来，我们会将计算机变成一个众多学科交叉结合而成的精灵。而到那时，我们相信那个精灵传承和发扬的仍然是计算思维。案例2： 抽象就是忽略一个主题中与当前问题(或目标)无关的那些方面，以便更充分地注意与当前问题(或目标)有关的方面。通过抽象，人们可以从众多的事物中抽取出共同的、本质性的特征，舍弃其非本质的特征。抽象是一种从个体把握一般、从现象把握本质的认知过程和思维方法。在本章中介绍了图灵机模型，它是一个抽象的计算模型。图灵把他的计算模型抽象成一种非常精简的装置：一条无限长的纸带、一个读写头、一套控制读写头工作的规则、

3、一个状态寄存器。有了图灵机这一抽象模型，我们可以得到很多本质的规律，通过抽象我们能够抽取事物的本质特性、忽略烦琐的细节，在抽象的模型上进行科学研究，有助于发现事物的内在规律。虽然图灵机是现代计算机的数学模型，但它不等同于实际的计算机，如何设计实际可用的计算机系统，也需要抽象的思维。在第3章中介绍的冯诺依曼体系结构就是对现代计算机体系结构的一种抽象认识。本章小结与思考本章通过对计算技术的发展起到关键作用的人物和事件的介绍，回顾了计算机的发展简史。从计算机的起源开始，介绍计算机系统的发展历程及未来可能的发展趋势。介绍了科学技术的发展特别是电子器件的发展在计算机发展中的重要作用。了解了计算机的“存储

4、程序方式”和采用二进制思想。计算机是20世纪最伟大的发明之一。计算技术从简单到复杂，经历了漫长的发展过程，但最近20余年却取得了飞速的进展。这里面蕴含了其自身的规律性，值得深刻领悟。计算机及计算机网络的应用己使人类社会的各个领域都发生了翻天覆地的变化，计算和计算机的应用己经无处不在。信息作为继物质和能源之后的第三类资源，它的价值日益受到人们的重视。在计算机渗透到社会各行各业的今天，每一名大学生都应该接受信息技术教育，应该具有“获取信息、分析信息、加工信息”的基础知识和实际能力。计算思维是运用计算机科学的基础概念去求解问题、设计系统和理解人类的行为，它包括了涵盖计算机科学之广度的一系列思维活动。

5、计算思维的本质是抽象和自动化。计算思维代表着一种普遍的认识和一类普适的技能，因此每个人都应热心于计算思维的学习和应用。计算机作为一种工具，既然为人类所广泛使用，它必将对人类的思维产生影响。计算机赖以运行的思想和方法也将从后台进入前台，走进人类的生活，成为人类工作和生活有力助手。如同所有其他学科一样，计算学科也有自己的认识和处理世界事物的方法学。未来，计算思维必将随着计算学科的发展而不断丰富和完善。学习完本章后，请思考并讨论以下提出的几个问题：1你认为一个学生应具有什么样的信息素养，才能在未来的职业生涯中具有较强的竞争力？这些竞争力体现在哪些方面？2结合你所学的专业谈谈计算思维对本学科研究领域的

6、影响和应用。3新一代计算机的发展趋势是什么？谈谈你对未来计算机发展及应用的看法。2.4本章计算思维的典型案例案例1： 现实世界可以表示为0 和1用0 和1 可进行逻辑与算术运算0 和1 可以用电子技术实现用二极管、三极管等实现基本门电路组合逻辑电路实现芯片（复杂组合逻辑电路）。具体来说，0 和1 的思维蕴含着：信息表示。数值信息和非数值信息均可用0 和1 表示，均能够被计算；符号化数字化。物理世界/语义信息符号化0和1（进位制与编码）数字计算（算术运算，逻辑运算）硬件与软件实现。即任何事物只要能表示成信息，也就能够表示成0 和1，也就能够被计算，也就能够被计算机所处理。案例2：递归是计算思维的

7、方法之一。当我们通过键盘将字母“A”输入到计算机，在计算机内部它将以二进制代码形式存储，但从显示器或打印机输出的依然是字母“A”,由此体现了一种递归的方式。究竟什么是递归呢？其实，递归就是大鱼吃小鱼，就是一条蛇咬住自己的尾巴。递归是指一样东西自己包含了自己。例如，当两面镜子相互之间近似平行时，镜中嵌套的图像是以无限递归的形式出现的。递归在数学与计算机科学中，是指在函数的定义中使用函数自身的方法。递归一词还较常用于描述用相似方法重复事物的过程。案例3：当数据被储存在硬盘或传送到网络上时，它们一般是不会发生改变的不过，有时候一些故障也会导致数据值突然改变，比如电子干扰。而避免这类事件的发生至关重要

8、。利用类似奇偶校验的方法，可以保护计算机中几乎所有的数据。数据硬盘、CD、DVD、闪存、网络下载、电子邮件和网页都在数据中添加了你看不到的校验码。一旦系统中个别比特发生错误，计算机就会在你不知情的情况下自动恢复原始数据。这充分体现了计算思维是按照预防、保护及通过冗余、容错、纠错的方式，并从最坏情况进行系统恢复的一种思维方法。奇偶校验是一种校验代码传输正确性的方法。根据被传输的一组二进制代码的数位中“1”的个数是奇数或偶数来进行校验。采用奇数的称为奇校验，反之，称为偶校验。采用何种校验是事先规定好的。通常专门设置一个奇偶校验位，用它使这组代码中“1”的个数为奇数或偶数。若用奇校验，则当接收端收到

9、这组代码时，校验“1”的个数是否为奇数，从而确定传输代码的正确性。在本章中，介绍了ASCII码为7位编码，占1个字节，空出来的最高位通常为0。但在需要传输数据时可以用作奇偶校验的校验位。例如偶校验时，若7位ASCII码中“1”的个数为偶数，则校验位置为“0”；若7位ASCII码中“1”的个数为奇数，则校验位置为“1”。这样就可以保证传送数据满足偶校验的要求。在接收方收到数据时，将按照奇校验的要求检测数据中“1”的个数，如果是偶数，表示传送正确，否则表示传送错误。奇偶校验位是最简单的错误检测码。案例4：对中国汉字的信息处理就是一种典型的计算思维应用，蕴含了构造原理。计算机是西方人发明的，他们用了

10、近40年的时间发展了一整套技术来实现对西文的处理。而汉字是一种象形文字，字种繁多，字形复杂，汉字的信息处理与通用的西方简单的字母数字类信息处理有很大差异，一度成为棘手问题。然而，近几十年来，汉字信息处理研究得到飞跃式的发展。这其中，让计算机能表示并处理汉字要解决的首要的问题就是要对汉字进行编码，即确定每个汉字同一组通用代码集合的对应关系。这样，在输入设备通过输入法接收汉字信息后，即按对应关系将其转换为可由一般计算机处理的通用字符代码，然后再利用传统计算机的信息处理技术对这些代码信息的组合进行处理，如信息的比较、分类合并、检索、存储、传输和交换等。处理后的代码组合，再通过汉字输出设备，按照同样的

11、对应关系转换为汉字字形库的相应字形序号，输出设备将处理后的汉字信息直观地显示或打印出来。本章小结与思考本章主要介绍了计算机基本信息表示方法，所谓基本信息，是指数值信息和字符信息。其中二进制的概念是十分重要的，因为二进制是计算机信息表示的基础，在计算机内部的底层，任何类型的信息都用二进制编码，还因为在计算领域，很多术语直接与二进制相联系，不懂得二进制，就不能很好理解这些术语。同一个数可以用不同的进制表示，不同进制表示之间存在等价关系，利用这个等价关系可以在不同的进制之间进行转换。针对数值的二进制表示，还介绍了如何采用原码、反码和补码的方法解决了带符号数值的处理，以及带小数点的实数表示方法。掌握这

12、些知识对于理解计算机的运算过程非常重要。计算机之所以具有逻辑处理能力，是因为计算机中采用了实现各种逻辑功能的电路，这些逻辑电路是由能够实现与、或、非等逻辑运算的基本电路组成的。而逻辑代数是进行逻辑电路设计的数学基础。通过组合基本的逻辑电路，可以设计出非常复杂的组合逻辑电路，用于构建计算机系统。了解计算机信息数据的编码对于计算机信息处理具有很大的帮助。由于计算机是以二进制方式组织、存放信息的，这就意味着所有需要计算机存储并处理的信息包括都要转换成二进制的形式来表示。因此，信息编码就是指对输入到计算机中的各种数值和非数值型数据用二进制数进行编码的方式。对于不同机器、不同类型的数据其编码方式是不同的

13、，编码的方法也很多。本章主要介绍了常用编码的国家标准或国际标准，如ASCII码、汉字编码等，包括计算机使用这些编码在计算机内部和外部设备之间以及计算机之间是如何进行信息交换的。 学习完本章后，请思考并讨论以下提出的几个问题：1假设有两支友邻军队夜间在一条河的两岸并行行军。为了保持行动一致，他们必须进行通信。双方预先确定了53条通信密语。两支军队都没有带通信设备，但带了至少8支手电筒。请为他们设计一种通信方案。2举例说明身边的某一编码，说说其编码方式、规则与取值范围，写出自己的看法与认识。3对下列ASCII码进行译码。 01001110 01101001 01101000 01100001 01

14、101111 00100001 01001010 01101001 01100001 01111001 01101111 01110101 001000014对于下面一组不同编码的数，请按照从小到大的顺序排列。 (+01110)原 (01101)补 (10110)反 (10000)反 (10110)原 (10010)补3.7 本章计算思维的典型案例案例1： 在计算机科学中，抽象是一种被广泛使用的计算思维方法。在本章中介绍的冯诺依曼体系结构就是对现代计算机体系结构的一种抽象认识。在冯诺依曼体系结构中，计算机由内存、处理单元、控制单元、输入设备和输出设备等五部分组成。这一体系结构屏蔽了实现上的诸多

15、细节，明确了现代计算应该具备的重要组成部分及各部分之间的关系，是计算机系统的抽象模型，为现代计算机的研制奠定了基础。案例2： 并行是一种重要的计算思维方法。并行计算一般是指许多指令得以同时进行的计算模式。我们在计算机系统的设计中看到了很多运用并行技术提高系统效率的例子，例如，本章介绍的“多核处理器”技术，是从空间的角度，通过硬件的冗余，让不同的处理器并发执行不同的任务。该种技术体现了运用并行方法解决问题的思路。在日常生活中也不乏并行思维的例子。在高速公路收费站服务中也可以经常见到并行。在车流量多的高峰时段，收费站可以通过增加一些通行通道提高服务的并行度，从而提高服务能力，减少车辆通行的等待时间

16、；而在车流量较少的时候，会通过关闭一些通道降低服务的并行度，在保证通行速度的同时减少高速公路收费站自身的运营成本。案例3： 缓存也是一种重要的计算思维方法。缓存是将未来可能会被用到的数据存放在高效存储区域中，使得将来用到这些数据时能够非常快地得到。在计算机系统中有一个重要的原理，即程序的局部性原理。程序的局部性原理有两方面的含义：时间局部性和空间局部性。时间局部性是指，如果一个信息项正在被访问，那么近期它很可能还会被再次访问；空间局部性是指，在最近的将来将用到的信息很可能与现在正在使用的信息在空间地址上是临近的。因此，在时间和空间上，程序总是趋向于使用最近使用过的数据和指令，其访问行为不是随机

17、的，而是相对集中的。CPU访问存储器，无论存取指令还是存取数据，所访问的存储单元都趋于聚集在一个较小的连续区域中。根据这一原理，计算机系统中采取了层次性的存储体系，包括高速缓存、内存储器、外存储器等。高速缓存的访问速度最快、容量最小、成本最高，外存储器的访问速度最慢、容量最大、成本最低。计算机系统充分利用了局部性原理，提高系统在缓存中命中数据的可能性，从而以较多的低速大容量存储器、配合较少的高速缓存，得到速度和高速存储器差别不大的大容量存储器，在存储容量、速度和成本上获得了较好的平衡。在我们的工作和生活中也存在有缓存思维的例子。例如，学生上学在书包中通常只放上当天上课需要的书本，而不需要把所有

18、书本都带上；我们的办公桌上总是放上最常用或刚刚看到过的书，而长时间不用的书都转移到书架上，这些都是通过缓存和预取提高效率的例子。案例4：以键盘输入与屏幕显示为例可以感受“信息处理的思维”，即：位置电信号编码存取/ASCII解码字形显示。理解和掌握这一思维之后，可以很容易地推广至其他语言文字的处理，如汉字等。更进一步，这一例子蕴含着一种普适的思维信息处理思维，即：物理对象通过采集设备采集相关信息(物理信息映射)，然后按一定的编码规则使用编码器进行编码及存储，再按编码规则使用解码器进行解码，识别所需信息并进行显示。本章小结与思考本章介绍了计算机中硬件的基本常识。首先从总体上介绍了其构成和各部分的作

19、用，以及构成的依据一一冯诺依曼体系结构。此后，以我们最熟悉的微型计算机为切入占，介绍了CPU的工作过程、主板的特性。接着，介绍了存储系统，存储系统的设计原则和工作原理。然后，介绍了连接计算机硬件系统各分系统的通路总线，以及连接主机和外部设备之间的部件接口。另外，还介绍了常用的外部存储设备，如硬盘、光盘，以及常用的输入输出设备。最后，介绍了简要地介绍了计算机指令系统。通过本章学习，应建立起计算机系统的全貌，并对各组成部分的构成和工作原理有一定的认识和理解。应能从总体上理解一个程序经过外部输入、CPU处理，最后输出结果的整个流程所涉及的硬件及其工作原理。学习完本章后，请思考并讨论以下提出的几个问题

20、：1解释硬盘分区的类别及特点，如果有一个新硬盘你将如何分区。2在当地的电脑销售商处收集一些不同品牌、不同配置电脑的宣传单，对收集到的资料按高、中、低档次分别配置一台电脑，列出相关的配置参数。3谈谈通过哪些方法可以提高计算机的速度。4简述内存与外存的关系。4.9 本章计算思维的典型案例案例1： 从裸机到虚拟机是一个用计算思维解决自身问题的典型案例。一台裸机通过加装软件(操作系统)，并由软件提供与用户的接口，直到用户通过接口使用这台计算机，是将一台复杂的、几乎不能使用的系统变成使用简单、功能强大的系统。整个过程拥有极其丰富的计算思维活动。同样，以分时操作系统为例。分时操作系统是指在一台主机上连接多

21、个带有显示器和键盘的终端，同时允许多个用户通过主机的终端，以交互方式使用计算机，共享主机中的资源。分时操作系统是一个多用户交互式操作系统。分时操作系统将CPU的时间划分成若干个片段，称为时间片。操作系统以时间片为单位，轮流为每个终端用户服务。每个用户轮流使用一个时间片而使每个用户并不感到有别的用户存在。宏观上看是多个人同时使用一个CPU，微观上是多个人在不同时刻轮流使用CPU。这种时间片轮转思想就是一个古老的、最简单、最公平的思想，它既解决了计算机自身的问题，又能解决实际的问题。案例2：操作系统的产生和使用，其本身就充分体现了运用计算思维抽象和分解的方法。计算机硬件经冯诺依曼阐述后，划分为五大

22、模块或称计算机的五大组成部分。而操作系统诞生及其所提供的四大功能，即进程管理、内存管理、文件管理、设备管理则是对硬件的五大模块所涉及的庞大而复杂的工作进行有效的控制和管理。操作系统架起了硬件与用户之间沟通的桥梁。案例3：操作系统对进程的管理采用了多道程序并行处理的方式。宏观上多个程序同时执行，微观上各程序轮流占用CPU，交替执行，即串行，这就大大提高了系统的资源利用率。这是将计算思维中使用并行方法解决问题的思路运用到操作系统设计的一个典型实例。案例4：内存管理，是指软件运行时对计算机内存资源的分配和使用的技术。其最主要的目的是如何高效，快速的分配，并且在适当的时候释放和回收内存资源。虚拟内存是

23、内存管理技术的一个极其实用的创新，当进程建立时，不需要在物理内存件之间搬移数据，数据储存于磁盘内的虚拟内存空间，也不需要为该进程去配置主内存空间，只有当该进程被被调用的时候才会被加载到主内存。可以想像一个很大的程序，当他执行时被操作系统调用，其运行需要的内存数据都被存到磁盘内的虚拟内存，只有需要用到的部分才被加载到主内存内部运行。内存管理的设计所用到的预置和缓存技术也是一种重要的计算思维方法。案例5：文件管理是操作系统中一项重要的功能。其重要性在于，在现代计算机系统中，用户的程序和数据，操作系统自身的程序和数据，甚至各种输出输入设备，都是以文件形式出现在操作系统的管理者和用户面前。文件管理是对

24、文件存储器的存储空间进行组织、分配和回收，负责文件的存储、检索、共享和保护。从用户角度来看，文件管理主要是实现“按名取存”，用户只要知道所需文件的文件名，就可存取文件中的信息，而无需知道这些文件究竟存放在什么地方。文件管理的设计运用了存储、检索、共享、保护等多种计算思维的方法，从而实现对信息的有效管理和快速存取。案例5：操作系统对设备的管理就是如何有效合理地使用这些设备。设备管理的功能之一是缓冲管理，即为达到缓解CPU和I/O设备速度不匹配的矛盾，达到提高CPU和I/O设备利用率，提高系统吞吐量的目的，许多操作系统通过设置缓冲区的办法来实现。在缓冲管理方面所用到的缓存技术是计算思维的一种重要的

25、方法。设备驱动程序是设备管理的重要组成部分。是一种可以使计算机和设备通信的特殊程序，可以 说相当于硬件的接口，操作系统只有通过这个接口，才能控制硬件设备的工作，假如某设备的驱动程序未能正确安装，便不能正常工作。 而计算机中的设备种类繁多，千差万别。所以编写设备驱动程序就要充分采取抽象、化简、统一的计算思维方法，尽可能实现驱动程序的通用性及程序与设备的无关性。本章小结与思考(待定)本章从操作系统是计算机系统管理者的角度，依次介绍了进程管理、存储管理、文件管理、设备管理和用户接口等内容。在这些内容的介绍中，重点介绍了各项管理功能所针对的对象、采用何种管理策略，即管理谁、怎么管的问题，进一步探讨了这

26、些管理功能是如何支持程序运行的问题。操作系统是计算机系统的管控中心，它管理计算机系统的所有资源，用户通过操作系统才能间接对计算机进行操作。程序是实现特定操作的指令集合。执行的程序被称为进程。进程是“活”着的程序，有其三命周期和活动规律。进程管理涉及进程创建、调度、资源分配、运行等一系列操作。文件是计算机中信息管理的基本单位。计算机中所有信息(包括操作系统本身都是以文的形式存在的。对计算机的操作实际上是对文件的操作。为了实现对文件的管理，系统内部设置了文件目录、文件分配表等组织结构。用户通过文件目录树结构对文件进行操作。文件因数量巨大所以被组织存放在硬盘中。文件名是文件存放在计算机中的唯一标识符

27、，文件名包括文件主名、文件扩展名和文件路径。文件操作包括创建、修改、复制、删除、重命名、共享、隐藏等。现代计算机系统中包含的外部设备越来越多，处理标准配置的设备鼠标、键盘、显示器)外，还包括许多非标配设备(移动硬盘、U盘、打印机、扫描仪等)。设备管理的任务除了保证这些外部设备本身处于正常的工作状态外，还要保证I/O控制器、通道、设备与CPU之间的信息通信和数据传输、各种设备的排队管理、各种设备的I/O操作等。存储管理的主要任务是存储分配、地址重定位、存储保护和存储扩充等。所有程序和数据一般是存放在外存中，执行时才调入内存，这就关系到存储器的分配和管理:程序本身的数据和代码是按逻辑地址存放的，运

28、行时是在物理地址空间，这就涉及地址空间的变换(地址重位);为了解决实际应用中在较小的实存空间中运行大程序的问题，存储管理中引入虚拟存储技术，即将部分外存空间开辟出来作为内存空间的补充，采用软、硬件技术结合的方式，实在的虚拟存储空间和较小的实存储空间的转换。用户接口是用户操作计算机的界面。用户接口包括命令方式、系统调用方式和图形窗式等操作界面。通过本章的学习，应从总体上对操作系统有一个整体认识。在学习中，要弄清楚计算机系统软硬件是如何配合起来支持程序运行的，要分清楚哪些支持由硬件提供，哪些由软件提供，它们是如何协调一致构成一个整体的。学习完本章后，请思考并讨论以下提出的几个问题：1为什么要使用操

29、作系统平台?而不是让用户直接面对裸机?2计算机系统为什么要组织成层次结构?它的实质是什么? 3同样是设计和开发程序，操作系统的设计和开发者的工作与应用程序员有什么不同?为什么?4你对操作系统和用户程序之间的关系有何看法?阐述你的视角。5有人说设备管理软件(设备驱动程序)因为经常由第三方提供，因此不应该作为操作系统的一部分，你对此有何看法? 驱动程序的作用是什么?为什么必须为外设安装驱动程序? 什么是设备无关性?为什么要在设备管理中引人设备无关性?5.6本章计算思维的典型案例案例1：计算思维反映的是利用计算机技术解决实际问题的思维方法，如果对利用计算机技术如何解决实际问题的认知出现误解，那是不可

30、能达到目的的。很多初学者以为计算机神乎其神，似乎什么都能干，所以就想当然起来。例如，某同学刚学了几天C语言程序设计，想试试自己的能力，找一道求方程3x2+5x-15=0的根的题目。用C语言写出下述的程序段： float x; /*定义变量*/3*x*x+5*x-15=0; /*给出方程，让计算机求解*/printf(“%f”,x); /*输出结果*/结果上机一试，才发现错误一大堆，根本不可能得到想要的解。该同学实在想不明白的是：计算机不是很神吗？怎么这么简单一个方程都不能求解？恐怕大多数人刚开始都和该同学一样，都有这样的疑问。事实上，计算机确实不能求解上述方程，至少目前基本如此(第四代问题描述

31、语言例外)。确切地说，计算机只会帮我们“计算”，至于如何计算那就是我们的事情了。就本例而言，如果我们自己都不知道如何求解此方程，那也就别指望计算机帮我们求解它。换句话说，我们得告诉计算机如何一步一步地去求解此方程，然后计算机按照我们的计算要求帮我们一步一步地去计算。只有很好地理解了这样的“计算思维”，我们才能写出下面的程序段：float x1 , x2, d; /*定义变量*/d=5 * 5-4 * 3 * (-15);x1 = (-5 + sqrt(d)/(2 * 3); /*求根公式*/x2 = (-5 - sqrt(d)/(2 * 3); /*求根公式*/printf(“%f”, %f”

32、, x1, x2); /*输出结果*/通过这个例子，大家应该明白计算机并不是你想象的那么“智能”。和人脑相比，它只是会算，而且算的速度非常快，除此以外计算机几乎没有什么更多的优越性了。如果你要完成的计算任务比较复杂，又不能(或者不会)分解成计算机能接受的基本操作，那就没法利用计算机求解了。记住，计算机永远都是在人脑的指挥下工作的！案例2： 在计算机科学中，将大规模的复杂问题分解成若干个较小规模的、更简单的问题加以解决，是一种常用的计算思维。运用问题分解这种思维方法进行问题求解，首先需对问题本身做出明确描述，并对问题解法做出全局性决策，把问题分解成相对独立的子问题，再以同样的方式对每个子问题进一

33、步精确化，直到获得对问题的明确的解答。在本章中，结构化程序设计采取了计算思维中的典型方法分解。按照“分而治之”的策略，将顶层问题的求解目标逐层分解成子目标，每个子目标用相应的程序模块进行实现，这样构成求解整个问题的程序。结构化程序设计方法的一个重要原则就是“自顶向下、逐步求精”，它是指程序设计时，先描述顶层问题的求解目标，然后步步深入，设计一些比较粗略的子目标作为过渡，再逐层细分，直到整个问题可用程序设计语言明确地描述出来为止。程序的模块化设计，则是针对任何一个大系统都可以按子结构之间的疏密程度分解成较小的模块，每个模块完成一定问题的求解。整个程序是由层次的、逐级细化的诸模块组成。一个复杂的问

34、题可以看成由若干稍简单的问题构成。对于可以用计算机求解的问题，所需的计算时间都与其规模有关，问题规模越小，解题所需的计算时间也越少，也越容易求解。因此，可以将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破、分而治之。模块化与自顶可下、逐步求精紧密联系。日常工作中的层次化管理也是一种对分解方法的运用。以企业运行为例，一个大型企业也是一个非常复杂的系统，采取“金字塔”型的管理层次是一种常用的策略，将企业逐层分解，越上层的机构越少，越向下功能分解越细、机构数目越多。各级机构管理好自己的下属机构，完成上级机构制定的目标，最终整个企业实现自己的整体目标。案例3：计算思维是利用海量数

35、据来加快计算，在时间和空间之间、在处理能力和存储容量之间进行折中的思维方法。计算机问题求解是以计算机为工具，利用计算思维解决问题的实践活动。计算机解题的核心是算法设计，设计算法是计算机问题求解中非常重要的步骤。查找(Searching)也称检索，计算机最重要的功能之一就是在浩瀚的数据中找到用户所要的信息。但是计算机的速度还并没有快到能瞬间完成这一过程的程度，而且等待计算机查找的数据集往往是异常庞大的，因此我们需要更快捷更有效的搜索方式。世界上最庞大的搜索问题是在网络世界中搜索信息，网络搜索引擎能实现同时为大量在线用户在数以百万计的网页中进行高速查询，这无疑是一个令人惊讶的事实，而它们能做到这点

36、无非是因为使用了正确的算法。查找的结果有两种：一种是查找到满足条件的结点，称为查找成功；否则称为查找失败。查找的方法很多，下面介绍两种针对线性表的查找算法。 顺序查找顺序查找是最简单的查找算法。计算机运行速度很快，你或许认为当计算机进行搜索时，应该从储存数据的开头开始找，直到找到指定数据时结束查找，这种方式称线性搜索，然而，这种算法对计算机来说是非常慢的。 折半查找如果所有待查的数据元素按关键字递增(或递减)有序，则可以采用折半查找也称为二分查找，它是一种效率较高的线性表查找算法。折半查找的基本思想是：先取表的中间位置的结点关键字与所给定的关键字进行比较，如果相等，则查找成功。如果给定值比该结

37、点的关键字大，则所找结点在表的后半部分；否则所找结点在表的前半部分，然后再把选定的部分表的中间结点的关键字与给定关键字进行比较。如此反复进行，直到查找成功或者查找失败为止。使用折半查找要比顺序查找效率高很多，只用检查队列的中间项就可锁定搜索关键词位于哪一半队列，这样一来，每查找一次相当于将待查找的目标数量减少一半。以查找超市商品为例(假设商品是按编号从小到大排序)，如果采用折半查找方式在10000件货品中查找，仅须用到14次搜索。值得注意的是折半查找效率虽然较高，但必须先将待查数据进行排序。这是折半查方法的前提条件或代价。下面例子显示了查找成功和查找失败的过程，给定线性表的各结点的关键字为05

38、，13，17，42，46，55，60，94。查找关键字为k=55的结点，查找过程如下：05 13 17 42 46 55 60 94 第1次 05 13 17 42 46 55 60 94 第2次，查找成功 查找关键字为k=12的结点，查找过程如下：05 13 17 42 46 55 60 94 第1次 05 13 17 42 46 55 60 94 第2次 05 13 17 42 46 55 60 94 第3次 05 13 17 42 46 55 60 94 第4次，查找失败案例4：排序(Sort)是数据处理中的一种重要运算，它的功能是将一组数据元素(或记录)从任意序列排列成一个按关键字排序

39、的序列。这是一种常用的计算思维方法。几乎所有计算机中的序列都是被排过序的，电子邮件列表按照日期排序，最新的邮件被放置在最顶端；播放器中的歌曲按照名字或歌手名排列在一起，以便你快速查找到最喜欢的那首歌，文件名则往往是按照字母顺序排列的。那么计算机是如何进行排序的呢？计算机科学家设计了很多排序的算法，这里介绍两种简单有效的排序算法。 直接插入排序直接插入排序是最简单的排序方法，适用于记录个数较少的场合。其算法的基本思想是：逐个处理待排序列中的记录，将其与前面已经排好序的子序列中的记录按关键字比较，确定要插入的位置，并将记录插入到子序列中。具体做法如下：开始时，把第一个记录看成是已经排好序的子序列，

40、这时子序列中只有一个记录； 从第二个记录起到最后一个记录，依次将每个记录与前面子序列的记录按关键字比较，确定记录插入的位置；将记录插入到子序列中，子序列记录个数加1，直至子序列长度与待排序列长度相等时结束。例如：已知一组记录的关键字值初始排列为：49，38，65，97，76。图5.14给出了直接插入排序的过程示意图。 冒泡排序冒泡排序是一种简单直观的排序算法。该算法重复地扫描要排序的数列，依次比较两个元素，如果它们的顺序错误就把它们交换过来。扫描数列的工作是重复地进行直到没有再需要的交换，也就是说该数列已经排序完成。在这个算法的工作过程中，较小的元素会通过交换慢慢“浮”到数列的前端，较大的元素

41、会慢慢“浮”到数列的末端，这就是该算法得名的原因。可以更具体地描述该算法，如下： 将第n个记录的关键字与将第n-1个记录的关键字进行比较，若为逆序则将两个记录进行位置的交换，否则保持原来顺序； 将第n-1个记录的关键字与将第n-2个记录的关键字进行比较； 重复上述排序过程，直到全部关键字均比较一遍； 上面三步的比较交换过程称为第一趟排序，其结果是使关键字最小的记录被交换到了第1个记录的位置，完成一趟排序； 第二趟排序从第n个记录到第2个记录进行同样的操作，结果是使关键字次小的记录被交换到了第2个记录的位置；依次类推，第i趟排序是从第n个记录到第i个记录依次比较交换。设有n个关键字，需要经过n-

42、1趟比较和交换，使得n个记录的关键字从小到大排好序了。判断冒泡排序结束的一个条件是“在一趟排序中没有进行过交换记录的操作”。例如：已知一组记录的关键字值初始排列为：13，49，38，27，65。图5.15给出了冒泡排序的过程示意图。人们在日常生活中将物品有规律的摆放，如水果由小到大摆放，图书按书名或学科顺序排序等。将物品按照某种规律顺序排列摆放称为排序。排序的根本目的是能够根据实际需要方便快捷地拿取物品。计算机经常被用来把数据清单排列成有序的顺序，无论是按字母、数字或日期。如果使用了错误的方法，即使是在高速的计算机上运行，它都可能需要很长的时间进行排序。初始 (49) 38 65 97 76i

43、=2： (38 49) 65 97 76i=3： (38 49 65) 97 76i=4： (38 49 65 97) 76i=5： (38 49 65 76 97)13 49 38 27 6513 49 27 38 6513 27 49 38 6513 27 49 38 6513 27 49 38 6513 27 38 49 6513 27 38 49 6513 27 38 49 6513 27 38 49 65第1趟第2趟第3趟图5.14 直接插入排序的过程图5.15 冒泡排序的过程本章小结与思考本章首先简要介绍了软件和程序这两个截然不同的概念。接着介绍了机器语言、汇编语言和高级语言三大程

44、序设计语言的分类及特点，描述了程序编码、编译和运行的基本过程。附加介绍了几种常用高级语言的特性、开发环境及选用范围，其目的是让初学者在宏观层面对常用的高级语言有一个大致的了解。另外，从“程序本质上是描述特定数据的处理过程”的观点出发，简要介绍了高级程序设计语言的构成、算法、数据结构等基本概念，并结合具体的例子介绍了常用的程序设计方法一一结构化程序设计方法的基本思想。计算机问题求解是以计算机为工具、利用计算思维解决问题的实践活动，一般包括分析问题、设计算法、实现算法等步骤，是最典型计算思维方法。在通过本章的学习，希望读者对计算思维和计算机问题求解有一个初步的了解，对于算法和程序的基本概念、算法设

45、计的基本方法以及程序设计的原则和思想有所理解。学习完本章后，请思考并讨论以下提出的几个问题：1. 结合你所学的专业谈谈你适合学习哪种程序设计语言。2. 谈谈你是如何理解算法是程序的灵魂，是计算机的灵魂，是计算思维的灵魂。6.7本章计算思维的典型案例案例1： 抽象和分解是计算思维的两个重要特征。设计一个数据库，本身就体现了计算思维抽象和分解的过程。在本章中需要在计算机上建立数据库，需要根据系统的需求，将客观世界的信息转化成计算机系统中的二进制信息。由于客观世界的复杂性，直接完成这种转换是非常复杂和困难的。因此，在数据库设计中，将建模分成了三个层次：概念数据模型、逻辑数据模型和物理数据模型。设计者

46、依次在这三个层次上进行建模，分别完成一定的信息转换，最终完成客观世界信息到计算机系统中二进制信息的转换。这就是一种将复杂问题进行分解而得到答案的例子。以上抽象思维的结果需要在计算机上实现，这体现了自动化这个本质，也是将理论成果应用于技术实践的过程。自动化隐含着需要某类计算机(可以是机器或人，或两者的组合)去解释抽象。案例2： 排序是信息处理中经常进行的一种操作，其目的是将一组元素从“无序”的序列调整为“有序”的序列。虽然排序算法是一个看似简单的问题，但它却是计算机科学的发展历史中一个重要的研究问题，计算机科学家设计了一系列的排序算法。由于排序操作是一项经常被使用的基本功能，所以高效的排序算法对

47、于提高信息处理的效率具有非常基础性的意义。和排序相关的另一个信息处理方法是索引，是指对具有共性的一组对象进行编目，以提供根据数据某一属性快速访问数据的能力。在数据库中，使用索引可快速访问数据库表中的特定信息。为了提高数据访问效率，可以建立一个对数据库表中一列或多列的值进行排序的一种结构(即索引)。以本章中的学生选课数据库为例，例如，要查看学生表中的数据，一般看到的是按学号由小到大排列。但有时可能需要查看按学生年龄、姓名或籍贯排列的学生记录。这时可以允许将数据表的数据按多种顺序排列显示出来。另外，如果要在“学生关系”表中按籍贯查找特定学生，如果没有索引，就必须依次搜索表中的所有行，效率非常低。而利用索引技术，可以为“学生关系”表的“籍贯”字段建立索引，这样如果需要在该表中按籍贯查找特定学生，例如，需要查找籍贯为“湖南”的某学生，通过索引，可以很快地找到该学生。在我们