《C语言程序设计 教学课件 ppt 作者 李晓东 庞岩梅 娄嘉鹏 第3章》由会员分享，可在线阅读，更多相关《C语言程序设计 教学课件 ppt 作者 李晓东 庞岩梅 娄嘉鹏 第3章（73页珍藏版）》请在金锄头文库上搜索。
1、第3章 算法设计,1,3.1 编写一个判断任意给定数是否为素数的程序 3.2 算法的概念 3.3 算法的结构 3.4 算法的数据组织 3.5 典型算法整理,2,3.1 编写一个判断任意给定数是否为素数的程序,对于复杂的问题，思路和步骤才是关键 考虑下面的问题：如何判断一个数是否是素数？,3.1 编写一个判断任意给定数是否为素数的程序,对于复杂的问题，不能直接映射为程序，而是首先思考问题的解决思路，思考这个问题手工如何去解，手工步骤出来了，得到最终程序只是一个把步骤映射为程序的问题。,3.1 编写一个判断任意给定数是否为素数的程序,具体的做法是： （1）寻找思路使得问题可解； （2）由思路获得手
2、工求解的步骤（应选择典型输入进行手工求解验证）； （3）把手工步骤映射为自动执行的程序。,3.1 编写一个判断任意给定数是否为素数的程序,3.1.1 思路和步骤 3.1.2 C语言代码,6,3.1.1 思路和步骤,问题：如何判断一个数是否是素数？ 思路：对于输入的整数n，可以计算它除以1到n的余数，如果有且只有两次余数为0，则为素数，否则不是素数。,3.1.1 思路和步骤,手工求解的步骤是什么呢？ 对于输入的数n，让n除以1，若余数为0，则计数器加1；让n除以2，若余数为0，则计数器加1；直到让n除以n，若余数为0，则计数器加1。总共用n次除法，即n个步骤就能够解决。,3.1.1 思路和步骤,
3、是不是对每个数都能保证经过这些步骤得到正确答案呢？ 如果n为负数呢？ 如果n为0、1按照上述步骤又怎样呢？ 还有其他情况吗？没有了 。,3.1.1 思路和步骤,最终步骤为： （1）判断输入的数，若为负数，输出“应输入非负整数”，结束； （2）n依次除以1到n，若余数为0则计数器加1； （3）若计数器为2，则输出“素数”，否则输出“非素数”； （4）结束；,3.1.2 C语言代码,经过映射，可以得到下面的代码： #include void main() int n,i,c; printf(“input a integer:n”); scanf(“%d”, ,3.2 算法的概念,3.2.1 什么是
4、算法 3.2.2 算法的描述,3.2.1 什么是算法,算法（Algorithm）简单地说，就是步骤的序列，也就是有后继关系的步骤的集合。如果每一个步骤被看作一个节点，那算法就可以看作是一个有向图。,3.2.1 什么是算法,一个算法应该具有以下五个基本的特征： 输入 输出 确切性 可行性 有穷性,3.2.1 什么是算法,对于一个问题来说，满足上述5个基本特征的能够解决该问题的步骤序列都是这个问题的算法，所以一个问题的求解算法可以有许多个。 好的算法应该速度快，耗费的资源少，反之则是不好的算法。,3.2.1 什么是算法,在算法方面，基本的能力是： 如何找出一个问题的算法 如何对算法进行优化（分析算
5、法的好坏，通过优化，获得优良的算法）。,3.2.2 算法的描述,算法常用的描述方式有： 自然语言 伪代码 流程图 N-S图,3.2.2 算法的描述,1自然语言 自然语言就是用人们日常使用的语言描述解决问题的方法和步骤. 通俗易懂，但在语法和语义上往往具有多义性，并且比较烦琐，对程序流向等描述不明了、不直观。 前面描述判断一个数是否为素数的算法就使用的是这种方式。,3.2.2 算法的描述,2. 伪代码 伪代码是介于自然语言和计算机语言之间的文字和符号，它与一些高级编程语言（如Visual Basic和Visual C+）类似，但是不需要真正编写程序时所要遵循的严格规则。 伪代码用一种从顶到底，易
6、于阅读的方式表示算法。 在程序开发期间，伪代码经常用于“规划”一个程序，然后再转换成程序。,用伪代码描述判断一个数是否为素数的算法,printf(“input a integer:”) scanf(“%d”, if(c=2) printf(“素数”) else printf(“非素数”) return,3.2.2 算法的描述,3. 流程图 流程图使用不同的几何图形来表示不同性质的操作，使用流程线来表示算法的执行方向。 比起前两种描述方式，具有直观形象、逻辑清楚、易于理解等特点，但它占用篇幅较大，流程随意转向，较大的流程图不易读懂。,3.2.2 算法的描述,流程图符号及说明,判断一个数是否为素数
7、的算法流程图,开始,结束,输出,输入整数n,n0?,输出,结束,计数器c=0,i=1,i为n的因子?,i=n?,Y,N,N,Y,i+,c=c+1,N,Y,c=2?,N,Y,输出,输出,3.2.2 算法的描述,4. N-S图 N-S图是1973年美国学者INassi和BShneiderman提出的一种符合结构化程序设计原则的描述算法的图形方法，又叫做盒图。 结构化程序设计原则是所有程序都只采用顺序、分支、循环三种基本控制结构。,用N-S图描述判断一个数是否为素数的算法,3.3 算法的基本执行结构,3.3.1 算法的基本执行结构 3.3.2 逐步求精,3.3.1 算法的基本执行结构,算法的三种基本
8、结构 顺序结构 选择结构 循环结构,3.3.2 逐步求精,逐步求精是在设计过程中，先将主体步骤整理出来，然后将主体步骤中不能用代码直接描述出来的再看做一个小问题继续以算法的思路进行分解，直到分解出的各个执行步骤都可方便的映射为代码。,3.4 算法的数据组织,程序=算法+数据结构 这里的数据结构就是数据的组织。,3.4 算法的数据组织,3.4.1 数组 3.4.2 多维数组 3.4.3 结构体 3.4.4 指针 3.4.5 链表 3.4.6 树和图 3.4.7 数据类型的扩展机制 3.4.8 利用数据组织获得好的算法,3.4.1 数组,对于数据面临的操作相同，但本身各自之间又没有直接的规律可以互
9、相推得的，就可以采用数组将它们组织起来。 在这个组中，每个元素都有自己的代号，而这些代号是有内在规律的，通常是以1为间隔递增的。,3.4.1 数组,例 计算25，38，79，10，25，32，18，45，51，64这十个数的平均值。 这是一个典型的循环结构。循环体就是加法；循环终止的判断条件就是加的次数是否达到了10次；循环初始状态就是初始加和为0。 累加和每次加完自动变化，而下一个待加的数如何表示呢？,3.4.1 数组,用数组存储这些数，在循环中就可以通过引用每个数字的代号来表示该数字，如numi。循环中每次让代号加1就可以让下一个待加的数自动参与运算。如： sum=sum+numi; i=
10、i+1;,3.4.2 多维数组,例 将通讯录中的前十个电话号码进行加密，加密的方法是电话号码中每个数字分别变为其后第三个数字，如0变为3，1变为4，7变0，8变1，9变为2。 【分析】这个问题是需要将十个电话号码加密。每个电话号码的基本特征都一样，加密方法也相同，所以使用循环就可以对十个电话号码加密了，因此是一个典型的循环结构。,3.4.2 多维数组,用数组将电话号码表示出来，电话号码的每一位都是该数组的一个元素。 这个问题中的电话号码最终表示在计算机世界中就是一个二维数组。因为一共有10个电话号码，每个电话又都是11位的手机号。,3.4.3 结构体,现实问题中，有一些数据本身之间有特殊的关系
11、（如通讯录中一个人的姓名和电话号码），它们同呼吸共命运，但又不能用数组组织起来，最适合这种情况的就是结构体。 所谓结构体，实际上也是一种特殊的数据组织形式，每个结构体里面都封装了多个数据，这多个数据都是隶属于同一个主体。,3.4.4 指针,现实世界中，有些数据并不存储直接有用的信息，而是存储如何找到其他数据的信息。它们被用来组织其他数据。这就是指针。,3.4.5 链表,链表可以看作是一种数据组织形式，它可以将多个数据组织成一条链。 链表就像项链一样，链表上的每个数据不仅包含直接有用的信息，还包含指向下一个数据的线索。,3.4.6 树和图,在现实生活中，很多问题中的数据不是连成线的，可能是连成一
12、棵树的样子。 比如某学校的行政组织结构，最顶层的校长，下面是副校长，下面是各级的主任，再下面是副主任，再下面是普通的老师或员工。 再比如家谱，一直从祖先到现在第N代传人，其数据组织都是典型的树状结构。,3.4.6 树和图,除了树状结构之外，现实生活还有很多数据组织是图状的问题。如：多个城市之间的交通图。,3.4.6 树和图,在图和树中，每个数据不仅包含直接有用的信息，还要指向多个其他的数据。 具体的树状结构和图状结构的相关问题，后续数据结构课程会进一步学习。,3.4.7 数据类型扩展机制,在基本数据类型和上面所讲的数组、结构体以及链表的基础上，可以根据自己的需要构造最有利于算法执行的各种数据类
13、型。 如：数组的元素还可以是数组、结构体或链表，结构体的每个成员还可以是结构体、数组或链表，链表同样也类似。 C语言如何支持这种数据类型的扩展机制会在第四章介绍。,3.4.8 利用数据组织获得好的算法,在分析问题时，能够设计和选择一种合适的数据的组织形式是相当重要的，会直接影响到算法的好坏。,3.5 典型算法整理,3.5.1 求累加和 3.5.2 求累乘积 3.5.3 求阶乘 3.5.4 查找 3.5.5 排序 3.5.6 进制转换 3.5.7 求最大公约数及最小公倍数 3.5.8 数值求解,3.5.1求累加和,求累加和的算法为： （1）把存储累加和的变量x初始化为0； （2）对于所有要累加的
14、数a，重复执行累加操作：x=x+a； （3）输出x的值； （4）结束；,3.5.2 求累乘积,求累乘积的算法与求累加和的算法类似，算法如下： （1）把存储乘积的变量x初始化为1； （2）对于所有要乘的数a，重复执行乘法操作：x=x*a； （3）输出x的值； （4）结束； 求累加和、求累乘积都属于累计算法,3.5.3 求阶乘,求阶乘显然是一个求累乘积的问题，算法如下： （1）输入n； （2）把存储结果的变量x初始化为1； （3）把a初始化为1； （4）执行乘法操作：x=x*a； （5）a加1； （6）若a小于等于n，转向（4）； （7）输出x的值； （8）结束；,3.5.3 求阶乘,实际上，多个
15、累计可以同时进行，一个累计为其他的累计提供输入 求前n个阶乘的累加和应该用什么算法？,3.5.3 求阶乘,下面给出一个算法： （1）输入n； （2）把存储结果的变量x初始化为1； （3）把a初始化为1； （4）把累加和变量y初始化为0； （5）执行乘法操作：x=x*a； （6）y=y+x; （7）a加1； （8）若a小于等于n，转向（4）； （9）输出y的值； （10）结束； 在级数求和中，经常会用到多个累计的情况。,3.5.4 查找,查找问题是在一个数据空间内寻找有没有指定数据的问题，查找的结果是给出所找到的指定数据的集合（集合为空时输出“未找到！”）。 有时，算法也会输出第一个找到的指定数
16、据，等用户要求下一个时，再继续查找。 最简单的查找就是遍历，即遍历整个数据空间，逐个看是否匹配。计算机与人相比其特点就是速度快，因此遍历匹配是最基本的查找算法。,3.5.4 查找,在未排序数组中查找一个数的遍历匹配算法： 数组A，序号从0开始，元素个数为n。 （1）输入要查找的数x； （2）i初始化为0，c初始化为0； （3）若i=n，转向（7）； （4）若Ai=x，c加1，并输出i； （5）i加1； （6）转向（3）； （7）若c=0，输出“未找到”； （8）结束；,3.5.4 查找,当数据空间的元素之间存在可以利用的关联时，查找的速度可以加快。 对于有序序列，和中间的元素比较大小能够使查找空间减半,3.5.4 查找,二分查找算法 元素按从大到小排序的数组A，序号从0开始,元素个数为n。 （1）输入要查找的数x； （2）查找区间下界m1初始化为0，上界m2初始化为n-1； （3）若m2A(m1+m2)/2，m2=(m1+m2)/2-1； （6）若x A(m1+m2)/2
