搜索
第二章程序的灵魂—算法§2.1算法的概念算法即程序操作的步骤。广义的说：算法就是为解决一个问题而采取的方法和步骤。数据结构就是程序中指定的数据类型和数据的组织形式。Wirth教授认为：程序＝数据结构＋算法实际上程序还应该包括语言环境和程序设计方法。§2.2简单举例例：对于一个大于3的正整数n，判断它是不是一个素数。(n被2,3,4……n-1除，若都不能整除，则n是素数)算法：S1:输入n的值S2：m＝2S3：n被m除，得余数rS4:如果r=0,表示n能被m整除，则打印“n不是素数”，算法结束;否则执行s5S5：m=m+1S6:如果m＝n-1，返回s3；否则打印“n不是素数”然后结束。§2.3算法的特性有穷性：即有限步解决问题；确定性:算法的每一个步骤不能含糊；有零个或多个输入；有一个或多个输出；有效性；§2.4算法的表示起止框输入输出框判断框处理框或流程线连接点注释框一些常用的流程图符号三种基本结构顺序结构选择（选取、分支）结构循环（重复）结构abAB顺序结构注：A,B可以是一个简单语句，也可以是一个基本结构选择（选取、分支）结构BAPab成立不成立APb成立不成立a选择结构BAPab成立不成立循环（重复）结构①当（while）型循环结构②直到型（Until）循环P1Aba成立当型循环结构P2Aba成立不成立直到型循环kA1A2AiAnk=k2k=k1k=knk=ki......多分支选择结构三种结构的特点：（1）只有一个入口和出口（2）结构内的每一部分都有机会被执行到。（3）结构内不存在死循环例：判断闰年的算法开始结束年份→yy能被4整除y能被100整除y能被400整除打印y“是润年”打印y“不是润年”打印y“不是润年”打印y“是润年”NNN表示算法的其他方法§用N-S流程图表示算法(1)顺序结构ABAB流程图N-S图(2)二分支选择结构PAB真假PBA真假(3)循环结构当型循环结构直到型循环结构PA假真当P为真AAP真假A直到P为真用伪代码表示算法例：打印2000－2500年中的每一年是否闰年。BEGIN2000ywhiley=2500{ify被4整除ify不被100整除printy;“闰年”elseify被400整除printy;“闰年”elseprinty;“非闰年”elseprinty;“非闰年”y=y+1}END§2.5结构化程序设计方法基本思路:把一个复杂问题的求解过程分阶段进行，每个阶段处理的问题都控制在人们容易理解和处理的范围内。具体方法：(1)自顶向下；(2)逐步细化；(3)模块化设计；(4)结构化编码。特点：考虑周全、结构清晰、层次分明、修改容易。过程：将问题求解由抽象逐步具体化，从顶层设计然后一步步细化。功能：将复杂的问题分解成若干个简单的问题。逐步细化的实现方法把给定的模块功能转换成它的详细过程性描述，通常都采用逐步细化的策略。例：在一组数中找出其中的最大数1.输入一组数;2.找出其中的最大数3.输出最大数2.1.任取一数,假设它就是最大数2.2.将该数与其余各数逐一比较2.3.若发现有任何数大于该假设的最大数,即取而代之.1.输入一个数组2.1先设第一个元素为最大数2.2从第二个到最后一个比较.2.3如果新元素最大数则将新元素→最大数3.输出逐步细化的实现方法逐步细化的步骤：（1）由粗到细地对程序进行逐步的细化。（2）在细化程序的过程中，同时对数据的描述进行细化。（3）每一步细化均使用相同的结构化语言，最后一步一般直接用伪代码来描述，以便编码时直接翻译为程序。优点：（1）每一步只优先处理当前最需要细化的部分，其余部分则推迟到适当的时机再考虑。（2）易于验证程序正确性，易为非专业人员接受，因而也更加实用。用“结构化”保证程序的清晰易读用“逐步细化”实现程序的正确性可靠