Python程序设计实践 课件 ch02 问题求解与计算思维

第二章问题求解与计算思维浙江省普通本科高校“十四五”重点教材Python程序设计实践教程01计算概述PARTONE1.几何法时期：割圆术最早计算圆周率的方法是割圆术。魏晋时期的数学家刘徽首创割圆术，为计算圆周率建立了严密的理论和完善的算法。所谓割圆术，就是不断倍增圆内接正多边形的边数，求出圆周率。刘徽从圆内接正6边形开始，每次都把边数加倍，直至圆内接正96边形，算得圆周率为157/50（即3.14）。后来，他在此基础上又计算出了圆内接正3072边形的面积，得到圆周率的近似值为3927/1250（即3.1416）。南北朝时期的数学家祖冲之进一步求出了圆内接正12288边形和圆内接正24576边形的面积，得出3.1415926<π<3.1415927。在之后的800年里，祖冲之计算出的圆周率是最准确的。2.解析法时期：无穷级数分析法割圆术的烦琐计算促使人们探索新的计算方法，通过无穷乘积、无穷连分数、无穷级数等各种计算方法，圆周率的计算精度迅速增加。1706年，英国数学家梅钦率先将圆周率突破百位。1948年，英国的弗格森和美国的伦奇共同发表了π的808位小数值，成为人工计算圆周率的最高纪录。

【例2-1】格里高利公式求圆周率利用格里高利公式（）求圆周率。3.计算机时期：蒙特卡罗法计算机的出现使圆周率的计算速度和精度有了突飞猛进的发展。2011年10月16日，日本长野县饭田市公司的职员近藤茂利用家用计算机将圆周率计算到小数点后10万亿位。图2-2圆及其外接正方形画一个圆的外接正方形，假设圆的半径是1，那么圆的面积是π，外接正方形的面积是4，如图2-2所示。任意产生正方形内的一个点，该点落在圆内的概率=圆面积/正方形面积，即π/4。3.计算机时期：蒙特卡罗法蒙特卡罗法利用了概率统计的思想，使用随机数来解决计算问题。随着实验次数增多，会出现概率收敛，计算值会更好地逼近精确解，这使求得的解是可以接受的。蒙特卡罗法在金融工程学、宏观经济学、计算物理学等领域中有着广泛的应用。蒙特卡罗法利用了概率统计的思想，使用随机数来解决计算问题。随着实验次数增多，会出现概率收敛，计算值会更好地逼近精确解，这使求得的解是可以接受的。蒙特卡罗法在金融工程学、宏观经济学、计算物理学等领域中有着广泛的应用。02求解计算机问题PARTTWO1.计算机解题的特性日常生活中有许多应用顺序流程的例子，炒菜时要根据一定的次序投放食材与调味品；网络购物时要通过规定的步骤完成购物过程，如选择商品、填写数据、付款等；使用自动提款机进行交易时，需要依次完成插卡、输入密码、选择金融交易方式、输入金额等步骤。

当我们要解决的问题比较复杂时，可以将大问题分成几个较小的问题，再设计较小问题的解决方案。计算机解题的特性是根据所设计的步骤按顺序执行，每次执行都会获得一致的结果。由于垂直式思维的推理结论具有正确性、系统性、普遍性，所以大部分步骤能转换成可以执行的步骤。2.计算机解题的应用（1）科学计算

科学计算是计算机应用的一个重要领域，如高能物理、工程设计、地震预测、气象预报、航天技术等。同时，由于计算机具有很高的运算速度、精度及逻辑判断能力，出现了计算力学、计算物理、计算化学、生物控制等新学科。（3）计算机辅助系统

计算机辅助系统包括计算机辅助设计（CAD）、计算机辅助工艺过程设计（CAPP）、计算机辅助制造（CAM）、计算机辅助教学（CAI）等。（2）数据处理

数据处理是指通过计算机获取、加工、处理各种数据及数据可视化，提高管理效率，如管理信息系统（MIS）、物资需求计划（MRP）、企业资源计划（ERP）、制造执行系统（MES）、电子商务系统等。2.计算机解题的应用（4）生产自动化

生产自动化包括工业流程控制、流水线控制、无人工厂等。（6）生活出行

网络信息资源的深层次利用和网络应用的日趋大众化正在改变着我们的工作方式和生活方式。（5）人工智能

生产自动化包括人脸识别、药物研发、机器人、交通等场景应用。3.计算机解题的基本步骤问题分析与建模1对现实问题进行分析、抽象，建立相应的数学模型，把对现实问题的求解转化为对抽象数学模型的求解，满足计算机处理问题的特点和基本要求。问题分析与建模时首先要确定问题的逻辑结构和基本功能，然后在结合数学、物理、计算机等的基础上，建立相关数学模型。数学建模是一种数学思考方法，是指运用数学语言和方法，通过抽象、简化建立能近似刻画并解决实际问题。3.计算机解题的基本步骤算法设计与实现2算法设计与实现是指设计解决某一特定问题或某一类问题的一系列步骤，并且要求这些步骤可以通过计算机的基本操作来实现。算法设计完成后，要将其表示成计算机语言，从而能够通过计算机来解决现实中的具体问题。算法分析3算法分析是指对所设计算法的性能特征进行分析、评价和总结。03计算思维PARTTHREE1.思维和思维过程

思维（Thinking）是人类对情感、信息处理过程的一种概括和抽象，是一种心理活动的反映，是人脑从对客观事物的直接感知过渡到抽象思维的升华，反映了客观事物的本质与规律。思维是通过一系列比较复杂的操作来实现的，如分析与综合、比较、抽象与概括等，通常具有概括性、间接性、能动性三大特性。1.思维和思维过程（1）概括性在人的感性基础上，将一类事物的共同特性和本质规律抽象出来，加以归纳与概括。例如，人类通过长期对地球气候和植物生长规律的观察，总结出了二十四节气与种植时节。（2）间接性将非直接的事物作为媒介，来反映事物的特征或规律。例如，医生根据医学知识和临床经验，结合病人的症状和化验结果，推断出病人的病情。（3）能动性思维不仅能认识和反映客观规律，而且能改造客观世界。例如，人类认识了万有引力，还发射了人造卫星、太空飞船。2.科学思维传统的科学研究手段理论研究和实验研究，计算则是两种研究的一种辅助手段。随着计算技术和计算机技术的迅速发展，计算已上升为科学研究的一种手段，它直接并有效地为科学研究服务。科学思维（ScientificThinking）理论认识及其过程，即通过整理和改造感性阶段获得的大量材料，形成概念、判断、推理，反映事物的本质和规律。2.科学思维理论思维（TheoreticalThinking）又称为逻辑思维1通过抽象和概括，描述事物的本质，用科学的方法探寻概念之间的联系。它以推理和演绎为特征，以数学学科为代表。通过观察和实验获取自然规律、法则的一种思维方法。它以观察和归纳自然规律为特征，以物理学科为代表。实验思维（ExperimentalThinking）又称为实证思维22.科学思维计算思维（ComputationalThinking）又称为构造思维3从具体的算法设计规范入手，通过算法过程的构造与实施来解决特定问题。它以设计和构造为特征，以计算学科为代表。3.理解计算思维

计算思维的认识过程计算思维的定义计算思维的特征计算机科学与计算思维010203044.计算思维的应用计算生物学1计算生物学是生物学的一个分支，用于开发和应用数据分析及理论、数学建模、计算机仿真等，并应用于生物学、行为学、社会群体研究的一门学科，如基因测序、蛋白质结构预测等。4.计算思维的应用计算化学2计算化学主要用计算机程序和方法对特定的化学问题进行研究，如数值计算（量子化学和结构化学中的演绎计算、分析化学中的条件模拟、化工过程中的应用计算等）、化学模拟、模式识别等。4.计算思维的应用计算数学3计算数学也叫作数值计算方法或数值分析，如数值计算和分析、系统建模和仿真、数字信号处理、数据可视化、财务与金融工程计算、软件机器人等。4.计算思维的应用其他学科领域4许多其他学科通过抽象建模，将研究从定性分析转化为定量研究，将计算思维应用于经济学、管理科学、法学、文学、艺术、体育等社会科学领域。计算思维改变了各学科领域的研究模式，如计算机博弈论改变了经济学家的思考方法。1994年诺贝尔经济学奖授予约翰·纳什（JohnNash）、莱茵哈德·泽尔腾（ReinhardSelten）、约翰·海萨尼（JohnC.Harsanyi）三位博弈论专家，他们有力地证明了博弈论在现代经济学中的地位。5.为什么要倡导计算思维计算思维就是用计算机科学解决问题的思维，它是每个人都应该具备的基本技能，不仅仅属于计算机科学家。计算思维训练对计算机应用人才的培养是极为重要的，它不仅能使学生理解计算机的实现机制和约束条件，有利于学生进行发明和创新，更重要的是有利于提高学生的信息素养，也就是处理计算机问题时应有的思维方法、表达形式、行为习惯。因此，提高计算机基础教学的质量，增强学生的计算思维能力，是培养应用型、创新型人才的必然要求。尽管计算机科学不等于程序设计，但不可否认的是，学习程序设计方法是理解计算机的最好途径。编程思维是无止境的，不同问题有不同的分析方法、算法、代码实现方法。在教学中有意识地引导学生多视角、多方位地进行编程思考，会使学生的思维能力得到跳跃式扩展和提高。（1）计算思维与数学基础的构建计算机科学在本质上源于数学思维，它的形式化解析基础筑于数学之上。（2）计算思维与计算机科学导论的学习为了对计算机科学的课程体系和知识体系有比较清晰的了解，必须站在计算思维的高度和广度来了解和掌握计算机学科的基本概念、基本方法、发展趋势，知晓学科的内涵和本质，将其作为计算机科学的导学部分。6.如何培养和训练计算思维（3）计算思维与思维能力的培养计算思维是人类求解问题的一条途径。过去，人们认为计算机科学家的思维就是用计算机去编程，这种认识是片面的。计算思维不仅是程序化的，而是在抽象的多个层次上进行思维。（4）计算思维与应用能力的培养目前，计算机应用已经深入到各行各业中，融入人类活动中，解决了大量计算时代之前无法解决的问题。（5）计算思维与创新能力的培养创新是一个民族生存、发展和进步的原动力。计算思维的培养对创新能力的培养至关重要，创新要靠科学素养和理解科学，靠科学的思想方法。6.如何培养和训练计算思维04算法PARTFOUR1.算法及其描述算法概述1算法解决特定问题的方法或步骤，或者说，算法是为解决一类特定问题而设计的确定的、有限的操作步骤。算法是程序设计的关键，找不到算法就无法编写计算机程序，也就无法用计算机来解决问题。广义上

算法是指通过运算的方式，按照某种机械的步骤逐步求解问题。狭义上

算法是解决一个问题采取的方法和步骤的描述，如图2-8所示。图2-8狭义的算法1.算法及其描述算法的分类2不是所有算法都适合在计算机上执行，能在计算机上执行的算法就是计算机算法。计算机算法可以分为两类：一类是数值算法，另一类是非数值算法。1.算法及其描述算法的特性3（1）有穷性一个算法必须在执行有限个计算步骤后终止。（2）确定性一个算法给出的每个计算步骤都必须是精确定义、无二义性的。（3）有效性算法中的每个步骤都必须被有效地执行，并能得到确定的结果。（4）有零个或多个输入信息一个算法可以没有输入信息，也可以有一个或多个输入信息，这些输入信息是算法的初始数据。（5）有一个或多个输出信息一个算法应有一个或多个输出信息，没有输出信息的算法是没有意义的。1.算法及其描述如何发现算法4（1）第一阶段：分析、理解、抽象、归纳问题。（2）第二阶段：寻找一个可能解决问题的思路。（3）第三阶段：用数学语言将其表达出来。（4）第四阶段：阐明算法并选用合适的数据结构，用程序将其编写出来。（5）第五阶段：评估算法的准确度以及算法是否有潜力作为一个解决问题的工具。2.算法的表示形式自然语言1自然语言就是人们日常使用的语言，可以是汉语、英语或其他语言。用自然语言表示算法的优点是通俗易懂，缺点是文字冗长，容易出现歧义性。伪代码2伪代码是介于自然语言和计算机语言之间的文字和符号（包括数学符号），如同写一篇文章，自上而下地写下来，每一行（或几行）表示一个基本操作。伪代码不使用图形符号，因此书写方便、格式紧凑，也比较易懂，便于向计算机语言程序转换。2.算法的表示形式流程图3流程图是一种传统的算法表示方法，它使用不同的几何图形框来代表不同性质的操作，用流程线来指示算法的执行方向。流程图直观形象、易于理解，所以应用广泛。05数据结构PARTFIVE1.数据结构的定义数据结构（DataStructure）计算机存储、组织数据的方式，是指相互之间存在一种或多种特定关系的数据元素的集合。数据结构主要包括数据的逻辑结构、数据的物理（存储）结构、数据的运算结构。2.常用的数据结构（1）数组（Array）在程序设计算法中，为了处理方便，把具有相同类型的若干变量有序地组织起来，这些按序排列的同类数据元素的集合称为数组。数组是n（n>1）个相同类型的数据元素a0，a1，…，an-1构成的有限序列，该有限序列存储在一块地址连续的内存单元中，可以把它看作一种长度固定的线性表。（2）栈（Stack）栈是只能在某一端插入和删除数据的特殊线性表。它按照“先入后出”的原则存储数据，先进入的数据被压入栈底，最后进入的数据在栈顶，读取数据时从栈顶开始弹出数据（最后进入的数据第一个被读取），如图2-11所示。特点：先入后出、后入先出；除了头、尾节点，每个节点都有一个后继和一个前驱。2.常用的数据结构（3）队列（Queue）队列是一种特殊的线性表，它只允许在表的前端（Front）进行删除操作，以及在表的后端（Rear）进行插入操作。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列是按照“先入先出”和“后入后出”的原则组织数据的。队列中没有元素时称为空队列。特点：先入先出，后入后出；除了尾节点，每个节点都有一个后继；除了头节点，每个节点都有一个前驱。（4）链表（LinkedList）链表是一种物理存储单元上非连续、非顺序的存储结构，它既可以表示线性结构，也可以表示非线性结构。数据元素的逻辑顺序是通过链表中的指针链接次序实现的。每个节点包括两部分，一是存储数据元素的数据域，二是存储下个节点地址的指针域。2.常用的数据结构（5）树（Tree）树是由n（n≥0）个节点组成的有限集合，若n=0，称为空树；若n>0，则满足以下两个条件。①有一个特定的称为根（Root）的节点，它只有直接后继，但没有直接前驱。②除根节点以外的其他节点可以划分为m（m≥0）个互不相交的有限集合（T0,T1,…,Tm-1），集合Ti（i=0,1,…,m-1）又是一棵树，称为根的子树。（6）图（Graph）图由节点的有穷集合V和边的集合E组成。为了与树形结构加以区别，在图结构中常将节点称为顶点，边是顶点的有序偶对。如果两个顶点之间存在一条边，就表示这两个顶点具有相邻关系。图被广泛应用于各个领域，可以解决很多实际问题。图的应用有求最短路径、拓扑排序、关键路径等。06算法评价PARTSIX1.算法的评价标准（1）正确性：算法的执行结果应当满足规定的功能和性能要求。（2）可读性：算法应当思路清晰、层次分明、简单明了、易读易懂。（3）健壮性：算法应具有对不合理数据的反应能力和处理能力，也称为容错性。。（4）高效性：算法应有较高的时间效率。（5）低存储量需求：存储量是指算法执行过程中需要的最大存储空间，即有效使用存储空间。2.时间复杂度算法的时间复杂度（TimeComplexity）是指算法运行的时间，是算法所求解的问题规模n的函数，通常记为T(n)。时间复杂度是算法的时间代价，用执行算法所需的基本操作（原操作）次数来描述，以基