c语言笔记.ppt

1、算法与程序设计基础,第二章,2/32,语言程序设计,语言计算机语言：是规则和符号的集合， 是人与计算机进行交流的工具。 程序计算机程序：求解问题的指令序列。 设计程序设计：如何用语言编制程序。,语法规则,程序结构,设计方法,3/32,本章内容,一、什么是程序设计 二、什么是算法 三、算法的描述方法 四、程序的三种基本结构 五、常用算法 六、结构化程序设计的思想和方法,计算机数据处理机 计算机的操作对象都是数据,4/32,一、程序设计的基本概念,程序 = 数据 + 代码 程序设计数据结构算法 数据结构：对数据的描述。数据的组织形式。 算法：对操作的描述。解决实际问题的方法和步骤。 程序设计的扩充

2、公式： 程序设计数据结构算法设计方法语言工具,Pascal之父 尼克劳斯沃思 Niklaus Wirth,5/32,程序设计步骤 分析问题，建立数学(据)模型 数据结构设计 算法设计（描述算法） 编制程序 测试与运行,概念世界,计算机世界,设计,实现,自然语言 流程图 伪代码,数据结构的优劣决定了软件或程序的复杂程度和面貌。,算法描述方法,一、程序设计的基本概念(续),6/32,二、算法的基本概念,计算机语言的别名：算法语言 算法：完成一项任务的具体步骤。 “一个算法，就是一个有穷规则的集合，其中之规则规定了一个解决某一特定类型的问题的运算序列。” 任何解决问题的过程都是由一定的步骤组成的，把

3、解决问题确定的方法和有限的步骤称作为算法。,程序的灵魂,7/32,例：交换两个墨水瓶中的墨水,有黑和蓝两个墨水瓶，但却错把黑墨水装在了蓝墨水瓶子里，而蓝墨水错装在了黑墨水瓶子里，要求将其互换。 算法分析：这是一个非数值运算问题。因为两个瓶子的墨水不能直接交换，所以，解决这一问题的关键是需要引入第三个空的墨水瓶。设第三个墨水瓶为白色，交换步骤如下： 将蓝瓶中的黑墨水装入白瓶中； 将黑瓶中的蓝墨水装入蓝瓶中； 将白瓶中的黑墨水装入黑瓶中； 交换结束。,用自然语言描述的算法,8/32,算法的基本特征,有穷性：算法必须在执行有限个操作后终止； 确定性：算法中每一步的含义必须是确切的，不可出现任何二义性

4、； 有效性：算法中的每一步操作都应该能有效执行，一个不可执行的操作是无效的； 有零个或多个输入 ； 有一个或多个输出。,9/32,例：计算函数M(x)的值。函数M(x)为：,算法分析：这是一个数值运算问题。其中M代表要计算的函数值，有两个不同的表达式，根据x的取值决定采用哪一个算式。根据计算机具有逻辑判断的基本功能，用计算机解题的算法如下：,10/32, 将a、b、c和x的值输入到计算机； 判断xa? 如果条件成立，执行第步，否则执行第步； 按表达式bx+a2计算出结果存放到M中，然后执行第步； 按表达式a(c-x)+c2计算出结果存放到M中，然后执行第步； 输出M的值； 算法结束。,用自然语

5、言描述的算法,用流程图描述的算法,11/32,三、算法的描述方法,可以用不同的方法描述算法，常用方法有： 自然语言 流程图 传统流程图 N-S流程图 ISO标准流程图 PAD图 伪代码：介于自然语言和计算机语言之间的用文字和符号来描述算法的工具。一种假的代码，不能被计算机所理解，但便于转换成编程语言。,结构化流程图,12/32,1、传统流程图,美国国家标准化协会ANSI(American National Standard Institute)规定了一些常用的流程图符号：,13/32,例：有50个学生，要求将他们之中成绩在80分以上者打印出来。用g代表学生成绩，gi 代表第i个学生成绩。 算法

6、可表示如下： S1：1i S2：如果gi 80，则打印 gi，否则不打印 S3：i+1 i S4：如果 i 50，返回S2， 继续执行；否则，算法结束。,14/32,传统流程图的弊端,传统流程图用流程线指出各框的执行顺序，对流程线的使用没有严格限制。因此，使用者可以毫不受限制地使流程随意地转向，使流程图变得毫无规律，阅读者要花很大精力去追踪流程，使人难以理解算法的逻辑。如图： 缺点：难以阅读、修改，使算法的可靠性和可维护性难以保证。 解决办法：必须限制箭头的滥用，即不允许无规律地使流程随意转向，只能顺序的进行下去。,A Bowl of Spaghetti,15/32,2、NS流程图,由美国学者

7、I.Nassi和B.Shneiderman提出表示算法的图形工具。 基本单元是矩形框，用不同的形状线分割，表示三种程序结构。只有一个入口，一个出口，没有流程线。 N-S图的优点：比文字描述直观、形象、易于理解；比传统流程图紧凑易画。尤其是它废除了流程线，整个算法结构是由各个基本结构按顺序组成的，N-S流程图中的上下顺序就是执行时的顺序。,Ike. Nassi 王大西,Ben. Shneiderman,16/32,0t,0i,i+1i,t+it,直到 i100不成立,输出 t 的值,成立,i100,不成立,开始,0t,0i,i+1i,t+it,输出 t 的值,结束,例：1+2+3+100,传统流

8、程图与N-S流程图的比较,17/32,四、程序的三种基本结构,#include /因为程序中用到了printf( ) main( ) double c, f; printf(请输入一个华氏温度：); scanf(%lf, ,顺序结构的程序,18/32,1、顺序结构,程序按照语句的书写次序顺序执行。,B,A,先执行A操作，再执行B操作，两者是顺序执行关系。,A B,传统流程图,N-S图,19/32,语句,不成立,条件P,成立,当P条件成立时，执行语句操作，否则跳过语句操作,2、选择结构,通过判断特定条件，选择一个分支执行。,传统流程图,N-S图,条件P,Y,N,语句,单分支结构,20/32,A,

9、条件P,B,成立,不成立,当P条件成立时，执行A操作，否则执行B操作,2、选择结构,通过判断特定条件，选择一个分支执行。,传统流程图,N-S图,条件P,Y,N,A B,双分支结构,21/32,不成立,P,A,成立,当P条件成立时，反复执行A，直到P不成立为止。,3、循环结构,在给定条件下，反复执行循环体，直到条件不满足为止,当型循环,传统流程图,N-S图,循环体,当条件P成立时,22/32,3、循环结构,在给定条件下，反复执行循环体，直到条件不满足为止,A,P,不成立,成立,先执行A操作，再判断P是否成立，若P成立，再执行A，直到P不成立为止。,直到型循环,循环体,直到条件P不成立时,传统流程

10、图,N-S图,23/32,五、常用算法简介,(1) 交换两个变量的值 采用间接交换方法t = a;a = b;b = t; (2)计数器、累加器、连乘器 计数器：用于统计循环的次数。如：i=i+1; 累加器：用于实现数值求和。如：sum=sum+x; 连乘器：用于实现数值求积。如：mul=mul*x;,a,t,b,i,24/32,(3) 枚举法（穷举法或试凑法）,根据题目确定答案的范围，然后在此范围内对所有可能的情况逐一验证。若某个情况符合题目条件，则为本题的一个答案；若全部情况验证完后均不符合题目的条件，则问题无解。 如：百元买百鸡问题。假定小鸡每只0.5元，公鸡每只2元，母鸡每只3元。现在

11、有100元钱要求买100只鸡，问共有几种购鸡方案？ 根据题目，设母鸡、公鸡、小鸡各为x, y, z只，列出方程为： x + y + z = 100 3x + 2y + 0.5z = 100,25/32,#include main( ) int x, y, z; printf(母鸡 公鸡 小鸡); for (x = 0; x = 100; x+) for (y = 0; y = 100; y+) for (z = 0; z = 100; z+) if (x+y+z=100 ,26/32,#include main( ) int x, y, z; printf(母鸡 公鸡 小鸡); for (x

12、= 0; x = 33; x+) for (y = 0; y = 50; y+) z = 100 - x - y; if (3 * x + 2 * y + 0.5 * z = 100) printf(n%-6d %-6d %-6d , x, y, z); printf(n); ,27/32,(4) 递推法（迭代法）,利用问题本身所具有的某种递推关系求解问题。从初值出发，归纳出新值与旧值间存在的关系，从而把一个复杂的计算过程转换为简单过程的多次重复，每次重复都在旧值的基础上递推出新值，并由新值代替旧值。 如：求高次方程的近似解问题、猴子吃桃问题。 小猴在一天内摘了若干个桃子，当天吃掉一半多一个；

13、第二天吃掉剩下的一半桃子多一个；以后每天都吃尚存桃子的一半零一个。直到第7天早上要吃时，只剩下一个了，问小猴共摘了多少个桃子？ 问题分析：先从最后一天推出倒数第二天的桃子，再从倒数第二天推出倒数第三天的桃子，。,找出前后两天桃子数的关系：xn=xn-1/2-1，xn-1=(xn+1)2,28/32,#include main( ) int i, x; x = 1; printf(第 7 天的桃子数为：1只n); for (i = 6; i = 1; i-) x = (x + 1) * 2; printf(第 %d 天的桃子数为：%d只n, i, x); ,29/32,(5)打擂台法（求最大值、

14、最小值问题）,在n个数中，先假设第一个数为最大值，成为擂主，依次同第2，3，n个数据逐一比较，一旦某个数大，马上替换擂主；所有值比较完，最大值也就获得。,#include main() int a10, i, max; for (i = 0; i max) max = ai; /如何求最小数？ printf(max=%dn, max); ,30/32,(6)冒泡法（排序问题）,#include #define N 6 main() int aN, i, j, t; for (i = 0; i aj) t = aj - 1; aj - 1 = aj; aj = t ; for (i = 0; i N; i+