任务二 算法的描述与设计

知识点

子任务一 算法的描述

1.算法的描述方法有哪几种？

算法的描述方法可以分为三种：

• 自然语言描述算法
• 流程图描述算法
• N-S图描述算法

2.什么是自然语言描述算法？其优缺点是什么？

用自然语言描述解决问题的过程，就是把算法的各个步骤，依次用人们熟悉的自然语言表示出来。

优点：容易理解

缺点：书写较烦、不确定性、对复杂的问题难以表达准确、不能被计算机识别和执行

3.什么是流程图描述算法？

流程图是算法的图形化描述。俗话说"一张图胜过千言万语"，用流程图可以清晰地描述出算法的思路和过程。

4.常用的流程图符号有哪些？各自的功能是什么？

符号图形	名称	功能
椭圆形	开始/结束	算法的开始或结束
平行四边形	输入/输出	输入或输出信息
矩形	处理	计算与赋值
菱形	判断	条件判断
箭头线	流程线	算法中的流向
圆形	连接圈	表示算法流向出口或入口连接点

图1-1 常见流程图符号及功能

子任务二 算法的设计

5.什么是算法设计？

算法设计（Designing Algorithm）作为计算机解决问题的一个步骤，其任务是对各类具体问题设计出良好的算法。算法设计作为一门课程，旨在研究算法设计中的规律和方法。

6.算法设计的要求有哪些？（四个质量标准）

在设计算法时，应当严格考虑算法的以下质量标准：

（1）正确性（Correctness）

一方面，算法对于一切合法的输入数据都能得出满足要求的结果；另一方面对于精心选择的、典型的、苛刻的几组输入数据，算法也能得出满足要求的结果。

（2）可读性（Readability）

算法主要是为了人的阅读与交流，其次才是让计算机执行。因此算法应该在设计时就以让人易于理解为原则。难读的算法易隐藏较多错误而难以调试。有些算法设计者总是把自己设计的算法写得只有自己才能看懂，这样的算法反而没有太大的实用价值。

（3）稳健性（Robustness）

当输入的数据非法时，算法应当恰当地做出反应或进行相应处理，而不是产生莫名其妙的输出结果。这就需要算法设计者充分考虑可能的异常情况，并且处理出错的方法不应当是简单地中断算法的执行，而应是返回一个表示错误或错误性质的值，以便在更高的抽象层次上进行处理。

（4）高效率与低存储量的要求

通常，效率指的是算法执行时间；存储量指的是算法执行过程中所需的最大存储空间。两者都与问题的规模无关。

7.算法的五个基本特征是什么？

并不是所有的问题都有可以解决它们的方法，也不是所有人类解决问题的方法都能设计出相应的算法。算法必须满足以下5个重要特性：

（1）有穷性

一个算法在执行有穷步骤之后必须结束，也就是说一个算法它所包含的计算步骤是有限的，即算法中的每个步骤都能在有限时间内完成。

（2）确定性

对于每种情况下所应执行的操作，在算法中都有确切的规定，使算法的执行者或阅读者都能明确其含义及如何执行。并且在任何条件下，算法都只有一条执行路径。

（3）可行性

算法中描述的操作都可以通过已经实现的基本操作运算有限次实现之。

（4）算法有零个或多个的输入

由输入方式成为算法加工对象的数据，通常体现为算法中的一组变量。有些输入量需要在算法执行过程中输入，而有的算法表面上可以没有输入，实际上已被嵌入算法之中。

（5）算法有一个或多个的输出

它是一组与输入有确定关系的量值，是算法进行信息加工后得到的结果。