程序设计思想与方法

教师信息办公地点：电院楼群3号楼519室电话：34205060转602E-mail dong-xj@ xjdong@网址 /~xiaoju/CT1程序设计思想与方法全文共47页，当前为第1页。助教靳阳jyjz2008@作业

请确定通过Python验证后发给助教

每个星期三晚上12点之前2程序设计思想与方法全文共47页，当前为第2页。课程信息教材《程序设计思想与方法——问题求解与计算思维》高教出版社，2013参考书PythonProgramming:AnIntroductiontoComputerScience.(电子版)

HowtoThinkLikeaComputerScientist—LearningwithPython.(电子版)

/thinkCSpy/Python学习手册3程序设计思想与方法全文共47页，当前为第3页。课程信息下载python软件的地址

/ cs190c:textsoft09

4程序设计思想与方法全文共47页，当前为第4页。教学方式课堂教学-每星期四3,4节讲课,演示机房上机双周周一1,2节,电院4号楼311教室完成当天上机作业并提交答疑

5程序设计思想与方法全文共47页，当前为第5页。66考核方式期末考试笔试,占最终成绩的50%平时作业编一些小程序,邮件或ftp上传给助教,占最终成绩的20%大作业编一个大程序,期末提交,占最终成绩的30%6程序设计思想与方法全文共47页，当前为第6页。第1章计算与计算思维程序设计思想与方法全文共47页，当前为第7页。计算机:硬件(1)8主存储器CPU输入设备输出设备次级存储器程序设计思想与方法全文共47页，当前为第8页。计算机:硬件(2)中央处理器(CPU):执行指令每条指令只能完成简单的操作!例如:加法,比较,移动,etc.但按一定的次序执行大量简单指令能完成复杂任务!存储器:存储信息(程序和数据)主存:

CPU能直接访问,速度快但易失次级存储器:速度慢但持久输入/输出设备:人机交互99程序设计思想与方法全文共47页，当前为第9页。101010计算机:软件计算机是信息处理机器,信息处理过程由预定的程序控制.单条指令是做不了什么事情的,需要大量指令组成一个逐步执行的指令序列,即程序.各种程序统称为计算机软件.没有软件的计算机毫无用处.10程序设计思想与方法全文共47页，当前为第10页。计算计算:利用计算机执行程序来解决问题.不是狭义的数学计算!程序使得简单指令能完成复杂任务.问:只会加法的小学生能完成乘法运算任务吗?答:能!关键是编写合适的程序

在纸上写下0，记住结果；给所记结果加上第1个n，记住结果；给所记结果加上第2个n，记住结果；

……给所记结果加上第m个n，记住结果;报告结果(即m×n)1111程序设计思想与方法全文共47页，当前为第11页。通用计算机计算机执行一个程序即可实现一个功能;换着执行不同的程序即可实现不同的功能.例如:word,mediaplayer,录音机,etc通用计算机:可以加载不同的程序来执行.与一些电器的比较电视机:功能单一洗衣机:功能较多(可加载多种洗涤程序)手机:功能更多,基本上就是计算机.12程序设计思想与方法全文共47页，当前为第12页。计算机科学并非研究计算机!计算机之于计算机科学家正如望远镜之于天文学家.(E.W.Dijkstra)CS研究计算的基础,实现与应用.例如,CS的一个基本问题:什么是可计算的?本课程的目标:像计算机科学家一样思考1313程序设计思想与方法全文共47页，当前为第13页。程序设计计算的关键是程序设计(编程).给定一个问题,利用计算机支持的简单操作,设计出一个操作步骤的序列,计算机执行这个序列从而解决问题.学习程序设计的好处:做计算机的主人提高问题求解能力本身是很有乐趣的智力活动14程序设计思想与方法全文共47页，当前为第14页。程序设计语言问:用什么语言告诉计算机做什么?答:用精确无歧义的程序设计语言.精确的语法和语义(形式和意义)1515程序设计思想与方法全文共47页，当前为第15页。程序设计语言有不同层次的程序设计语言计算机的“母语”:

机器语言例如:0000010000000001.是Intel8086能理解的一条指令将机器语言用助忆符表示:汇编语言上例即:ADDAL,1.需要汇编器处理后机器才懂适合人用的语言:

高级语言如:x=y+1.需要编译器或解释器翻译后机器才懂1616程序设计思想与方法全文共47页，当前为第16页。程序设计语言高级语言的翻译编译

源代码编译成目标代码,再执行

一次编译,多次执行.解释

源代码直接被解释执行

每次执行都要重新解释.1717程序设计思想与方法全文共47页，当前为第17页。编译vs解释思考:为什么高级语言程序具有可移植性,即同一个程序可以在不同厂商的计算机上执行?18程序设计思想与方法全文共47页，当前为第18页。算法与编码实现程序设计先用非形式化的语言将问题求解步骤表达出来——算法;伪代码再用形式化的编程语言将上述算法实现——程序代码19程序设计思想与方法全文共47页，当前为第19页。算法例:欧几里德算法欧几里德算法:求最大公约数.输入:自然数a,b输出:a,b的最大公约数步骤:第1步:令r为a除以b所得余数第2步:若r=0,则算法结束,

b即为答案

否则置a←b,b←r,转到第1步.20程序设计思想与方法全文共47页，当前为第20页。对算法的要求算法的每个步骤必须是明确的,可行的.不明确:"在菜中放点盐"不可行:"用青菜豆腐做出龙肝凤髓的美味"每个步骤不必是最底层的琐细步骤,可以是组合的高级步骤.如:"焯水"算法的所有步骤必须在有限时间内完成.我们说的计算,即是指"算法计算":用明确可行的基本步骤组成的序列来解决问题.21程序设计思想与方法全文共47页，当前为第21页。222222计算思维计算思维(computationalthinkin计算机科学家利用计算机(计算过程)解决问题时的思想和方法计算机科学(CS)是关于“计算”的科学如何像计算机科学家一样思考?22程序设计思想与方法全文共47页，当前为第22页。23真的有计算思维吗?人们在解决不同问题时有不同的思考方式数学思维:解数学问题工程思维:工程设计形象思维:文学创作......计算思维:建立在计算机的能力与局限之上.由于计算机的广泛应用,计算思维未来会成为人们的基本能力.与阅读,书写,算术能力一样!程序设计思想与方法全文共47页，当前为第23页。计算思维例:问题表示问题的表示(建模)抽象:将现实中的各种数量关系,空间关系,处理过程抽象为计算机的数据结构和控制结构例如:温度数据抽象为数值还是文字?不同抽象层次问题表示得合适与否直接影响问题的解法的发现和效率24程序设计思想与方法全文共47页，当前为第24页。计算思维例:算法设计化难为易:

分解,约简,嵌入,转换,模拟…分治法,递归法,贪心法,动态规划...递归地思考并行处理25程序设计思想与方法全文共47页，当前为第25页。计算思维例:编程实现类型系统与类型检查结构化与模块化的思考编程范型:过程式,面向对象,函数式,...程序美学,系统设计的简洁与优雅26程序设计思想与方法全文共47页，当前为第26页。计算思维例:计算理论算法复杂度分析问题的解法是有效率差别的有些问题是难解的寻求近似解问题的可计算性有些问题是不可计算的27程序设计思想与方法全文共47页，当前为第27页。计算思维例:其他预取和缓存对最坏情况的预防,保护,恢复启发式推理时空等不可兼得要素的权衡……28程序设计思想与方法全文共47页，当前为第28页。计算思维的特点是概念化思考,而非编程是基本思考能力,而非机械的套用是人的思考,而非计算机与数学思维和工程思维相结合是思想,而非人造物人人皆有,处处皆是29程序设计思想与方法全文共47页，当前为第29页。生活中的计算思维算法:最大公约数查找方法:查黄页是顺序翻找还是借助索引排序:整理扑克牌排队:先来先处理预取与缓存:书包存放当天上课用的书并行处理:烧菜……30程序设计思想与方法全文共47页，当前为第30页。计算+X计算数学,计算几何,自动定理证明计算物理学计算化学计算生物学,生物信息学计算经济学计算机艺术:电影特效,计算机作曲绘画书法……31程序设计思想与方法全文共47页，当前为第31页。计算+X:十二五863计划征集重大应用软件课题聚变与裂变能源数值模拟真实飞机外型全流场和优化设计数值模拟航天飞行器全飞行流域数值模拟新药研发与蛋白质折叠数值模拟真实感动漫渲染与创作大型工程设备结构力学分析复杂电磁环境数值模拟新型材料设计与性能评估32程序设计思想与方法全文共47页，当前为第32页。2013年诺贝尔化学奖多尺度复杂化学系统模型:在多尺度模型的辅助下,化学家们让计算机“做帮手”来揭示化学过程.诺贝尔化学奖评选委员会:对化学家来说,计算机是同试管一样重要的工具,计算机对真实生命的模拟已为化学领域大部分研究成果的取得立下了“汗马功劳”LuChaojun,SJTU3333程序设计思想与方法全文共47页，当前为第33页。本课程的定位学习利用计算机解决问题的思想方法,应用于其他专业领域不是程序设计语言课程!编程是计算思维的实践坏消息:学习编程语言需要掌握非常繁琐的细节好消息:Python语言非常简单,易学易用不是算法和数据结构课程!会学习一些基本的知识34程序设计思想与方法全文共47页，当前为第34页。本课程的定位(续)计算机科学程序设计语言算法设计与分析数据结构理,化,生...经,管,金融...工程数学艺术计算思维可计算性理论35程序设计思想与方法全文共47页，当前为第35页。Python语言荷兰人GuidovanRossum于1980年代发明.通用/跨平台/开源/自由(免费)简单易学,高度的可读性支持多种编程范型编译+解释

源代码先编译成字节码,再解释执行36程序设计思想与方法全文共47页，当前为第36页。Python语言流行编程语言前10名之一(当前第8位)/index.php/content/paperinfo/tpci/index.html

LuChaojun,SJTU3737程序设计思想与方法全文共47页，当前为第37页。Python安装与运行版本:教材和上课都采用Python2.7与最新的Python3.x有不兼容的地方.安装后,启动Python解释器命令行GUI38程序设计思想与方法全文共47页，当前为第38页。第一个程序:HelloWorld交互方式>>>print"Hello,World!"Hello,World!本课程的教学中常用交互方式演示新语句实际上很少用交互方式执行程序多次执行同一程序需要多次输入程序多行语句无法一次性执行39程序设计思想与方法全文共47页，当前为第39页。第一个程序:HelloWorld程序文件将语句保存在纯文本文件hello.py中四种执行方式在IDLE中用RunModule菜单执行双击hello.py文件图标>>>importhelloC:\Python27>pythonhello.pyprint"Hello,World!"40程序设计思想与方法全文共47页，当前为第40页。程序构件:数据数据是被处理的信息有不同类型的数据字符串数据>>>print"Hello,World!"数值数据>>>print3.141541程序设计思想与方法全文共47页，当前为第41页。程序构件:变量和数学类似:用一个名字表示可变的数据数学中多用单字母,程序中多用单词/词组标识符:Python命名以字母或下划线开头,后跟0个或多个字母,数字,下划线.区分大小写字母.合法:xxYzx_123_

___w3非法:3qx-123

firstname良好的命名风格:有意义,风格一致42程序设计思想与方法全文共47页，当前为第42页。程序构件:表达式表达式:能计算出一个值.字面值:3