[其它课程]第二章 算法.pptVIP

第二章 程序的灵魂—算法 一个程序应包括： 对数据的描述：在程序中要指定数据的类型和数据的组织形式，即数据结构（data structure）。 对操作的描述：即操作步骤，也就是算法（algorithm）。 Nikiklaus Wirth提出的公式： 数据结构 + 算法 = 程序 程序=算法+数据结构+程序设计方法+语言工具和环境 2.1 算法的概念 做任何事情都有一定的步骤。 为解决一个问题而采取的方法和步骤，就称为算法。 计算机算法：计算机能够执行的算法。 计算机算法可分为两大类： 数值运算算法：求解数值； 非数值运算算法：事务管理领域 2.2 简单算法举例 【例2.1】求1×2×3×4×5。 最原始方法： 步骤1：先求1×2，得到结果2。 步骤2：将步骤1得到的乘积2乘以3，得到结果6。 步骤3：将6再乘以4，得24。 步骤4：将24再乘以5，得120。 这样的算法虽然正确，但太繁。 改进的算法： S1: 使t=1 S2: 使i=2 S3: 使t×i, 乘积仍然放在在变量t中，可表示为t×i→t S4: 使i的值+1，即i+1→i S5: 如果i≤5, 返回重新执行步骤S3以及其后的S4和S5；否则，算法结束。 如果计算100！只需将S5:若i≤5改成i≤100即可。 求1×3×5×7×9×11 算法也只需做很少的改动： S1: 1→t S2: 3→i S3: t×i→t S4: i+2→i S5:若i≤11, 返回S3，否则，结束。 该算法不仅正确，而且是计算机较好的算法，因为计算机是高速运算的自动机器，实现循环轻而易举。 思考：若将 S5写成：S5:若i＜11, 返回S3;否则，结束 。结果将怎样？ 【例2.2】有50个学生，要求将他们之中成绩在80分以上者打印出来。 如果，n表示学生学号，ni表示第个学生学号；g表示学生成绩，gi表示第个学生成绩；则算法可表示如下： S1: 1→i S2: 如果gi≥80，则打印ni和gi，否则不打印 S3: i+1→i S4:若i≤50, 返回S2，否则，结束。 【例2.3】判定2000 — 2500年中的每一年是否闰年，将结果输出。 润年的条件： 能被4整除，但不能被100整除的年份； 能被100整除，又能被400整除的年份； 设y为被检测的年份，则算法可表示如下： S1: 2000→y S2:若y不能被4整除，则输出y“不是闰年”，然后转到S6 S3:若y能被4整除，不能被100整除，则输出y“是闰年”，然后转到S6 S4:若y能被100整除，又能被400整除，输出y“是闰年” 否则输出y“不是闰年”，然后转到S6 S5:输出y“不是闰年”。 S6:y+1→y S7:当y≤2500时, 返回S2继续执行，否则，结束。 【例2.4】求 算法可表示如下： S1: sign=1 S2: sum=1 S3: deno=2 S4: sign=(-1)×sign S5: term= sign×(1/deno ) S6: sum=sum+term S7: deno= deno +1 S8:若deno≤100，返回S4；否则，结束。 【例2.5】对一个大于或等于3的正整数，判断它是不是一个素数。 S1: 输入n的值 S2: i=2 S3: n被i除，得余数r S4:如果r=0，表示n能被i整除，则打印n“不是素数”，算法结束；否则执行S5 S5: i+1→i S6:如果i≤n-1，返回S3；否则打印n“是素数”；然后算法结束。 改进： S6:如果i≤ ，返回S3；否则打印n“是素数”;然后算法结束。 2.3 算法的特性 有穷性：一个算法应包含有限的操作步骤而不能是无限的。 确定性：算法中每一个步骤应当是确定的，而不能应当是含糊的、模棱两可的。 有零个或多个输入。 有一个或多个输出。 有效性：算法中每一个步骤应当能有效地执行，并得到确定的结果。 2.4 怎样表示一个算法 2.4.1用自然语言表示算法 除了很简单的问题，一般不用自然语言表示算法。 2.4.2用流程图表示算法 流程图表示算法，直观形象，易于理解。 【例2.6】将例2.1求5!的算用流程图表示。 【例2.7】将例2.2的算用流程图表示。 【例2.8】将例2.3判定闰年的算用流程图表示。 综上所述一个流程图包括： 表示相应操作的框； 带箭头的流程线； 框内外必要的文字说明。 2.4.3 三种基本结构和改进的流程图 1. 顺序结构： 2. 选择结构： 3. 循环结构 三种基本结构的共同特点： 只有一个入口； 只有一个出口； 结构内的每一部分都有机会被执行到； 结构内不存在“死循环”。 2.4.4 用N-S流程图表示算法 1973年美国学者提出了一种新型流程图：N-S流程图。 顺序结构： 选择结构