算法与程序设计基础c语言

•授课学时（讲授32学时，上机24学时4-15周）•教材:C语言程序设计C语言程序设计习题解析与上机指导机械工业出版社•参考教材：C语言程序设计谭浩强编写清华大学出版社•交流平台：网上学习中心•关于考试：课程结束全校统一安排关于本课程教员：杨微EmaiL:[e-mail]第一章C语言程序设计本章要点什么是程序设计什么是算法，如何设计和表示算法结构化程序设计的思想和方法共33页第4页•计算机语言：是规则和符号的集合，是与计算机交流的工具。必须具有数据表达和数据处理（流程控制）的能力。•程序：求解问题的指令序列•软件：程序的集合学习语言设计程序制作软件概念：学软件：学思想、学功能、学操作。熟练工种学语言：学规则、学方法、学设计、学应用。规范学习，灵活应用共33页第5页计算机语言分类•面向过程语言•面向对象语言FORTRANBASICCPASCALCOBOLLISPC++C#VisualCVisualBASICVisualJ++系统软件设计具有图形功能科学计算商用人工智能共33页第6页1.1程序设计的基本概念•数据元素：数据的最小单位•数据结构：数据元素的组织形式程序设计＝数据结构＋算法＋方法＋工具数据结构的优劣决定了软件或程序的复杂程度和面貌一个程序应包括两个方面的内容:•对数据的描述：数据结构•对操作的描述：算法完整的程序设计应该包括四部分:共33页第7页程序设计的步骤•分析问题，建立数学模型•确定数据结构•确定算法，描述算法•编制程序，调试程序•运行结果xnns1共33页第8页程序的三种基本结构1.顺序结构程序按照语句的书写次序顺序执行。BA先执行A操作，再执行B操作，两者是顺序执行关系。共33页第9页2.选择结构通过判断特定条件，选择一个分支执行。当P条件成立时，执行A操作，否则执行B操作APB成立不成立语句不成立P成立当P条件成立时，执行语句操作，否则跳过语句操作共33页第10页3.循环结构在给定条件下，反复执行循环体，直到条件不满足为止.(1)形式a（当型循环结构）不成立PA成立当P条件成立时，反复执行A,直到P为零为止。共33页第11页(2)形式b（直到型循环结构）先执行A操作，再判断P是否成立，若P成立，再执行A，直到P不成立为止。AP成立不成立共33页第12页•算法：完成一项任务的具体步骤•计算机语言的别名：算法语言1.算法的概念1.2算法概述“一个算法，就是一个有穷规则的集合，其中之规则规定了一个解决某一特定类型的问题的运算序列。”任何解决问题的过程都是由一定的步骤组成的，把解决问题确定的方法和有限的步骤称作为算法。共33页第13页•例1：计算函数M(x)的值。函数M(x)为：算法分析：这是一个数值运算问题。其中M代表要计算的函数值，有两个不同的表达式，根据x的取值决定采用哪一个算式。根据计算机具有逻辑判断的基本功能，用计算机解题的算法如下：axaxcxcaabxxM22)()(共33页第14页①将a、b、c和x的值输入到计算机；②判断x≤a?如果条件成立，执行第③步，否则执行第④步；③按表达式bx+a2计算出结果存放到M中，然后执行第⑤步；④按表达式a(c-x)+c2计算出结果存放到M中，然后执行第⑤步；⑤输出M的值；⑥算法结束。这是用自然语言描述的算法共33页第15页•例2：有黑和蓝两个墨水瓶，但却错把黑墨水装在了蓝墨水瓶子里，而蓝墨水错装在了黑墨水瓶子里，要求将其互换。算法分析：这是一个非数值运算问题。因为两个瓶子的墨水不能直接交换，所以，解决这一问题的关键是需要引入第三个墨水瓶。设第三个墨水瓶为白色，其交换步骤如下：共33页第16页①将蓝瓶中的黑墨水装入白瓶中②将黑瓶中的蓝墨水装入蓝瓶中③将白瓶中的黑墨水装入黑瓶中④交换结束共33页第17页2.算法的基本特征算法是一个有穷规则的集合，这些规则确定了解决某类问题的一个运算序列。算法的基本特征：有穷性：算法必须在执行有限个操作后终止；确定性：算法中每一步的含义必须是确切的，不能出现任何二义性；有效性：算法中的每一步操作都应该能有效执行，一个不可执行的操作是无效的；有零个或多个输入：执行算法时，从外界获得必要的信息；有一个或多个输出：算法的解就是输出。共33页第18页3.算法的常用表示方法可以用不同的方法表示算法，常用方法有：–自然语言–传统流程图–结构化流程图（1）自然语言自然语言即是使用汉语、英语或其他语言去描述算法。[例]有50名学生的成绩，要求将他们之中80分以上的成绩打印出来。设用g代表学生成绩，gi代表第i个学生成绩。算法可表示如下：1）使i=1；2）如果gi80，则打印gi，否则不打印；3）使i的值加1；4）如果i50,返回步骤2，继续执行；否则，算法结束。特点：描述算法通俗易懂，容易产生歧义。对复杂问题，语句繁琐、冗长，并且很难清楚地表达算法的逻辑流程，往往需要根据上下文判别其含义，尤其对描述含有选择、循环结构的算法，不太方便和直观，一般不常使用。共33页第20页(2)传统流程图美国国家标准化协会ANSI(AmericanNationalStandardInstitute)规定了一些常用的流程图符号：起止框判断框处理框输入/输出框注释框流向线连接点程序流程图表示开始1igi=80输出gii+1ii=50结束成立成立不成立不成立传统流程图用流程线指出各框的执行顺序，对流程线的使用没有严格限制。共33页第22页传统流程图的流程可以是：缺点：使用者可以毫不受限制地使流程随意地转向，使流程图变得毫无规律，难以阅读、修改，使算法的可靠性和可维护性难以保证。解决办法：必须限制箭头的滥用，即不允许无规律地使流程随意转向，只能顺序的进行下去。共33页第23页（3）N–S流程图•N—S流程图由美国学者I.Nassi和B.Shneiderman提出表示算法的图形工具。基本单元是矩形框,用不同的形状线分割,表示三种结构。只有一个入口,一个出口,没有流程线。N--S图的优点比文字描述直观、形象、易于理解；比传统流程图紧凑易画。尤其是它废除了流程线，整个算法结构是由各个基本结构按顺序组成的，N--S流程图中的上下顺序就是执行时的顺序。共33页第24页三种基本程序结构的N–S流程图条件TF语句1语句22.选择结构语句1语句21.顺序结构3.循环结构循环体循环体当满足条件时直到条件成立循环结构一循环结构二共33页第25页0t,0ii+1it+it直到i100输出t的值传统流程图与N-S流程图的比较i100NY开始0t,0ii+1it+it输出t的值结束例1：1+2+3+……+加到100为止共33页第26页例：打印50名学生中成绩高于80分的学号和成绩用N--S图表示。共33页第27页1.枚举法（穷举法）特点:算法简单，容易理解，运算量大。基本思想：根据题目的部分条件确定答案的大致范围，然后在此范围内对所有可能的情况逐一验证，直到所有情况均通过验证。若某个情况符合题目条件，则为本题的一个答案；若全部情况验证完后均不符合题目的条件，则问题无解。如：百元买百鸡问题。假定小鸡每只0.5元，公鸡每只2元，母鸡每只3元。现在有100元钱要求买100只鸡，问共有几种购鸡方案？根据题目，设母鸡、公鸡、小鸡各为x,y,z只，列出方程为：x+y+z=100，3x+2y+0.5z=100利用穷举法，将各种可能的组合一一测试，输出符合条件的组合。即在各个变量的取值范围内不断变化x,y,z的值，穷举x,y,z全部可能的组合，若满足方程组则是一组解。1.3几种常用算法介绍共33页第28页#includestdio.hmain(){intx,y,z;printf(母鸡公鸡小鸡);for(x=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);}}百元买百鸡程序：共33页第29页2.递推法（迭代法）基本思想：利用问题本身所具有的某种递推关系求解问题。从初值出发，归纳出新值与旧值间直到最后值为止存在的关系，从而把一个复杂的计算过程转换为简单过程的多次重复，每次重复都从旧值的基础上递推出新值，并由新值代替旧值。如：猴子吃桃子问题，求高次方程的近似解问题。共33页第30页例：小猴吃桃子问题。小猴在一天内摘了若干个桃子，当天吃掉一半多一个；第二天吃掉剩下的一半桃子多一个；以后每天都吃尚存桃子的一半零一个。直到第7天早上要吃时，只剩下一个了，问小猴共摘了多少个桃子？问题分析：先从最后一天推出倒数第二天的桃子，再从倒数第二天推出倒数第三天的桃子，……设第n天的桃子为x,它是前一天的桃子数的一半少一个，即xn=xn-1-1前一天的桃子数为：xn-1=(xn+1)×2(递推公式）程序示例21共33页第31页#includestdio.hmain(){inti,x;x=1;printf(第7天的桃子数为：1只\n);for(i=6;i=1;i--){x=(x+1)*2;printf(第%d天的桃子数为：%d只,i,x);printf(\n);}}小猴吃桃子源程序：共33页第32页3.求最大值、最小值问题采用如同打擂台的方法。在n个数中，先假设第一个数为最大值，成为擂主，依次同第2，3，……n个数据逐一比较，一旦某个数大，马上替换擂主；所有值比较完，最大值也就获得。求最小值问题则先假设第一个数为最小值。如对输入的若干个学生成绩，求出最高分。共33页第33页1.4结构化程序设计方法结构化程序设计方法是公认的面向过程编程应遵循的基本方法和原则。结构化程序设计方法主要包括：①只采用三种基本的程序控制结构来编制程序，从而使程序具有良好的结构；②程序设计自顶而下；③用结构化程序设计流程图表示算法。