语言算法和程序设计方法精.ppt

《语言算法和程序设计方法精.ppt》由会员分享，可在线阅读，更多相关《语言算法和程序设计方法精.ppt（50页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、语言算法和程序设计方法语言算法和程序设计方法第1页，本讲稿共50页从算法到程序再到软件从算法到程序再到软件计算机完成各种计算机完成各种不同的任务不同的任务，需要，需要不不同的软件同的软件软件开发软件开发算法算法程序程序软件软件程序设计程序设计是软件开发的一部分是软件开发的一部分l l程序设计分解为几个步骤程序设计分解为几个步骤程序设计分解为几个步骤程序设计分解为几个步骤l l程序设计需要使用程序设计语言程序设计需要使用程序设计语言程序设计需要使用程序设计语言程序设计需要使用程序设计语言算法设计算法设计软件开发软件开发的任务之一的任务之一的任务之一的任务之一l l选择一种选择一种选择一种选择一种

2、语言语言语言语言l l使用这个语言使用这个语言使用这个语言使用这个语言编写编写编写编写完成操作任务的完成操作任务的完成操作任务的完成操作任务的代码代码代码代码程序设计程序设计程序设计程序设计软件开发的核心工作是算法设计软件开发的核心工作是算法设计第2页，本讲稿共50页算法算法l l一项工作如何被完成的步骤一项工作如何被完成的步骤一项工作如何被完成的步骤一项工作如何被完成的步骤l l数学问题数学问题数学问题数学问题寻找如何解决特定问题的方法寻找如何解决特定问题的方法寻找如何解决特定问题的方法寻找如何解决特定问题的方法一个著名的算法一个著名的算法欧几里德算法欧几里德算法欧几里德算法欧几里德算法：求

3、两个正整数求两个正整数A和和B的最大公约数的最大公约数如：如：如：如：9 9、6 6的最大公约数是的最大公约数是的最大公约数是的最大公约数是3 3l l第一步：比较第一步：比较第一步：比较第一步：比较A A和和和和B B这两个数，将这两个数，将这两个数，将这两个数，将A A设置为较大的数，设置为较大的数，设置为较大的数，设置为较大的数，B B设置设置设置设置 为较小的数；为较小的数；为较小的数；为较小的数；l l第二步：第二步：第二步：第二步：A A除以除以除以除以B B，得到余数，得到余数，得到余数，得到余数C C；l l第三步：如果第三步：如果第三步：如果第三步：如果C C等于等于等于等于

4、0 0，则最大公约数就是，则最大公约数就是，则最大公约数就是，则最大公约数就是B B；否则将否则将否则将否则将B B赋值给赋值给赋值给赋值给A A，C C赋值给赋值给赋值给赋值给B B，重复进行第二、三步，重复进行第二、三步，重复进行第二、三步，重复进行第二、三步从算法到程序再到软件从算法到程序再到软件ABC9636303第3页，本讲稿共50页图灵理论图灵理论图灵理论图灵理论只要能被分解为有限步骤的问题就可以被计算机执行只要能被分解为有限步骤的问题就可以被计算机执行只要能被分解为有限步骤的问题就可以被计算机执行只要能被分解为有限步骤的问题就可以被计算机执行l l有限的步骤有限的步骤有限的步骤有

5、限的步骤l l能够将这些步骤设计为计算机所执行的程序能够将这些步骤设计为计算机所执行的程序程序设计中，首先寻找算法，算法找到后，实现算法的程序设计中，首先寻找算法，算法找到后，实现算法的步骤步骤算法的描述算法的描述l l使用某种计算机语言使用某种计算机语言使用某种计算机语言使用某种计算机语言l l不同的计算机语言对一个算法具有不同的实现方法不同的计算机语言对一个算法具有不同的实现方法算法是程序设计的基础算法是程序设计的基础算法是程序设计的基础算法是程序设计的基础从算法到程序再到软件从算法到程序再到软件第4页，本讲稿共50页程序和指令程序和指令程序程序programl l计算机计算机执行执行执行

6、执行某种某种某种某种任务任务任务任务的一系列的一系列的一系列的一系列操作步骤操作步骤操作步骤操作步骤的的总和总和 l l一组计算机指令的有序集合一组计算机指令的有序集合 指令指令instructioninstructionl l控制计算机控制计算机控制计算机控制计算机执行执行执行执行各种基本操作的各种基本操作的命令命令l l指令是计算机执行的最基本操作指令是计算机执行的最基本操作 如：处理器从内存中读取一个数据如：处理器从内存中读取一个数据如：处理器从内存中读取一个数据如：处理器从内存中读取一个数据 二进制的算术运算加、减、乘、除二进制的算术运算加、减、乘、除二进制的算术运算加、减、乘、除二进

7、制的算术运算加、减、乘、除逻辑判断等逻辑判断等逻辑判断等逻辑判断等l l处理器能执行的处理器能执行的二进制代码二进制代码二进制代码二进制代码第5页，本讲稿共50页程序和指令程序和指令指令作为计算机软件和硬件的接口指令作为计算机软件和硬件的接口l l指令在处理器中指令在处理器中以逻辑电路实现以逻辑电路实现 软件硬件 指指令令第6页，本讲稿共50页指令系统指令系统l l 一个一个CPU能够执行的所有指令能够执行的所有指令能够执行的所有指令能够执行的所有指令l l 指令的主要类型指令的主要类型指令的主要类型指令的主要类型数据传输类数据传输类数据传输类数据传输类将数据从一个地方将数据从一个地方将数据从

8、一个地方将数据从一个地方(源源源源)传输到另外一个地方传输到另外一个地方传输到另外一个地方传输到另外一个地方(目的目的目的目的)一种是在一种是在一种是在一种是在CPUCPU内部、存储器内部、内部、存储器内部、内部、存储器内部、内部、存储器内部、CPUCPU和存储器之间进行和存储器之间进行和存储器之间进行和存储器之间进行一种是在一种是在一种是在一种是在CPUCPU和外设（外设接口）之间进行和外设（外设接口）之间进行和外设（外设接口）之间进行和外设（外设接口）之间进行的的的的算术逻辑运算类算术逻辑运算类控制操作类控制操作类控制操作类控制操作类有条件转移、无条件转移有条件转移、无条件转移有条件转移、

9、无条件转移有条件转移、无条件转移第7页，本讲稿共50页翻译系统翻译系统基本概念基本概念l l源程序源程序源程序源程序用各种语言编写的程序用各种语言编写的程序用各种语言编写的程序用各种语言编写的程序l l目标程序目标程序目标程序目标程序源程序经过翻译，成为机器可执行的机器语言程序源程序经过翻译，成为机器可执行的机器语言程序l l库文件库文件库文件库文件由一些标准子程序由一些标准子程序(函数和过程函数和过程)及常用的应用程序块及常用的应用程序块组成的文件组成的文件l l可执行程序可执行程序可执行程序可执行程序目标程序与库文件连接后形成的程序目标程序与库文件连接后形成的程序l l程序的整个处理过程程

10、序的整个处理过程翻译翻译翻译翻译和库文件和库文件和库文件和库文件连接连接连接连接装入装入装入装入源程序源程序源程序源程序目标程序目标程序目标程序目标程序可执行程序可执行程序可执行程序可执行程序执行执行执行执行第8页，本讲稿共50页翻译系统翻译系统l l语言处理系统，语言处理系统，翻译计算机程序翻译计算机程序l l任务是把任务是把任务是把任务是把非机器语言非机器语言非机器语言非机器语言编写的编写的编写的编写的源程序源程序翻译翻译成成成成目标程序目标程序目标程序目标程序l l是系统软件是系统软件是系统软件是系统软件l l不同编程语言的翻译系统是不同的不同编程语言的翻译系统是不同的分类分类分类分类l

11、 l汇编程序汇编程序汇编程序汇编程序l l编译程序编译程序编译程序编译程序l l解释程序解释程序解释程序解释程序逐条翻译并执行源程序的语句逐条翻译并执行源程序的语句逐条翻译并执行源程序的语句逐条翻译并执行源程序的语句，不，不，不，不生成可执行文件生成可执行文件生成可执行文件生成可执行文件把源程序代码一次性翻译成目标程序代码，把源程序代码一次性翻译成目标程序代码，最终生成可执行文件最终生成可执行文件把汇编语言源程序翻译为机器语言程序把汇编语言源程序翻译为机器语言程序第9页，本讲稿共50页编编译译系系统统的的结结构构和和工工作作过过程程词法分析程序词法分析程序语法分析程序语法分析程序中间代码生成程

12、序中间代码生成程序优化程序优化程序目标代码生成程序目标代码生成程序目标程序目标程序源程序源程序Ifx=0Theny=1Elsey=-1第10页，本讲稿共50页程序设计语言程序设计语言发展阶段发展阶段l l机器语言机器语言低级低级语言语言语言语言l l汇编语言汇编语言中级中级中级中级语言语言l l面向过程的面向过程的高级高级语言语言l l面向对象的面向对象的高级高级语言语言第11页，本讲稿共50页机器语言和指令机器语言和指令机器语言机器语言l l计算机能直接执行的程序设计语言计算机能直接执行的程序设计语言计算机能直接执行的程序设计语言计算机能直接执行的程序设计语言l l二进制语言二进制语言二进制

13、语言二进制语言，用二进制机器指令来编写程序，用二进制机器指令来编写程序机器指令的信息机器指令的信息机器指令的信息机器指令的信息l l操作类型操作类型操作类型操作类型l l操作数或操作数的地址（操作数的存储位置）操作数或操作数的地址（操作数的存储位置）l l操作结果的存储位置操作结果的存储位置l l下一条指令的地址信息下一条指令的地址信息下一条指令的地址信息下一条指令的地址信息指令格式指令格式操作码操作码操作码操作码操作数或地址码操作数或地址码操作数或地址码操作数或地址码下一条指令的地址下一条指令的地址下一条指令的地址下一条指令的地址第12页，本讲稿共50页机器语言和指令机器语言和指令指令的例子

14、：指令的例子：指令的例子：指令的例子：数数1和和3的相加的相加l l指令指令指令指令100000000000000100000011“加加加加”操作码操作码操作码操作码Number1Number1：1Number21Number2：3 3l l实现过程实现过程用计算器用计算器用计算器用计算器计算机计算机计算机计算机程序程序过程过程l l指令执行过程指令执行过程特点特点特点特点l l既简单又难既简单又难既简单又难既简单又难l l执行速度最快执行速度最快执行速度最快执行速度最快l l面向机器，兼容性差，移植性差面向机器，兼容性差，移植性差l l最低级语言最低级语言第13页，本讲稿共50页汇编语言汇

15、编语言机器语言的机器语言的“符号化符号化”l l用容易记忆的文字符号用容易记忆的文字符号用容易记忆的文字符号用容易记忆的文字符号(助记符助记符助记符助记符)表示指令中的操作码和地表示指令中的操作码和地址码址码指令格式指令格式助记符助记符助记符助记符符号地址符号地址符号地址符号地址l l例：加法语句例：加法语句ADDA，B特点特点特点特点l l机器不能直接识别机器不能直接识别机器不能直接识别机器不能直接识别l l可读性好可读性好l l面向机器，兼容性差，移植性差面向机器，兼容性差，移植性差面向机器，兼容性差，移植性差面向机器，兼容性差，移植性差l l中级语言中级语言第18页，本讲稿共50页高级语

16、言高级语言与机器与机器与机器与机器完全独立的语言完全独立的语言，描述解题过程，描述解题过程，描述解题过程，描述解题过程语法与自然语言接近语法与自然语言接近特点特点l l面向问题，通用，可移植面向问题，通用，可移植分类分类l l面向过程面向过程面向过程面向过程BASICCPASCALPASCALFORTRANFORTRANCOBOLCOBOLAdaAdal l面向对象面向对象VisualBasicVisualBasic C+C+JAVAJAVADelphiDelphiPowerBuildPowerBuild第19页，本讲稿共50页面向对象程序设计面向对象程序设计程序的基本成分程序的基本成分程序的

17、基本成分程序的基本成分l l对象对象是具有特殊是具有特殊是具有特殊是具有特殊属性属性(数据数据)和和和和方法方法方法方法(行为、操作行为、操作)的的实体实体实体实体特点特点特点特点l l封装性封装性l l继承性继承性继承性继承性l l多态性多态性多态性多态性把对象的属性和操作结合在一起，构成一个独立的对象把对象的属性和操作结合在一起，构成一个独立的对象把对象的属性和操作结合在一起，构成一个独立的对象把对象的属性和操作结合在一起，构成一个独立的对象 子类可以拥有父类的属性和行为子类可以拥有父类的属性和行为子类可以拥有父类的属性和行为子类可以拥有父类的属性和行为 基类中定义的属性和行为被子类继承后

18、，可以具有不同的数据类型基类中定义的属性和行为被子类继承后，可以具有不同的数据类型基类中定义的属性和行为被子类继承后，可以具有不同的数据类型基类中定义的属性和行为被子类继承后，可以具有不同的数据类型或不同的行为或不同的行为或不同的行为或不同的行为 第20页，本讲稿共50页程序设计语言的发展历史程序设计语言的发展历史第23页，本讲稿共50页怎样编写程序怎样编写程序程序设计是一个系统过程程序设计是一个系统过程程序设计是一个系统过程程序设计是一个系统过程l l不是简单的编写程序代码不是简单的编写程序代码不是简单的编写程序代码不是简单的编写程序代码一般可以分为一般可以分为六个步骤六个步骤六个步骤六个步

19、骤l l问题的定义（程序说明）问题的定义（程序说明）l l设计解决问题的方案设计解决问题的方案设计解决问题的方案设计解决问题的方案l l编写程序代码编写程序代码编写程序代码编写程序代码l l进行程序测试进行程序测试l l编写程序的文档编写程序的文档编写程序的文档编写程序的文档l l程序应用（程序运行与维护）程序应用（程序运行与维护）程序应用（程序运行与维护）程序应用（程序运行与维护）第24页，本讲稿共50页一、理解问题：程序说明一、理解问题：程序说明程序设计中最重要的部分程序设计中最重要的部分程序设计中最重要的部分程序设计中最重要的部分l l是对问题的描述是对问题的描述l l设计一个程序是为了

20、解决某个特定的问题设计一个程序是为了解决某个特定的问题设计一个程序是为了解决某个特定的问题设计一个程序是为了解决某个特定的问题l l分析特定问题，决定分析特定问题，决定分析特定问题，决定分析特定问题，决定应该做什么，如何做应该做什么，如何做应该做什么，如何做应该做什么，如何做系统分析员系统分析员主要弄清以下问题：主要弄清以下问题：主要弄清以下问题：主要弄清以下问题：l l程序的目标是什么？即程序需要解决什么样的问题程序的目标是什么？即程序需要解决什么样的问题l l可能需要输入哪些数据？可能需要输入哪些数据？l l数据具体的处理过程和要求是什么？数据具体的处理过程和要求是什么？数据具体的处理过程

21、和要求是什么？数据具体的处理过程和要求是什么？l l程序可能产生的数据输出以及输出形式是什么？程序可能产生的数据输出以及输出形式是什么？示例示例示例示例1 1示例示例示例示例2 2第25页，本讲稿共50页二、设计解决问题的方案二、设计解决问题的方案对要解决的问题设计出具体的解决方案对要解决的问题设计出具体的解决方案l l确定确定程序的逻辑结构程序的逻辑结构l l关键关键关键关键设计算法设计算法例：例：欧几里德算法欧几里德算法求两个正整数求两个正整数A和和B的最大公约数的最大公约数第一步：比较第一步：比较A和和B这两个数，将这两个数，将A设置为较大的数，设置为较大的数，B设设置为较小的数；置为较

22、小的数；第二步：第二步：A除以除以B，得到余数，得到余数C；第三步：如果第三步：如果C等于等于0，则最大公约数就是，则最大公约数就是B；否则将否则将B赋值给赋值给A，C赋值给赋值给B，重复进行第二、三步重复进行第二、三步第26页，本讲稿共50页三、编写程序代码三、编写程序代码编写程序代码编写程序代码l l选择合适的编程语言选择合适的编程语言选择合适的编程语言选择合适的编程语言l l按照上阶段设计的算法编写代码按照上阶段设计的算法编写代码选择哪种程序设计语言？选择哪种程序设计语言？选择哪种程序设计语言？选择哪种程序设计语言？l l主要看是否能够完成程序设计任务主要看是否能够完成程序设计任务主要看

23、是否能够完成程序设计任务主要看是否能够完成程序设计任务l l编程人员对这个语言的熟悉程度编程人员对这个语言的熟悉程度程序代码的例子程序代码的例子l l计算计算计算计算5 5！fac=1*2*3*4*5分别用分别用C语言、语言、VB和和Java实现实现第30页，本讲稿共50页一个程序代码的例子（一个程序代码的例子（C语言）语言）计算计算5！#include/*C语言编译系统的库函数语言编译系统的库函数*/main()/*程序开始程序开始*/inti,fac;/*定义变量定义变量*/fac=1;/*变量变量fac被赋值被赋值1*/for(i=2;i=5;i+)/*从从2到到5，循环执行乘法得到，循

24、环执行乘法得到5的阶乘的阶乘*/fac=fac*i;printf(the5!=%d,fac)；/*输出结果输出结果*/第31页，本讲稿共50页一个程序代码的例子（一个程序代码的例子（VB语言）语言）DimiAsInteger,facAsIntegerDimiAsInteger,facAsInteger 定义定义定义定义ii、facfac为整型数变量为整型数变量为整型数变量为整型数变量fac=1 变量变量变量变量facfac赋值赋值赋值赋值1 1Fori=2To5Step1Fori=2To5Step1 循环，从循环，从2到到5，每次步长为，每次步长为1fac=fac*i 计算计算计算计算5 5的

25、阶乘的阶乘的阶乘的阶乘Nexti nextnext和和和和forfor构成循环体构成循环体构成循环体构成循环体PrintPrint fac=fac=;facfac 输出阶乘结果输出阶乘结果计算计算计算计算5 5！第32页，本讲稿共50页一个程序代码的例子（一个程序代码的例子（Java语言）语言）publicclassFactorialpublicstaticvoidmain(Stringargs)publicstaticvoidmain(Stringargs)inti=1;/循环控制变量循环控制变量循环控制变量循环控制变量doublefac=1;/存放结果的变量，注意类型存放结果的变量，注意类

26、型存放结果的变量，注意类型存放结果的变量，注意类型while(i=5)while(i=5)fac=fac*i;/循环体循环体循环体循环体i=i+1;i=i+1;System.out.println(5!=+fac);/输出结果输出结果输出结果输出结果 计算计算5！第33页，本讲稿共50页四、寻找错误：程序测试四、寻找错误：程序测试调试程序，找出程序中的错误调试程序，找出程序中的错误调试程序，找出程序中的错误调试程序，找出程序中的错误l l语法错误语法错误违反编程语言的语法规则违反编程语言的语法规则l l逻辑错误逻辑错误程序得到的结果不对程序得到的结果不对需用大量数据测试需用大量数据测试需用大量

27、数据测试需用大量数据测试测试方法测试方法l l黑盒测试黑盒测试黑盒测试黑盒测试例例例例：加法程序：加法程序：加法程序：加法程序l l白盒测试白盒测试白盒测试白盒测试专业测试，使用一组特意设计的数据测试专业测试，使用一组特意设计的数据测试第34页，本讲稿共50页五、编写程序文档五、编写程序文档对前面所做的各种设计形成完整的手册对前面所做的各种设计形成完整的手册l l设计过程中形成的文档设计过程中形成的文档流程图流程图变量列表变量列表变量列表变量列表程序代码程序代码程序代码程序代码运行结果等运行结果等供日后程序的维护、升级使用供日后程序的维护、升级使用l l设计完成后的使用手册设计完成后的使用手册

28、设计完成后的使用手册设计完成后的使用手册程序的功能程序的功能程序的功能程序的功能操作说明操作说明第35页，本讲稿共50页六、运行与维护六、运行与维护培训用户培训用户程序的安装、设置等程序的安装、设置等程序进行修改甚至升级程序进行修改甚至升级第36页，本讲稿共50页算算法法算法算法算法算法是一组是一组明确明确明确明确的、的、的、的、可以执行可以执行可以执行可以执行的步骤的的步骤的的步骤的的步骤的有序有序有序有序集合集合就是为了解决问题而采用的方法和步骤就是为了解决问题而采用的方法和步骤就是为了解决问题而采用的方法和步骤就是为了解决问题而采用的方法和步骤算法分类算法分类算法分类算法分类l l数值运

29、算算法数值运算算法l l非数值运算算法非数值运算算法 算法特性算法特性l l确定性确定性确定性确定性l l有穷性有穷性有穷性有穷性l l有效性有效性有效性有效性l l可有零个或多个输入可有零个或多个输入l l有一个或多个输出有一个或多个输出第37页，本讲稿共50页算法的表示方法算法的表示方法l l自然语言自然语言l l流程图流程图l l伪代码伪代码伪代码伪代码l lPAD图（问题分析图）图（问题分析图）例：例：求求5！的算法！的算法 *用自然语言描述用自然语言描述 *用伪代码表示用伪代码表示 用流程图表示用流程图表示用流程图表示用流程图表示P=1*2*3*4*5P=1*2*3*4*5P=P*I

30、P PI IP*IP*I1 11 1 1 11 12 2 2 22 2 3 3 6 66 6 4 4 24242424 5 5120120 120120 6 6第38页，本讲稿共50页算法设计算法设计程序设计有两个阶段程序设计有两个阶段l l第一是第一是第一是第一是设计算法设计算法设计算法设计算法l l第二是第二是第二是第二是实现算法实现算法解决问题的基本原理解决问题的基本原理(4个步骤个步骤)1.理解问题理解问题2.2.设计一个解决问题的方案设计一个解决问题的方案设计一个解决问题的方案设计一个解决问题的方案3.执行这个方案执行这个方案4.检验这个方案检验这个方案第42页，本讲稿共50页*常用

31、的算法结构常用的算法结构l l迭代结构迭代结构l l递归结构递归结构递归结构递归结构l l排序问题排序问题排序问题排序问题l l查找问题查找问题第43页，本讲稿共50页例子分析例子分析例子分析例子分析l l 判断一个整数是否为素数判断一个整数是否为素数素数是指只能被素数是指只能被素数是指只能被素数是指只能被1 1 1 1和它本身整除的数和它本身整除的数和它本身整除的数和它本身整除的数判断方法：判断方法：判断方法：判断方法：用用用用2 2到到到到(n-1)(n-1)的的的的各个整数轮流去除各个整数轮流去除各个整数轮流去除各个整数轮流去除n n n n，如果都不能，如果都不能，如果都不能，如果都不

32、能整除，则整除，则整除，则整除，则n n是素数。是素数。是素数。是素数。算法：算法：算法：算法：第第第第1 1步：输入步：输入步：输入步：输入n n的值的值的值的值第第第第2 2步：步：步：步：j=2(j=2(准备用准备用准备用准备用j j去除去除去除去除n)n)第第第第3 3步：步：步：步：n n被被被被j j除，得到余数除，得到余数除，得到余数除，得到余数a a第第第第4 4步：步：步：步：如如如如a=0a=0，表示，表示，表示，表示n n能被能被能被能被j j整除，输出信息整除，输出信息整除，输出信息整除，输出信息“n n不是素数不是素数不是素数不是素数”，算法结束；否则就是，算法结束；否则就是，算法结束；否则就是，算法结束；否则就是n n不能被不能被不能被不能被j j整除，进入下一步；整除，进入下一步；整除，进入下一步；整除，进入下一步；第第第第5 5步：将步：将步：将步：将j j加加加加1 1送回给送回给送回给送回给j j第第第第6 6步：步：步：步：如果如果如果如果jnjn，则跳到第，则跳到第，则跳到第，则跳到第3 3步执行，步执行，步执行，步执行，否则否则否则否则输出输出输出输出“n n是素数是素数是素数是素数”的信息的信息的信息的信息算法结束算法结束算法结束算法结束第45页，本讲稿共50页