程序设计思想与方法

程序设计思想与方法 2 课程信息 教材 程序设计思想与方法 问题求解与计算思维 陆朝俊 高教出版社 2013参考书PythonProgramming AnIntroductiontoComputerScience 电子版 HowtoThinkLikeaComputerScientist LearningwithPython 电子版 Python学习手册第4版 原版 LearningPython 3 课程信息 下载python软件的地址PurdueUniversity的课件地址 cs190c textsoft09 4 教学方式 课堂教学 每星期四3 4节讲课 演示机房上机单周 3 15周 共7次 周一1 2节 电院4号楼313教室完成当天上机作业并提交答疑 5 考核方式 期末考试笔试 占最终成绩的50 平时作业上机作业 章节后的作业ftp上传给助教 占最终成绩的40 自选作业编一个大程序 期末提交 占最终成绩的10 第1章计算与计算思维 问题的提出 当今时代 计算机几乎无处不在 企业管理产品设计气象预报电影制作工业控制游戏 写文章 上网 问题 计算机究竟是什么 怎么能做这么多不同的事情 7 8 计算机 硬件 1 9 计算机 硬件 2 中央处理器 CPU 执行指令每条指令只能完成简单的操作 例如 加法 比较 移动 etc 但按一定的次序执行大量简单指令能完成复杂任务 存储器 存储信息 程序和数据 主存 CPU能直接访问 速度快但易失次级存储器 速度慢但持久输入 输出设备 人机交互 9 10 10 10 10 计算机 软件 计算机是信息处理机器 信息处理过程由预定的程序控制 单条指令是做不了什么事情的 需要大量指令组成一个逐步执行的指令序列 即程序 各种程序统称为计算机软件 没有软件的计算机毫无用处 11 计算 计算 利用计算机执行程序来解决问题 不是狭义的数学计算 程序使得简单指令能完成复杂任务 问 只会加法的小学生能完成乘法运算任务吗 答 能 关键是编写合适的程序在纸上写下0 记住结果 给所记结果加上第1个n 记住结果 给所记结果加上第2个n 记住结果 给所记结果加上第m个n 记住结果 报告结果 即m n 11 12 12 12 通用计算机 计算机是具有如下特征的机器 能够存储和处理信息输入 处理 输出信息处理由程序控制计算机程序是一个详细的逐步执行的指令序列 告诉计算机该做什么程序可改变 不同的程序完成不同的处理任务计算机执行一个程序即可实现一个功能 换着执行不同的程序即可实现不同的功能 人们造了各种各样的计算机 但 所有计算机具有相同的能力 13 计算机科学 并非研究计算机 计算机之于计算机科学家正如望远镜之于天文学家 E W Dijkstra CS研究计算的基础 实现与应用 例如 CS的一个基本问题 什么是可计算的 本课程的目标 像计算机科学家一样思考 13 14 程序设计 计算的关键是程序设计 编程 给定一个问题 利用计算机支持的简单操作 设计出一个操作步骤的序列 计算机执行这个序列从而解决问题 学习程序设计的好处 做计算机的主人提高问题求解能力本身是很有乐趣的智力活动 15 程序设计语言 问 用什么语言告诉计算机做什么 答 用精确无歧义的程序设计语言 精确的语法和语义 形式和意义 15 16 程序设计语言 有不同层次的程序设计语言计算机的 母语 机器语言例如 00001 是Intel8086能理解的一条指令将机器语言用助忆符表示 汇编语言上例即 ADDAL 1 需要汇编器处理后机器才懂适合人用的语言 高级语言如 x y 1 需要编译器或解释器翻译后机器才懂 16 高级语言 高级程序设计语言有很多种 据说2008年网上被引用最多的10个语言是 按字母顺序 C C C Java JavaScript Perl PHP Python Ruby SQL 17 18 程序设计语言 高级语言的翻译编译源代码编译成目标代码 再执行一次编译 多次执行 解释源代码直接被解释执行每次执行都要重新解释 18 19 编译vs解释 思考 为什么高级语言程序具有可移植性 即同一个程序可以在不同厂商的计算机上执行 Python Python采用编译 解释混合方式先编译成字节码 再解释执行安装Python2 x与新的Python3 x有不兼容的地方启动Python 20 21 算法与编码实现 程序设计先用非形式化的语言将问题求解步骤表达出来 算法 伪代码再用形式化的编程语言将上述算法实现 程序代码 22 算法例 欧几里德算法 欧几里德算法 求最大公约数 输入 自然数a b输出 a b的最大公约数步骤 第1步 令r为a除以b所得余数第2步 若r 0 则算法结束 b即为答案否则置a b b r 转到第1步 23 对算法的要求 算法的每个步骤必须是明确的 可行的 不明确 在菜中放点盐 不可行 用青菜豆腐做出龙肝凤髓的美味 每个步骤不必是最底层的琐细步骤 可以是组合的高级步骤 如 焯水 算法的所有步骤必须在有限时间内完成 我们说的计算 即是指 算法计算 用明确可行的基本步骤组成的序列来解决问题 24 24 计算思维 计算思维 computationalthinkin计算机科学家利用计算机 计算过程 解决问题时的思想和方法计算机科学 CS 是关于 计算 的科学如何像计算机科学家一样思考 25 真的有计算思维吗 人们在解决不同问题时有不同的思考方式数学思维 解数学问题工程思维 工程设计形象思维 文学创作 计算思维 建立在计算机的能力与局限之上 由于计算机的广泛应用 计算思维未来会成为人们的基本能力 与阅读 书写 算术能力一样 26 计算思维例 问题表示 问题的表示 建模 抽象 将现实中的各种数量关系 空间关系 处理过程抽象为计算机的数据结构和控制结构例如 温度数据抽象为数值还是文字 不同抽象层次问题表示得合适与否直接影响问题的解法的发现和效率 27 计算思维例 算法设计 化难为易 分解 约简 嵌入 转换 模拟 分治法 递归法 贪心法 动态规划 递归地思考并行处理 28 计算思维例 编程实现 类型系统与类型检查结构化与模块化的思考编程范型 过程式 面向对象 函数式 程序美学 系统设计的简洁与优雅 29 计算思维例 计算理论 算法复杂度分析问题的解法是有效率差别的有些问题是难解的寻求近似解问题的可计算性有些问题是不可计算的 30 计算思维例 其他 预取和缓存对最坏情况的预防 保护 恢复启发式推理时空等不可兼得要素的权衡 31 计算思维的特点 是概念化思考 而非编程是基本思考能力 而非机械的套用是人的思考 而非计算机与数学思维和工程思维相结合是思想 而非人造物人人皆有 处处皆是 32 生活中的计算思维 算法 最大公约数查找方法 查黄页是顺序翻找还是借助索引排序 整理扑克牌排队 先来先处理预取与缓存 书包存放当天上课用的书并行处理 烧菜 33 计算 X 计算数学 计算几何 自动定理证明计算物理学计算化学计算生物学 生物信息学计算经济学计算机艺术 电影特效 计算机作曲绘画书法 34 计算 X 十二五863计划 征集重大应用软件课题聚变与裂变能源数值模拟真实飞机外型全流场和优化设计数值模拟航天飞行器全飞行流域数值模拟新药研发与蛋白质折叠数值模拟真实感动漫渲染与创作大型工程设备结构力学分析复杂电磁环境数值模拟新型材料设计与性能评估 35 2013年诺贝尔化学奖 多尺度复杂化学系统模型 在多尺度模型的辅助下 化学家们让计算机 做帮手 来揭示化学过程 诺贝尔化学奖评选委员会 对化学家来说 计算机是同试管一样重要的工具 计算机对真实生命的模拟已为化学领域大部分研究成果的取得立下了 汗马功劳 36 本课程的定位 学习利用计算机解决问题的思想方法 应用于其他专业领域不是程序设计语言课程 编程是计算思维的实践坏消息 学习编程语言需要掌握非常繁琐的细节好消息 Python语言非常简单 易学易用不是算法和数据结构课程 会学习一些基本的知识 37 本课程的定位 续 计算机科学 程序设计语言 算法设计与分析 数据结构 理 化 生 经 管 金融 工程 数学 艺术 计算思维 可计算性理论 38 Python语言 荷兰人GuidovanRossum于1980年代发明通用 跨平台 开源 自由 免费 简单易学 高度的可读性支持多种编程范型编译 解释源代码先编译成字节码 再解释执行 39 Python语言 流行编程语言前10名之一 40 Python安装与运行 版本 教材和上课都采用Python2 7与最新的Python3 x有不兼容的地方 安装后 启动Python解释器命令行GUI 41 第一个程序 HelloWorld 交互方式 print Hello World Hello World 本课程的教学中常用交互方式演示新语句实际上很少用交互方式执行程序多次执行同一程序需要多次输入程序多行语句无法一次性执行 42 第一个程序 HelloWorld 程序文件将语句保存在纯文本文件hello py中四种执行方式在IDLE中用RunModule菜单执行双击hello py文件图标 importhelloC Python27 pythonhello py print Hello World 43 程序构件 数据 数据是被处理的信息有不同类型的数据字符串数据 print Hello World 数值数据 print3 1415 44 程序构件 变量 和数学类似 用一个名字表示可变的数据数学中多用单字母 程序中多用单词 词组标识符 Python命名以字母或下划线开头 后跟0个或多个字母 数字 下划线 区分大小写字母 合法 xxYzx 123 w3非法 3qx 123firstname良好的命名风格 有意义 风格一致 45 程序构件 表达式 表达式 能计算出一个值 字面值 3 14 hello 变量数据 运算符 如 2 3 4 5运算符不同类型的数据有不同运算运算符有优先级良好编程风格 用空格 括号增加表达式的可读性 46 程序构件 语句 输出语句我们用语句模板来给出正确用法printprint 赋值语句 x 3 14 printx 10 47 程序构件 函数 多条语句构成一个整体 并命名 d