程序设计导论(讲解如何画算法流程图)

程序设计导论一、算法概述二、程序流程图与算法的基本逻辑结构一个程序主要包括以下两方面的信息：(1)对数据的描述。在程序中要指定用到哪些数据以及这些数据的类型和数据的组织形式:这就是数据结构(datastructure)(2)对操作的描述。即要求计算机进行操作的步骤也就是算法(algorithm)第一部分:算法概述•数据:是操作的对象•操作的目的:是对数据进行加工处理，以得到期望的结果•著名计算机科学家沃思(NikiklausWirth)提出一个公式：算法+数据结构=程序算法是解决“做什么”和“怎么做”的问题程序中的操作语句代码，是算法的体现不了解算法就谈不上程序设计1.什么是算法广义地说，为解决一个问题而采取的方法和步骤，就称为“算法”对同一个问题，可以有不同的解题方法和步骤为了有效地进行解题，不仅需要保证算法正确，还要考虑算法的质量，选择合适的算法计算机算法可分为两大类别：◦数值运算算法◦非数值运算算法数值运算的目的是求数值解非数值运算包括的面十分广泛，最常见的是用于事务管理领域2.简单的算法举例例.1求1×2×3×4×5可以用最原始的方法进行：◦步骤1：先求1*2，得到结果2。◦步骤2：将步骤1得到的乘积2再乘以3，得到结果6。◦步骤3：将6再乘以4，得24。◦步骤4：将24再乘以5，得120。这就是最后的结果。例.1求1×2×3×4×5×…×1000太繁琐改进的算法：◦设变量p为被乘数◦变量i为乘数◦用循环算法求结果S1：使p=1，或写成1pS2：使i=2，或写成2iS3：使p与i相乘，乘积仍放在变量p中，可表示为：p*ipS4：使i的值加1，即i+1iS5：如果i不大于5，返回重新执行S3；否则，算法结束最后得到p的值就是5!的值若是1000，求什么？例:判定2000—2500年中的每一年是否闰年，并将结果输出。闰年的条件：(1)能被4整除，但不能被100整除的年份都是闰年，如2008、2012、2048年(2)能被400整除的年份是闰年，如2000年◦不符合这两个条件的年份不是闰年◦例如2009、2100年设year为被检测的年份。算法表示如下：◦S1：2000year◦S2：若year不能被4整除，则输出year的值和“不是闰年”。然后转到S6◦S3：若year能被4整除，不能被100整除，则输出year的值和“是闰年”。然后转到S6◦S4：若year能被400整除，则输出year的值和“是闰年”，然后转到S6◦S5:其他情况输出year的值和“不是闰年”◦S6：year+1year◦S7：当year≤2500时，转S2，否则停止year不能被4整除非闰年year被4整除，但不能被100整除闰年year被100整除，又能被400整除闰年其他非闰年逐渐缩小判断的范围例:给出一个大于或等于3的正整数，判断它是不是一个素数。所谓素数(prime)，是指除了1和该数本身之外，不能被其他任何整数整除的数例如，13是素数，因为它不能被2，3，4，…，12整除。判断一个数n(n≥3)是否素数：将n作为被除数，将2到(n-1)各个整数先后作为除数，如果都不能被整除，则n为素数S1：输入n的值S2：i=2（i作为除数）S3：n被i除，得余数rS4：如果r=0，表示n能被i整除，则输出n“不是素数”，算法结束；否则执行S5S5：i+1iS6：如果i≤n-1，返回S3；否则输出n“是素数”，然后结束。可改为n/2n十进制数转换成二进制数（整数部分）方法:除2取余214……027…..02223….11…1..1028余数高位低位你能用算法步骤将此算法描述出来吗?S1:S2:……3.算法的特性一个有效算法应该具有以下特点：(1)有穷性。一个算法应包含有限的操作步骤，而不能是无限的。(2)确定性。算法中的每一个步骤都应当是确定的，而不应当是含糊的、模棱两可的。一个有效算法应该具有以下特点：(3)有零个或多个输入。所谓输入是指在执行算法时需要从外界取得必要的信息。(4)有一个或多个输出。算法的目的是为了求解，“解”就是输出。◦没有输出的算法是没有意义的。(5)有效性。算法中的每一个步骤都应当能有效地执行，并得到确定的结果。对于一般最终用户来说:◦他们并不需要在处理每一个问题时都要自己设计算法和编写程序◦可以使用别人已设计好的现成算法和程序◦只需根据已知算法的要求给予必要的输入，就能得到输出的结果输入3个数黑箱子3个数中最大数求3个数的最大数4.怎样表示一个算法常用的方法有：◦自然语言◦传统流程图◦结构化流程图◦伪代码◦……(1)用自然语言表示算法(2)用流程图表示算法(3)用N-S流程图表示算法(4)用伪代码表示算法(5)用计算机语言表示算法(1)用自然语言表示算法以上几个方面介绍的算法是用自然语言表示的用自然语言表示通俗易懂，但文字冗长，容易出现歧义性用自然语言描述包含分支和循环的算法，不很方便除了很简单的问题外，一般不用自然语言(2)用流程图表示算法例:将以下算法用流程图表示。求1×2×3×4×5如果需要将最后结果输出:1ti5开始2it*iti+1i结束NY(4)用伪代码表示算法伪代码是用介于自然语言和计算机语言之间的文字和符号来描述算法用伪代码写算法并无固定的、严格的语法规则，可以用英文，也可以中英文混用例:求5!begin(算法开始)1t2iwhilei≤5{t*iti+1i}printtend(算法结束)(5)用计算机语言表示算法要完成一项工作，包括设计算法和实现算法两个部分。设计算法的目的是为了实现算法。不仅要考虑如何设计一个算法，也要考虑如何实现一个算法。例:（求5!）用C语言表示。#includestdio.hintmain(){inti,t;t=1;i=2;while(i=5){t=t*i;i=i+1;}printf(%d\n,t);return0;}二、程序流程图与算法的基本逻辑结构1、流程图表示算法例：判断素数的算法用流程图表示。对一个大于或等于3的正整数，判断它是不是一个素数。NY输出n是素数结束开始输入n2in%irr=0i+1iin输出n是素数YN通过以上例子可以看出流程图是表示算法的较好的工具一个流程图包括以下几部分：(1)表示相应操作的框(2)带箭头的流程线(3)框内外必要的文字说明流程线不要忘记画箭头，否则难以判定各框的执行次序2.三种基本结构和改进的流程图的画法1）.传统流程图的弊端传统的流程图用流程线指出各框的执行顺序，对流程线的使用没有严格限制使用者可以毫不受限制地使流程随意地转来转去，使人难以理解算法的逻辑2)三种基本结构(1)顺序结构AB(2)选择结构ABYpNAYpN(3)循环结构①当型循环结构AYp1NYx5N0x输出x的值x+1x输出1,2,3,4,5②直到型循环结构AYp2NYx≧5N0x输出x的值x+1x输出1,2,3,4,5以上三种基本结构，有以下共同特点：(1)只有一个入口(2)只有一个出口一个判断框有两个出口一个选择结构只有一个出口(3)结构内的每一部分都有机会被执行到。也就是说，对每一个框来说，都应当有一条从入口到出口的路径通过它(4)结构内不存在“死循环”由三种基本结构派生出来的结构：ANp2YB根据表达式p的值进行选择AB…MN求质数（素数）3.三种基本结构流程图的画法举例例例