程序设计导论-课件

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