第1章-计算思维解析课件.ppt

1、第第一一章章 计计算算科科学学与与计计算算思思维维大学计算机基础大学计算机基础第第一一章章 计计算算科科学学与与计计算算思思维维大学计算机基础大学计算机基础教学目标教学目标了解科学、计算、计算科学与计算学科、思维与计了解科学、计算、计算科学与计算学科、思维与计算思维的基本概念算思维的基本概念了解计算学科与其它学科之间的关系了解计算学科与其它学科之间的关系了解计算思维的作用，学会计算思维的基本方法，了解计算思维的作用，学会计算思维的基本方法，掌握其基本技能掌握其基本技能了解运用计算机求解问题的基本思路和一般过程了解运用计算机求解问题的基本思路和一般过程第第一一章章 计计算算科科学学与与计计算算思

2、思维维大学计算机基础大学计算机基础n知识要点知识要点计算、可计算性以及计算学科的概念计算、可计算性以及计算学科的概念思维、计算思维进行问题求解的一般过程思维、计算思维进行问题求解的一般过程计算思维在人类社会的经济、科技等各领域计算思维在人类社会的经济、科技等各领域发展中的作用和对人的能力发展的影响发展中的作用和对人的能力发展的影响计算科学研究与应用（普适计算、网格计算计算科学研究与应用（普适计算、网格计算和云计算、人工智能、物联网等）和云计算、人工智能、物联网等）重点！重点！第第一一章章 计计算算科科学学与与计计算算思思维维大学计算机基础大学计算机基础n举案引思举案引思 1 1、皇帝会答应大臣

3、的请赏？、皇帝会答应大臣的请赏？ 古代皇帝和他的大臣下象棋，大臣赢了。皇帝问大臣：古代皇帝和他的大臣下象棋，大臣赢了。皇帝问大臣：“你想要得到什么奖赏？你想要得到什么奖赏？”大臣向皇帝说：大臣向皇帝说：“微臣不敢奢求，微臣不敢奢求，只要皇上按棋盘的格子数，依次给予只要皇上按棋盘的格子数，依次给予1 1粒黄豆，粒黄豆，2 2粒黄豆，粒黄豆，4 4粒黄豆，粒黄豆，8 8粒黄豆，粒黄豆，1616粒黄豆，粒黄豆，. .按此规律按此规律 ( (每次给出黄每次给出黄豆的数目是前一次给出黄豆数目的豆的数目是前一次给出黄豆数目的2 2倍倍) ) 给给6464次就无比地感次就无比地感谢皇上了谢皇上了”。请问皇帝

4、会答应这个大臣的请赏吗？你能很快。请问皇帝会答应这个大臣的请赏吗？你能很快(10(10秒内秒内) )给出答案吗？给出答案吗？ 2 2、到底谁说真话？、到底谁说真话？张三说张三说: :李四在说谎李四在说谎; ;李四说李四说: :王五在说谎王五在说谎; ;王五说王五说: : 张三和李四都在说谎。张三和李四都在说谎。已知三人中只有一人说真话。已知三人中只有一人说真话。第第一一章章 计计算算科科学学与与计计算算思思维维大学计算机基础大学计算机基础n举案引思举案引思3 3、如图、如图1-11-1所示，从哪一点出发开始旅行既能游览所示，从哪一点出发开始旅行既能游览每一个景点每一个景点(A-J(A-J表示景

5、点，连线表示通路表示景点，连线表示通路) )，又不走，又不走重复路线？重复路线？ 第第一一章章 计计算算科科学学与与计计算算思思维维大学计算机基础大学计算机基础1.1什么是什么是思维思维，思维思维有哪些有哪些种类种类，思维思维对人的能力的对人的能力的影响影响1、思维的概念：、思维的概念： 思维思维是人脑对现实事物的概括、加工，最终揭示其本质特征是人脑对现实事物的概括、加工，最终揭示其本质特征和内在规律的活动；和内在规律的活动； 人脑对信息的加工处理包括分析、抽象、综合、概括等。人脑对信息的加工处理包括分析、抽象、综合、概括等。 思维思维是人的高级心理活动，认识事物的高级形式；是人的高级心理活动

6、，认识事物的高级形式； 是人和动物的根本区别之一，是人的重要本质所在。是人和动物的根本区别之一，是人的重要本质所在。 人类文明，人化的世界，重要源泉是人的思维。人类文明，人化的世界，重要源泉是人的思维。 2、思维的作用：、思维的作用：思维思维对于知识具有本原作用对于知识具有本原作用。思维思维是人类获得知识的途径，加工知识的机器。是人类获得知识的途径，加工知识的机器。3、思维的分类：思维的分类：第第一一章章 计计算算科科学学与与计计算算思思维维大学计算机基础大学计算机基础思维分类方法思维分类方法思维的形式思维的形式从思维的进程方向可分为从思维的进程方向可分为横向思维、纵向思维、发散思维、横向思维

7、、纵向思维、发散思维、收敛思维收敛思维从思维的抽象程度可分为从思维的抽象程度可分为直观行动思维直观行动思维(操作思维、实践思操作思维、实践思维维)、形象思维、抽象思维、形象思维、抽象思维(逻辑思逻辑思维或理论思维维或理论思维)从思维的形成与应用领域从思维的形成与应用领域可分为可分为日常思维、科学思维日常思维、科学思维科学思维科学思维是指形成并运用于科学认识活动的人脑，借助信息符是指形成并运用于科学认识活动的人脑，借助信息符号对感性认识材料号对感性认识材料,经过整理、归纳、加工处理，形成概念、分经过整理、归纳、加工处理，形成概念、分析、判断和推理，揭示事物的本质和内在规律的思维活动。析、判断和推

8、理，揭示事物的本质和内在规律的思维活动。 简而言之，简而言之，科学思维科学思维就是人们认识自然界、社会和人类意识就是人们认识自然界、社会和人类意识的本质和客观规律性的高级思维活动。的本质和客观规律性的高级思维活动。 特点特点是比日常思维更具是比日常思维更具理性理性、客观性客观性、严谨性严谨性、系统性系统性与与科学科学性性。第第一一章章 计计算算科科学学与与计计算算思思维维大学计算机基础大学计算机基础科学思维科学思维的分类的分类理论思维理论思维实证思维实证思维计算思维计算思维对事物的感性认识资料，经过抽象、概括，形成描述事物本质对事物的感性认识资料，经过抽象、概括，形成描述事物本质的概念，主要以

9、推理和演绎的方法，探寻概念之间相互联系的的概念，主要以推理和演绎的方法，探寻概念之间相互联系的一种思维活动。一种思维活动。理论源于数学，理论思维支撑着所有的学科领域。理论源于数学，理论思维支撑着所有的学科领域。通过观察和实验的手段，揭示自然规律法则的一种思维方法。通过观察和实验的手段，揭示自然规律法则的一种思维方法。特征特征是观察、整理、归纳、对比和验证。是观察、整理、归纳、对比和验证。人们往往要借助于某些特定的设备、工具，通过实验，获取资人们往往要借助于某些特定的设备、工具，通过实验，获取资料，以便分析研究。料，以便分析研究。例如星球运行规律与万有引力的发现，设备性能的物理测量、例如星球运行

10、规律与万有引力的发现，设备性能的物理测量、化学的分解与化合、生物的解剖等实验，就是认识事物本质和化学的分解与化合、生物的解剖等实验，就是认识事物本质和变化规律的有效手段和思维方法。变化规律的有效手段和思维方法。又叫构造思维，是指从具体的算法设计规范入手，通过算法过又叫构造思维，是指从具体的算法设计规范入手，通过算法过程的构造与实施，来解决给定问题的一种思维方法。程的构造与实施，来解决给定问题的一种思维方法。目前被广泛接受的计算思维概念是目前被广泛接受的计算思维概念是2006年美籍华裔计算机科年美籍华裔计算机科学家周以真教授首次明确提出的定义：计算思维就是运用计算学家周以真教授首次明确提出的定义

11、：计算思维就是运用计算机科学的基础概念去求解问题、设计系统和理解人类行为的涵机科学的基础概念去求解问题、设计系统和理解人类行为的涵盖了计算机科学之广度的一系列思维活动。盖了计算机科学之广度的一系列思维活动。第第一一章章 计计算算科科学学与与计计算算思思维维大学计算机基础大学计算机基础1.2计算思维的计算思维的本质本质、特征特征，及其对人能力的影响，及其对人能力的影响1、本质、本质:抽象抽象(Abstract)和和自动化自动化(Automation) 2、特征、特征:是概念化，不是程序化是概念化，不是程序化 计算机科学不是计算机编程。像计算机科学家那样去思维，意味着远远计算机科学不是计算机编程。

12、像计算机科学家那样去思维，意味着远远不是只能为计算机编程，还要求能够在抽象的多个层次上思维。不是只能为计算机编程，还要求能够在抽象的多个层次上思维。计算机科学不只是关于计算机，就像音乐产业不只是关于钢琴一样。计算机科学不只是关于计算机，就像音乐产业不只是关于钢琴一样。 是根本的，不是刻板的技能是根本的，不是刻板的技能是人的，不是计算机的思维是人的，不是计算机的思维是思想，不是人造品是思想，不是人造品是数学思维和工程思维的互补与融合是数学思维和工程思维的互补与融合 面向所有的人，所有地方面向所有的人，所有地方 关注依旧亟待理解和解决的智力上及有挑战性并且引人关注依旧亟待理解和解决的智力上及有挑战

13、性并且引人入胜的科学问题。入胜的科学问题。 第第一一章章 计计算算科科学学与与计计算算思思维维大学计算机基础大学计算机基础3、计算思维品质对人的能力影响作用、计算思维品质对人的能力影响作用问题问题抽象层次的能力抽象层次的能力是衡量人的是衡量人的思维品质思维品质的重要方面。的重要方面。根据求解问题的需要，在分析问题的过程中，人们可以对问题进根据求解问题的需要，在分析问题的过程中，人们可以对问题进行多层次的抽象，将注意力集中在感兴趣的抽象层次或关系相对行多层次的抽象，将注意力集中在感兴趣的抽象层次或关系相对密切的上下层，抛弃那些不感兴趣的密切的上下层，抛弃那些不感兴趣的(不重要的不重要的)层次或细

14、节，使层次或细节，使问题分析相对简单，以控制问题解决的复杂性。问题分析相对简单，以控制问题解决的复杂性。抽象的概念是由具体概念依其抽象的概念是由具体概念依其“共性共性”而产生的，把具体概念而产生的，把具体概念的诸多个性排出，集中描述其共性，就会产生一个抽象性的概的诸多个性排出，集中描述其共性，就会产生一个抽象性的概念。念。人的大脑人的大脑思维方法思维方法和和思维品质思维品质的差异的差异决定决定着：着：同一同一问题解决办法和处理方式问题解决办法和处理方式各不相同。其付出的代价与取得各不相同。其付出的代价与取得效果甚至可能天壤之别。效果甚至可能天壤之别。 第第一一章章 计计算算科科学学与与计计算算

15、思思维维大学计算机基础大学计算机基础4、计算思维的应用领域、计算思维的应用领域 计算思维是每个人应当具备的基本技能，也是创新人才的基计算思维是每个人应当具备的基本技能，也是创新人才的基本要求和专业素质，每个人都应当学习和应用计算思维。正如本要求和专业素质，每个人都应当学习和应用计算思维。正如印刷出版促进了阅读、写作和算术的传播一样，计算和计算机印刷出版促进了阅读、写作和算术的传播一样，计算和计算机也促进着计算思维的传播。也促进着计算思维的传播。迄今为止，计算思维不仅渗透到每个人的生活，而且对生物迄今为止，计算思维不仅渗透到每个人的生活，而且对生物信息学、生物计算、专家系统、经济学等学科领域产生

16、了重大信息学、生物计算、专家系统、经济学等学科领域产生了重大影响，在科技创新与教育教学中起着非常重要的作用。影响，在科技创新与教育教学中起着非常重要的作用。 计算思维领域提出的新思想、新方法不断地促进自然科学、计算思维领域提出的新思想、新方法不断地促进自然科学、工程技术和社会经济等领域产生革命性的发展。典型的应用领域工程技术和社会经济等领域产生革命性的发展。典型的应用领域有：有： 生物信息学生物信息学仿生计算仿生计算 专家系统专家系统 数值计算数值计算 工程、模型模拟工程、模型模拟 统计模式识别统计模式识别 虚拟现实虚拟现实 第第一一章章 计计算算科科学学与与计计算算思思维维大学计算机基础大学

17、计算机基础1.3科学科学与与计算科学计算科学科学科学是是反映反映现实世界中各种现象的现实世界中各种现象的本质和运动规律本质和运动规律的的知识体系知识体系。“科学科学”在现实生活中，被人们普遍简单朴实而又模糊地认为在现实生活中，被人们普遍简单朴实而又模糊地认为就是就是 “真实的真实的”、“客观的客观的”意思。意思。 1、科学的分类、科学的分类 分类方式分类方式划分的类型划分的类型按照研究对象的不同按照研究对象的不同 自然科学、社会科学、思维科学自然科学、社会科学、思维科学 按照人类目标的不同按照人类目标的不同广义科学、狭义科学广义科学、狭义科学 按照人类对自然规律利用的直接程度按照人类对自然规律

18、利用的直接程度自然科学、实验科学自然科学、实验科学 按照与实践联系的不同按照与实践联系的不同理论科学、技术科学、应用科学理论科学、技术科学、应用科学按照研究手段和方法的不同按照研究手段和方法的不同理论科学、实验科学、计算科学理论科学、实验科学、计算科学第第一一章章 计计算算科科学学与与计计算算思思维维大学计算机基础大学计算机基础2、计算科学计算科学与与计算学科计算学科 从计算的角度来看，从计算的角度来看，计算科学计算科学（Computational Science）又）又称之为称之为科学计算科学计算，是一种与数学建模、定量分析方法和采用计，是一种与数学建模、定量分析方法和采用计算机进行分析、解

19、决科学问题的研究领域。算机进行分析、解决科学问题的研究领域。从计算机的角度来说，从计算机的角度来说，计算科学计算科学(Computing Science)是应用是应用高性能计算能力预测和了解客观世界物质运动或复杂现象演化高性能计算能力预测和了解客观世界物质运动或复杂现象演化规律的科学，它包括数值模拟、工程仿真、高效计算机系统和规律的科学，它包括数值模拟、工程仿真、高效计算机系统和应用软件等。应用软件等。3、学科、学科 一是指学术的分类；指一定科学领域或一门科学的分支。一是指学术的分类；指一定科学领域或一门科学的分支。如自然科学中的物理学、化学；社会科学中的法学、社会学等。如自然科学中的物理学、

20、化学；社会科学中的法学、社会学等。二是二是 “教学科目教学科目”的简称，也称的简称，也称“科目科目”。教学中按逻辑程序。教学中按逻辑程序组织的一定知识和技能范围的单位。组织的一定知识和技能范围的单位。如中小学的数学、物理、语文、音乐等；高等学校中讲授或研如中小学的数学、物理、语文、音乐等；高等学校中讲授或研究知识的分科。究知识的分科。 第第一一章章 计计算算科科学学与与计计算算思思维维大学计算机基础大学计算机基础从计算的角度来说，从计算的角度来说，利用计算科学利用计算科学对其它学科的问题对其它学科的问题进行计进行计算机模拟算机模拟或者或者其它形式的计算其它形式的计算而而形成的学科形成的学科(诸

21、如计算化学、生诸如计算化学、生物计算或计算生物、计算物理等学科统物计算或计算生物、计算物理等学科统)称为称为计算学科计算学科(Computational Discipline)。从计算机的角度来说，从计算机的角度来说，计算学科计算学科(Computing Discipline)是是对描述和变换信息的算法过程对描述和变换信息的算法过程进行进行系统的研究系统的研究，它包括算法过，它包括算法过程的理论、分析、设计、效率分析、实现和应用等。程的理论、分析、设计、效率分析、实现和应用等。计算学科来源于对数理逻辑、算法理论、计算模型和自动计计算学科来源于对数理逻辑、算法理论、计算模型和自动计算机器的研究，

22、形成于算机器的研究，形成于20世纪世纪40年代。年代。 4、计算学科、计算学科 计算学科计算学科的的基本问题基本问题是是“什么能被什么能被(有效地有效地)自动执行自动执行”,讨论可行讨论可行性的有关内容，包括性的有关内容，包括:什么是什么是(实际实际)可计算的可计算的，什么是什么是(实际实际)不可不可计算的，计算的，如保证计算的自动性、有效性和正确性。如保证计算的自动性、有效性和正确性。计算学科计算学科是在是在数学和电子科学基础上发展起来的一门新兴学科，它既是一门深数学和电子科学基础上发展起来的一门新兴学科，它既是一门深入理论研究的学科，又是一门实践性很强的学科。入理论研究的学科，又是一门实践

23、性很强的学科。第第一一章章 计计算算科科学学与与计计算算思思维维大学计算机基础大学计算机基础计算学科计算学科包括：包括：计算机科学与技术计算机科学与技术(Computer science and technology)和和计算机科学与工程计算机科学与工程(Computer Science and Engineering) 5、计算机科学与计算机学科的关系、计算机科学与计算机学科的关系 计算机学科计算机学科(Computer Discipline),即计算机科学与技术，即计算机科学与技术，是研究计算机的设计与制造，利用计算机进行信息获取、表示、是研究计算机的设计与制造，利用计算机进行信息获取、表

24、示、存储、处理、控制等的理论、原则、方法和技术的学科。存储、处理、控制等的理论、原则、方法和技术的学科。它包括它包括科学科学和和技术技术两个方面。两个方面。计算机科学计算机科学侧重于研究现象和揭示规律；侧重于研究现象和揭示规律；计算机技术计算机技术侧重于研制计算机及使用计算机进行信息技术处侧重于研制计算机及使用计算机进行信息技术处理的方法和技术手段。理的方法和技术手段。 第第一一章章 计计算算科科学学与与计计算算思思维维大学计算机基础大学计算机基础计算机科学计算机科学分为分为理论计算机科学理论计算机科学与与应用计算机科学应用计算机科学两部分。两部分。理论计算机科学理论计算机科学包括计算理论、信

25、息与编码理论、算法与包括计算理论、信息与编码理论、算法与数据结构、程序设计语言理论、形式化方法、并行与分布计算数据结构、程序设计语言理论、形式化方法、并行与分布计算系统、数据库与信息检索等；系统、数据库与信息检索等；应用计算机科学应用计算机科学包括人工智能、计算机系统结构、计算机包括人工智能、计算机系统结构、计算机图形学、计算机视觉、计算机安全与密码学、信息科学与软件图形学、计算机视觉、计算机安全与密码学、信息科学与软件工程等。工程等。计算机人才的专业基本能力包括计算思维能力、算法分析计算机人才的专业基本能力包括计算思维能力、算法分析与设计能力、程序设计与实现能力、系统分析与应用开发能力。与设

26、计能力、程序设计与实现能力、系统分析与应用开发能力。但是，学科形态的不同，相应类型的人才需要强调的能力但是，学科形态的不同，相应类型的人才需要强调的能力是有区别的。比如，研究型人才强调的是理论形态的内容，培是有区别的。比如，研究型人才强调的是理论形态的内容，培养的重点在于强化计算思维分析能力、算法分析与设计能力、养的重点在于强化计算思维分析能力、算法分析与设计能力、系统分析设计能力；系统分析设计能力；工程应用型人才强调的是涉及形态的内容，培养的重点在工程应用型人才强调的是涉及形态的内容，培养的重点在于强化计算思维应用能力、系统分析与开发应用能力、程序设于强化计算思维应用能力、系统分析与开发应用

27、能力、程序设计与实现能力。计与实现能力。第第一一章章 计计算算科科学学与与计计算算思思维维大学计算机基础大学计算机基础6、计算学科的三个形态、计算学科的三个形态计算机科学与技术学科中的三个学科形态（理论、抽象和设计算机科学与技术学科中的三个学科形态（理论、抽象和设计）描述了该学科的研究与实践的三种形态，对应于计算机科计）描述了该学科的研究与实践的三种形态，对应于计算机科学与技术学科中问题求解的三个过程，也是学科方法论最根本学与技术学科中问题求解的三个过程，也是学科方法论最根本的内容。的内容。理论理论理论源于数学，其主要要素为定义、公理、定理证明和结果。理论源于数学，其主要要素为定义、公理、定理

28、证明和结果。即用定义和公理来表达被研究对象的特征，用定理来假设对象即用定义和公理来表达被研究对象的特征，用定理来假设对象之间的基本性质和对象之间可能存在的关系，通过证明来确定之间的基本性质和对象之间可能存在的关系，通过证明来确定这些关系是否成立，最后得出相应的结果这些关系是否成立，最后得出相应的结果(论论)。 抽象抽象 即抽出事物的本质特征，从现象中把握本质的认知过程和思即抽出事物的本质特征，从现象中把握本质的认知过程和思维方法。抽象的结果是概念、符号。抽象建模是自然科学之根维方法。抽象的结果是概念、符号。抽象建模是自然科学之根本。其主要要素为确定可能的实现环境并形成假设，构造模型本。其主要要

29、素为确定可能的实现环境并形成假设，构造模型并给出预测结果，设计实验并采集数据，进行试验结果分析。并给出预测结果，设计实验并采集数据，进行试验结果分析。第第一一章章 计计算算科科学学与与计计算算思思维维大学计算机基础大学计算机基础设计设计 设计设计源于工程科学，即广泛采用工程科学的研究方法来开发源于工程科学，即广泛采用工程科学的研究方法来开发或求解某个问题的系统和装备。在计算学科中，理论的主要要或求解某个问题的系统和装备。在计算学科中，理论的主要要素为需求分析、规格说明、设计和实现方法、测试和分析。素为需求分析、规格说明、设计和实现方法、测试和分析。 计算理论计算理论是研究使用计算机解决计算问题

30、的数学理论。是研究使用计算机解决计算问题的数学理论。它有它有3个核心领域个核心领域:自动机理论自动机理论、可计算性理论可计算性理论和和计算的复杂性理论计算的复杂性理论。自动机理论自动机理论是数理语言学中研究抽象自动机的理论。是数理语言学中研究抽象自动机的理论。抽象抽象自自动机是一种能够识别语言的动机是一种能够识别语言的抽象的装置抽象的装置.7、计算理论、计算理论请注意：请注意：它不是真正物理的机器，而是表示它不是真正物理的机器，而是表示计算机运算方式的计算机运算方式的抽象的逻辑关系系统抽象的逻辑关系系统，这，这样的抽象自动机可以用来检验输入的符号串样的抽象自动机可以用来检验输入的符号串是不是是

31、不是语言语言中合格的句子，如果是合格的句中合格的句子，如果是合格的句子，自动机就接收它，如果不是，就不接收子，自动机就接收它，如果不是，就不接收它。它。图示如下：图示如下： 第第一一章章 计计算算科科学学与与计计算算思思维维大学计算机基础大学计算机基础可计算性理论可计算性理论的中心问题是建立计算的数学模型的中心问题是建立计算的数学模型, 进而研究进而研究哪些是可计算的哪些是可计算的,哪些是不可计算的。哪些是不可计算的。它通过建立计算的数学模型它通过建立计算的数学模型(如抽象计算机如抽象计算机),精确区分精确区分哪些是哪些是可计算的可计算的，哪些是，哪些是不可计算的不可计算的。计算的过程就是执行

32、算法的过程。计算的过程就是执行算法的过程。可计算性理论的重要课题之一是将可计算性理论的重要课题之一是将算法精确化算法精确化。算法精确化算法精确化的途径很多的途径很多,其中之一是通过其中之一是通过定义抽象计算机定义抽象计算机,把把算算法法看作看作抽象计算机抽象计算机的的程序程序。通常把那些存在算法计算其值的函。通常把那些存在算法计算其值的函数叫做数叫做可计算函数可计算函数。因此。因此,可计算函数可计算函数的精确定义为：的精确定义为：能够在抽象计算机上编出程序能够在抽象计算机上编出程序,并计算其值的函数。并计算其值的函数。可计算性理论是算法设计与分析的基础可计算性理论是算法设计与分析的基础,也是计

33、算机科学的理也是计算机科学的理论基础。论基础。可计算性是函数的一个特性。设函数可计算性是函数的一个特性。设函数f的定义域是的定义域是D,值域是值域是R,如果存在一种算法如果存在一种算法,对对D中任意给定的值中任意给定的值X都能计算出都能计算出f(X)的值的值,则称函数则称函数f是可计算的。是可计算的。第第一一章章 计计算算科科学学与与计计算算思思维维大学计算机基础大学计算机基础例如例如: 若若M和和N是两个正整数是两个正整数,并且并且M=N时时,求求M和和N的最大公因数的的最大公因数的欧几里得算法可表示为：欧几里得算法可表示为： 步骤一：步骤一：【求余数求余数】以以N除除M得余数得余数R。步骤

34、二：步骤二：【余数为余数为0吗吗】若余数若余数R=0,计算结束计算结束,N即为答案；否即为答案；否则转到步骤步骤则转到步骤步骤3。步骤三：步骤三：【互换互换】把把M的值变为的值变为N,N的值变为的值变为R,重复上述步骤。重复上述步骤。 依照这依照这3条规则指示的步骤条规则指示的步骤,可计算出任何两个正整数的最可计算出任何两个正整数的最大公因数大公因数,可以把计算过程看成执行这些可以把计算过程看成执行这些步骤的序列步骤的序列。 计算过程是计算过程是有穷的有穷的, 计算的每一步都是计算的每一步都是能够机械实现能够机械实现的。的。为了精确刻画算法的特征为了精确刻画算法的特征,人们建立了各种各样的数学

35、模型。人们建立了各种各样的数学模型。计算机学科的三个过程计算机学科的三个过程(抽象、理论和自动化设计及实现抽象、理论和自动化设计及实现)中，最中，最根本的问题在是：根本的问题在是：如何描述问题如何描述问题?哪些部分能够被自动化哪些部分能够被自动化?如何进行自动化描述如何进行自动化描述? 建立物理建立物理符号系统符号系统并对其实施等价变并对其实施等价变换是计算机学科进行换是计算机学科进行问题描述和求解问题描述和求解的重要手段的重要手段。 可行性可行性所要求的所要求的形式形式化化及其及其离散特征离散特征使得数学成为重要使得数学成为重要的工具的工具,而计算模型无论方法还是工具而计算模型无论方法还是工

36、具等方面等方面,都表现出它在计算机上科学中都表现出它在计算机上科学中的重要作用。的重要作用。第第一一章章 计计算算科科学学与与计计算算思思维维大学计算机基础大学计算机基础计算的复杂性理论计算的复杂性理论研究的是算法的时间复杂性和空间复杂性。研究的是算法的时间复杂性和空间复杂性。在复杂性理论中在复杂性理论中,目标是把可计算的问题分成简单的和困难目标是把可计算的问题分成简单的和困难的。的。 1.41.4计算机与计算思维的关系计算机与计算思维的关系1、计算机促进计算思维的研究与发展、计算机促进计算思维的研究与发展 2、计算思维研究推动计算机的发展、计算思维研究推动计算机的发展 计算机对信息的处理快速

37、快、记忆力强的特点，使得原本只能理论上实现的过程，变计算机对信息的处理快速快、记忆力强的特点，使得原本只能理论上实现的过程，变成实际可行的实现过程。成实际可行的实现过程。 在对计算思维的广泛、深入研究过程中，逐步揭示出一些属于在对计算思维的广泛、深入研究过程中，逐步揭示出一些属于计算思维的特点，计算思维与理论思维、验证思维的差异越来计算思维的特点，计算思维与理论思维、验证思维的差异越来越明晰。计算思维的内容得到不断的丰富与发展。越明晰。计算思维的内容得到不断的丰富与发展。从思维的角度来说，计算科学主要研究计算思维的概念、方法从思维的角度来说，计算科学主要研究计算思维的概念、方法和内容，并发展成

38、为解决问题的一种思维方式，极大地推动了和内容，并发展成为解决问题的一种思维方式，极大地推动了计算思维的发展。计算思维的发展。第第一一章章 计计算算科科学学与与计计算算思思维维大学计算机基础大学计算机基础1.51.5计算学科的典型案例计算学科的典型案例【案例案例1】到底谁真话？到底谁真话？张三说张三说:李四在说谎李四在说谎;李四说李四说:王五在说谎王五在说谎;王五说王五说: 张三和李四都在说张三和李四都在说谎。谎。已知三人中只有一人说真话。根据以上的陈述，现在要问到底谁说已知三人中只有一人说真话。根据以上的陈述，现在要问到底谁说真话？真话？这是一个典型的逻辑推理命题。看上去好像跟计算沾不上边。实

39、这是一个典型的逻辑推理命题。看上去好像跟计算沾不上边。实际上利用穷举法求解，即把逻辑推理的叙述性命题数学化，再用计算际上利用穷举法求解，即把逻辑推理的叙述性命题数学化，再用计算机程序的自动化，把每一种可能情况中，满足条件的情况输出，就可机程序的自动化，把每一种可能情况中，满足条件的情况输出，就可求得命题的解。求得命题的解。首先可以考虑每个人说话的真假，用一个表达式来表示。首先可以考虑每个人说话的真假，用一个表达式来表示。设设Z、L、W分别代表张三、李四和王五，各自取值为分别代表张三、李四和王五，各自取值为0(或或False)时时表示说的是假话，取值为表示说的是假话，取值为1(或或True)时表

40、示说的是真话；时表示说的是真话；再用再用C代表说真话计数器，每当有说真话时，代表说真话计数器，每当有说真话时，C就加就加1。如果如果Z、L、W三人中只有一人说真话三人中只有一人说真话(即即Z+L+W=1) 并且并且C的值为的值为1，说明满足命题给定的前提条件。，说明满足命题给定的前提条件。此时可得出结论，即输出此时可得出结论，即输出Z、L、W各自的值。其中值为各自的值。其中值为1(True)的的就是说真话的人。就是说真话的人。第第一一章章 计计算算科科学学与与计计算算思思维维大学计算机基础大学计算机基础如第一句话如第一句话张三说张三说:李四在说谎李四在说谎;中的中的“李四在说谎李四在说谎;”用

41、数学式子表示为用数学式子表示为L=0(或或L=False),同时也表达了如果张三说的是真话，则同时也表达了如果张三说的是真话，则L=0(或或L=False)表达式表达式成立。成立。同理第二句话同理第二句话李四说李四说:王五在说谎王五在说谎; 中的中的“王五在说谎王五在说谎;” 用数学式子表示为用数学式子表示为W=0(或或W=False)；同时也表达了如果李四说的是真话，则同时也表达了如果李四说的是真话，则W=0(或或W=False)表达表达式成立。式成立。第三句话第三句话王五说王五说: 张三和李四都在说谎。张三和李四都在说谎。“张三和李四都在说谎张三和李四都在说谎”用数学式子表示为用数学式子表

42、示为Z=0 And L=0 (或或Z=False And L=False)；同时也表达了如果王五说的是真话，则同时也表达了如果王五说的是真话，则Z=0 And L=0 (或或Z=False And L=False)表达式成立。表达式成立。第第一一章章 计计算算科科学学与与计计算算思思维维大学计算机基础大学计算机基础第四句话第四句话已知三人中只有一人说真话。已知三人中只有一人说真话。即即Z、L、W中只有一个变量的值是中只有一个变量的值是1(或或False)。如果用如果用1和和0表示真假，则表达式表示真假，则表达式Z+L+W=1恰好可以表示三人中只恰好可以表示三人中只有一人说真话。有一人说真话。由

43、上分析、从计算思维的角度来考虑、分析，可把原来的推理命题由上分析、从计算思维的角度来考虑、分析，可把原来的推理命题转化为计算机求解的算法转化为计算机求解的算法第第一一章章 计计算算科科学学与与计计算算思思维维大学计算机基础大学计算机基础YesYesYesYesYesYesNoYes开始开始Z=0，L=0，W=0C=0Z+L+W=1?L=0?W=0?C=C+1C=C+1Z = 0 A n d L=0?C=C+1C=1?输出结果输出结果W=W+1W1?L1?L=L+1Z1?Z=Z+1结束结束Yes第第一一章章 计计算算科科学学与与计计算算思思维维大学计算机基础大学计算机基础【案例案例2】哥尼斯堡七

44、桥问题。哥尼斯堡七桥问题。有关有关图论图论研究的热点问题。研究的热点问题。18世纪初世纪初普鲁士普鲁士的哥尼斯堡的一个公园的哥尼斯堡的一个公园里，有一条名为里，有一条名为普雷格尔普雷格尔河穿过，河中有两个小岛河穿过，河中有两个小岛A和和 B，有七座桥，有七座桥把两个岛与河岸联系起来（如下右图所示）。把两个岛与河岸联系起来（如下右图所示）。有个人提出一个问题：一个步行者从这四块陆地中任一块出发，怎有个人提出一个问题：一个步行者从这四块陆地中任一块出发，怎样才能不重复、不遗漏地一次走完七座桥，最后回到出发点。后来样才能不重复、不遗漏地一次走完七座桥，最后回到出发点。后来大数学家欧拉大数学家欧拉(L

45、eonhard Euler，17071783)，把它转化成一个，把它转化成一个几何几何问题（如上左图）问题（如上左图）一笔画问题一笔画问题。证明上述走法是不可能的。证明上述走法是不可能的。他不仅解决了此问题，且给出了连通图可以一笔画的充分必要条件他不仅解决了此问题，且给出了连通图可以一笔画的充分必要条件是图是连通的，且奇顶点是图是连通的，且奇顶点(通过此点连线的条数是奇数通过此点连线的条数是奇数)的个数为的个数为0或或2.ACDB第第一一章章 计计算算科科学学与与计计算算思思维维大学计算机基础大学计算机基础欧拉的解法如下：欧拉的解法如下：每一块陆地考虑成一个点，连接两块陆地的桥以线表示。每一块

46、陆地考虑成一个点，连接两块陆地的桥以线表示。除了起点以外，每一次当一个人由一座桥进入一块陆地（或点）除了起点以外，每一次当一个人由一座桥进入一块陆地（或点）时，他（或她）同时也由另一座桥离开此点。时，他（或她）同时也由另一座桥离开此点。所以每行经一点时，计算两座桥（或线），从起点离开的线与所以每行经一点时，计算两座桥（或线），从起点离开的线与最后回到始点的线亦计算两座桥，因此每一个陆地与其他陆地最后回到始点的线亦计算两座桥，因此每一个陆地与其他陆地连接的桥数必为偶数。连接的桥数必为偶数。七桥所成的图形中，任何一点都不含有偶数条边，因此上述的七桥所成的图形中，任何一点都不含有偶数条边，因此上述的

47、任务无法完成。任务无法完成。 第第一一章章 计计算算科科学学与与计计算算思思维维大学计算机基础大学计算机基础1.5.11.5.1问题求解的基本步骤问题求解的基本步骤一般问题的求解可以归纳为六个主要步骤，即：一般问题的求解可以归纳为六个主要步骤，即：确定问题确定问题分析问题分析问题设计方案设计方案方案选择方案选择求解步骤求解步骤方案评价。方案评价。 确定问题确定问题:确定并明确解决什么。确定并明确解决什么。 分析问题分析问题: 分析并理解问题，了解该问题背后的相关知识。分析并理解问题，了解该问题背后的相关知识。 设计方案设计方案: 根据分析设计出多种方案，尽可能全面地列出备选方案。根据分析设计出

48、多种方案，尽可能全面地列出备选方案。 方案选择方案选择: 从中挑选最佳方案。从中挑选最佳方案。求解步骤求解步骤: 运用知识范围内的有限、分步的指令描述选定的方案的解决步骤。运用知识范围内的有限、分步的指令描述选定的方案的解决步骤。问题的解决步骤是有限的指令序列，按照这些指令的执行，才能达到最后的结果。问题的解决步骤是有限的指令序列，按照这些指令的执行，才能达到最后的结果。在计算机中，问题解决的步骤集合，称之为算法。在计算机中，问题解决的步骤集合，称之为算法。程序就是按照算法，用指定的计算机程序设计语言编写的用于求解问题的指令集程序就是按照算法，用指定的计算机程序设计语言编写的用于求解问题的指令

49、集合。程序中绝对不能使用任何人或机器都无法理解的指令。合。程序中绝对不能使用任何人或机器都无法理解的指令。 方案评价方案评价:通过方案的执行，检验它的结果正确与否，是否令人满意。通过方案的执行，检验它的结果正确与否，是否令人满意。如果结果错误或用户不满意，就必须对方案进行修改完善，甚至重新设计一套方案。如果结果错误或用户不满意，就必须对方案进行修改完善，甚至重新设计一套方案。第第一一章章 计计算算科科学学与与计计算算思思维维大学计算机基础大学计算机基础【案例案例3】皇帝会答应大臣的请赏？皇帝会答应大臣的请赏？古代皇帝和他的大臣下象棋，大臣赢了。皇帝问大臣：古代皇帝和他的大臣下象棋，大臣赢了。皇

50、帝问大臣：“你想你想要得到什么奖赏？要得到什么奖赏？”大臣向皇帝说：大臣向皇帝说：“微臣不敢奢求，只要皇微臣不敢奢求，只要皇上按棋盘的格子数，依次给予上按棋盘的格子数，依次给予1粒黄豆，粒黄豆，2粒黄豆，粒黄豆，4粒黄豆，粒黄豆，8粒黄豆，粒黄豆，16粒黄豆，粒黄豆，.按此规律按此规律 (每次给出黄豆的数目是前每次给出黄豆的数目是前一次给出黄豆数目的一次给出黄豆数目的2倍倍) 给给64次就无比地感谢皇上了次就无比地感谢皇上了”。请问。请问皇帝会答应这个大臣的请赏吗？皇帝会答应这个大臣的请赏吗？方案一、方案一、相信很多人经过对这个问题的理解、分析之后，会直相信很多人经过对这个问题的理解、分析之后