计算机基础课件-算法与程序设计

第5章算法与程序设计算法4.程序设计开发环境3.程序设计方法2.程序设计语言1.一、算法什么是算法?规范的定义：定义一个可终止过程的有序的、无歧义的、可执行的步骤的集合简单的理解：解决计算问题的方法，可以用一系列操作步骤来描述所有步骤应有明确的执行顺序每一步操作均应具体、唯一每一步操作都应有效应带来最终的确定执行结果1、若A大于B，则比较A、C2、若A大于C，则A最大；否则C最大3、若B大于A，则比较B、C4、若B大于C，则B最大；否则C最大使用不同类型的语言怎样表示算法?举例在A、B、C中找出最大数ifA>BthenifA>CthenAisMax;else

CisMax;IfB>AthenifB>Cthen

BisMax;else

CisMax;A>B?max←AEndStartmax←BC>max?max←CYesYesNoNo算法描述方法：自然语言、流程图、伪代码、程序设计语言……流程图：算法的常用描述方法A>B?max←AEndStartmax←BC>max?max←CYesYesNoNo用一组几何图形和有向线条、配以简单文字符号来表示算法起止框处理框判断框流程线I/O框连接点用以上符号可以表示任意复杂的算法如何发现算法？发现算法是一种富有挑战性的艺术性工作今有鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一。凡百钱买鸡百只，问鸡翁母雏各几何。FORa=0TO100FORb=0TO100FORc=0TO100IFa+b+c=100AND5a+3b+c/3=100THENPRINTa,b,cENDIFNEXTcNEXTbNEXTa

穷举法①a+b+c=100②5a+3b+c/3=100其它基本算法累加、累乘、迭代、递归、交换、查找、排序、……对同一问题有不同的算法

(X1+X2)X3Y=+Y=X1X3X2X3vsFORa=0TO100FORb=0TO100FORc=0TO100IFa+b+c=100AND5a+3b+c/3=100THENPRINTa,b,cENDIFNEXTcNEXTbNEXTa

a、b、c的组合方案数：共100*100*100种若考虑：a最多为100/5=20，则a、b、c的组合方案数：共20*100*100种若考虑：b最多为100/3=33，则a、b、c的组合方案数：共20*33*100种哪种方案更好？还有没有更好的算法？对算法的评价与分析评价一种算法正确性可理解性时间复杂度空间复杂度算法运行时间的函数算法占用内存空间大小的函数时、空复杂度与求解问题的规模及需处理数据量的大小有关二、程序设计语言机器语言：最低级的语言特点：

面向机器硬件，直接以二进制书写程序，是计算机唯一能够认识的语言0001

010101101100

//将内存6C单元数据加载进寄存器R50001

011001101101//将内存6D单元数据加载进寄存器R60101

0000

0101

0110//将R5与R6相加，结果送入寄存器R00011

0000

01101110//

将R0数据存储进内存6E单元1100

000000000000//停机缺陷编写困难，代码冗长，容易出错，难以阅读和理解，可移植性差LDR5,6C//将内存6C单元数据加载进寄存器R5LDR6,6D

//将内存6D单元数据加载进寄存器R6ADDR0,R5,R6//将R5与R6相加，结果送入寄存器R0STR0,6E//

将R0数据存储进内存6E单元HLT

//停机汇编语言：符号化的低级语言特点

与机器语言本质相同，面向底层硬件操作，因采用助记符而较易使用计算机能直接认识汇编语言吗？否！必须经过汇编操作！对汇编语言程序的汇编操作汇编程序：一类系统软件LDR5,6CLDR6,6DADDR0,R5,R6STR0,6EHLT00010101011011000001011001101101010100000101011000110000011011101100000000000000

源程序目标程序高级语言：类自然、数学语言inputX1;inputX2;Y=X1+X2;printY;scanf(“%d”,&x1);if(x1==my_password)

printf(“Welcome!”);else

printf(“Error!”);“高级”的含义：1、从问题的角度考虑，而非从机器的角度

2、绕开复杂的硬件问题，易于掌握和使用

3、主要用于编写位于较高层次的应用程序常见高级语言：

AdaFortranBASIC、VisualBASIC

C、C++、C#

Java……与汇编语言类似需要将高级语言源程序翻译

成机器语言目标程序整体编译

vs

逐行解释不同类型的高级语言面向对象面向过程

面向问题面向函数面向过程型：注重解决问题的算法和实现过程细节面向对象型：模拟现实世界中各种对象之间的交互三、程序设计方法程序设计的一般过程AddYourTitle分析问题理解问题明确要求整理入口规划出口设计算法总体规划逐层抽象自上而下由粗到细编码确定语言选择工具遵守语法自下而上调试程序编译连接试运行反复调试以输入密码登录系统为例AddYourTitle整理文档使用说明开发资料阶段化成果连接将编译产生的目标程序转换为可执行程序程序设计中的基本概念变量：X1、X2、Y运算符：+、-、*、/、and、or、not、……InputX1InputX2Y=X1+X2PrintYINPUTpwdIFpwd=my_passwordTHENPRINT“Welcome!”ELSEPRINT“Error!”ENDIF整型int：X1=13;X2=378实型float：X1=12.47;X2=3.9字符型char：x1=‘a’;x2=‘K’字符串型string：pwd=“helloword”……变量有不同数据类型常量：X1=123表达式：X1+X2语句：Y=X1+X2因此变量在使用之前必须先行定义程序设计中的基本概念DefineX1,X2,YasIntegerInputX1InputX2Y=X1+X2PrintYDefinex1asStringINPUTx1IFx1=my_passwordTHENPRINT“Welcome!”ELSEPRINT“Error!”ENDIF注释语句//在屏幕上显示X1和X2相运算的结果执行性语句说明性语句说明性语句：编译后不产生目标代码执行性语句：编译后将产生目标代码顺序结构三种基本程序控制结构语句A语句BInputX1InputX2Y=X1+X2PrintY分支结构语句B语句A条件TrueFalseINPUTx1IFx1=“123”THENPRINT“Yse”ELSEPRINT“No”ENDIF循环结构语句A条件TrueFalse可以是多条语句的集合Sum=0i=1DoSum=Sum+ii=i+1LoopWhilei<=100PrintSum语句A条件TrueFalseWhile-do型Do-while型结构化程序设计方法任何复杂算法，都可以由此三种结构组成子程序：另一种重要的基本结构子程序、过程、函数、……功能相对独立的程序段，可以由其它程序调用InputX1InputX2Y=X1+X2PrintY……InputX1InputX2Y=X1+X2PrintY……InputX1InputX2Y=X1+X2PrintYSubAdder

InputX1InputX2

Y=X1+X2PrintYEndSubCallAdder……CallAdder……CallAdder……子程序的要素调用、跳转、执行、返回程序模块化1、将复杂程序划分为若干个功能模块2、各个模块可相对独立开发3、模块之间通过一定的接口相互联系面向对象的方法：更接近现实世界面向过程的方法：强调如何实现过程的细节，将数据及其操作截然分开面向对象的方法：模拟现实世界中的人类思维方式，用对象表达各种元素面向对象的方法面向过程的方法主控程序发球回击计算路径判分考虑一个网球游戏开发PlayerAPlayerB技巧Skill力度Endurance发球Serve回击Return属性方法PlayerClassJudgeScore面向对象的方法：更接近现实世界JudgeScorePlayerAPlayerB裁决发球裁决回击修改计分要求回击要求回击裁决回击可实现软件复用像其它工程领域一样，将已有的软件产品做成构件(组件),

并用于新的软件系统组装和集成，从而实现产业化四、程序设计开发环境狭义的程序设计过程编辑编译连接调试发布产生源程序产生目标程序产生可执行程序编辑程序Editor编译程序Compiler连接程序Linker调试程序DebuggerIDE集成开发环境IntegratedDevelopmentEnvironment整合以上各项工具的应用软件套件一般针对特定语言量身打造TurboC：学习C语言编程的经典工具小巧，快捷、但：只能用键盘操作，只能编辑一份程序VisualC++：C&C++语言的