代码探险家

这个屌丝很懒，什么也没留下！

热门标签

【C语言】C语言从入门到精通 | 第2章算法—自学笔记_算法的定义和特性

作者：代码探险家 | 2024-06-29 23:19:36

踩

算法的定义和特性

前言

本篇是本人自学 C 语言过程进行编辑的文章笔记，如果对大家有用，点赞加收藏吧。

注：笔记基于《C语言从入门到精通（第3版）》明日科技编著，清华大学出版社出版的。

一、算法的基本概念

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

（一）算法的特性

1、有穷性

一个算法必须在执行有穷步之后结束，且每一步都在有穷时间内完成，不能无限地执行下去。例如在编写从小到大整数累加程序中，一定要设置整数的最上限，如果没有最上限，则程序将无终止进行下去，称为死循环。

2、确定性

算法的每一个步骤都应当是确切定义的，对于每一个过程不能有二义性，必须对将要执行的的每个动作作出严格而清楚的规定。

3、可行性

算法中的每一步都应当能有效地运行，算法是可执行的，并要求最终得到正确的结果。

在下面的代码中，“ z=x/y; ”就是一个无效语句，因为 0 不能做分母。


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

4、输入

一个算法中应有零个或多个输入，输入是在执行算法时需要从外界取得的一些必要的信息（如算法的初始量等）。


/*多个输入*/
int x,y,z;
scanf("%d,%d,%d",&x,&y,&z);
 
/*零输入*/
main()
{
    printf("Hello world!");
}

5、输出

一个算法中应有一个或多个输出，输出是算法最终所求的结果。编写程序的目的就是要得到一个结果，如果程序运行后没有任何结果，则这个程序没有意义。

（二）算法的优劣

1、正确性

正确性是指所写的的算法应能满足具体问题的要求。

其“正确”的含义大体包含四个层次

①算法没有语法错误。

②算法对几组输入数据能够得到满足要求的结果。

③算法对精心选择的典型、苛刻而且有刁难性的输入数据能够得到满足要求的结果。

④算法对于一切合法的输入数据都能产生满足要求的结果。

其中第③层含义的正确性作为衡量一个程序是否正确的标准。

2、可读性

可读性是指算发写好后，被理解的难易程度。算法应该便于人们理解和相互交流，其次才是机器可执行。所以算法应当思路清晰、层次分明，简明易懂。

3、健壮性

健壮性（也称鲁棒性）是指当输入的数据非法时，算法也会作出相应的判断并处理，而不会因为输入的错误造成误动作或瘫痪。

4、时间复杂度与空间复杂度

时间复杂度（算法的效率）是算法运行所需要的时间，空间复杂度（存储量）是指算法运行所需要的存储空间的多少。

二、算法的描述

算法包含算法设计和算法分析两个方面内容，算法设计主要研究怎样针对某一特定类型的问题设计出求解步骤；算法分析则是要讨论所设计出来的算法步骤的正确性和复杂性。

算法描述是对于一些问题的求解步骤，需要一种表达方式，常用的有自然语言、流程图、N-S 流程图等。

（一）自然语言

自然语言就是人们日常用的语言，而自然语言描述也称文字描述，是算法最原始的表现形式。自然语言描述好处就是通俗易懂，但也有很大的弊端就是容易产生歧义，在描述较复杂的算法时，不是很方便。

【实例】任意输入3个数，求这3个数中的最小数。

（1）定义4个变量分别为x、y、z以及min。

（2）输入大小不同的3个数分别赋给x、y、z。

（3）判断x是否小于y，如果小于，则将x的值赋给min，否则将y的值赋给min。

（4）判断min是否小于z，如果小于，则执行步骤（5），否则将z的值赋给min。

（5）将min的值输出。

（二）流程图

流程图是一种传统的算法表示方法，用一些图框来代表各种不同性质的操作，用流程线来指示算法的执行方向。

优点：直观形象、易于理解，应用广泛。

1、流程图符号

如图所示为一些常见的流程图符号，其中，起止框用于标识算法的开始和结束；判断框用于对一个给定的条件进行判断，根据条件成立与否来决定如何执行后续操作；连接点用于将画在不同地方的流程线连接起来。

【实例】 从键盘中输入3个数分别赋给a、b、c，要求按大小顺序把它们打印出来。流程图如图所示：

2、三种基本结构

Bohra 和 Jacopini 为了提高算法的质量，经研究提出了 3 种基本结构，即顺序结构、选择结构和循环结构，因为任何一个算法都可由这 3 种基本结构组成，这3种基本结构之间可以并列，可以相互包含，但不允许交叉，不允许从一个结构直接转到另一个结构的内部去。

（1）顺序结构

顺序结构是简单的线性结构，在顺序结构的程序里，各操作是按照出现的先后顺序执行的。

【实例】输入两个数分别赋给变量i和j，再将这两个数分别输出。本实例流程图可以采用顺序结构来实现，如图所示。

（2）选择结构

选择结构也叫分支结构，如图所示。选择结构中必须包含一个判断框。图中所代表的含义是根据给定的条件 P 是否成立选择执行 A 框或者是 B 框。

【实例】 输入一个数，判断该数是否为偶数，并给出相应提示。本实例流程图可以采用选择结构来实现，如图所示。

（3）循环结构

在循环结构中，反复地执行一系列操作，直到条件不成立时才终止循环。按照判断条件出现的位置，可将循环结构分为当型循环结构和直到型循环结构。

当型循环结构是先判断条件P是否成立，如果成立，则执行A框；执行完A框后，再判断条件P是否成立，如果成立，接着再执行A框；如此反复，直到条件P不成立为止，此时不执行A框，跳出循环（先判断，后执行）。

直到型循环结构是先执行A框，然后判断条件P是否成立，如果条件P成立则再执行A；然后判断条件P是否成立，如果成立，接着再执行A框；如此反复，直到条件P不成立，此时不执行A框，跳出循环（先执行，后判断）。

【实例】求1和100之间（包括1和100）所有整数之和。

用当型循环结构来表示，如图1所示。

用直到型循环结构来表示，如图2所示。

（三）N-S 流程图

N-S 流程图是另一种算法表示法，是由美国人 I.Nassi 和 B.Shneiderman 共同提出的，根据是：既然任何算法都是由 3 种基本结构结构组成，则各基本结构之间的流程线就是多余的，因此去掉了流程线，将全部的算法写在一个矩形框内，N-S图也是算法的一种结构化描述方法。

1、顺序结构

顺序结构的 N-S 流程图如图所示，【实例】输入两个数分别赋给变量i和j，再将这两个数分别输出，N-S 流程图如图所示。

2、选择结构

选择结构的 N-S 流程图如图所示，【实例】输入一个数，判断该数是否为偶数，并给出相应提示。本实例 N-S 流程图如图所示。

3、循环结构

（1）当型循环结构

当型循环结构的 N-S 流程图如图所示，【实例】求1和100之间（包括1和100）所有整数之和。本实例当型循环结构 N-S 流程图如图所示。

（2）直到循环结构

直到循环结构的 N-S 流程图如图所示，【实例】输入一个数，判断该数是否为偶数，并给出相应提示。本实例直到循环结构 N-S 流程图如图所示。

【实例】从键盘中输入一个数n，求n！本实例的流程图以及N-S流程图如图所示：

【实例】求两个数a和b的最大公约数。本实例的流程图以及N-S流程图如图所示：

总结

主要介绍了算法的基本概念以及算法描述两个方面的内容。算法的基础概念包括算法的特征和评价算法的优劣，算法的特征包括有穷性、确定性、可行性、输入和输出 5 个方面的内容，评价算法的优劣可从正确性、可读性、健壮性以及时间复杂性与空间复杂性 4 个方面来考虑。在算法描述中介绍了自然语言、流程图、N-S 流程图 3 种方法，其中要重点掌握顺序结构、选择结构和循环结构的画法。

尾注

希望这篇笔记文章对你有所帮助，记得转载、点赞、收藏，支持一下，小编将会持续更新哦

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/代码探险家/article/detail/770657

【C语言】C语言从入门到精通 | 第2章 算法—自学笔记_算法的定义和特性

前言

目录