《计算思维与算法入门》 —1.2 算法的条件

1.2    算法的条件

在计算机中，算法更是不可或缺的一环。在认识了算法的定义之后，我们再来看看算法所必须符合的5个条件（可参考图1-18和表1-1）。

图1-18  算法必须符合的5个条件

表1-1  算法必须符合的5个条件

我们认识了算法的定义与条件后，接着要来思考：用什么方法表达算法最为适当呢？其实算法的主要目的在于让人们了解所执行的工作流程与步骤，只要能清楚地体现算法的5个条件即可。

常用的算法一般可以用中文、英文、数字等文字来描述，也就是使用文字或语言语句来说明算法的具体步骤，有些算法则是使用可读性高的高级程序设计语言（如Python、C、C++、Java等）或者伪语言（Pseudo-Language）来描述或说明的。例如，以下算法就是用Python语言来描述函数Pow()的执行过程：计算所传入的两个数x、y的xy值。

def Pow(x,y):

    p=1

    for i in range(1,y+1):

        p *=x

    return p

print(Pow(4,3))

公约数是指可以整除两个整数的整数，通过辗转相除法可以求两个整数的最大公约数，就是通过算法来求解的。下面我们使用while循环设计一个C语言程序，求所输入的两个整数的最大公约数（g.c.d）。辗转相除法的算法如下：

if (Num1 < Num2)

{

    TmpNum=Num1;

    Num1=Num2;

    Num2=TmpNum;  /* 找出两个整数中的较大值 */

}

while (Num2 != 0) /* 辗转相除法，直到除数为0就终止循环 */

{

    TmpNum=Num1 % Num2;   /* 求两个整数的余数 */

    Num1=Num2;

    Num2=TmpNum; /* 将本轮相除求得的余数作为下一轮的除数 */

}

    printf("最大公约数(g.c.d)=%d\n",Num1);

提  示

伪语言接近于高级程序设计语言，是一种不能直接放进计算机中执行的语言。一般都需要通过一种特定的预处理器（Preprocessor）或者通过人工编写转换成真正的计算机语言才能够加载到计算机中执行，目前较常使用的伪语言有SPARKS、PASCAL-LIKE等。

流程图（Flow Diagram）是一种相当通用的算法表示法，就是使用某些特定图形符号来表示算法的执行过程。为了让流程图具有更好的可读性和一致性，目前较为通用的是ANSI（美国国家标准协会）制定的统一图形符号。表1-2列出了流程图中一些常见的图形符号并附有简单的说明。

表1-2  流程图中常见的图形符号

假如我们要设计一个程序，让用户输入一个整数，而这个程序可以帮助用户判断输入的整数是奇数还是偶数，那么这个程序的流程图大致如图1-19所示。

为了让他人容易阅读，绘制流程图应注意以下几点：

（1）采用标准通用符号，符号内的文字尽量简明扼要。

（2）绘制方向应自上而下，从左到右。

（3）连接线的箭头方向要清楚，线条避免太长或交叉。

图1-19  用流程图描述算法的例子——判断奇数和偶数

提  示

算法和过程是有区别的，过程不一定要满足算法有限性的要求，例如操作系统或计算机上运行的过程，除非宕机，否则永远在等待循环中（waiting loop），这就违反了算法五大条件中的“有限性”。

再来看一个算法的例子，我们知道计算机内部是以二进制数的方式来处理数据和信息的，而人类则是以十进制数的方式来处理日常运算的。在计算机中，有些数据也会采用八进制数或十六进制数来表示。十进制数转换成非十进制数要分为整数部分的转换和小数部分的转换，下面通过范例来说明相关的转换算法。

（1）十进制数转换成二进制数

(63)10= (111111)2（十进制整数转换成二进制整数，参考图1-20）

图1-20  十进制整数转成二进制整数

(0.625)10 = (0.101)2（十进制小数转换成二进制小数，参考图1-21）

图1-21  十进制小数转换成二进制小数

(12.75)10＝(12)10 ＋ (0.75)10（十进制数转换成二进制数），参考图1-22。

图1-22  十进制数转换成二进制数

其中，(12)10＝(1100)2，(0.75)10＝(0.11)2

所以(12.75)10 ＝ (12)10 ＋ (0.75)10

＝(1100)2 ＋ (0.11)2

＝(1100.11)2

（2）十进制数转换成八进制数

(63)10 ＝ (77)8（参考图1-23）

图1-23  十进制整数转换成八进制整数

(0.75)10＝(0.6)8（参考图1-24）

图1-24  十进制小数转换成八进制小数

（3）十进制转换成十六进制

(63)10 ＝ (3F)16（参考图1-25）

图1-25  十进制整数转换成十六进制整数

(0.62890625)10 ＝ (0.A1)16（参考图1-26）

图1-26  十进制小数转换成十六进制小数

(120.5)10 ＝ (120)10 ＋ (0.5)10

其中，(120)10＝(78)16，(0.5)10＝(0.8)16，参考图1-27。

图1-27  十进制数转换成十六进制数