C语言程序设计第3版算法与程序设计基础

1、共 32 页 第 1 1 页共 32 页 第 2 2 页共 32 页 第 3 3 页 计算机语言：是规则和符号的集合，是与计算机语言：是规则和符号的集合，是与计算机交流的工具。必须具有数据表达和计算机交流的工具。必须具有数据表达和数据处理（流程控制）的能力。数据处理（流程控制）的能力。 程序：求解问题的指令序列程序：求解问题的指令序列 软件：程序的集合软件：程序的集合学习语言学习语言 设计程序设计程序 制作软件制作软件学思想、学功能、学操作。熟练工种学思想、学功能、学操作。熟练工种学规则、学方法、学设计、学应用。学规则、学方法、学设计、学应用。 规范学习，灵活应用规范学习，灵活应用共 32 页

2、 第 4 4 页计算机语言分类计算机语言分类 面向过程语言面向过程语言 面向对象语言面向对象语言FORTRANFORTRANBASICBASICC CPASCALPASCALCOBOLCOBOLLISPLISPC+C+C#C#Visual CVisual CVisual BASICVisual BASICVisual J+Visual J+系统软件设计系统软件设计具有图形功能具有图形功能科学计算科学计算商用商用人工智能人工智能共 32 页 第 5 5 页1.1 1.1 程序设计的基本概念程序设计的基本概念 数据元素：数据的最小单位数据元素：数据的最小单位 数据结构：数据元素的组织形式数据结构：

3、数据元素的组织形式程序设计程序设计数据结构数据结构算法算法方法方法工具工具数据结构的优劣决定了数据结构的优劣决定了 软件或程序的复杂程度和面貌软件或程序的复杂程度和面貌一个程序应包括两个方面的内容一个程序应包括两个方面的内容: : 对数据的描述：数据结构对数据的描述：数据结构 对操作的描述：算法对操作的描述：算法完整的程序设计应该包括四部分完整的程序设计应该包括四部分: :共 32 页 第 6 6 页程序设计的步骤程序设计的步骤 分析问题，建立数学模型分析问题，建立数学模型 确定数据结构确定数据结构 确定算法，描述算法确定算法，描述算法 编制程序，调试程序编制程序，调试程序 运行结果运行结果x

4、nns1 一个正确的程序通常包含两方面的含义：一是书写正一个正确的程序通常包含两方面的含义：一是书写正确，二是结果正确。书写正确是指程序语法正确，符合程确，二是结果正确。书写正确是指程序语法正确，符合程序语言的规则；结果正确是指对应于正确的输入，程序能序语言的规则；结果正确是指对应于正确的输入，程序能够得到所期望的输出。够得到所期望的输出。共 32 页 第 7 7 页程序的三种基本结构1.1.顺序结构顺序结构 程序按照语句的书写次序顺序执行。程序按照语句的书写次序顺序执行。 BA 先执行先执行A A操作，再执行操作，再执行B B操作，两者是顺序执行关系。操作，两者是顺序执行关系。共 32 页

5、第 8 8 页 2. 2.选择结构选择结构 通过判断特定条件，选择一个分支执行。通过判断特定条件，选择一个分支执行。当当P P条件成立时，执行条件成立时，执行A A操作，否则执行操作，否则执行B B操作操作APB 成立成立不成立不成立 语句语句不成立不成立 P成立成立当当P P条件成立时，执行语句操作，否则跳过语句操作条件成立时，执行语句操作，否则跳过语句操作共 32 页 第 9 9 页 3. 循环结构循环结构 在给定条件下，反复执行循环体，直到条件不满足为止在给定条件下，反复执行循环体，直到条件不满足为止. .(1)形式形式a （当型循环结构）（当型循环结构）不成立不成立 PA成立成立 当当

6、P P条件成立时，反复执行条件成立时，反复执行A,A,直到直到P P为零为止。为零为止。共 32 页 第 1010 页(2)(2)形式形式b b （直到型循环结构）（直到型循环结构）先执行先执行A A操作，再判断操作，再判断P P是否成立，若是否成立，若P P成立，再执成立，再执行行A A，直到，直到P P不成立为止。不成立为止。AP成立成立不成立不成立 共 32 页 第 1111 页1. 1. 算法的概念算法的概念1.2 1.2 算法概述算法概述 “ “一个算法，就是一个有穷规则的一个算法，就是一个有穷规则的集合，其中之规则规定了一个解决某一集合，其中之规则规定了一个解决某一特定类型的问题的

7、运算序列。特定类型的问题的运算序列。” ” 任何解任何解决问题的过程都是由一定的步骤组成的，决问题的过程都是由一定的步骤组成的，把把解决问题确定的方法和有限的步骤称解决问题确定的方法和有限的步骤称作为算法作为算法。共 32 页 第 1212 页算法分析：算法分析：这是一个数值运算问题。其中这是一个数值运算问题。其中M M代表要计算的函数值，有两个不同的表代表要计算的函数值，有两个不同的表达式，根据达式，根据x x的取值决定采用哪一个算式。的取值决定采用哪一个算式。根据计算机具有逻辑判断的基本功能，根据计算机具有逻辑判断的基本功能，用计算机解题的算法如下：用计算机解题的算法如下：axaxcxca

8、abxxM22)()(共 32 页 第 1313 页 将将a a、b b、c c和和x x的值输入到计算机；的值输入到计算机； 判断判断xa?xa?如果条件成立，执行第如果条件成立，执行第步，步，否则执行第否则执行第步；步； 按表达式按表达式bx+abx+a2 2计算出结果存放到计算出结果存放到M M中，中，然后执行第然后执行第步；步； 按表达式按表达式a(c-x)+ca(c-x)+c2 2计算出结果存放到计算出结果存放到M M中，然后执行第中，然后执行第步；步； 输出输出M M的值；的值； 算法结束。算法结束。axaxcxcaabxxM22)()(共 32 页 第 1414 页算法分析：算法

9、分析：这是一个非数值运算问题。因这是一个非数值运算问题。因为两个瓶子的墨水不能直接交换，所以，为两个瓶子的墨水不能直接交换，所以，解决这一问题的关键是需要解决这一问题的关键是需要引入第三个引入第三个墨水瓶墨水瓶。设第三个墨水瓶为白色，其交。设第三个墨水瓶为白色，其交换步骤如下：换步骤如下：共 32 页 第 1515 页将蓝瓶中的黑墨水装入白瓶中将蓝瓶中的黑墨水装入白瓶中将黑瓶中的蓝墨水装入蓝瓶中将黑瓶中的蓝墨水装入蓝瓶中将白瓶中的黑墨水装入黑瓶中将白瓶中的黑墨水装入黑瓶中交换结束交换结束共 32 页 第 1616 页2.2.算法的基本特征算法的基本特征 算法是一个有穷规则的集合，这些规则确定了

10、算法是一个有穷规则的集合，这些规则确定了解决某类问题的一个运算序列。解决某类问题的一个运算序列。 算法的基本特征：算法的基本特征：l有穷性：有穷性：算法必须在执行有限个操作后终止；算法必须在执行有限个操作后终止； l确定性：确定性：算法中每一步的含义必须是确切的，不算法中每一步的含义必须是确切的，不能出现任何二义性；能出现任何二义性；l有效性：有效性：算法中的每一步操作都应该能有效执行算法中的每一步操作都应该能有效执行，一个不可执行的操作是无效的；，一个不可执行的操作是无效的；l有零个或多个输入：有零个或多个输入：执行算法时，从外界获得必执行算法时，从外界获得必要的信息要的信息 ；l有一个或多

11、个输出：有一个或多个输出：算法的解就是输出算法的解就是输出。共 32 页 第 1717 页3.3.算法的常用表示方法算法的常用表示方法可以用不同的方法表示算法，常用方法有：可以用不同的方法表示算法，常用方法有：自然语言自然语言传统流程图传统流程图结构化流程图结构化流程图 共 32 页 第 1818 页（1 1）自然语言）自然语言自然语言即是使用汉语、英语或其他语言去描述算法。自然语言即是使用汉语、英语或其他语言去描述算法。 例例 有有5050名学生的成绩，要求将他们之中名学生的成绩，要求将他们之中8080分以上的成绩分以上的成绩打印出来。设用打印出来。设用g g代表学生成绩，代表学生成绩，gi

12、 gi 代表第代表第i i个学生成绩。个学生成绩。算法可表示如下：算法可表示如下：1 1）使使i=1i=1 ；2 2）如果如果gi gi 80 80 ，则打印，则打印 gi gi ，否则不打印；，否则不打印；3 3）使使i i的值加的值加1 1 ；4 4）如果如果 i i 50, 50, 返回返回S2S2， 继续执行；继续执行； 否则，算法结束否则，算法结束。特点特点：描述算法通俗易懂，容易产生歧义。对复杂问题，：描述算法通俗易懂，容易产生歧义。对复杂问题，语句繁琐、冗长，并且很难清楚地表达算法的逻辑流程，语句繁琐、冗长，并且很难清楚地表达算法的逻辑流程，往往需要根据上下文判别其含义，尤其对描

13、述含有选择、往往需要根据上下文判别其含义，尤其对描述含有选择、循环结构的算法，不太方便和直观，一般不常使用。循环结构的算法，不太方便和直观，一般不常使用。共 32 页 第 1919 页(2)(2)传统流程图传统流程图 美国国家标准化协会美国国家标准化协会ANSI(American ANSI(American National Standard Institute)National Standard Institute)规定了规定了一些常用的流程图符号：一些常用的流程图符号：起止框起止框判断框判断框处理框处理框输入输入/输出框输出框注释框注释框流向线流向线连接点连接点共 32 页 第 2020

14、页程序流程图表示程序流程图表示开始开始1 igi=80输出输出gii+1 ii50结束结束成立成立不成立不成立不成立不成立成立成立传统流程图用流传统流程图用流程线指出各框的程线指出各框的执行顺序，对流执行顺序，对流程线的使用没有程线的使用没有严格限制。严格限制。共 32 页 第 2121 页传统流程图的流程可以是：缺点：缺点：使用者可以毫不受限制地使流程随意地转向，使用者可以毫不受限制地使流程随意地转向，使流程图变得毫无规律，难以阅读、修改，使算法的使流程图变得毫无规律，难以阅读、修改，使算法的可靠性和可维护性难以保证。可靠性和可维护性难以保证。解决办法：解决办法：必须限制箭头的滥用，即不允许

15、无规律地必须限制箭头的滥用，即不允许无规律地使流程随意转向，只能顺序的进行下去。使流程随意转向，只能顺序的进行下去。 共 32 页 第 2222 页（3 3）NSNS流程图流程图 NSNS流程图流程图 由美国学者由美国学者I.I.N Nassiassi和和B.B.S Shneidermanhneiderman提出表提出表示算法的图形工具。基本单元是矩形框示算法的图形工具。基本单元是矩形框, ,用不同用不同的形状线分割的形状线分割, ,表示三种结构。只有一个入口表示三种结构。只有一个入口, ,一一个出口个出口, ,没有流程线。没有流程线。N-SN-S图的优点图的优点 比文字描述直观、形象、比文字

16、描述直观、形象、 易于理解；比传易于理解；比传统流程图紧凑易画。尤其是它废除了流程线，整统流程图紧凑易画。尤其是它废除了流程线，整个算法结构是由各个基本结构按顺序组成的，个算法结构是由各个基本结构按顺序组成的，N-N-S-S流程图中的上下顺序就是执行时的顺序。流程图中的上下顺序就是执行时的顺序。共 32 页 第 2323 页 三种基本程序结构的三种基本程序结构的NSNS流程图流程图条件条件TF语句1 语句22.2.选择结构选择结构语句1语句21.1.顺序结构顺序结构3.3.循环结构循环结构 循环体循环体循环体循环体当满足条件时当满足条件时 直到条件成立直到条件成立循环结构一循环结构一循环结构二

17、循环结构二共 32 页 第 2424 页0t,0ii+1i t+it直到直到 i 100输出输出 t 的值的值传统流程图与传统流程图与N-SN-S流程图的比较流程图的比较i 100 NY开始开始 0t,0ii+1i t+it输出输出 t 的值的值结束结束例例1 1：1+2+3+ 1+2+3+ 加到加到100100为止为止共 32 页 第 2525 页例：例：打印打印5050名名学生中成绩学生中成绩高于高于8080分的分的学号和成绩学号和成绩用用N-SN-S图表图表示。示。 共 32 页 第 2626 页1. 1. 枚举法（穷举法）枚举法（穷举法）特点特点: :算法简单，容易理解，运算算法简单，

18、容易理解，运算量大。量大。基本思想：基本思想： 根据题目的部分条件确定答案的大致范围，然后在根据题目的部分条件确定答案的大致范围，然后在此范围内对所有可能的情况逐一验证，直到所有情况均此范围内对所有可能的情况逐一验证，直到所有情况均通过验证。若某个情况符合题目条件，则为本题的一个通过验证。若某个情况符合题目条件，则为本题的一个答案；若全部情况验证完后均不符合题目的条件，则问答案；若全部情况验证完后均不符合题目的条件，则问题无解。题无解。 如：百元买百鸡问题。假定小鸡每只如：百元买百鸡问题。假定小鸡每只0.50.5元，公鸡每元，公鸡每只只2 2元，母鸡每只元，母鸡每只3 3元。现在有元。现在有1

19、00100元钱要求买元钱要求买100100只鸡，只鸡，问共有几种购鸡方案？问共有几种购鸡方案？ 根据题目，设母鸡、公鸡、小鸡各为根据题目，设母鸡、公鸡、小鸡各为x,y,zx,y,z只，列出只，列出方程为：方程为：x+y+z=100 x+y+z=100，3x+2y+0.5z=1003x+2y+0.5z=100 利用穷举法，将各种可能的组合一一测试，输出符合利用穷举法，将各种可能的组合一一测试，输出符合条件的组合。即在各个变量的取值范围内不断变化条件的组合。即在各个变量的取值范围内不断变化x,y,zx,y,z的值，穷举的值，穷举x,y,zx,y,z全部可能的组合，若满足方程组则是一全部可能的组合，若满足方程组则是一组解。组解。 1.3 1.3 几种常用算法介绍几种常用算法介绍共 32 页 第 2727 页#include stdio.hmain() int x,y,z; printf(母鸡母鸡 公鸡公鸡 小鸡