算法与结构化程序设计.pptx

实际上，一个程序除了以上两个主要要素之外，还应当采用结构化程序设计方法进行程序设计，并且用某一种计算机语言表示。因此，可以这样表示：程序=算法+数据结构+程序设计方法+语言工具和环境也就是说，以上4个方面中，算法是灵魂，数据结构是加工对象，语言是工具，编程需要采用合适的方法。算法是解决“做什么”和“怎么做”的问题。程序中的操作语句，实际上就是算法的体现。显然，不了解算法就谈不上程序设计。第1页/共28页第八讲第八讲 算法与结构化程序设计算法与结构化程序设计综合第5章、第11章学习目标熟悉算法的基本概念，了解算法、程序与代码的关系学会怎样表示一个算法掌握结构化程序设计的一般方法了解程序测试的基本方法与手段第2页/共28页算法的概念与特征算法的基本概念为解决某类问题而设计或采取的方法或步骤演算过程的抽象表述算法必须能够转化为计算机可执行的指令序列（代码）算法的基本特征有穷性：算法必须能够在有限步内终止确定性：每一步骤的顺序和内容不能有二义性有效性：所有操作都有明确含义并能够实现有零个或多个输入：算法应该接受处理数据有一个或多个输出：算法必须能够输出结果正确性不是算法的特征，算法的正确正确性不是算法的特征，算法的正确正确性不是算法的特征，算法的正确正确性不是算法的特征，算法的正确性由设计者保证！性由设计者保证！性由设计者保证！性由设计者保证！第3页/共28页有50个学生，要求将他们之中成绩在80分以上者打印出来。用n表示学生学号，n1代表第一个学生学号，ni代表第i个学生学号。用g代表学生成绩，gi代表第i个学生成绩，算法可表示如下。S1：1=i S2：如果gi80，则打印ni和gi，否则不打印 S3：i+1=i S4：如果i50，返回S2，继续执行；否则，算法结束。本例中，变量i作为下标，用它来控制序号(第几个学生，第几个成绩)。当i超过50时，表示已对50个学生的成绩处理完毕，算法结束。算法举例第4页/共28页怎样表示一个算法一个算法可用不同的方法表示。自然语言 流程图 NS图（结构化流程图）伪代码 等等 第5页/共28页用流程图表示算法流程图是用一些图框表示各种操作。用图形表示算法，直观形象，易于理解。美国国家标准化协会ANSI(American National Standard Institute)规定了一些常用的流程图符号。第6页/共28页第7页/共28页第8页/共28页N-S图表示算法(1)顺序结构:A和B两个框组成一个顺序结构。(2)选择结构：当p条件成立时执行A操作，p不成立则执行B操作。请图是一个整体，代表一个基本结构。第9页/共28页N-S图表示算法（3）循环结构 第10页/共28页用伪代码表示算法伪代码是用介于自然语言和计算机语言之间的文字和符号来描述算法。它如同一篇文章，自上而下地写下来。每一行(或几行)表示一个基本操作。它不用图形符号，因此书写方便、格式紧凑，也比较好懂，便于向计算机语言算法(即程序)过渡。用伪代码写算法并无固定的、严格的语法规则，以便于书写和阅读为原则，只要把意思表达清楚，书写格式要清晰易读的形式。第11页/共28页代码与伪代码给定两个正整数m与n，设计求解最大公因子的算法int int gcdgcd(int(int mm,int,int n n)int int r r;start start:r r=mm%n n;if(if(r r=0)=0)return return n n;mm=n n;n n=r r;goto goto startstart;代码代码代码代码以计算机语言书写，计算机易理解，以计算机语言书写，计算机易理解，以计算机语言书写，计算机易理解，以计算机语言书写，计算机易理解，程序员不易理解程序员不易理解程序员不易理解程序员不易理解伪代码界于自然语言与计算机语言之间，伪代码界于自然语言与计算机语言之间，伪代码界于自然语言与计算机语言之间，伪代码界于自然语言与计算机语言之间，一般用符号或文字表示算法的实际执行一般用符号或文字表示算法的实际执行一般用符号或文字表示算法的实际执行一般用符号或文字表示算法的实际执行步骤，程序员易理解，计算机不理解步骤，程序员易理解，计算机不理解步骤，程序员易理解，计算机不理解步骤，程序员易理解，计算机不理解输入：整数输入：整数输入：整数输入：整数mm与与与与n n输出：输出：输出：输出：mm与与与与n n的最大公因子的最大公因子的最大公因子的最大公因子步骤步骤步骤步骤1 1：mm除以除以除以除以n n，余数为余数为余数为余数为r r步骤步骤步骤步骤2 2：若：若：若：若r r为为为为0 0，则，则，则，则n n为所求，算法终为所求，算法终为所求，算法终为所求，算法终止；否则止；否则止；否则止；否则步骤步骤步骤步骤3 3：将：将：将：将n n作为新作为新作为新作为新mm，r r作为新作为新作为新作为新n n，返回返回返回返回第第第第1 1步重新计算步重新计算步重新计算步重新计算P113第12页/共28页结构化程序的组织程序的结构化程序的一般结构结构化与函数抽象第13页/共28页程序的结构化结构化结构化语句：满足单入口单出口条件的语句复合语句、分支语句与循环语句都是结构化语句结构化程序：使用结构化语句设计的程序结构定理：所有程序都可使用上述三类结构化语句实现结构化优点单入口单出口的控制流易于确定程序动态计算过程，易于理解注意事项结构化程序并不一定是好程序，程序合理组织最重要！数据代码的基本概念见教材5.1和5.2第14页/共28页程序的一般结构根据用户输入的底面半径与高度，计算圆柱体体积#include include /*/*包含必要的头文件包含必要的头文件包含必要的头文件包含必要的头文件*/*/#define define PIPI 3.14159265 3.14159265 /*PI/*PI宏定义宏定义宏定义宏定义,一次定义多次使用一次定义多次使用一次定义多次使用一次定义多次使用*/*/float float radiusradius,heightheight,volumevolume;/*/*全局变量声明全局变量声明全局变量声明全局变量声明*/*/void void mainmain()()/*/*主函数主函数主函数主函数*/*/*/*输入半径与高度输入半径与高度输入半径与高度输入半径与高度*/*/printfprintf(“This program computes the volume of the cylinder.(“This program computes the volume of the cylinder.n n“);“);printfprintf(“Please input the radius value:“);(“Please input the radius value:“);scanfscanf(“%(“%f f“,&“,&radiusradius););printfprintf(“Please input the height value:“);(“Please input the height value:“);scanfscanf(“%(“%f f“,&“,&heightheight););/*/*计算体积计算体积计算体积计算体积*/*/volumevolume=PIPI*radiusradius*radiusradius*heightheight;/*/*输出体积输出体积输出体积输出体积*/*/printfprintf(“The volume of the cylinder is%(“The volume of the cylinder is%f f n n“,“,volumevolume););主函数包括输入、计算与输出三部分主函数包括输入、计算与输出三部分主函数包括输入、计算与输出三部分主函数包括输入、计算与输出三部分程序无非是对特定输入数据进行处程序无非是对特定输入数据进行处程序无非是对特定输入数据进行处程序无非是对特定输入数据进行处理并输出处理结果的指令序列，所理并输出处理结果的指令序列，所理并输出处理结果的指令序列，所理并输出处理结果的指令序列，所以任何程序都应包括输入、计算与以任何程序都应包括输入、计算与以任何程序都应包括输入、计算与以任何程序都应包括输入、计算与输出三部分输出三部分输出三部分输出三部分第15页/共28页结构化与函数抽象程序设计过程按照功能需求，进行自顶向下的功能分解与逐步求精，最终形成代码大多数问题的求解过程非常复杂，如何合理地控制程序规模和复杂性呢？程序的分割与结构化：着重于安排操作序列而不是数据结构，使程序易于创建、理解与维护函数抽象：结构化程序设计的主要工具体现要执行的命令、计算或任务，这些抽象构成了函数用户只关心抽象的语法和该抽象提供的功能或服务，不关心如何实现该功能第16页/共28页结构化与函数抽象示例根据用户输入的底面半径与高度，计算圆柱体体积#include include /*/*包含必要的头文件包含必要的头文件包含必要的头文件包含必要的头文件*/*/#define define PIPI 3.14159265 3.14159265 /*/*PIPI宏定义宏定义宏定义宏定义,一次定义多次使用一次定义多次使用一次定义多次使用一次定义多次使用*/*/float float radiusradius,heightheight,volumevolume;/*/*全局变量声明全局变量声明全局变量声明全局变量声明*/*/void void InputInput();();/*/*输入半径与高度，将实际的输入操作隐藏在函数内部输入半径与高度，将实际的输入操作隐藏在函数内部输入半径与高度，将实际的输入操作隐藏在函数内部输入半径与高度，将实际的输入操作隐藏在函数内部 */*/void void ComputeCompute();();/*/*计算体积，将实际的计算过程隐藏在函数内部计算体积，将实际的计算过程隐藏在函数内部计算体积，将实际的计算过程隐藏在函数内部计算体积，将实际的计算过程隐藏在函数内部*/*/void void OutputOutput();();/*/*输出体积，将实际的输出操作隐藏在函数内部输出体积，将实际的输出操作隐藏在函数内部输出体积，将实际的输出操作隐藏在函数内部输出体积，将实际的输出操作隐藏在函数内部*/*/void void mainmain()()/*/*主函数，表现为对上述函数的调用，无其他代码主函数，表现为对上述函数的调用，无其他代码主函数，表现为对上述函数的调用，无其他代码主函数，表现为对上述函数的调用，无其他代码 */*/InputInput();();ComputeCompute();();OutputOutput();();主函数是否更容易理解？主函数是否更容易理解？主函数是否更容易理解？主函数是否更容易理解？没有复杂的输入、计算与输出的实现细节，理解主函数一点都不没有复杂的输入、计算与输出的实现细节，理解主函数一点都不没有复杂的输入、计算与输出的实现细节，理解主函数一点都不没有复杂的输入、计算与输出的实现细节，理解主函数一点都不困难困难困难困难在主函数层次，只需了解一旦声明三个全局变量，连续调用上述三个函数即能完成主在主函数层次，只需了解一旦声明三个全局变量，连续调用上述三个函数即能完成主在主函数层次，只需了解一旦声明三个全局变量，连续调用上述三个函数即能完成主在主函数层次，只需了解一旦声明三个全局变量，连续调用上述三个函数即能完成主函数的计算任务就可以了函数的计算任务就可以了函数的计算任务就可以了函数的计算任务就可以了第17页/共28页结构化与函数抽象示例（续）void void InputInput()()printf printf(“This program computes the volume of the cylinder.(“This program computes the volume of the cylinder.n n“);“);printfprintf(“Please input the radius value:“);(“Please input the radius value:“);scanfscanf(“%(“%f f“,&“,&radiusradius););printfprintf(“Please input the height value:“);(“Please input the height value:“);scanfscanf(“%(“%f f“,&“,&heightheight););void void ComputeCompute()()volumevolume=PIPI*radiusradius*radiusradius*heightheight;void void OutputOutput()()printf printf(“The volume of the cylinder is%(“The volume of the cylinder is%f f n n“,“,volumevolume););只有在确实必要的时候才需要了解只有在确实必要的时候才需要了解只有在确实必要的时候才需要了解只有在确实必要的时候才需要了解这三个函数的具体实现细节与代码这三个函数的具体实现细节与代码这三个函数的具体实现细节与代码这三个函数的具体实现细节与代码通过程序分割与逻辑分组，程序分离通过程序分割与逻辑分组，程序分离通过程序分割与逻辑分组，程序分离通过程序分割与逻辑分组，程序分离成一个一个的模块成一个一个的模块成一个一个的模块成一个一个的模块在需要的时候，在需要的时候，在需要的时候，在需要的时候，我们可以使用这些模块像积木一样构我们可以使用这些模块像积木一样构我们可以使用这些模块像积木一样构我们可以使用这些模块像积木一样构造整个程序造整个程序造整个程序造整个程序第18页/共28页功能分解与逐步求精自顶向下的功能分解先从整体考虑问题，将原始问题分解成逻辑上相互独立的多个部分；一一实现分解后的各部分，将上述实现组装成原始问题的解功能分解必须按照程序需求进行，分解后的各部分应能实现为单入口单出口的函数逐步求精对于复杂系统，功能分解可能不会一步到位，对于某些部分可能需要重复上述功能分解步骤第19页/共28页第20页/共28页程序测试与代码优化程序测试顺序结构：一般一次测试分支结构：所有分支路径都需测试循环结构：第一次迭代，最后一次迭代，中间一次迭代程序调试：查找与改正错误语法错误与逻辑错误程序效率与代码优化正确性不是程序设计的全部，效率同样重要第21页/共28页程序测试示例编程实现摄氏温度到华氏温度的转换，温度转换公式为 ，c 为摄氏温度值，f 为转换后的华氏温度值#include include /*/*包含必要的头文件包含必要的头文件包含必要的头文件包含必要的头文件*/*/float float f f,c c;/*/*全局变量声明全局变量声明全局变量声明全局变量声明*/*/float float GetFloatValueGetFloatValue(char*(char*promptprompt););/*/*获取用户输入的浮点数据获取用户输入的浮点数据获取用户输入的浮点数据获取用户输入的浮点数据*/*/void void InputInput();();/*/*输入数据，将实际的输入过程隐藏在函数内部输入数据，将实际的输入过程隐藏在函数内部输入数据，将实际的输入过程隐藏在函数内部输入数据，将实际的输入过程隐藏在函数内部*/*/void void ComputeCompute();();/*/*温度转换，将实际的计算过程隐藏在函数内部温度转换，将实际的计算过程隐藏在函数内部温度转换，将实际的计算过程隐藏在函数内部温度转换，将实际的计算过程隐藏在函数内部*/*/void void OutputOutput();();/*/*输出结果，将实际的输出操作隐藏在函数内部输出结果，将实际的输出操作隐藏在函数内部输出结果，将实际的输出操作隐藏在函数内部输出结果，将实际的输出操作隐藏在函数内部*/*/void void mainmain()()/*/*主函数，表现为对上述函数的调用，无其他代码主函数，表现为对上述函数的调用，无其他代码主函数，表现为对上述函数的调用，无其他代码主函数，表现为对上述函数的调用，无其他代码 */*/InputInput();();ComputeCompute();();OutputOutput();();第22页/共28页程序测试示例（续）float float GetFloatValueGetFloatValue(char*(char*promptprompt)float float t t;printfprintf(“%(“%s s“,“,promptprompt););scanfscanf(“%(“%f f“,&“,&t t);return);return t t;void void InputInput()()c c=GetFloatValueGetFloatValue(“Please input temperature value(C):“);(“Please input temperature value(C):“);void void ComputeCompute()()f f=c c*1.8+32;*1.8+32;void void OutputOutput()()printfprintf(“Temperature Value(F):%(“Temperature Value(F):%f f n n“,“,f f););功能分解的好处：本例主函数的实现与体积计算程序完功能分解的好处：本例主函数的实现与体积计算程序完功能分解的好处：本例主函数的实现与体积计算程序完功能分解的好处：本例主函数的实现与体积计算程序完全相同，程序结构也相同全相同，程序结构也相同全相同，程序结构也相同全相同，程序结构也相同第23页/共28页程序调试示例下述程序存在一些错误，请找出#include include float float f f,c c;float float GetFloatValueGetFloatValue(char*(char*promptprompt););void void InputInput();();void void ComputeCompute();();void void OutputOutput();();void void mainmain()()InputInput();();ComputComput();();OutputOutput();();绝对零度的概念必须遵守：程序不能脱离所解决问绝对零度的概念必须遵守：程序不能脱离所解决问绝对零度的概念必须遵守：程序不能脱离所解决问绝对零度的概念必须遵守：程序不能脱离所解决问题的物理世界而存在题的物理世界而存在题的物理世界而存在题的物理世界而存在如何改正？如何改正？如何改正？如何改正？使用断言！使用断言！使用断言！使用断言！#include include assertassert(c c 273.13);273.13);#define define ABSOLUTE_ZEROABSOLUTE_ZERO 273.13 273.13assertassert(c c ABSOLUTE_ZEROABSOLUTE_ZERO););第24页/共28页代码优化示例如何优化下述代码，提高程序执行效率？#include include#include include#define define ABSOLUTE_ZEROABSOLUTE_ZERO 273.13 273.13float float f f,c c;void void ComputeCompute()()f f=c c*1.8+32;*1.8+32;void void mainmain()()InputInput();();assertassert(c c ABSOLUTE_ZEROABSOLUTE_ZERO););Compute Compute();();OutputOutput();();f f的计算需要三次类型转换：的计算需要三次类型转换：的计算需要三次类型转换：的计算需要三次类型转换：c c为为为为floatfloat，1.81.8为为为为doubledouble，而而而而3232为为为为intint，乘法运算前乘法运算前乘法运算前乘法运算前c c需先转换成需先转换成需先转换成需先转换成doubledouble，加法加法加法加法运算前运算前运算前运算前3232需先转换成需先转换成需先转换成需先转换成doubledouble，结果为结果为结果为结果为doubledouble，再转再转再转再转换成换成换成换成floatfloat赋值给赋值给赋值给赋值给f f，转换过程浪费了时间转换过程浪费了时间转换过程浪费了时间转换过程浪费了时间#include include#include include#define define ABSOLUTE_ZEROABSOLUTE_ZERO 273.13 273.13F Ffloat float f f,c c;void void ComputeCompute()()f f=c c*1.8*1.8F F+32.0+32.0F F;void void mainmain()()InputInput();();assertassert(c c ABSOLUTE_ZEROABSOLUTE_ZERO););Compute Compute();();OutputOutput();();修改后代码不需要类型转换，效率更高修改后代码不需要类型转换，效率更高修改后代码不需要类型转换，效率更高修改后代码不需要类型转换，效率更高第25页/共28页本讲小结算法与结构化程序设计 什么是算法？算法的五个基本特征 算法的表示方法：流程图、N-S图、伪代码 程序结构化：结构化语句、结构化程序 结构化程序设计：自顶向下、逐步求精 程序测试的基本方法 第26页/共28页作 业第132页：第三题（编程题）第1、8小题第27页/共28页感谢您的观看！第28页/共28页