第2章 程序的灵魂——算法 2.1 算法的概念 2.2 简单算法举例 2.3 算法的特性 2.4 怎样表示一个算法 2.5结构化程序设计方法 习题
2.1 算法的概念 2.2 简单算法举例 2.3 算法的特性 2.4 怎样表示一个算法 2.5 结构化程序设计方法 习题 第2章 程序的灵魂——算法
2.1算法的概念 从事各种工作和活动，都必须事先想好进行的步骤， 然后按部就班地进行，才能避免产生错乱。 不要认为只有“计算”的问题才有算法。广义地说， 为解决一个问题而采取的方法和步骤，就称为 “算法”。 对同一个问题，可以有不同的解题方法和步骤。方 法有优劣之分。有的方法只需进行很少的步骤， 而有些方法则需要较多的步骤。一般说，希望采 用简单的和运算步骤少的方法。因此，为了有效 地进行解题，不仅需要保证算法正确，还要考虑 算法的质量，选择合适的算法
2.1 算 法 的 概 念 从事各种工作和活动，都必须事先想好进行的步骤， 然后按部就班地进行，才能避免产生错乱。 不要认为只有“计算”的问题才有算法。广义地说， 为解决一个问题而采取的方法和步骤，就称为 “算法”。 对同一个问题，可以有不同的解题方法和步骤。方 法有优劣之分。有的方法只需进行很少的步骤， 而有些方法则需要较多的步骤。一般说，希望采 用简单的和运算步骤少的方法。因此 ，为了有效 地进行解题，不仅需要保证算法正确，还要考虑 算法的质量，选择合适的算法
2.2简单算法举例 例2.3判定2000一2500年中的每一年是否闰年，将结 果输出。 闰年的条件是：①能被4整除，但不能被100整除的 年份都是闰年，如1996年，2004年是闰年；②能 被100整除，又能被400整除的年份是闰年。如 1600年、2000年是闰年。不符合这两个条件的年 份不是闰年。 算法可表示如下： 设y为被检测的年份。可采取以下步骤： S1:2000=>y S2:y不能被4整除，则输出y“不是闰年”。然后转 到S6
例2.3 判定2000—2500年中的每一年是否闰年，将结 果输出。 闰年的条件是： ①能被4整除，但不能被100整除的 年份都是闰年，如1996年，2004年是闰年；②能 被100整除，又能被400整除的年份是闰年。如 1600年、2000年是闰年。不符合这两个条件的年 份不是闰年。 算法可表示如下： 设y 为被检测的年份。可采取以下步骤： S1：2000=>y S2： y不能被4整除，则输出y “不是闰年”。然后转 到S6 2.2 简单算法举例
S3:若y能被4整除，不能被100整除，则输出y“是 闰年”。然后转到S6 S4:若y能被100整除，又能被400整除，输出y“是闰 年”；否则输出“不是闰年”。然后转到S6 S5:输出y“不是闰年” S6:y+1=>y S7:当y≤2500时，转S2继续执行，如y>2500,算法 停止
S3：若y能被4整除，不能被100整除，则输出y “是 闰年”。然后转到S6 S4：若y能被100整除，又能被400整除，输出y“是闰 年”；否则输出“不是闰年”。 然后转到S6 S5：输出y “不是闰年” S6：y+1=>y S7：当y≤2500时，转S2继续执行，如y＞2500，算法 停止
例2.4求1-1/2+1/3-1/4+.+1/99-1/100。 算法可以表示如下： S1:1=>sign S2:1=>sum S3:2=>deno S4:(-1)X sign=>sign S5:signX(1/deno)=>term S6:sum+term=>sum S7:deno+l=>deno S8:若deno≤100返回S4;否则算法结束
例2.4 求1-1/2+1/3-1/4+.+1/99-1/100。 算法可以表示如下： S1：1=>sign S2：1=>sum S3：2=>deno S4：(-1)×sign=>sign S5：sign×(1/deno)=>term S6：sum+term=>sum S7：deno+1=>deno S8：若deno≤100返回S4；否则算法结束
2.3算法的特性 一个算法应该具有以下特点： 1.有穷性 一个算法应包含有限的操作步骤，而不能是无限的。 事实上，“有穷性”往往指“在合理的范围之内”。 究竞什么算“合理限度”，并无严格标准，由人 们的常识和需要而定。 2.确定性 算法中的每一个步骤都应当是确定的，而不应当是 含糊的、模棱两可的
2.3 算法的特性 一个算法应该具有以下特点： 1.有穷性 一个算法应包含有限的操作步骤，而不能是无限的。 事实上，“有穷性”往往指“在合理的范围之内”。 究竟什么算“合理限度”，并无严格标准，由人 们的常识和需要而定。 2.确定性 算法中的每一个步骤都应当是确定的，而不应当是 含糊的、模棱两可的
3.有零个或多个输入 所谓输入是指在执行算法时需要从外界取得必要的 信息。一个算法也可以没有输入。 4.有一个或多个输出 算法的目的是为了求解，“解”就是输出。没有输 出的算法是没有意义的。 5.有效性 算法中的每一个步骤都应当能有效地执行，并得到 确定的结果
3.有零个或多个输入 所谓输入是指在执行算法时需要从外界取得必要的 信息。一个算法也可以没有输入。 4. 有一个或多个输出 算法的目的是为了求解，“解” 就是输出。没有输 出的算法是没有意义的。 5. 有效性 算法中的每一个步骤都应当能有效地执行，并得到 确定的结果
2.4怎样表示一个算法 为了表示一个算法，可以用不同的方法。常用的有 自然语言、传统流程图、结构化流程图、伪代码、 PAD图等。 2.4.1用自然语言表示算法 在2.2节中介绍的算法是用自然语言表示的。用自然 语言表示通俗易懂，但文字冗长，容易出现“歧 义性”。自然语言表示的含义往往不太严格，要 根据上下文才能判断其正确含义。此外，用自然 语言描述包含分支和循环的算法，不很方便（如例 2.5的算法)。因此，除了很简单的问题以外，一般 不用自然语言描述算法
2.4 怎样表示一个算法 为了表示一个算法，可以用不同的方法。常用的有 自然语言、传统流程图、结构化流程图、伪代码、 PAD图等。 2.4.1 用自然语言表示算法 在2.2节中介绍的算法是用自然语言表示的。用自然 语言表示通俗易懂，但文字冗长， 容易出现“歧 义性”。自然语言表示的含义往往不太严格，要 根据上下文才能判断其正确含义。此外，用自然 语言描述包含分支和循环的算法，不很方便(如例 2.5的算法)。因此，除了很简单的问题以外，一般 不用自然语言描述算法
2.4.2用流程图表示算法 流程图是用一些图框表示各种操作。用图形表示算 法，直观形象，易于理解。美国国家标准化协会 ANSI(American National Standard Institute) 了一些常用的流程图符号（见图2.3）。 图2.3中菱形框的作用是对一个给定的条件进行判断， 根据给定的条件是否成立来决定如何执行其后的 操作。它有一个入口，两个出口。见图2.4。 连接点（小圆圈）是用于将画在不同地方的流程线连接 起来。如图2.5中有两个以O为标志的连接点（在连 接点圈中写上“1)，它表示这两个点是互相连接 在一起的。实际上它们是同一个点，只是画不下 才分开来画。用连接点，可以避免流程线的交叉 或过长，使流程图清晰
2.4.2 用流程图表示算法 流程图是用一些图框表示各种操作。用图形表示算 法，直观形象，易于理解。美国国家标准化协会 ANSI(American National Standard Institute)规定 了一些常用的流程图符号(见图2.3)。 图2.3中菱形框的作用是对一个给定的条件进行判断， 根据给定的条件是否成立来决定如何执行其后的 操作。它有一个入口，两个出口。见图2.4。 连接点(小圆圈)是用于将画在不同地方的流程线连接 起来。如图2.5中有两个以○为标志的连接点(在连 接点圈中写上“1”)，它表示这两个点是互相连接 在一起的。实际上它们是同一个点，只是画不下 才分开来画。用连接点，可以避免流程线的交叉 或过长，使流程图清晰
起止框 输入输出框 判断框 处理框 图2.3 或 流程线 连接点 注释框
图 2.3