计算思维导论..ppt

计算机思维与程序设计 c 赵治国南华大学计算机学院 导论 说明教材大学计算机基础自学为主大学c c 语言程序设计基础课时第1学期 2 导论 26 c 理论 20 上机 考试第1 2学期末分别考试 笔试成绩笔试 70 平时成绩 30 具体要求了解计算机的组成 工作原理了解计算机的软 硬件系统掌握os和office办公软件的使用掌握一种程序设计语言的语法和基本的编程方法掌握一种程序设计工具的应用了解常用的算法和数据结构了解软件的基本开发过程和方法 第一章计算思维与程序设计 1 1计算思维1 2算法1 3程序设计1 4数制转换计算 某海军陆战队在原始森林进行为时一个月左右的生存实验 要求 一 每个队员除了身上穿的衣服外 随身只能带三件物品 每件物品不能超过二公斤 二 队员都是由飞机空降到半径为1000公里原始森林的中心地带 要求在一个月时间内从森林里走出来 问题 队员带哪三件物品合适 想一想 理想的答案 钢刀 火石 指南针人类要在世界上生存与发展要获取物质 能量 信息三大要素 在农业社会和工业社会中 物质和能源是主要资源 所从事的是大规模的物质生产 20世纪50年代 信息赶超上材料 能源成为影响人类社会发展的决定性力量 在信息社会中 信息成为比物质和能源更为重要的资源 生成 发布和使用信息成为重要的经济和文化行为 数字化生存 尼葛洛庞帝 negroponte 美国麻省理工学院教授及媒体实验室的创办人 1996年7月被 时代 周刊列为当代最主要的未来学家之一 计算不再只和计算机有关 它决定我们的生存 数字化生存的智慧 计算思维 一 计算改变了什么 二 什么是计算 三 什么是计算思维 1 计算改变科学家的思考方式 计算生物学改变着生物学家的思考方式计算博弈理论改变着经济学家的思考方式纳米计算改变着化学家的思考方式计算物理学改变着物理学家的思考方式数学机械化改变数学家的思考方式社会计算改变社会学家的思考方式 计算生物学 应用数据分析及理论的方法 数学建模和计算机仿真技术 来研究生物学 行为学和社会群体系统 计算经济学 运用计算思想分析和综合经济问题分析 模型 决策计算思想在诺贝尔奖获奖理论中占到70 以上的比例 计算考古学 人脸复原 2000年前的马王堆辛追夫人与3500年前的古埃及最美丽的王妃 妮菲蒂蒂 2 计算改变工作方式 数字化会议 数字化医疗 数字化教学 数字化制造 富士康的转型之路 机器人来了 富士康 百万机器人 计划 3 计算改变生活方式 智能家居 网络冰箱 监测食物收集菜谱知道你喜欢吃什么 20 从家信到视频聊天的变迁 烽火连三月 家书抵万金 海内存知己 天涯若比邻 拜年方式悄然演变 人类的智力面临挑战 15年前ibm的超级电脑 深蓝 击败世界国际象棋冠军加里 卡斯帕罗夫 这次ibm向人类的冠军发出挑战的超级电脑名叫 沃森 这部以ibm公司创始人名字命名的计算机 具备非常强大的计算功能 它登上了美国著名老牌智力游戏节目 危险边缘 挑战人类智力 挑战该节目的两名总冠军肯 詹宁斯和布拉德 鲁特尔 实现有史以来首次人机智力问答对决 深蓝 与 沃森 二 什么是计算 计算是人类文明最古老而又最时新的成就之一计算方法及计算工具不断地发展 对推动社会进步发挥了巨大作用计算的本质就是基于规则的符号串变换 手动计算工具时代 手动式计算工具 算筹图1 3手动式计算工具 算盘 机械式计算工具时代 法国著名数学家 物理学家 近代概率论的奠基者和他的计算工具 帕斯卡加法器1642年 机电计算工具时代 美国哈佛大学应用数学教授霍华德 艾肯和他的机电式计算机 marki 电子计算机时代 第一台电子数字计算机eniac eniac的发明人与制作人阿塔纳索夫 莫齐利 埃克特 天河一号 是我国首台千万亿次超级计算机 计算是基于规则的符号串变换 1 2 3 1 2 3 结合律 3 3 加法口诀 替换规则 6 加法口诀从一个已知的符号串开始 按照一定的规则 一步一步地改变符号串 经过有限步骤 最后得到一个满足预先规定的符号串 这种变换过程就是计算 三 什么是计算思维 笛卡尔 renedescartes 解析几何之父我思故我在思维是对某个问题或事物的思考过程以及产生的想法或见解思维是人脑对客观现实概括的和间接的反映 它反映的是事物的本质和事物间规律性的联系 思维是与时俱进的 人类的思维水平也必然随着认识工具的进步而逐步地由浅入深 由单纯到复杂 由片面至全面发展我们所使用的工具影响着我们的思维方式和思维习惯 从而也将深刻地影响着我们的思维能力计算无处不在的时代思维 计算思维 艾兹格 w 迪科斯彻 1930 2002 edsgerwybedijkstra 荷兰计算机科学家 荷兰leiden大学1972年获得图灵奖 例 在中央电视台的 幸运52 节目中 要求参与者快速猜出物品的价格 主持人出示某件物品 参与者每次估算出一个价格 主持人只能回答高了 低了或者正确 在某次节目中 主持人出示了一台价值在1000元以内的随身听 并开始了竞猜 下面是主持人和参与者的一段对话 如果你是参与者 你接下来会怎么猜 800元 高了 400元 600元 低了 高了 参与者 主持人 李咏 计算思维 猜猜猜 计算思维的定义 运用计算机科学的思想 方法和技术进行问题求解 系统设计 以及人类行为理解等涵盖计算机科学之广度的一系列思维活动 周以真 jeannettem wing 美国计算机科学家卡内基 梅隆大学教授acm与ieee会士 计算思维的核心是算法思维 为解决一个问题而采取的方法和步骤 就称为算法 算法 一个农夫带着一只狼 一只羊和一棵白菜 身处河南岸 要把东西全部运到北岸 约束条件是只有一条能容下他和一件物品的小船 只有农夫能撑船 不能单独留下羊和白菜 也不能单独留下羊和狼 例如 农夫过河算法 带羊到对岸空手回本岸带菜到对岸带羊回本岸带狼到对岸空手回本岸带羊到对岸 带羊到对岸空手回本岸带狼到对岸带羊回本岸带菜到对岸空手回本岸带羊到对岸 或 计算机算法的特性 1 有穷性 一个算法在执行有穷步之后必须结束 也就是说 一个算法 它所包含的计算步骤是有限的 2 确定性 算法的每一个步骤必须要确切地定义 即算法中所有有待执行的动作必须严格而不含混地进行规定 不能有歧义性 3 输入 算法有零个或多个的输入 即在算法开始之前 对算法最初给出的量 4 输出 算法有一个或多个的输出 即与输入有某个特定关系的量 简单地说就是算法的最终结果 5 可操作性 算法上描述的操作在计算机上都是可以实现的 算法效率 算法的效率可以通过复杂度来说明 分为时间复杂度和空间复杂度 时间复杂度 执行该算法所需要的计算工作量 一般用所需基本运算的执行次数来度量 空间复杂度 执行该算法所需的内存空间 问题 在242356768794129140有序数列中插入数据90使之依然保持有序需要多少次 采用算法思维求解问题分为以下几个基本步骤 问题的抽象 问题的符号化表示 问题求解的算法 算法的实现 计算思维 笼统地讲 是像计算机科学家一样思维 即像计算机科学家一样发现问题 分析问题并最终解决问题 其核心是算法思维 算法思维的最后一个步骤是实现算法 算法的实现是需要一定的步骤 程序就是算法步骤的一种体现 什么是程序 程序一词源于生活 做任何一件事情 都是有程序的 例如 颁奖大会的程序 做菜的程序等等 把做菜的步骤用大家看得懂的方式记录下来 其他人可以按这些步骤顺序实施就完成了该事情 程序 program 程序是为实现特定目标或解决特定问题而用计算机语言编写的指令序列 平常所说的各种软件就是由程序和数据构成的 程序设计 程序设计 programming 是给出解决特定问题程序的过程 是软件构造活动中的重要组成部分 程序设计往往以某种程序设计语言为工具 给出这种语言下的程序 程序设计语言 第一代机器语言 第二代汇编语言 第三代高级语言 vb c c java 第四代应用语言 powerbuilder delphi informox 4gl 第五代自然语言 计算5 6 8 00000001000000001000数据5装入寄存器000000001000100001010数据6装入寄存器100000101000000000001寄存器0与1的数据乘00000001000100001001数据8装入寄存器100000100000000000001寄存器0与1的数据加00000010000000001110保存寄存器0里的数38难写难读 使用不便 程序开发效率极低 最初的语言是机器语言 是二进制编码 机器可直接执行 汇编语言用简洁的英文字母 符号串替代一个特定的指令的二进制串 比如 用 add 代表加法 mov 代表数据传递等等 例 load0 5将单元5的数据装入寄存器0load1 6将单元6的数据装入寄存器1mult0 1寄存器0与1的数据乘load1 8将单元8的数据装入寄存器1add0 1寄存器0与1的数据加save0 d将寄存器0里的数存入单元d 38 高级语言实现一条语句 例 d 5 6 8高级语言程序必须经过翻译变成机器语言程序 翻译有两种做法 编译和解释 相应的翻译工具分别叫做编译器和解释器 四数制转换计算 位 bit 字节 byte 计算机存储容量的基本单位 计算机内部 一个字节可以表示一个数据 一个英文字母 两个字节可以表示一个汉字 8 bit 1 byte byte 字节1024 byte 1 kb kb 千字节1024 kb 1 mb mb 兆字节1024 mb 1 gb gb 千兆字节 二进制数的基本单位 字 word 计算机一次存取 加工 运算和传送的数据长度 一个字的二进制位数称为字长 字长一般为8的倍数 1 为什么字长一般为8的整数倍 进制是一种 量 的表示方式十进制0 9 逢十进位 的规则和一个小数点构成了一套完整的进制体系二进制 逢二进位 的进制0 1表示数据 数制表示 一个完整的数制是由基数 数位和权三要素构成的 基数指数制中用到的基本数字符号 数位指数字符号在一个数中所处的位置 而权指的是对应数位的基值 一个数据对应的量是该数的每一数位按进制权展开的数量的和 基数 基数个数进位值十进制0 9 10个10二进制0和1 2个2八进制0 7 8个8十六进制0 9及a b 16个16r进制r个r 1999 10 1 103 9 102 9 101 9 100 基数 权 101 11 2 1 22 0 21 1 20 1 2 1 1 2 2 权 十进制数转换为 进制数 整数 除 取余法 先得最低位 后得最高位 小数 乘 取整法 先得最高位 后得最低位 35 2 17 1 2 8 1 2 4 0 2 2 0 2 1 0 1 2 0 最高位 最低位 转换整数部分 例 将十进制数35 625转换为二进制数 十进制转换为二进制 35 10 100011 2 625 10 101 2 0 625 2 1 250 2 0 500 2 1 000 最高位 最低位 转换小数部分 35 625 10 100011 101 2 1 0 1 十进制转换为八进制 100 8 12 4 8 1 4 8 0 1 最高位 最低位 例 将十进制数100转换为八进制数 100 10 144 8 练习 19 10 2 207 10 8 10011 317 r进制转化成十进制r进制转化成十进制 数码乘以各自的权的累加例 10101 b 24 22 1 21101 11 b 22 1 2 1 2 2 5 75101 o 82 1 65101a h 163 16 10 4106 进制表示符号b二进制o八进制d十进制h十六进制 r进制转化成十进制 练习 365 2 8 10 3 82 6 81 5 80 2 8 1 245 25 10 二 八 十 十六进制数的对照表 转换原则 一位八进制数对应三位二进制数一位十六进制数对应四位二进制数 八进制和十六进制转化成二进制 举例说明 八进制和十六进制转化成二进制 练习 2c1d h b2c1d 7123 o b7123 111001010011 0010110000011101 转换方法 整数部分 从右向左进行分组 小数部分 从左向右进行分组 转化成八进制时三位一组 转化成十六进制时四位一组 不足补零 然后将对应的每一组转换为一位八进制或十六进制数 1101101110 110101 b 36f d4 h36fd4 1101101110 110101 b 1556 65 o155665 二进制转化成八进制和十六进制 后边补两个零 变成0100 前边补两个零 变成001 转换表八进制数二进制数八进制数二进制数00004100100151012010611030117111二进制数转换为八进制数举例 001101001110 110100 b 1516 64 o八进制数转换为二进制数举例 2467 32 o 010100110111 011010 b 八进制数与二进制数的转换 十六进制数与二进制数的转换 转换表十六进制数二进制数十六进制数二进制数0000081000100019100120010a101030011b101140100c110050101d110160110e111070111f1111二进制数转换为十六进制数举例 001101001110 11001100 b 34e cc h十六进制数转换为二进制数举例 35a2 cf h 0011010110100010 11001111 b 1100100 2 8 1100100 2 16 144 64 2数值数据的编码和运算 对于真值0 可认为它是正零 也可认为它是负零 0 原 00000000 0 原 10000000 1 机器数与真值将数的符号也数值化的数据称为机器数 而将原来由正负号表示的数值 称为机器数的真值 机器数的位数与字长有关 若字长为n位 符号占一位 数值部分为n 1位 机器数有原码 反码 补码三种编码形式 2 原码 反码 补码 正数 原 正数 反 正数 补 负数的反码规定为 把负数的原码除符号位之外的其它各位按位取反 x 原 11011011 x 反 10100100 负数的补码规定为 先求负数的反码 再把反码的最低位加1 x 原 11011011 x 反 10100100 x 补 10100101 特殊 0 反 00000000 0 反 11111111 补码表示的0有唯一的形式 0 补 0 补 00000000 减法运算与加法类似 可以看成负数的加 算术运算 加 减 乘 除 内在联系 乘法