C语言基础课程（1.2）——C语言算法的理解

前言

相信大家已经对C语言结构有了基本的认识，接下来，我们还需要了解下C语言的算法。

算法的概念

对于一个问题，有不同的解题思路，这个解题思路就可以说是算法。广义地说，为解决一个问题而采取的方法和步骤，就称为“算法”。

一个程序应包括两个方面的内容：

1. 对数据的描述：数据结构(data structure)
2. 对操作的描述：算法(algorithm)

对于同一个问题，如果采用不同的算法，会导致其执行时间、使用空间和效率会大有不同。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。在解题时，不仅要算法正确，还要考虑算法的质量，选择合适的算法。希望方法简单，运算步骤少。

简单算法举例

累加的计算

例如：我们要计算1+2+3+……+n，可以定义一个i变量，用于存储目前所累加的值，定义一个sum变量，用于存储目前前i项的累加和。

因此，基本的处理流程如下：

1. 首先初始值为：i=1，sum=1
2. i值+1，即i=2，sum=sum+2，则sum=3
3. i值+1，即i=3，sum=sum+3，则sum=6
4. i值+1，即i=4，sum=sum+4，则sum=10
5. …… ……
6. 依次类推，直到i=n，sum=sum+i结束计算

可以留意到i的值会进行增加，每次+1，sum是之前i-1项的和加上新增的第i项。

这里会用到一个循环，i值会从1开始，到n结束循环。

思考

接下来，我们对上面的问题稍作变换，大家可以思考下用什么算法可以解决呢？

1. 计算1*2*3*……*n
2. 计算2+4+6+……+n(n是偶数）
3. 计算一组学生的总分
4. 计算整个长沙市区的总电量

可以发现，上述的算法比较相似，都是累加或者累乘的问题。

有条件的累加计算

上述的思考题中，有一个计算2+4+6+……+n(n是偶数），我们可以采用以下几种算法：

直接将i的值设置为偶数值

1. 首先初始值为：i=2，sum=2
2. i值+2，即i=4，sum=sum+4，则sum=6
3. i值+2，即i=6，sum=sum+6，则sum=12
4. i值+2，即i=8，sum=sum+8，则sum=20
5. …… ……
6. 依次类推，直到i=n，sum=sum+i结束计算

该方法重在判断i的增量情况。

i值遍历所有整数，累加前判断是否是偶数

1. 首先初始值为：i=2，sum=2
2. i值+1，即i=3，奇数，sum不累加
3. i值+1，即i=4，偶数，sum累加，sum=sum+i，得sum=6
4. i值+1，即i=5，奇数，sum不累加
5. i值+1，即i=6，偶数，sum累加，sum=sum+i，得sum=12
6. …… ……
7. 依次类推，直到i=n，sum=sum+i结束计算

这种算法则是需要进行sum的累加条件判断。

思考

1. 计算3+6+9+……+n(n是3的倍数）
2. 计算一组学生中不及格的分数的和
3. 计算整个长沙市区大于等于100度的总电量
4. 计算双今年自己所有消费中服装类所占的比重

算法的特性

算法具有如下性质：

1. 有穷性：包含有限的操作步骤
2. 确定性：算法中的每一个步骤都应当是确定的
3. 有零个或多个输入：输入是指在执行算法时需要从外界取得必要的信息
4. 有一个或多个输出：算法的目的是为了求解，“解” 就是输出
5. 有效性：算法中的每一个步骤都应当能有效地执行，并得到确定的结果

算法的表示

可以用不同的方法表示算法，常用的有：

1. 自然语言
2. 传统流程图
3. 结构化流程图
4. 伪代码
5. PAD图

这些属于拓展知识，大家可以自己看一下哦~

流程图

这里主要对流程图做一下简单说明。

流程图的主要符号

常用的流程图符号有以下几种：

1. 圆角矩形：起止框，表示流程的开始或者结束
2. 菱形：判断框，表示该语句要进行判断真假，再根据其逻辑结果走向不同的分支
3. 矩形：执行框或处理框，表示需要执行的语句
4. 平行四边形：输入输出框，表示该处要输入数据或者将某值进行输出
5. 一边开口的矩形：表示注释，不执行，表示另一个部分的具体含义和对应的解释
6. 箭头：流向线，不含箭头的表示上一个语句，含箭头的是下一个要执行的语句，通过流向线可以了解整体的执行顺序
7. 圆圈：连接点，部分比较复杂的流程图可能会用到连接点，用于表示两处之间的执行关系

如下用流程图来表示1×2×3×4×5的过程：

流程图的基本结构

流程图中有三种基本结构：顺序结构、选择结构、循环结构

1. 顺序结构：依照流向线的指向顺序依次从开始到结束的执行过程，这是一个最基本最简单的流程图的类型。
2. 选择结构：选择结构中必然会含有判断框，依据判断框的结果走向不同的分支，如果成立，走Y/是这条分支，如果不成立，走N/否这条分支，选择结构又叫做分支结构。
3. 循环结构：循环结构中会有循环的语句，当某条件成立的情况下，会继续循环执行某些语句。循环结构又分成当型循环和直到型循环。

总结

然后看下本次的小结：

1. 一个程序应包括两个方面的内容：对数据的描述：数据结构(data structure)；对操作的描述：算法(algorithm)；
2. 算法的性质：有穷性、确定性、有零个或多个输入、有一个或多个输出和有效性；
3. 算法常用的表示方法有：自然语言、传统流程图、结构化流程图、伪代码和PAD图。

关于C语言算法的理解内容就讲解到这里，上述思考里面的算法建议大家好好想一想哦~