自学C语言-2

第2章 算法

开发一个程序通常要解决算法、数据结构、程序设计方法以及语言工具和环境这4个问题。其中，算法是核心，解决的是“做什么”和“如何做”的问题。正是因为算法非常重要，所以这里单独列出一章来介绍算法的基本知识。
本章的知识架构及重难点如下：

*算法

• 算法的基本概念

算法的特性：有穷性，确定性，可行性，输入，输出
算法的优劣：正确性，可读性，健壮性，时间复杂度与空间复杂度

• 算法描述：
  自然语言，流程图，N-S流程图 表示重点内容

2.1 算法的基本概念

算法与程序设计及数据结构密切相关，是解决一个问题的完整的步骤描述，更是解决这个问题的策略、规则和方法。算法的描述形式有很多种，如传统流程图、结构化流程图及计算机程序语言等，下面就介绍算法的一些相关内容。

2.1.1 算法的特性

算法是为解决某一特定类型的问题而制定的一个实现过程，它具有下列特性。

1. 有穷性
   一个算法必须在执行有穷步之后结束，且每一步都可在有穷时间内完成，不能无限地执行下去。如要编写一个由小到大整数累加的程序，就需要给出整数的上限，也就是加到哪个数为止。若没有上限，那么程序将无终止地运行下去，进入死循环。
   2.确定性
   算法的每一个步骤都应当有确切定义，每一个过程都不能有二义性，必须对将要执行的每个动作做出严格而清楚的规定。
   3.可行性
   算法中的每一步都应当能有效地运行，也就是说算法是可执行的，并能够最终得到正确的结果。如下面一段程序：

int x, y, z; 
scanf("%d, %d, %d", &x, &y, &z);
if(y==0)
z=x/y;

在这段代码中，“z=x/y;"就是一个无效的语句，因为0不可以做分母。
4.输入
一个算法应有零个或多个输入。输入就是执行算法时需要从外界取得的一些必要的（如算法所需要的初始量等）信息。例如：

int a,b,c;
scanf_s("%d,%d,%d", &a,&b,&c);

上面的代码中有3个输入。又如：

main()
{
	printf("hello world!");
}

上面的代码需要零个输入。

5.输出
一个算法应有一个或多个输出。什么是输出？输出就是算法最终所求的结果。编写程序的目的就是要得到一个结果，如果一个程序运行下来没有任何结果，那么这个程序本身也就失去了意义。
误区警示：需要注意的是：一个程序，可能存在输入，也可能不存在输入，但是一定存在输出。也就是说，至少存在一个输出。

2.1.2 算法的优劣

衡量一个算法的好坏，通常要从以下几个方面来分析。
1.正确性
正确性是指所写的算法应能满足具体问题的要求，即对任何合法的输入，算法都会得出正确的结果。
2.可读性
可读性是指算法被写好之后，该算法被理解的难易程度。一个算法可读性的好坏十分重要，如果一个算法比较抽象，难以理解，那么这个算法就不易于进行交流和推广使用，其后续修改、扩展、维护都十分不方便。因此在写一个算法时，要尽量将该算法写得简明、易懂。
3.健壮性
一个程序完成后，运行该程序的用户对程序的理解各有不同，并不能保证每一个人都能按照要求进行输入。健壮性就是指当输入的数据非法时，算法也会做出相应判断，而不会因为输入的错误造成瘫痪。
4.时间复杂度与空间复杂度
简单地说，时间复杂度就是算法运行所需要的时间。不同的算法具有不同的时间复杂度，当一个程序较小时，会感觉不到时间复杂度的重要性；但当一个程序特别大时，时间复杂度实际上是十分重要的。因此，如何写出更高速的算法一直是算法优化的目标。空间复杂度是指算法运行时所需的存储空间的大小。随着计算机硬件的发展，空间复杂度已经不再显得那么重要。

2.2 算法描述

算法包含算法设计和算法分析两个方面。算法设计主要研究怎样针对某一特定类型的问题设计出求解步骤，算法分析则要讨论所设计出来的算法步骤的正确性和复杂性。
对于一些问题的求解步骤，需要一种表达方式，即算法描述。他人可以通过算法描述来了解算法设计者的思路。表示一个算法，可以用不同的方法，常用的有自然语言法、流程图法、N-S流程图法等。

2.2.1 自然语言

自然语言就是人们日常所用的语言，这种表达方式通俗易懂，下面通过实例具体介绍。
例2.1 求n!。
算法描述步骤如下：
（1）定义3个变量i、n及mul ,为i和mul均赋初值为1。
（2）从键盘中输入一个数，赋给n。
（3）将mul乘以i的结果赋给mul。
（4）i的值加1，判断i的值是否大于n,如果大于n,则执行步骤（5），否则执行步骤（3）。
（5）将mul的结果输出。
例2.2 农夫、羊、狼及白菜过河。
一名农夫要将一只狼、一只羊和一袋白菜运到河对岸。农夫的船很小，每次只能载下农夫本人以及狼、羊、白菜中的一个。但是，他不能把羊和白菜留在岸边，因为羊会把白菜吃掉；也不能把狼和羊留在岸边，因为狼会吃掉羊。那么，农夫该怎样将这3样东西送过河呢？
算法描述步骤如下：
（1）先把羊运过去。
（2）回来运狼。
（3）把狼运到对岸后，把羊装上船运回来。
（4）把羊放到开始的地方，把白菜运过去。
（5）再把羊运过去。
例2.1和例2.2的算法实现过程就是采用自然语言来描述的。从上面的描述中可以发现，自然语言描述的好处就是易懂，弊端是容易产生歧义。例如，将例2.1步骤（3）中的”将mul乘以i的结果赋给mul”改为“mul等于i乘以mul”,这样就产生了歧义。并且，用自然语言来描述较为复杂的算法时，会显得不是很方便，因此一般情况下不采用自然语言来描述。

2.2.2 流程图

流程图是一种传统的算法表示法，它用一些图框来代表各种不同性质的操作，用流程线来指示算法的执行方向。由于它直观形象，易于理解，所以应用广泛。特别是在语言发展的早期阶段，只有通过流程图才能简明地表述算法。

1.流程图符号
流程图使用一些图框来表示各种操作。如图2.1所示为一些常见的流程图符号，其中，起止框用来标识算法的开始和结束；判断框用于对一个给定的条件进行判断，根据条件成立与否来决定如何执行后续操作；输入/输出框用来表示输入/输出；处理框用来表示变量的计算或赋值；流程线用于表示算法的流向；注释框用于表示算法的注释；连接点用于将画在不同地方的流程线连接起来。
2.3种基本结构
Bohra和Jacopini为 了提高算法的质量，提出了3种基本结构，即顺序结构、选择结构和循环结构，因为任何一个算法都可由这3种基本结构组成。这3种基本结构之间可以并列，可以相互包含，但不允许交叉，不允许从一个结构直接转到另一个结构的内部去。
任何算法都是由3种基本结构组成的，所以只要规定好3种基本结构的流程图的画法，就可以画出任何算法的流程图。
1）顺序结构
顺序结构是最简单的线性结构。在顺序结构的程序中，各操作按照它们出现的先后顺序执行。如图2.2所示，在执行完A框所指定的操作后，接着执行B框所指定的操作。这个结构中只有一个入口点A和一个出口点B。

例2.3 输出数学、语文成绩。
输入两个数，分别代表数学、语文成绩，并分别赋给变量math和chinese,再将这两个数分别输出。本实例的流程图可以采用顺序结构来实现，如图2.3所示。
2）选择结构
选择结构也称为分支结构，其常见形式有两种，如图2.4和图2.5所示。

开始
输入两个数，赋给math和chinese
输出变量math和chinese的值
结束

图2.3 输出数学、语文成绩
选择结构中必须包含一个判断框。图2.4所代表的含义是根据给定的条件P是否成立选择执行A框还是B框。图2.5所代表的含义是根据给定的条件P进行判断，如果条件成立则执行A框，否则什么也不做。
例2.4 判断是否为偶数。
输入一个数，判断该数是否为偶数，并给出相应提示。
本实例的流程图可以采用选择结构来实现，如图2.6所示。
3）循环结构
在循环结构中，反复地执行一系列操作，直到条件不成立时才终止循环。按照判断条件出现的位置，可将循环结构分为当型循环结构和直到型循环结构。
当型循环的流程结构如图2.7所示。先判断条件P是否成立，如果成立，则执行A框；执行完A框后，再判断条件P是否成立，如果成立，接着再执行A框；如此反复，直到条件P不成立为止，此时不执行A框，跳出循环。
直到型循环的流程结构如图2.8所示。先执行A框，然后判断条件P是否成立，如果条件P成立则再执行A；然后判断条件P是否成立，如果成立，接着再执行A框；如此反复，直到条件P不成立，此时不执行A框，跳出循环。
开始
输入一个数赋给变量i
判断i是否能被2整除
yes
i是偶数
No
i不是偶数
结束
例2.5 计算1+2+3+…+100的结果。
求1和100之间（包括1和100）所有整数之和。
本实例的流程图可以用当型循环结构来表示，如图2.9所示。也可以用直到型循环结构来表示，如图2.10所示。
当型循环结构求和
开始
i=1;
sum = 0;
i<=100 Yes sum=sum+i; i++
No
输出sum
结束
直到型循环结构求和
开始
i=1;
sum=0;
sum=sum+i;
i++;
i<=100
输出sum
结束

2.2.3 N-S流程图

N-S流程图是另一种算法表示法，是由美国人I.Nassi和B.Shneiderman提出的。其根据是：既然任何算法都可以由顺序、选择和循环3种结构组成，则各基本结构之间的流程线就是多余的，因此可以去掉所有流程线，将全部的算法写在一个矩形框内。N-S图也是算法的一种结构化描述方法，同样也有3种基本结构，下面分别进行介绍。
1.顺序结构
顺序结构的N-S流程图如图2.11所示。例2.3的N-S流程图如图2.12所示。