程序设计思想与方法讲述

《程序设计思想与方法讲述》由会员分享，可在线阅读，更多相关《程序设计思想与方法讲述（49页珍藏版）》请在金锄头文库上搜索。

1、程序设计思想与方法程序设计思想与方法 课程信息课程信息 n n 教材教材 程序设计思想与方法程序设计思想与方法问题求解与计算思维问题求解与计算思维 陆朝俊，高教出版社，陆朝俊，高教出版社，20132013 n n 参考书参考书 Python Programming: An Introduction to Python Programming: An Introduction to Computer Science. (Computer Science. (电子版电子版) ) How to Think Like a Computer ScientistHow to Think Like a Co

2、mputer Scientist Learning with Python.(Learning with Python.(电子版电子版) ) PythonPython学习手册学习手册 第第4 4版版 ( (原版：原版：LearningLearning Python)Python) 2 2 课程信息课程信息 n n 下载下载python python 软件的地址软件的地址 https:/www.python.org/https:/www.python.org/ n n Purdue UniversityPurdue University的的课件地址：课件地址： http:/secant.cs.p

3、urdue.edu/http:/secant.cs.purdue.edu/ cs190c:textsoft09cs190c:textsoft09 3 3 教学方式教学方式 n n 课堂教学课堂教学 - - 每星期四每星期四3, 43, 4节节 讲课讲课, , 演示演示 n n 机房上机机房上机 单单周周(3-15(3-15周，共周，共7 7次次) ) 周一周一1, 21, 2节节, , 电院电院4 4号楼号楼31313 3教室教室 完成当天上机作业并提交完成当天上机作业并提交 答疑答疑 4 4 考核方式考核方式 n n 期末考试期末考试 笔试笔试, , 占最终成绩的占最终成绩的50%50% n

4、 n 平时作业平时作业 上机作业、章节后的作业上机作业、章节后的作业 ftpftp上传给助教上传给助教, , 占最终成绩的占最终成绩的4 40%0% n n 自选作业自选作业 编一个大程序编一个大程序, , 期末提交期末提交, , 占最终成绩的占最终成绩的1 10%0% 5 5 第第1 1章章 计算与计算思维计算与计算思维 问题的提出问题的提出 n n 当今时代当今时代, ,计算机几乎无处不在计算机几乎无处不在: : 企业管理企业管理 产品设计产品设计 气象预报气象预报 电影制作电影制作 工业控制工业控制 游戏游戏, , 写文章写文章, , 上网上网, , n n 问题问题: :计算机究竟是什

5、么计算机究竟是什么? ?怎么能做这么怎么能做这么 多不同的事情多不同的事情? ? 7 计算机计算机: : 硬件硬件(1)(1) 8 8 主存储器 CPU 输入设备 输出设备 次级存储器 计算机计算机: :硬件硬件(2)(2) n n 中央处理器中央处理器(CPU):(CPU):执行执行指令指令 每条指令只能完成简单的操作每条指令只能完成简单的操作! ! n n 例如例如: : 加法加法, , 比较比较, , 移动移动, etc., etc. 但按一定的次序执行大量简单指令能完成复杂任但按一定的次序执行大量简单指令能完成复杂任 务务! ! n n 存储器存储器: : 存储信息存储信息( (程序和

6、数据程序和数据) ) 主存主存: : CPUCPU能直接访问能直接访问, ,速度快但易失速度快但易失 次级存储器次级存储器: :速度慢但持久速度慢但持久 n n 输入输入/ /输出设备输出设备: :人机交互人机交互 9 9 9 101010 计算机计算机: :软件软件 n n 计算机是信息处理机器计算机是信息处理机器, ,信息处理过程信息处理过程 由预定的由预定的程序程序控制控制. . 单条指令是做不了什么事情的单条指令是做不了什么事情的, ,需要大量需要大量 指令组成一个逐步执行的指令组成一个逐步执行的指令序列指令序列, ,即程序即程序 . . n n 各种程序统称为计算机软件各种程序统称为

7、计算机软件. . n n 没有软件的计算机毫无用处没有软件的计算机毫无用处. . 1010 计算计算 n n 计算计算: : 利用计算机执行程序来解决问题利用计算机执行程序来解决问题. . 不是狭义的数学计算不是狭义的数学计算! ! n n 程序使得简单指令能完成复杂任务程序使得简单指令能完成复杂任务. . 问问: :只会加法的小学生能完成乘法运算任务吗只会加法的小学生能完成乘法运算任务吗? ? 答答: :能能! !关键是编写合适的程序关键是编写合适的程序 在纸上写下在纸上写下0 0，记住结果；，记住结果； 给所记结果给所记结果加加上第上第1 1个个 n n ，记住结果；，记住结果； 给所记结

8、果给所记结果加加上第上第2 2个个 n n ，记住结果；，记住结果； 给所记结果给所记结果加加上第上第 m m 个个 n n ，记住结果，记住结果; ; 报告结果报告结果( (即即 m m n n) ) 11 1111 121212 通用计算机通用计算机 n n 计算机是具有如下特征的机器计算机是具有如下特征的机器: : 能够存储和处理信息能够存储和处理信息 n n 输入输入处理处理输出输出 信息处理由程序控制信息处理由程序控制 n n 计算机计算机程序程序是一个详细的逐步执行的指令序列是一个详细的逐步执行的指令序列, , 告诉计算机该做什么告诉计算机该做什么 n n 程序可改变程序可改变:

9、: 不同的程序完成不同的处理任务不同的程序完成不同的处理任务 n n 计算机执行一个程序即可实现一个功能计算机执行一个程序即可实现一个功能; ;换着换着 执行不同的程序即可实现不同的功能执行不同的程序即可实现不同的功能. . n n 人们造了各种各样的计算机人们造了各种各样的计算机, , 但但: : 所有所有 计算机具有相同的能力计算机具有相同的能力! ! 计算机科学计算机科学 n n 并非研究计算机并非研究计算机! ! 计算机之于计算机科学家正如望远镜之于天计算机之于计算机科学家正如望远镜之于天 文学家文学家. (E. W. Dijkstra). (E. W. Dijkstra) n n C

10、SCS研究计算的基础研究计算的基础, ,实现与应用实现与应用. . 例如例如,CS,CS的一个基本问题的一个基本问题: :什么是可计算的什么是可计算的? ? n n 本课程的目标本课程的目标: :像计算机科学家一样思考像计算机科学家一样思考 13 1313 程序设计程序设计 n n 计算的关键是程序设计计算的关键是程序设计( (编程编程).). 给定一个问题给定一个问题, ,利用计算机支持的简单操利用计算机支持的简单操 作作, ,设计出一个操作步骤的序列设计出一个操作步骤的序列, ,计算机执计算机执 行这个序列从而解决问题行这个序列从而解决问题. . n n 学习程序设计的好处学习程序设计的好

11、处: : 做计算机的主人做计算机的主人 提高问题求解能力提高问题求解能力 本身是很有乐趣的智力活动本身是很有乐趣的智力活动 1414 程序设计语言程序设计语言 n n 问问: :用什么语言告诉计算机做什么用什么语言告诉计算机做什么? ? 答答: :用精确无歧义的程序设计语言用精确无歧义的程序设计语言. . 精确的语法和语义精确的语法和语义( (形式和意义形式和意义) ) 15 1515 程序设计语言程序设计语言 n n 有不同层次的程序设计语言有不同层次的程序设计语言 计算机的计算机的“ “母语母语”:”: 机器语言机器语言 n n 例如例如: 0000010000000001.: 00000

12、10000000001.是是Intel8086Intel8086能理解能理解 的一条指令的一条指令 将机器语言用将机器语言用助忆符助忆符表示表示: :汇编语言汇编语言 n n 上例即上例即: ADD AL,1.: ADD AL,1.需要需要汇编器汇编器处理后机器才懂处理后机器才懂 适合人用的语言适合人用的语言: : 高级语言高级语言 n n 如如: x = y + 1. : x = y + 1. 需要需要编译器编译器或或解释器解释器翻译后机器才懂翻译后机器才懂 16 1616 高级语言高级语言 n n 高级程序设计语言有很多种高级程序设计语言有很多种, , 据说据说 20082008年网上被引

13、用最多的年网上被引用最多的1010个语言是个语言是 ( (按字母顺序按字母顺序): C, C+, C#, Java, ): C, C+, C#, Java, JavaScript, Perl, PHP, JavaScript, Perl, PHP, PythonPython, , Ruby, SQL.Ruby, SQL. 17 程序设计语言程序设计语言 n n 高级语言的翻译高级语言的翻译 编译编译 源代码编译成目标代码源代码编译成目标代码, , 再执行再执行 一次编译一次编译, , 多次执行多次执行. . 解释解释 源代码直接被解释执行源代码直接被解释执行 每次执行都要重新解释每次执行都要重

14、新解释. . 18 1818 编译编译vsvs解释解释 思考:为什么高级语言程序具有可移植性, 即同一个程序可以在不同厂商的计算机上执行? 1919 PythonPython n n PythonPython采用编译采用编译/ /解释混合方式解释混合方式 先编译成字节码先编译成字节码, , 再解释执行再解释执行 n n 安装安装Python 2.xPython 2.x 与新的与新的Python 3.xPython 3.x有不兼容的地方有不兼容的地方 n n 启动启动PythonPython 20 算法与编码实现算法与编码实现 n n 程序设计程序设计 先用非形式化的语言将问题求解步骤表达先用非

15、形式化的语言将问题求解步骤表达 出来出来算法算法; ; n n 伪代码伪代码 再用形式化的编程语言将上述算法实现再用形式化的编程语言将上述算法实现 程序程序 n n 代码代码 2121 算法算法 例例: :欧几里德算法欧几里德算法 n n 欧几里德算法欧几里德算法: :求最大公约数求最大公约数. . 输入输入: :自然数自然数a a, , b b 输出输出: : a a, , b b的最大公约数的最大公约数 步骤步骤: : 第第1 1步步: :令令r r为为a a除以除以b b所得余数所得余数 第第2 2步步: :若若r r = 0,= 0,则算法结束则算法结束, , b b即为答案即为答案 否则置否则置a ab b, , b br r, ,转到第转到第1 1步步. . 2222 对算法的要求对算法的要求 n n 算法的每个步骤必须是明确的算法的每个步骤必须是明确的, ,可行的可行的. . 不明确不明确:“:“在菜中放点盐在菜中放点盐“ “ 不可行不可行:“:“用青菜豆腐做出龙肝凤髓的美味用青菜豆腐做出龙肝凤髓的美味“ “ 每个步骤不必是最底层的琐细步骤每个步骤不必是最底层的琐细步骤, ,可以是组合的可以是组合的 高级步骤高级步骤. .如如:“:“焯水焯水“ “ n n 算法的所有步骤必须在有限时间内完成算法的所有步骤必须在有限时间内完成. . n n 我们说