计算机文化第1章 绪论

1、科学出版社科学出版社计算机导论计算机导论第第1 1章章 绪论绪论了解计算机在各领域中的应用了解计算机在各领域中的应用掌握计算机的定义掌握计算机的定义了解计算工具的发展历史了解计算工具的发展历史了解计算机硬件的发展历史及趋势了解计算机硬件的发展历史及趋势了解计算机软件的发展历史了解计算机软件的发展历史理解计算机软件的执行过程理解计算机软件的执行过程掌握计算机的分类和特点掌握计算机的分类和特点了解计算机科学与技术学科的研究范畴了解计算机科学与技术学科的研究范畴了解计算机中的基本问题了解计算机中的基本问题学习目标学习目标主要内容主要内容计算机在各领域中的应用计算机在各领域中的应用1第第1 1章章 绪

2、论绪论计算的历史计算的历史2计算机科学与技术学科简介计算机科学与技术学科简介3主要内容主要内容计算机在各领域中的应用计算机在各领域中的应用1第第1 1章章 绪论绪论计算的历史计算的历史2计算机科学与技术学科简介计算机科学与技术学科简介31.1 1.1 计算机在各领域的应用计算机在各领域的应用计算机在交通运输业的应用计算机在交通运输业的应用坐席预定系统、交通控制系统、全球卫星定位系统坐席预定系统、交通控制系统、全球卫星定位系统(GPS)和智能监控系统等就是计和智能监控系统等就是计算机在交通运输业的典型应用。算机在交通运输业的典型应用。1.1 1.1 计算机在各领域的应用计算机在各领域的应用计算机

3、在交通运输业的应用计算机在交通运输业的应用坐席预定系统、交通控制系统、全球卫星定位系统坐席预定系统、交通控制系统、全球卫星定位系统(GPS)和智能监控系统等就是计和智能监控系统等就是计算机在交通运输业的典型应用。算机在交通运输业的典型应用。1.1 1.1 计算机在各领域的应用计算机在各领域的应用计算机在教育业的应用计算机在教育业的应用计算机在教育领域中的典型应用有校园网、远程教育、计算机辅助教育计算机在教育领域中的典型应用有校园网、远程教育、计算机辅助教育（Computer-Aided Instruction，CAI）等。）等。1.1 1.1 计算机在各领域的应用计算机在各领域的应用计算机在商

4、业中的应用计算机在商业中的应用计算机在零售业的应用，改变了人们的购物环境和方式。计算机在零售业的应用，改变了人们的购物环境和方式。随着互联网行业的发展而发展起来的电子商务，更是从根本上改变了企业的供销模随着互联网行业的发展而发展起来的电子商务，更是从根本上改变了企业的供销模式和人们的消费模式。式和人们的消费模式。1.1 1.1 计算机在各领域的应用计算机在各领域的应用计算机在银行和证券业的应用计算机在银行和证券业的应用计算机和网络从根本上改变了银行和金融机构的业务处理模式。计算机和网络从根本上改变了银行和金融机构的业务处理模式。计算机在证券市场中的应用为投资者进行证券交易提供了必不可少的环境。

5、计算机在证券市场中的应用为投资者进行证券交易提供了必不可少的环境。图1.9 计算机在证券业中的应用图1.10 计算机在银行业中的应用 1.1 1.1 计算机在各领域的应用计算机在各领域的应用计算机在医学中的应用计算机在医学中的应用医学专家系统可以将著名医学专家或医生的知识和经验存储到知识库中，并建立从医学专家系统可以将著名医学专家或医生的知识和经验存储到知识库中，并建立从病情表述和检测指标到诊断结论以及治疗方案的推理机构。这样，根据患者的病情病情表述和检测指标到诊断结论以及治疗方案的推理机构。这样，根据患者的病情和各种检测数据，就可以诊断出所患的疾病以及作出治疗方案。对于边远地区，医和各种检测

6、数据，就可以诊断出所患的疾病以及作出治疗方案。对于边远地区，医学专家系统可以为患者提供当地医院无法提供的医疗服务。学专家系统可以为患者提供当地医院无法提供的医疗服务。一些现代化的医疗检测仪器如超声波仪、心电图仪、脑电图仪、核磁共振仪、一些现代化的医疗检测仪器如超声波仪、心电图仪、脑电图仪、核磁共振仪、X光光摄像机等医疗检测设备中也嵌入了计算机，可以采用数字成像技术，使得图像更加摄像机等医疗检测设备中也嵌入了计算机，可以采用数字成像技术，使得图像更加清晰。清晰。图1.11 计算机在医学中的应用 1.1 1.1 计算机在各领域的应用计算机在各领域的应用计算机在科学研究中的应用计算机在科学研究中的应

7、用计算机用在科学研究领域，可进行科技文献的存储与查询、复杂的科学计算、系统计算机用在科学研究领域，可进行科技文献的存储与查询、复杂的科学计算、系统仿真与模拟、复杂现象的跟踪与分析以及知识发现等。仿真与模拟、复杂现象的跟踪与分析以及知识发现等。图1.12 计算机在科学研究中的应用 1.1 1.1 计算机在各领域的应用计算机在各领域的应用计算机在文化艺术业的应用计算机在文化艺术业的应用艺术家如果能够以计算机为工具进行音乐、舞蹈、美术、摄影、电影与电视等技术艺术家如果能够以计算机为工具进行音乐、舞蹈、美术、摄影、电影与电视等技术创作，则能够创作出更具特色、效果更佳的作品。很多游戏设计人员借助于计算机

8、创作，则能够创作出更具特色、效果更佳的作品。很多游戏设计人员借助于计算机设计出引人入胜的计算机游戏软件。使用计算机控制的电子合成器可以模拟一种或设计出引人入胜的计算机游戏软件。使用计算机控制的电子合成器可以模拟一种或多种乐器的声音。艺术家可以使用专门的软件作为工具来创作绘画、雕塑等技术作多种乐器的声音。艺术家可以使用专门的软件作为工具来创作绘画、雕塑等技术作品；在影片制作过程中利用计算机可以获得过去无法获得的效果。品；在影片制作过程中利用计算机可以获得过去无法获得的效果。 主要内容主要内容计算机在各领域中的应用计算机在各领域中的应用1第第1 1章章 绪论绪论计算的历史计算的历史2计算机科学与技

9、术学科简介计算机科学与技术学科简介31.2 1.2 计算的历史计算的历史什么是计算机什么是计算机能够按照事先存储好的指令序列，接收用户输入的数字、文本、图像、声音等数据，能够按照事先存储好的指令序列，接收用户输入的数字、文本、图像、声音等数据，并对其进行存储、处理和结果输出的系统。并对其进行存储、处理和结果输出的系统。 图1.14 计算机处理流程1.2 计算机的历史输入到计算机系统的数据既可以是用户通过键盘输入的，也可以来自于其他的设备，如数码相机或数字摄像机或其他的计算机。输入设备如键盘或鼠标，可收集输入数据并将其转换成计算机能够识别的信号，以供计算机存储和处理。输出指的是计算机的处理结果。

10、常见的计算机输出形式有报表、文档、音乐、图形和图像。用户可通过计算机的显示屏查看输出结果，也可将其通过打印机在纸上进行打印或者是刻录到光盘。1.2 计算机的历史计算工具的发展历史1.2 计算机的历史计算工具的发展历史到了19世纪初，英国数学家查尔斯巴比奇（Charles Babbage，1792-1871）取得了突破性进展，计算机不但能快速地完成加、减、乘、除运算，还能够自动完成复杂的运算，从手动机械跃入自动机械的新时代。同时巴比奇还提出了分析机的新设计思想。分析机（如图1.22所示）的重要贡献就在于它包括了现代计算机所具有的5个基本组成部分。（1）输入装置：用穿孔卡片输入数据。（2）存储装置

11、：既能存储运算数据，又能存储运算结果。（3）资料处理装置：完成加、减、乘、除运算。还能根据运算结果的符号改变运算的进程。也就是能实现现代的条件转移指令。（4）控制装置：使用指令进行控制，用程序自动改变操作次序。（5）输出装置：用穿孔卡片或打印方法输出。1.2 计算机的历史 巴比奇 巴比奇分析机1.2 计算机的历史英国著名诗人拜伦的女儿Ada（Ada Augusta Lovelace，1815-1852）在剑桥大学帮助巴比奇研究分析机时，她意识到巴比奇对新分析机的设计思想完全可行，也非常支持巴比奇的工作。Ada建议用二进制存储取代原设计的十进制存储。她指出分析机可以像雅各织布机一样进行编程，并发

12、现了程序设计和编程的基本要素，还为某些计算开发了一些指令。由于她在程序设计上的开创性工作，被誉为世界上第一位程序员。1.2 计算机的历史第一次采用电器元件来制造计算机的是德国工程师朱斯（K. Zuse）。1941年，他的Z-3计算机开始运转，这是世界上真正的第一台通用程序控制计算机（如图1.23所示）。Z-3不仅全部采用继电器，同时采用了浮点记数法、二进制运算、带数字存储地址的指令形式等。1936年美国哈佛大学应用数学教授霍华德艾肯（Howard Aiken，1900-1973）受了巴比奇和爱达的笔记后，受到启发并在IBM公司的大力支持下，研制成功了被称为Mark-I的计算机（如图1.24所示

13、）。Mark-I是个庞然大物，长15.5米，高2.4米，由75万个零部件组成。它用大量的继电器作为开关元件，用十进制计数齿轮组作为存储器，用穿孔纸带进行程序控制。1.2 计算机的历史第二次世界大战期间，美国宾夕法尼亚大学莫尔学院电工系同阿伯丁弹道研究实验室共同负责为陆军每天提供六张火力表，这一任务非常困难和紧迫。正是在该背景下，促成了第一台电子计算机ENIAC（Electronic Numerical Integrator and Computer，简称ENIAC）的产生。ENIAC起初是专门用于弹道计算，后来经过多次改进而成为能进行各种科学计算的通用计算机。ENIAC占地面积达170平方米，

14、差不多相当于10间普通房间的大小；使用了大约18000只电子管，1500个继电器，70000只电阻，18000只电容。ENIAC的最大特点就是采用了电子线路来执行算术运算、逻辑运算和储存信息。由于广泛采用了电子线路，ENIAC同以往计算机相比最突出的优点就是高速度。1.2 计算机的历史1.2 计算机的历史计算机硬件的发展历史第一代计算机 以真空管作为主要元器件，体积庞大，价格昂贵，采用二进制代替十进制，程序虽然可以存储，但存储设备还比较落后，输入输出装置主要用穿孔卡、速度很慢。只有专家们方可使用。第二代计算机 以晶体管代替电子管，减小计算机体积的同时，也降低了费用，使得中小企业也能负担得起。普

15、遍采用磁心存储器作为主存，并且采用磁带和磁盘作为辅存，使存储容量增大，可靠性提高，为操作系统的发展奠定了硬件基础。与此同时，变址寄存器、浮点数据表示、间接寻址、中断、I/O处理机等现代计算机体系结构的特性相继出现。同时程序设计语言也有了很大发展，先是用汇编代替了机器语言，接着又出现了高级语言FORTRAN、COBOL。第三代计算机 用集成电路取代晶体管，更加减少了计算机的成本和大小。用半导体存储器淘汰了磁心存储器，普遍采用了微程序设计技术，系统软件与应用软件都有很大发展，出现了第一代小型计算机（minicomputer），如DEC的PDP-8。1.2 计算机的历史计算机硬件的发展历史第四代计算

16、机 用微处理器（microprocessor）或超大规模集成电路VLSI（Vely Large Scale Integration）取代了普通集成电路。存储容量进一步扩大，输入采用了OCR（字符识别）与条形码，输出采用了激光打印机，以及引进光盘和新的程序设计语言Pascal、Ada。微型计算机也蓬勃发展起来，使得计算技术由集中化向分散化转变。与此同时，数据通信、计算机网络、分布式处理有了很大的发展。Internet、广域网（WAN）、城域网（CAN）和局域网（LAN）的发展将世界各地紧密地联系在一起。当前的计算机依然属于第四代计算机。第五代计算机 很多国家的学术团体都对未来计算机的发展有所研究

17、和期望。第五代计算机系统将会拥有智能特性，带有知识表示与推理能力，可以模拟人的设计、分析、决策、计划以及其他智能活动并具有人机自然通信能力，可作为各种信息化企业的智能助手。1.2 计算机的历史计算机硬件的发展历史计算机的发展趋势为巨型化、微型化、多媒体化、网络化和智能化。（1）巨型化 巨型化是指运算高速、大存储容量和强功能的超大型计算机。这不仅是尖端科学（如气象、宇航、核反应等）及新兴学科（生物工程、基因工程）的需要，也为了使得计算机具有人脑学习、推理的复杂功能。（2）微型化 大规模和超大规模集成电路的发展，使得微型机可以渗透到家用电器、导弹弹头等中、小型机无法进入的领域。（3）多媒体化 以数

18、字技术为核心的图像、声音等与计算机、通信融为一体的信息环境。通过这种环境，无论在什么地方，只需要简单的设备，就能自由自在地以接近自然的交互方式收发所需要的各种媒体信息。（4）网络化 不受地理区域的限制，将分布在不同地点的不同机型的计算机和专门的外部设备由通信线路互联组成一个规模大、功能强的网络系统，以达到资源和信息共享的目的。（5）智能化 让计算机能够模拟人的感觉、行为和思维过程，使计算机具有一定的逻辑推理、学习和证明等能力，形成智能型计算机。1.2 计算机的历史计算机软件的发展历史第一代软件（1951-1959）第一代软件由机器语言编写。机器语言是内置在计算机电路中的指令。即使求“3+5”的

19、结果这一简单计算就需要三条完全由0、1组成的指令。对程序设计人员而言，需要面对一系列的0、1数字组合，他们不得不记住每个0、1串代表的含义。由于编写机器语言程序非常乏味，就有程序设计员开发出了一种使用助记码表示的人工程序设计语言，这些语言被称为“汇编”语言。 虽然汇编语言的出现简化了程序设计的工作。但每个程序在计算机上执行时采用的最终形式依然是机器语言。所以，为了让汇编语言编写的程序能够运行，还需要翻译程序或汇编器，将每条用助记码编写的程序指令翻译成等价的机器语言。其流程如图所示。汇编源程序汇编程序翻译器机器语言程序输入输出1.2 计算机的历史计算机软件的发展历史第二代软件（1959-1965

20、） 第二代软件时期开发的是高级语言，目前仍在使用有FORTRAN、COBOL和Lisp。高级语言的出现使得可以在多台计算机上运行同一个程序。因为每中高级语言都有配套的翻译程序，它可将高级语言编写的语句翻译成等价的机器语言指令。最早时，高级语言的语句通常被翻译成汇编语言，然后这些汇编后的语句再被翻译成机器指令。其流程如图所示。汇编源程序汇编程序翻译器机器语言程序输入输出高级语言程序输入高级语言翻译器输出1.2 计算机的历史计算机软件的发展历史第三代软件（1965-1971） 随着计算机处理速度的不断提高，人机矛盾日益凸显。当人们准备下一批处理数据时，计算机无所事事。为了让计算机的所有资源都在计算

21、机的控制中，需要编写一种程序来决定何时运行什么程序，这种程序被称作操作系统。应用程序包系统软件高级语言汇编语言机器语言1.2 计算机的历史计算机软件的发展历史第四代软件（1971-1989） 20世纪70年代出现了结构化程序设计方法，这是一种有逻辑、有规则的程序设计方法。该阶段出现了Pascal、Modula-2、BASIC和C等结构化程序设计语言。结构化程序设计语言C+还允许用户使用低级语句，成为了业界的选择。与此同时，更好、更强大的操作系统也被开发出来了。AT&T公司开发了UNIX系统；为IBM PC机开发的PC-DOS和为了兼容开发的MS-DOS系统都成了个人计算机的标准系统。M

22、acintosh机的操作系统在引入了鼠标和点击式的图形界面，彻底改变了人机交互的方式。很多高品质的、价格合理的应用程序软件包如电子表格软件、文字处理软件和数据库管理系统等，也都被系统程序员开发了出来。1.2 计算机的历史计算机软件的发展历史第五代软件（1990至今） 这一时期，操作系统不断改进，Microsoft公司的Windows操作系统在个人计算机市场占有显著优势。也是微软公司的Office套件也逐渐取代了以往的办公自动化软件。 面向对象的程序设计方法成为大型程序设计项目的首选。结构化设计基于任务的层次划分，而面向对象的设计则基于数据对象的层次划分。Sun公司为面向对象的编程方法设计的Ja

23、va语言成为了C+语言的竞争对手。1.2 计算机的历史计算机的分类从不同的角度，可以将计算机分成不同的种类。但目前被广泛采用的方法是美国电气和电子工程师协会（IEEE Institute of Electrical and Electronics Engineers）于1989年11月提出的标准，即把计算机划分为巨型机、小巨型机、大型机、小型机、工作站和个人计算机6类。 （1）巨型机（Super Computer）在所有计算机类型中功能最强，价格最贵，浮点运算速度最快，常用于战略武器设计、空间技术、石油勘探的概念领域。往往成为衡量一个国家经济实力和科技水平的重要标志。 （2）小巨型机（Mini

24、 Super Computer）功能略低于巨型机，运算速度每秒10亿次，价格只有巨型机的十分之一，可满足一些较高应用需求的用户。 （3）大型主机（Mainframe）也称大型电脑，整机运算速度高达每秒30亿次，具有很强的处理和管理能力。是规模较大的银行、高校和科研院所常用的一种机型。 （4）小型机（Mini Computer） 结构简单，可靠性高，成本较低，不需要经长期培训即可维护和使用，比较适用于中小客户。 （5）工作站（Workstation） 介于小型机和个人计算机之间的一种高档微机，主要用于特殊的专业领域，如图像处理、计算机辅助设计等。 （6）个人计算机（Personal Comput

25、er，简称PC） 日常生活中最常见的一种机型。因其软件丰富、处理能力强、价格便宜等优势深受普通用户的青睐。目前，PC机除了台式的，还有膝上型、笔记本型、掌上型、手表型等。1.2 计算机的历史计算机的特点运算速度快 目前计算机的运算速度（也称处理速度）用MIPS（每秒百万条指令）来衡量。计算机如此高的运算速度是其他任何计算工具无法比拟的，它使得以往需要几年甚至几十年才能完成的复杂运算任务，现在只需要几天、几小时、甚至更短的时间就可完成计算精度高 计算机内的数采用二进制编码，数的精度由该数所对应的二进制码的位数决定，所以通过增加数的二进制位数来提高精度，位数越多精度就越高。具有记忆能力 计算机具有

26、内存和外部存储器，内存用来存储正在运行中的程序和有关数据，外存储器用来存储需要长期保存的数据。这就像人的“大脑”一样，能够记忆数据。具有逻辑判断能力 计算机在运行过程中，能够根据上一步的结果判断下一步该执行的指令。这就使得计算机不仅能够完成数值计算工作，还可以完成非数值数据的处理工作，如信息检索、图像识别等。1.3 计算机科学与技术学科简介计算机科学与技术学科的研究范畴 计算机与技术的研究范畴包括了计算机理论、硬件、软件、网络及应用等，按照研究的内容，可以划分为基础理论、专业基础和应用三个层面。在这些研究领域中，有的方面前人已经研究得比较透彻，取得了很多成果，需要我们在后续课程中去学习、掌握和

27、继承；有的方面还不够成熟和完备，需要我们进一步去研究、完善和发展。1.3 计算机科学与技术学科简介计算机理论的研究内容离散数学：是计算机科学的理论基础，主要研究数理逻辑、集合论和图论等。算法分析理论：主要研究算法设计与分析中的数学方法与理论，如概率论、数理统计等，用于分析算法的时间复杂度和空间复杂度。形式语言与自动机理论：研究程序设计语言以及自然语言的形式化定义、分类、结构等有关理论以及识别各类语言的形式化模型及其相互关系。程序设计语言理论：运用数学和计算机科学的理论研究程序设计语言的基本规律，包括形式语言文法理论、形式语义学（如代数语义、操纵语义等）和计算语言学等。程序设计方法学：研究如何从

28、号结构的程序定义出发，通过对构成程序的基本结构的分析，给出能保证高质量程序的各种程序设计规范化方法，并研究程序正确性证明理论、形式化验证技术等。1.3 计算机科学与技术学科简介计算机硬件的研究内容元器件与存储介质：研究构成计算机硬件的各类电子的、磁性的、超导的、光学的元器件和存储介质。微电子技术：研究各类集成电路、大规模集成电路、超大规模集成电路芯片的结构和制造技术等。计算机组成原理：研究通用计算机的硬件组成结构以及运算器、控制器、存储器、输入和输出设备等各部件得构成和工作原理。微型计算机技术：研究使用广泛的微型计算机的组成原理、结构、芯片、接口及其应用技术。计算机体系结构：研究计算机软硬件的

29、总体结构、各种新型体系结构（如并行计算机系统、陈列计算机、集群计算机、网络计算机）以及提高计算机性能的各种新技术。1.3 计算机科学与技术学科简介计算机软件的研究内容程序设计语言的设计：设计新颖的程序设计语言，包括定义程序设计语言的词法规则、语法规则和语义规则。数据结构与算法：对数据的逻辑和物理结构定义相应的运算，设计出实现这些运算的算法，并确保经过这些运算后所得到的新结构仍然是原来的结构类型。常用的数据结构包括：线性表、栈、队列、串、树和图等。相关的算法有查找、内部排序和外部排序等。程序设计语言翻译系统：研究程序设计语言翻译系统的基本理论、原理和实现技术，如词法规则和语法规则的形式化定义、程

30、序设计语言翻译系统的体系结构及其各模块（如词法分析、语法分析、中间代码生成、优化和目标代码生成）的实现技术。操作系统：研究如何自动地对计算机系统的软件和硬件资源进行有效的管理，最大限度地方便用户的使用。1.3 计算机科学与技术学科简介数据库系统：研究数据模型以及数据库系统的实现技术。其中包括：数据模型、数据库语言、数据库的存储结构、查询处理、查询优化、事务管理、数据库应用以及数据仓库等。算法设计与分析：研究计算机相关领域中常用算法的设计方法，分析算法的时间和空间复杂度以评价算法的优劣。有排序算法、串匹配算法、并行算法和模糊算法等。软件工程学：指导计算机软件开发和维护的工程学科，研究如何采用工程

31、的概念、原理、技术和方法来开发和维护软件。可视化技术：可视化技术研究如何用图形和图像来直观地表征数据，即用计算机来生成、处理、显示能在屏幕上逼真运动的三维形体，并能与人进行交互式对话。1.3 计算机科学与技术学科简介计算机网络的研究内容网络结构：研究局域网、远程网、Internet、Intranet等各种网络的拓扑结构和构成方法及接入方式。数据通信与网络协议：研究实现连接在网络上的计算机之间进行数据通信（如卫星、微波、宽带、光纤、有线、无线）的介质、原理、技术以及通信双方必须共同遵守的各种规约。网络服务：研究如何为计算机网络的用户提供方便的远程登录、文件传输、电子邮件、信息浏览、文档查询、网络

32、新闻以及全球范围内的超媒体信息浏览等服务。网络安全：研究计算机网络中的设备安全、软件安全、信息安全以及病毒防治等技术，以提高计算机网络的安全性和可靠性。1.3 计算机科学与技术学科简介计算机应用的研究内容软件开发工具：研究软件开发工具的有关技术（如程序调试技术、代码优化技术、软件重用技术、软件自动生成技术等）以及研制各种新型的程序设计语言及其翻译系统、文字和报表处理工具、数据库开发工具、多媒体开发工具等。完善已有的应用系统：根据最新的技术平台和实际需求对已有的应用系统进行升级和改造，使其功能更加强大，更加易于使用。开拓新的应用领域：研究如何打破计算机的传统应用领域，扩大计算机在国民经济和社会生

33、活中的应用。人机工程：研究人与计算机的交互和协同技术，为人们使用计算机提供更加友好的环境和界面。1.3 计算机科学与技术学科简介计算机科学与技术学科中的基本问题 汉诺塔问题 证比求易法并行计算 找零问题 哲学家进餐问题1.3 计算机科学与技术学科简介汉诺塔问题 相传，印度教的天神梵天在创造地球时建了一座神庙，庙里竖有3根宝石柱子，柱子由一个铜座支撑。梵天将64个直径大小不一的金盘子，按照从大到小的顺序依次套放在第一根柱子上，形成一座金塔（梵天塔或汉诺塔）。天神让庙里的僧侣们将第一根柱子上的64个盘子借助第二根柱子全部移到第三根柱子上，即将整个塔迁移，同时定下3条规则： 每次只能移动一个盘子；

34、盘子只能在3根柱子上来回移动，不能放在他处； 在移动过程中，3根柱子上的盘子必须始终保持大盘在下，小盘在上。 当时僧侣们在对该问题分析之后预言，当所有的进盘子都移动到第三根柱子上时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽。 如果没有科学的分析过程，也许我们会认为以上说法是骇人听闻的。但当使用计算机解决这一问题时，汉诺塔问题就是一个典型的用递归方法求解的问题。递归是计算学科中的一个重要概念。1.3 计算机科学与技术学科简介 所谓递归，就是将一个较大的问题归约为一个或多个子问题的求解方法。按照递归的方法，可将64个盘子的移动问题转化为求解63个盘子的问题。如果63个盘子的能解决

35、，则可先将63个盘子移动到第二根柱子上，再将一个盘子直接移动到第三根柱子上，最后又一次将63个盘子借助于第一根柱子，移动到第三根柱子上。依此类推，63个盘子的移动问题又可转化为62个盘子的移动问题，62个盘子的移动问题又可转化为61个盘子的移动问题，直到1个盘子的求解问题。再由1个盘子的汉诺塔问题的求解求出2个盘子的移动方法，直到求出64个盘子的移动方法。由此，可用C语言对该问题的求解进行描述。 Hanoi(i,char left,char middle,char right) If i=1 Move(1,left,_,right); Else Hanoi(n-1,left,middle,ri

36、ght); Move(1,left,_,right); Hanoi(n-1,middle,left,right);1.3 计算机科学与技术学科简介证比求易法并行计算 从前，有一个酷爱数学的年轻国王艾述向邻国一位聪明美丽的公主秋碧贞楠求婚。公主出了这样一道题：求出48 770 428 433 377 171的一个真因子。若国王能在一天之内求出答案，公主便接受他的求婚。国王回去后立即开始逐个数地进行计算，他从早到晚，共算了3万多个数，最终还是没有结果。于是国王向时任宰相的大数学家孔焕石求教，大数学家在仔细思考后认为这个数为17位，则最小的一个真因子不会超过9位，于是他给国王出了一个主意：按自然数的

37、顺序给全国老百姓每人编一个号发下去，让每个老百姓用自己的编号去除这个数，除尽了立即上报。最后，国王用这个方法求婚成功。 这位数学家所用的方法就是并行算法，在某些场合，用顺序算法难以求解的问题，可用并行算法解决。但大家也会意识到一个问题，使用并行算法时，空间方面的复杂度较高，如果空间受到了限制，那么需要用计算机解决的难解性问题，还需要从降低时间复杂度入手。1.3 计算机科学与技术学科简介找零问题 有一顾客拿一面值100元的钞票在超市买了4元钱的商品，收银员需要找96元的零钱，该如何选择呢？ 一般情况下，虽然可有多种找法，但是收银员会凭直觉选择1张50元的，两张20元的，1张5元的和1张1元的，这可使得找的零钱数目最少。 收银员采用的方法，就是一种典型的贪婪算法。可以证明，按照这种方法找到的零钱数目的确最少。 贪婪算法也被用在在计算机求解问题的很多场合。它是一种典型的启发式算法，它采用逐步构造最优解的方法，即在算法的每个阶段都做出在当时看上去最好的决策，以获得最大的“好处”。换言之，就是在每一个决策过程中都要尽可能的“贪”，直到算法中的某一步不能继续前进时，算法才停止。1.3 计算机科学与技术