下载掌阅APP，畅读海量书库
立即打开
算法和我们的生活息息相关。从广义的角度来说，算法是为了解决某一问题而采用的方法与步骤。例如：对于乐队来说，乐谱就是他们进行演奏和指挥的算法；对于厨师来说，菜谱就是用来烧菜的算法。
举例说明：假设现在厨师需要做一盘西红柿炒鸡蛋，基本步骤如下所示。
步骤1：准备食材；
步骤2：点好燃气，打开油烟机；
步骤3：放油入锅，烧热；
步骤4：放入鸡蛋，翻炒；
步骤5：放入西红柿，炒匀；
步骤6：放入盐，继续翻炒；
步骤7：熄火，将菜盛入盘中。
上述做菜步骤就称为厨师炒制“西红柿炒鸡蛋”的算法。
再比如金币问题，假设一位商人有9枚金币，其中有一枚是假币，其比其他金币略微轻一些，现在有一台没有砝码的天平，如何借助它把假币找出来，请思考解决这个问题的算法。
（1）算法1
步骤1：任取一枚金币放在天平的左边，再取一枚金币放在右边。若不平衡，则轻的一边是假币；否则，进行步骤2。
步骤2：取下右边的金币，把其余的金币依次放入天平的右边，直到天平不平衡为止，则轻的一边是假币。
（2）算法2
步骤1：将金币两个一组分别放在天平的两端，若天平不平衡，则轻的一边是假币；否则，进行步骤2。
步骤2：重复执行步骤1，如果前四组都平衡，则最后一枚是假币。
（3）算法3
步骤1：将9枚金币按三个一组分为三组。
步骤2：取出两组放在天平的两端，若不平衡，则轻的一边有假币，即假币在轻的一组中；否则，假币就在未放上天平的一组中。
步骤3：选择含有假币的那组，取出其中的任意两枚放在天平的两端。若天平不平衡，则轻的一边是假币；否则，未放上天平的是假币。
在计算机中，算法是为了解决具体的问题而设计的一系列计算步骤，以处理用户输入的数据并将其转换成结果输出，如图1.1所示。算法对于我们来说是工具，可用来解决实际问题。如果一个算法对于任意一个输入都能够输出正确的结果并终止，就称它为正确的算法；反之，就称它为错误的算法。在解决问题的时候，我们需要思考并关注如何给出正确的算法。
【例1.1】假设有两个杯子，杯子a中放的是牛奶，杯子b中放的是水，写出交换两个杯子中液体的算法。
图1.1 算法的含义
思路：如果想要交换，则必须借助第三个（空）杯子t。
步骤1：将杯子a中的牛奶倒入杯子t中。
步骤2：将杯子b中的水倒入杯子a中。
步骤3：将杯子t中的牛奶倒入杯子b中。
【例1.2】写出在有限整数序列中找到最大值的算法。
步骤1：假设第一个数就是最大值max。
步骤2：从第二个数开始将它们依次与max做比较，如果发现有大于max的数，就让max等于这个数。
步骤3：重复步骤2，直到比完最后一个数为止。
步骤4：此时，max中存放的就是最大数。
【例1.3】写出求三个整数中最小数的算法。
步骤1：假设第一个数a就是最小值min。
步骤2：对第二个数b与min进行比较，如果b小于min，令min=b。
步骤3：对第三个数c与min进行比较，如果c小于min，令min=c。
步骤4：此时，min中放的就是三个整数中的最小数。
在计算机领域，算法被称为程序的灵魂，图灵奖获得者尼古拉斯·沃斯提出了如下著名的公式：算法+数据结构=程序。如图1.2所示，为了解决现实生活中的问题，人们想要借助计算机去完成，而计算机语言就是人类和计算机之间沟通的工具，程序是由使用者用某种计算机语言编写的一组有序指令的集合，计算机根据程序并按照步骤逐步执行每一条指令。在程序设计过程中，我们需要考虑两方面的问题：一方面是数据结构设计，主要关注待处理数据的存储方式和数据之间关系的组织问题；另一方面是算法设计，主要关注解决问题的思路，提出解决问题的一系列步骤。两者之间是密切相关的，算法设计要在结合具体数据结构的基础上才能设计出解决问题的正确算法。
图1.2 计算机求解问题的过程
算法具有以下5个特性。
（1）确定性：算法中的每个步骤都有确定的定义，不允许出现二义性。例如对于同一个输入，必须保证每次运行能得到相同的结果。
（2）可行性：算法中的每个步骤是实际能够进行的，并且整个算法是能够在可接受时间内完成的。
（3）有限性：算法的执行步骤是有限的，是能够终止的，并且每一步骤都能在有限时间内完成。
（4）输入性：算法可以有零个或多个输入。大多数算法需要接收外界的数据来完成运算，对于一些比较简单的问题，可以不需要输入数据，例如在屏幕上打印文字。
（5）输出性：算法需要有一个或多个输出。算法的目的是求解问题，问题求解的结果应以一定的方式输出。
请阅读下列两个求1000以内能被3整除的数之和的算法，判断其是否满足算法的特性。
【例1.4】算法1。
void try1()
{
int s=0;
int i=0;
while(i%3==0)
{
s=s+i;
i=i+3;
}
printf("%d\n",s);
}
分析：在这个算法中，变量 i 的值会一直增加，将形成一个死循环，不会终止，因此不符合算法的有限性。
【例1.5】算法2。
void try2()
{
int s=0;
int i=1;
while(i%3==0&&i<=1000)
{
s=s+i;
i=i+1;
}
}
分析：在这个算法中，计算完成后没有给出任何有效结果，对此，用户显然是不满意的，因此不符合算法的输出性。
我们再来看下面这个输出一个整数因子的例子，看看是否符合算法的特性。
【例1.6】算法3。
void try3()
{
int n=15;
int i=0;
while(n%i==0)
printf("%d\n",i);
}
分析：在这个算法中，当进行第一轮循环时 i =0。 i 又是除数，出现了除数为零的错误，因此不符合算法的可行性。
由此可见，我们在设计算法时一定要遵循算法的5大特性，这也是评价算法优劣的依据之一。除此之外，在设计算法时，还要遵循算法的5个设计目标。
（1）正确性：算法能够满足需求，完成规定的功能和性能要求，得出正确的结果。
（2）可使用性：对于用户来说算法能够很方便地使用。
（3）可读性：算法具有良好的可读性，便于人的理解。算法的设计要条理清晰、逻辑性强且具有结构化特性。
（4）健壮性：算法要拥有应对不符合规范要求的输入情况的处理能力，对于不符合规范要求的输入，算法能够及时进行判断，并提供妥善的处理方式。
（5）高效率与低存储量：对于同一个问题来说，求解的算法不是唯一的，这就需要我们找到最优算法。当问题的规模逐渐增大时，需要考虑的问题有两个。一是算法的时间效率，执行时间越短效率越高；二是算法执行过程中所需的空间存储量，需要的空间越小越好。
【例1.7】接收用户输入的两个整数，输出它们的商。
void qu()
{
int a,b,q;
scanf("%d,%d",&a,&b);
q=a/b;
printf("%d\n",q);
}
分析：这个算法是存在问题的，当用户输入5和0的时候，算法执行就会出错。所以，该算法不满足健壮性这一设计目标，应修改为以下算法：
void qu1()
{
int a,b,q;
scanf("%d,%d",&a,&b);
if(b==0)
printf("The divisor cannot be zero！");
else
{
q=a/b;
printf("%d\n",q);
} }
在算法设计过程中，算法的描述方式主要有4种：自然语言、流程图、伪代码和程序设计语言，如表1.1所示。
表1.1 对比算法的4种描述方式
下面以判断一个大于2的正整数是否为素数的问题为例，分别采用上述四种方式进行描述。
解题思路：素数是指只能被1和自身整除的数。在判断一个数是否是素数的时候，通常采用的是这样的方式：假设现在这个数是7，就从2开始，用2去除7，如果余数不为零，就接着用3去除7，……，直到用6去除7为止，此时余数依然不为零，因此得出结论——7是素数。对于数字
n
来说，其需要尝试的数的范围就是2~
n
-1，其实算法还可以进行优化，不需要测试到
n
-1，只需要测试到
即可，原因在于
就是分界线。如果在[2,
]区间里有一个数
h
能够整除
n
的话，在[
,
n
-1]区间里必定会有一个数
k
与之对应，有
h
×
k
=
n
。例如15这个数，我们在[2,
]区间里找到一个数
3
能够整除它，在[
, 14]区间里就有一个
数
5与之对应，有3×5=15。对应地，如果在[2,
]区间里找不到能够整除
n
的数，那么在[
,
n
-1]区间里也肯定没有能整除它的数。
用日常生活中使用的语言来描述算法，相对来说易于理解，但书写起来比较烦琐，也有可能因为表述不到位引起歧义，对于较为复杂的问题较难表述准确。对于计算机来说，自然语言是不可识别和执行的。
判断一个大于2的正整数是否为素数的算法描述如下。
步骤1：输入 n 。
步骤2：定义变量 i ，赋初始值为2。
步骤3：判断 n 除以 i 的余数是否为0，如果为0，则转到步骤6。
步骤4：变量 i 的值自加1。
步骤5：判断
i
的值是否小于
，如果小于，则返回步骤3。
步骤6：判断
i
的值是否大于
，如果大于，则输出“This is not a prime.”；否则，输出“This is a prime.”。
流程图使用不同的图框来表示各类操作，在图框内部写出步骤，再用箭头连接起来表示先后顺序。通过图形的方式来描述算法，直观而又形象。判断一个大于2的正整数是否为素数的算法流程如图1.3所示。
图1.3 判断一个大于2的正整数是否为素数的算法流程
伪代码是一种介于自然语言与计算机语言之间的用来描述算法的语言，参照计算机语言的书写形式来表示算法的各个步骤，相比计算机语言更加接近自然语言，相对来说容易理解。伪代码旨在用接近自然语言的形式描述程序的执行过程，一般是不能被计算机直接执行的。判断一个大于2的正整数是否为素数的算法的伪代码描述如下。
步骤1：输入 n 。
步骤2： i =2。
步骤3：循环直到
i
大于
。
3.1如果 n % i ==0，break。
3.2 i = i +1。
步骤4：如果
i
大于
，输出“This is not a prime.”，否则输出“This is a prime.”。
也可以直接用计算机语言的形式来描述算法，通常是将算法写成子函数。这样的算法是可以直接在计算机上执行的。判断一个大于2的正整数是否为素数的算法的程序设计语言描述如下。
int main()
{
int i, n;
scanf("%d", &n);
for(i=2; i < sqrt(n); i++)
{
if(n%i==0)
break;
}
if(i >sqrt(n))
printf("This is a prime.");
else
printf("This is not a prime.");
return 0;
}
算法设计的步骤如图1.4所示，包括理解和分析问题、选择数据结构、设计算法策略、描述算法、验证算法、分析算法效率和编写程序实现，各步骤之间紧密相连，存在循环反复的过程。
（1）理解和分析问题。在设计算法之前，首先要深入分析问题，明确求解问题的要求和算法实现的功能目标，预测可能输入的数据，确定输出的结果。
（2）选择数据结构。理清算法涉及的数据之间的关系，选择和设计数据的逻辑结构与存储结构。
（3）设计算法策略。算法设计有几类常用的算法策略，例如穷举法、分治法、贪心法和动态规划法等，各类算法的特性和适用情况有所不同，在此基础上结合前面对问题的分析结果，选择适当的算法策略。
（4）描述算法。选取适当的描述方法对算法进行描述，要清晰、准确且完整地对算法的各个步骤进行详细描述。
图1.4 算法设计的步骤
（5）验证算法。一般而言，计算机中常用的算法策略都是经过验证的，也是比较成熟的算法策略，所以在设计算法的时候尽量选取这些算法。如果在设计过程中使用其他新的算法，就需要运用数学方法进行证明，因而需要耗费一些时间。如果无法证实算法的正确性，就要重新修正算法。
（6）分析算法效率。对于同一问题来说，求解的算法可能有很多种。此时就需要对算法进行分析，主要围绕两个方面展开分析，一是时间复杂度分析，二是空间复杂度分析，然后根据分析结果不断优化算法。
（7）编写程序实现。选择计算机语言根据算法编写程序，实现算法。