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

1 专题五计算思维与问题求解 计算机概论九讲 基于计算思维能力培养的 2 引导问题浅谈计算思维问题求解 第六讲计算思维与问题求解 3 导引问答题 一 对三杯不同颜色的水进行颜色深浅排序处理 你会怎么做 计算机又会怎么做 计算机为什么那样做 ABC 输入 输出 分析过程 可能的输入排列情况 分析过程 ABCT 第一步 交换 ABCT 第二步 交换 分析过程 ABCT 第三步 交换 分析过程 ABC 第三步 交换 最终结果 算法表示 开始 分别从键盘输入数值A B C 交换A B的值 T A A B B T 输出结果A B C 结束 A B 交换A C的值 T A A C C T A C A A B C 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 49 14 14 交朋友算法 计算思维 能力培养 32 不插电的计算思维 视频范例 交朋友算法 计算思维 能力培养 33 不插电的计算思维 视频范例 交朋友算法 计算思维 能力培养 34 不插电的计算思维 视频范例 交朋友算法 计算思维 能力培养 35 不插电的计算思维视频范例生活大爆炸第二季第14集 00 00 1 47 看电影算法 计算思维 能力培养 36 不插电的计算思维 视频范例 看电影算法 计算思维 能力培养 37 不插电的计算思维 视频范例 看电影算法 计算思维 能力培养 38 不插电的计算思维 视频范例 看电影算法 计算思维 能力培养 39 不插电的计算思维 视频范例 看电影算法 计算思维 能力培养 40 不插电的计算思维 视频范例 看电影算法 计算思维 能力培养 41 不插电的计算思维视频范例生活大爆炸第四季第1集机械手算法 00 00 2 00 计算思维 能力培养 42 不插电的计算思维 视频范例 机械手算法 计算思维 能力培养 43 不插电的计算思维 视频范例 机械手算法 计算思维 能力培养 44 不插电的计算思维 视频范例 机械手算法 计算思维 能力培养 45 不插电的计算思维 视频范例 机械手算法 计算思维 能力培养 46 不插电的计算思维 视频范例 机械手算法 计算思维 能力培养 47 不插电的计算思维视频范例生活大爆炸第四季第2集 00 00 2 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 18THENprint 工作时间 ELSEprint 下班时间 ENDIF 问题求解算法 算法语句 用计算机处理实际问题的过程也就是程序设计的过程 一是必须掌握一门程序设计语言 二是必须掌握程序设计语言中的基本算法和编程思想 算法语句 是计算机处理问题时的最基本核心语句 c c 1 称其为计数器 s s x 称其为累加器 p p x 称其为累积器 x x n 称其为累除器 t t 称其为正负号变换器 t a a b b t a b变量值交换 f 1 f 0 称其为标记器 p I 称其为跟踪器 问题求解算法 实现 用计算机处理实际问题的过程也就是程序设计的过程 一是必须掌握一门程序设计语言 二是必须掌握程序设计语言中的基本算法和编程思想 使用程序设计语言编制程序去解决实际问题 要经过问题的分析 算法的描述和程序设计等 在程序设计中 我们要考虑数据的类型 变量的定义 要用到算法语句 要考虑使用顺序结构 选择结构和循环结构来控制程序等等 最终将一个具体的实际问题用程序设计语言表示出来并由计算机去执行完成 问题求解算法 编程思想 计算机解决问题的方法思想与我们解决问题的传统习惯及想法是不一样的 这就要我们在学习程序设计时 去学会 去思考计算机的想法 逐步适应计算机的编程思想 即所谓的计算思维 问题求解算法归纳 算法归纳整合求两个数中的最大数求三个数中的最大数求N个数中的最大数交换两个数 排序 交换三个数 排序 交换N个数 排序 问题求解算法归纳 数学算法累加累乘 n以及n mn 多项式求和问题 拆数 数字重组 字符串重组 水仙花数 完数 同构数 回文数等 拆字符串 字符串重组 统计字符种类个数 进制转换问题 2 10 2 8 2 16 8 10 8 16 16 10 递推迭代算法 兔子繁殖问题 Fibonacci数列 穷举算法 百钱买百鸡 抓钱币游戏等 整除求余 素数判断问题 分解因子问题 辗转相除法 求两个整数的最大公约数和最小公倍数 最大数最小数问题 求N个数中的最大数和最小数 值的比较交换问题数组问题 冒泡排序算法 选择排序算法 顺序查找法 递归算法 问题求解算法归纳 根据下面给出的动画分析 画出问题求解的流程图或者伪代码具体可以参考 计算机基础案例解析指导教程 中的案例8 70 原始排列顺序 排序后的顺序 比较交换排序法 71 原始排列顺序 排序后的顺序 N个数的从小到大排序问题 72 第一轮比较 比较交换排序法 73 第一轮比较 比较交换排序法 74 第一轮比较 第一轮比较后的顺序 比较交换排序法 2020 3 18 75 可编辑 76 第二轮比较 比较交换排序法 77 第二轮比较 第二轮比较后的顺序 比较交换排序法 78 第三轮比较 第三轮比较后的顺序 比较交换排序法 79 第四轮比较 第四轮比较后的顺序 比较交换排序法 80 比较交换排序法 第四轮比较后的顺序 第四轮比较 81 最终排好的顺序 比较交换排序法 82 原始排列顺序 排序后的顺序 选择排序法 83 第一轮比较 排序后的顺序 选择排序法 84 第一轮比较 排序后的顺序 选择排序法 85 第一轮比较 排序后的顺序 选择排序法 86 第一轮比较 排序后的顺序 选择排序法 87 第一轮比较 排序后的顺序 选择排序法 88 第一轮比较结果 排序后的顺序 选择排序法 89 第二轮比较 排序后的顺序 选择排序法 90 第二轮比较 排序后的顺序 选择排序法 91 第二轮比较 排序后的顺序 选择排序法 92 第二轮比较 排序后的顺序 选择排序法 93 第二轮比较结果 排序后的顺序 选择排序法 94 第三轮比较 排序后的顺序 选择排序法 95 第三轮比较 排序后的顺序 选择排序法 96 第三轮比较 排序后的顺序 选择排序法 97 第三轮比较结果 排序后的顺序 选择排序法 98 第四轮比较 排序后的顺序 选择排序法 99 第四轮比较 排序后的顺序 选择排序法 100 排序后的顺序 选择排序法 最终排好的顺序 101 原始排列顺序 排序后的顺序 冒泡排序法 102 第一轮比较 冒泡排序法 103 第一轮比较 冒泡排序法 104 第一轮比较 冒泡排序法 105 第一轮比较 冒泡排序法 106 第一轮比较后得到最大的 第一轮比较后的顺序 冒泡排序法 107 第二轮比较 第一轮比较后的顺序 冒泡排序法 108 第二轮比较 冒泡排序法 109 第二轮比较 冒泡排序法 110 第二轮比较后得到次大的 第二轮比较后的顺序 冒泡排序法 111 第三轮比较 冒泡排序法 112 第三轮比较 冒泡排序法 113 第三轮比较后得到第三大的 第三轮比较后的顺序 冒泡排序法 114 第四轮比较 冒泡排序法 115 第四轮比较之后得到最小和次小 第四轮比较后的顺序 冒泡排序法 116 N个有求最大值问题 maximum minimum 117 N个有求最大值问题 118 123456789101112131415 N个数排序问题 119 123456789101112131415 N个有序数中查找指定数问题 120 折半查找法 123456789101112131415 TOP 1 BOTTOM 15 MIDDLE BOTTOM TOP 2 8 121 折半查找法 123456789101112131415 TOP 1 BOTTOM 15 MIDDLE BOTTOM TOP 2 8 122 折半查找法 123456789101112131415 TOP MIDDLE 1 9 BOTTOM 15 MIDDLE BOTTOM TOP 2 12 123 折半查找法 123456789101112131415 TOP MIDDLE 1 9 BOTTOM MIDDLE 1 11 MIDDLE BOTTOM TOP 2 10 124 折半查找法 123456789101112131415 TOP MIDDLE 1 11 BOTTOM MIDDLE 1 11 MIDDLE BOTTOM TOP 2 11 找到了 125 折半查找法 123456789101112131415 TOP 1 BOTTOM 15 MIDDLE BOTTOM TOP 2 8 126 折半查找法 123456789101112131415 TOP 1 BOTTOM 15 MIDDLE BOTTOM TOP 2 8 127 折半查找法 123456789101112131415 TOP MIDDLE 1 9 BOTTOM 15 MIDDLE BOTTOM TOP 2 12 128 折半查找法 123456789101112131415 TOP MIDDLE 1 13 BOTTOM 15 MIDDLE BOTTOM TOP 2 14 129 折半查找法 123456789101112131415 TOP MIDDLE 1 15 BOTTOM 15 MIDDLE BOTTOM TOP 2 15 当TOP BOTTOM还不等就意味着找不到 130 111121133114641 12345 12345 杨辉三角形 归纳