专题五 计算思维与问题求解.ppt

1,专题五计算思维与问题求解,计算机概论九讲,基于计算思维能力培养的,2,引导问题浅谈计算思维问题求解,第六讲计算思维与问题求解,3,导引问答题（一）,对三杯不同颜色的水进行颜色深浅排序处理，你会怎么做？计算机又会怎么做？计算机为什么那样做？,ABC,输入：,输出：,分析过程,可能的输入排列情况,分析过程,ABCT,第一步：,交换：,ABCT,第二步：,交换：,分析过程,ABCT,第三步：,交换：,分析过程,ABC,第三步：,交换：,最终结果,算法表示,开始,分别从键盘输入数值A，B，C,交换A,B的值，T=A,A=B,B=T,输出结果A,B,C,结束,AB?,交换A,C的值，T=A,A=C,C=T,AC?,A,A,BC?,N,N,N,Y,Y,Y,交换B,C的值，T=B,B=C,C=T,程序代码实现,11,导引问答题（一）,计算机在解决处理问题时涉及到哪些软件与硬件的支撑概念？信息的输入输出信息的表示信息的存储信息的处理数据的描述控制结构计算方法高级语言程序设计环境与实现,12,导引问答题（二）,分析过程,分析过程,最终结果,算法表示,分析过程,18,引导问题浅谈计算思维问题求解,第六讲计算思维与问题求解,计算思维-定义,“我们所使用的工具影响着我们的思维方式和思维习惯，从而也将深刻地影响着我们的思维能力。”-1972年图灵奖获得者EdsgerDijkstra,计算思维-定义,回顾历史，不同的计算工具的发明与使用阶段，都会影响甚至决定这个时期的文化普识教育方向与趋势，都会约束和限制这个时期的科技创新与思维活动的能力，都会在这个时期留下属于这个工具时代的烙痕与印记。,计算思维-定义,计算思维（ComputationalThinking）是运用计算机科学的基础概念进行问题求解、系统设计以及人类行为理解等涵盖计算机科学之广度的一系列思维活动。,计算思维-定义,计算思维建立在计算过程的能力和限制之上，它是选择合适的方式去陈述一个问题，对一个问题的相关方面建模并用最有效的办法实现问题的求解，整个过程由人和机器协同配合执行。计算方法和模型使我们敢于去处理那些原本无法由任何个人独自完成的问题求解和系统设计。,计算思维-定义,计算思维直面机器智能的不解之谜：什么人类比计算机做得好？什么计算机比人类做得好？最基本的问题是：什么是可计算的？迄今为止我们对这些问题仍是一知半解。,计算思维-特征,是概念化而不是程序化的。计算机科学不仅仅是计算机编程。像计算机科学家那样去思维意味着远不止能为计算机编程，还要求能够在抽象的多个层次上思维；是根本而不是刻板的技能。根本技能是每一个人为了在现代社会中发挥职能所必须掌握的。刻板技能意味着机械的重复；,计算思维-特征,是人而不是计算机的思维方式。计算思维是人类求解问题的一条途径，但决非要使人类像计算机那样地思考。计算机枯燥且沉闷，人类聪颖且富有想象力。是人类赋予计算机激情。配置了计算设备，我们就能用自己的智慧去解决那些在计算机时代之前不敢尝试的问题，实现“只有想不到，没有做不到”的境界；,计算思维-特征,是数学和工程思维的互补与融合。计算机科学在本质上源自数学思维，因为像所有的科学一样，其形式化基础建筑于数学之上。计算机科学又从本质上源自工程思维，因为我们建造的是能够与实际世界互动的系统，基本计算设备的限制迫使计算机科学家必须计算性地思考，不能只是数学性地思考。构建虚拟世界的自由使我们能够设计超越物理世界的各种系统；,计算思维-特征,是思想而不是人造物。不仅仅是我们生产的软件硬件等人造物将以物理形式到处呈现，并时时刻刻触及我们的生活，更重要的是还将包含我们用以接近和求解问题、管理日常生活、与他人交流和互动的计算概念与思想；是面向所有人和所有地方。当计算思维真正融入人类的各种活动，而不再停留和表现为一种形式上的理论的时候，它就将成为一种现实。计算思维就是一个引导着计算机教育家、研究者和实践者的前沿理念，面向所有专业，而不仅仅是计算机科学专业的学生，引导我们怎么像计算机科学家一样去思维。,计算思维-能做什么,计算思维是每个人都应该具备的基本技能，不仅仅属于计算机科学家。我们应当在培养个人解析能力的同时，不但要掌握3R（-读Read、写wRite、算aRithmetic），还要学会计算思维。计算思维将计算机从工具到思维的发展提升到了适合于每一个人的一种普遍的认识和一类普适的技能。在一定程度上，这也意味着计算机科学从前沿高端到基础普及的转型。,计算思维-能做什么,计算思维可以化繁为简、化难为易计算思维是一种递归和并行处理计算思维采用了抽象和分解计算思维是恢复的一种思维计算思维利用启发式推理,30,不插电的计算思维在日常生活和游戏活动中体会理解计算机解决问题的方法和思路。趣例：老婆给当程序员的老公打电话：“下班顺路买一斤包子带回来，如果看到卖西瓜的，就买一只。”当晚，程序员老公手捧一只包子进了家门老婆怒道：“你怎么就买了一只包子？！”老公答曰：“因为看到了卖西瓜的。”（算法具有二义性，人应该可以理解，但不应该让自己变成刻板的机器人）,计算思维-能力培养,31,不插电的计算思维视频范例生活大爆炸第二季第13集（11：4914：14）交朋友算法,计算思维-能力培养,32,不插电的计算思维视频范例（交朋友算法）,计算思维-能力培养,33,不插电的计算思维视频范例（交朋友算法）,计算思维-能力培养,34,不插电的计算思维视频范例（交朋友算法）,计算思维-能力培养,35,不插电的计算思维视频范例生活大爆炸第二季第14集（00：001：47）看电影算法,计算思维-能力培养,36,不插电的计算思维视频范例（看电影算法）,计算思维-能力培养,37,不插电的计算思维视频范例（看电影算法）,计算思维-能力培养,38,不插电的计算思维视频范例（看电影算法）,计算思维-能力培养,39,不插电的计算思维视频范例（看电影算法）,计算思维-能力培养,40,不插电的计算思维视频范例（看电影算法）,计算思维-能力培养,41,不插电的计算思维视频范例生活大爆炸第四季第1集机械手算法（00：002：00）,计算思维-能力培养,42,不插电的计算思维视频范例（机械手算法）,计算思维-能力培养,43,不插电的计算思维视频范例（机械手算法）,计算思维-能力培养,44,不插电的计算思维视频范例（机械手算法）,计算思维-能力培养,45,不插电的计算思维视频范例（机械手算法）,计算思维-能力培养,46,不插电的计算思维视频范例（机械手算法）,计算思维-能力培养,47,不插电的计算思维视频范例生活大爆炸第四季第2集（00：002：00）计算寿命算法,计算思维-能力培养,48,不插电的计算思维视频范例（计算寿命算法）,计算思维-能力培养,49,不插电的计算思维视频范例（计算寿命算法）,计算思维-能力培养,50,不插电的计算思维视频范例（计算寿命算法）,计算思维-能力培养,51,不插电的计算思维视频范例（计算寿命算法）,计算思维-能力培养,计算思维-能力培养,象计算机科学家一样思考问题并解决问题，是当下或即将到来的时代的迫切呼唤与必然趋势。什么是可计算的？怎么去计算？这些问题将始终萦绕着我们的思绪。我们必须清楚和明白现有计算工具处理信息的原理、模式和方法，以及它所存在的局限和能力缺陷。发明创造、科技创新、寻求突破是人类不懈努力的动力与源泉。而培养和具备计算思维似乎成为实现这一切的重要前提和必备条件。,计算思维-能力培养,计算思维与数学基础构建计算机科学在本质上源自数学思维，它的形式化解析基础筑于数学之上。计算思维与计算机科学导论为了一开始就能对计算机科学的课程体系和知识体系有一个比较清晰的了解，必须站在计算思维的高度和广度来了解和掌握计算机学科的基本概念、基本方法和发展趋势，知晓学科的内涵和本质，将这一切作为计算机科学的导学。计算思维与思维能力的培养计算思维是人类求解问题的一条途径。过去，人们都认为计算机科学家的思维就是用计算机去编程，这种认识是片面的。计算思维不仅仅是程序化的，而是在抽象的多个层次上进行思维。,计算思维-能力培养,计算思维与应用能力的培养计算机科学又从本质上源自工程思维，因为我们建造的是能够与实际世界互动的系统。目前，计算机应用已经深入到各行各业，融入人类活动的整体，解决了大量计算时代之前不敢解决的问题。计算思维与创新能力的培养创新是一个民族生存、发展和进步的原动力。计算思维能力的培养对我们每个人的创新能力的培养是至关重要的。创新要靠科学素养和理解科学，靠科学的思想方法。,55,引导问题浅谈计算思维问题求解,第六讲计算思维与问题求解,问题求解算法概述,程序设计就是通过分析问题、确定算法、编程求解等步骤来解决问题的过程，其中，算法具有重要的作用，它能够提供一种思考问题的方向和方法。在计算机中，把解决具体问题的过程准确完整地描述出来就形成解决该问题的算法。,问题求解算法要素,一个算法是由操作与控制结构两个要素组成。操作计算机最基本的操作有：算术运算关系运算逻辑运算数据传送控制结构各操作之间的执行顺序为算法的控制结构顺序结构选择结构循环结构,问题求解算法性质,算法的性质一般归纳为下列五点：输入要求若干个信息的输入；有穷性任意一个算法在执行有限个计算步骤后必须终止；可行性有限个步骤应该在一个合理的范围内进行；确定性每一个计算步骤，必须是精确地定义、无二义性；输出有若干个输出信息即处理结果.,问题求解算法描述方法,为了描述算法，可以使用多种方法。自然语言用自然语言表达算法，就是把算法的各个步骤，依次用人们所熟悉的自然语言表示出来。伪代码用一些介于自然语言与高级语言之间的符号语言表达算法，依次用人们所熟悉的并简洁的方式表示出来。流程图流程图是用一些图框、线条以及文字说明来形象地、直观地描述算法。计算机语言计算机无法识别和执行自然语言、流程图、伪代码。这些方法只是为了帮助人们描述、理解算法，要用计算机解决问题，就要用计算机程序设计语言来描述算法。,问题求解算法描述方法,自然语言用自然语言表达算法，就是把算法的各个步骤，依次用人们所熟悉的自然语言表示出来。1、如果时间在九点以前，那么处理私人事务；2、否则如果时间在9点到18点之间，那么工作时间；3、否则下班时间;4、判断结束,问题求解算法描述方法,伪代码用一些介于自然语言与高级语言之间的符号语言表达算法，依次用人们所熟悉的并简洁的方式表示出来。确定时间IF九点以前THENdo私人事务；ELSEIF9点到18点THEN工作；ELSE下班;ENDIF,问题求解算法描述方法,流程图流程图是用一些图框、线条以及文字说明来形象地、直观地描述算法。,问题求解算法描述方法,计算机语言计算机无法识别和执行自然语言、流程图、伪代码。这些方法只是为了帮助人们描述、理解算法，要用计算机解决问题，就要用计算机程序设计语言来描述算法。Dimtasintegert=val(inputbox(“t=“)IFt=9andt?,?,?,=BOTTOM还不等就意味着找不到！,=?,129,111121133114641,12345,12345,杨辉三角形,归纳整理输出N行N列的杨辉三角形的算法（要求用一维数组实现）,11112113311464115101051,123456,123456,130,111121133114641,12345,12345,杨辉三角形,X(1)=1,x(2)=0,x(3)=0,x(4)=0,x(5)=0X(1)=1,x(2)=1,x(3)=0,x(4)=0,x(5)=0X(1)=1,x(2)=2,x(3)=1,x(4)=0,x(5)=0X(1)=1,x(2)=3,x(3)=3,x(4)=1,x(5)=0X(1)=1,x(2)=4,x(3)=6,x(4)=3,x(5)=1,归纳整理输出N行N列的杨辉三角形的算法（要求用一维数组实现）,假设有n行，如果i=(n-1)2,x(i)=x(i-1)+x(i),131,111121133114641,12345,12345,杨辉三角形,X(1,1)=1,x(1,2)=0,x(1,3)=0,x(1,4)=0,x(1,5)=0X(2,1)=1,x(2,2)=1,x(2,3)=0,x(2,4)=0,x(2,5)=0X(3,1)=1,x(3,2)=2,x(3,3)=1,x(3,4)=0,x(3,5)=0X(4,1)=1,x(4,2)=3,x(4,3)=3,x(4,4)=1,x(4,5)=0X(5,1)=1,x(5,2)=4,x(5,3)=6,x(5,4)=3,x(5,5)