C语言程序设计教程 课件 第2章 算法初步.pptx

第2章算法初步

理论知识算法概述12算法描述3算法设计方法4算法特性

尼古拉斯·沃斯（NikiklasWirth）

1.算法概述一个程序应包括：（1）对数据的描述。在程序中要指定数据的类型和数据的组织形式，即数据结构（DataStructure）（2）对操作的描述。即操作步骤，也就是算法（Algorithm）算法：精确描述解决问题的方法步骤尼古拉斯·沃斯（NikiklasWirth）提出的公式：数据结构+算法=程序教材认为：程序=算法+数据结构+程序设计方法+语言工具环境

1.算法概述C语言基本（典型）算法：1.列(穷)举法：百鸡百钱2.归纳法：斐波列契3.递推法猴子吃桃4.递归法阶乘5.减半递推法猜数字6.回溯法（试探法）树的遍历

简单算法举例例1求1*2*3*4*5。最原始的方法：步骤1：先求1*2，得到结果2步骤2：将步骤1得到的乘积2乘以3，得到6步骤3：将6再乘以4，得24步骤4：将24再乘以5，得120.#includestdio.hvoidmain(){ intsum; sum=1*2*3*4*5; printf(%d\n,sum);}#includestdio.hvoidmain(){inti,sum;sum=1;i=2;while(i=5){sum=sum*i;i=i+1;}printf(%d\n,sum);}改进的算法：S1:使t=1S2:使i=2S3:使t*i，乘积仍然放在变量t中，可表示为t*i→tS4：使i的值+1，即i+1→iS5：如果i=5,返回重新执行步骤S3以及其后的S4和S5；否则，算法结束。这样的算法虽然正确，但太繁。

2.算法的特性有穷性：一个算法应包含有限的操作步骤而不能是无限的。确定性：算法中每一个步骤应当是确定的，而不能应当是含糊的、模棱两可的。有零个或多个输入。有一个或多个输出。有效性：算法中每一个步骤应当能有效地执行，并得到确定的结果。时间复杂度空间复杂度

3.算法描述-怎么表示一个算法自然语言：一般不用，除了很简单的问题伪代码：使用介于自然语言和计算机语言之间的文字和符号来描述算法

伪代码：现在的编程语言种类很多，伪代码不是具体某一种编程语言的代码，而是专用普遍的可以理解的方式写出的代码，写这样的代码的目的是为了讲解描述算法，而不是为了通过编译得到可执行程序。3.算法描述-怎么表示一个算法

3.算法描述-怎么表示一个算法自然语言：一般不用，除了很简单的问题伪代码：使用介于自然语言和计算机语言之间的文字和符号来描述算法流程图：直观形象，易于理解程序流程图又称程序框图，是用统一规定的标准符号描述程序运行具体步骤的图形表示。程序框图的设计是在处理流程图的基础上，通过对输入输出数据和处理过程的详细分析，将计算机的主要运行步骤和内容标识出来。

流程图实例1：求圆的面积

流程图实例2：求两个数中的大数定义三个数值求最大

流程图实例3：求5！

三种基本结构的流程三种基本结构的共同特点：（1）只有一个入口；（2）只有一个出口；（3）结构内的每一部分都有机会被执行到；（4）结构内不存在“死循环”

3.算法描述-怎么表示一个算法自然语言：一般不用，除了很简单的问题伪代码：使用介于自然语言和计算机语言之间的文字和符号来描述算法流程图：直观形象，易于理解N-S图：1973年美国学者提出了一种新型流程图

3.算法描述-怎么表示一个算法自然语言：一般不用，除了很简单的问题伪代码：使用介于自然语言和计算机语言之间的文字和符号来描述算法流程图：直观形象，易于理解N-S图：1973年美国学者提出了一种新型流程图计算机语言：必需严格遵循所用语言的语法规则#includestdio.hvoidmain(){inti,sum;sum=1;i=2;while(i=5){sum=sum*i;i=i+1;}printf(%d\n,sum);}

4.算法设计方法——结构化程序设计方法自顶向下；逐步细化；模块化设计；结构化编码。

工作任务两个变量互换12三个变量排序3三个变量求最大值4求圆面积

实践知识任务1:两个变量值互换/*案例1-1*/#includestdio.hvoidmain(){ inta=5,b=3;a=3;b=5; printf(“a=%d\nb=%d”,a,b);}

实践知识任务1:两个变量值互换/*案例1-1*/#includestdio.hvoidmain(){