第一章 程序设计基础知识

C语言程序设计A主讲教师：李凤英联系方式：[e-mail]第一章程序设计基础知识1.1程序与程序语言1.1.1语言1、计算机语言是人与计算机进行交流的方式，有其符合数学规范的单词、句子和含义的定义。2、语言的发展第一代：机器语言——二进制代码，计算机母语第二代：汇编语言——用符号表示的计算机指令——面向计算机的语言第三代：高级语言——采用完全符号化的描述，用类似自然语言的形式来描述对问题的处理过程，用数学表达式的形式来描述对数据的处理过程，Pascal,C等，要求人告诉计算机怎样做，——面向过程的语言第四代：非结构化语言——VisualC++，Delphi，VB,C++Build,C#,JAVA等。要求人告诉计算机做什么，——面向对象的语言第五代：智能化语言——PROLOG面向过程的语言是程序设计的基础1.1.2程序设计1程序计算机是一种具有内部存储能力的自动、高效的电子设备，其本质的使命就是执行指令所规定的操作。程序＝{指令}，是用计算机语言来对所要解决问题中数据以及处理问题的方法和步骤所做的完整而准确的描述。——这个描述过程称为程序设计程序=算法+语言+数据结构语言工具和环境1/4时间具体步骤、设计方法3/4时间*程序设计如同建房子=设计图纸+具体施工+材料2程序设计步骤⑴分析问题，建立数学模型将解题过程归纳为一系列的数学表达式⑵确定数据结构和算法确定存放数据的内部结构，解决问题的方法和步骤⑶编制程序用某种计算机语言把问题的解决方案严格的书写出来。⑷调试程序在计算机上用实际的输入数据对编好的程序进行测试。3程序涉及方面数据结构、算法、编程语言和程序设计方法1.2算法和算法的表示1.2.1算法的概念1算法是为解决一个特定的问题所采取的确定的有限的步骤。例1：解数学题——解题的计算步骤和过程。例2：演唱歌曲——歌谱，它规定了歌唱家如何唱歌，先唱什么，后唱什么，唱什么音阶，什么音符……。例3：制作写字台——加工顺序：从桌腿→桌面→抽屉→组装的过程。2计算机算法告诉计算机如何一步步进行操作，直至解决问题的具体步骤。包含：数值计算和非数值计算3设计算法的思维方法例1—1有黑和蓝两个墨水瓶，但却错把黑墨水装在了蓝墨水瓶子里，而蓝墨水错装在了黑墨水瓶子里，要求将其互换。算法分析：这是一个非数值运算问题。因为两个瓶子的墨水不能直接交换，所以一问题的关键是需要引入第三个墨水瓶。设第三个墨水瓶为白色，其交换步骤如下：①将黑瓶中的蓝墨水装人白瓶中；②将蓝瓶中的黑墨水装入黑瓶中；③将白瓶中的蓝墨水装入蓝瓶中；④交换结束。M(x)=bx+a2x≦aa(c–x)+c2xa(a，b，c为常数)算法分析：本题是—个数值运算问题。其中M代表要计算的函数值式，根据x的取值决定采用哪一个算式。根据计算机具有逻辑判断的基本的算法如下：①将a、b、c和x的值输入到计算机；②判断x≦a？，如果条件成立执行第③步，否则执行第④步；③按表达式bx＋a2计算出M(x)结果，然后执行第⑤步；④按表达式a(c–x)+c2计算出M(x)结果，然后执行第⑤步；⑤输出M(x)的值；⑥算法结束。例1—2计算函数M(x)的值。函数M(x)为：假设每天有an(n=1…10)只桃子，而我们可以看出，a1,a2,..，a10之间存在一个简单的关系：a9=2*(a10+1)a8=2*(a9+1)┇a1=2*(a2+1)也就是：ai=2*(ai+1+1)(i=9,8,7,6,...,1)这就是此题的数学模型。再考察上面从a9，a8直至a1的计算过程，这其实是一个递推过程，这种递推的方法在计算机解题中经常用到。另一方面，这九步运算从形式上完全一样，不同的只是ai的下标而已。[例]猴子吃桃问题：有一堆桃子不知数目，猴子第一天吃掉一半，觉得不过瘾，又多吃了一只，第二天照此办理，吃掉剩下桃子的一半另加一个，天天如此，到第十天早上，猴子发现只剩一只桃子了，问这堆桃子原来有多少个？由此，我们引入循环的处理方法，并统一用a0表示前一天的桃子数，a1表示后一天的桃子数，将算法改写如下：1)a1=1;｛第10天的桃子数，a1的初值｝i=9。｛计数器初值为9｝2)a0=2*(a1+1)。｛计算当天的桃子数｝3)a1=a0。｛将当天的桃子数作为下一次计算的初值｝4)i=i-1。5)若i=1，转2)。6)输出a0的值。其中2)～5)步循环执行9次。这就是一个从具体到抽象的过程，具体方法是：1)弄清如果由人来做，应该采取哪些步骤。2)对这些步骤进行归纳整理，抽象出数学模型。3)对其中的重复步骤，通过使用相同变量等方式求得形式的统一，然后简练地用循环解决。算法可以描述如下：①将两个正整数存放到变量m和n中，保证m不小于n；②求余数：计算m除以n，将所得余数存放到变量r中；③判断余数是否为0：若余数为0则执行第⑤步，否则执行第④步：④更新被除数和余数：将n的储存放到m中，将r的值存放到n中，并转向第②步继续循环执行；⑤输出n的当前值，算法结束。…商nrm余数→除数→被除数若r不为0若r＝0，前个非0的r即是例：设m＝35，n＝1521553530①则：最大公约数为53501515②例1—3给定两个正整数m和n(m≧n)，求它们的最大公约数。算法分析：用辗转相除法(也称欧几里德算法)求解。总结一个算法由若干个操作步骤构成，并且这些操作是按一定的控制结构所规定的次序执行。4．算法的两要素4.1两要素：基本功能操作+控制结构4.2计算机的基本功能操作包括以下四个方面：(1)逻辑运算：与、或、非；(2)算术运算：加、减、乘、除；(3)数据比较：大于、小于、等于、不等于、大于等于、小于等于(4)数据传送：输入、输出、赋值。4.3算法的控制结构决定了算法的执行顺序，包括：顺序结构、分支结构、循环结构。1.2.2算法的基本特征(1)有穷性：一个算法必须在执行有限个操作步骤后终止；(2)确定性：算法中每一步的含义必须是确切的，不可出现任何二义性；(3)有效性：算法中的每一步操作都应该能有效执行，一个不可执行的操作是无效的，如一个数被0除的操作就是无效的，应避免。(4)有零个或多个输入：这里的输入是指在算法开始之前所需要的初始数据。例如，例l—1的算法中有2个输入，即需要输人a和b两个初始数据，而例1—2的算法中则需要输入四个初始数据。有些特殊算法也可以没有输入。(5)有一个或多个输出：所谓输出是指与输入有某种特定关系的量，在一个完整的算法中至少会有一个输出。如上述三个例子中都有输出。试想若例1—3中没有“输出n的当前值”这一步，则该算法将毫无意义。1.2.3算法的表示原则上说，算法可以用任何形式的语言和符号来描述．通常有自然语言、程序语言、流程图、NS图、PAD团、伪代码等。第一节中的三个例子就是用自然语言来表示算法，流程图是最早提出的用图形表示算法的工具，具有直观性强、便于阅读等特点；NS图和PAD图符合结构化程序设计要求，是软件工程中强调使用的图形工具。1．流程图符号由美国国家标准化协会ANSI规定了一些常用的符号．(b)注释框：表示对算法中的某操作或某部分操作所作的必要的备注说明。(a)流程线：表示算法的执行方向或或(c)连接点：表示不同地方的流程图的连接。(d)起止框：用以表示算法的开始或结束。(e)输入／输出框：表示算法的输入和输出操作。(f)处理框：算法中各种计算和赋值的操作均以处理框加以表示。(g)判断框：表示算法中的条件判断操作。2．用流程图表示算法例1－1例1－2例1－31.2.4几种常用算法介绍1．枚举法（穷举法）首先根据问题的部分条件预估答案的范围，然后在此范围内对所有可能的情况进行逐一验证，直到全部情况均通过了验证为止。若某个情况使验证符合题目的全部条件，则该情况为本题的一个答案；若全部情况验证结果均不符合题目的全部条件，则说明该题无答案。例题1--4．鸡翁—，值钱五；母鸡一，值钱三；雏鸡三，值钱一；百钱买百鸡，翁、母、雏各几何？这就是列方程：x十Y十z＝1005x十3Y十z/3＝100据题意可知，x,y,z的范围一定是0到100的正整数，则最简单的解题方法是假设一组x,y,z值，直接带入方程组求解，即在各个变量的取值范围内不断变化x,y,z全部可能的组合，若满足方程组则是一组解。利用枚举法解题需要以下步骤：(1)分析题目，确定答案的大致范围。(2)确定列举方法。常用的列举方法有：顺序列举，排列列举和组合列举。(3)作试验，直到遍历所有情况。(4)试验完后可能找到与题目要求完全一致的一组或多组答案，也可能没找到答案，即证明题目无答案。枚举法的特点是算法简单，容易理解，但运算量较大。对于可确定取值范围但又找不到其它更好的算法时，就可以用枚举法。通常枚举法用来解决“有几种组合”、“是否存在”、求解不定方程等类型的问题。利用枚举法设计算法大多以循环控制结构实现。2．迭代法是一种数值近似求解的方法，特点是：把一个复杂问题的求解过程转化为相对简单的迭代算式，然后重复执行这个简单的算式，直到得到最终解。迭代法有精确迭代法和近似迭代法。所谓精确选代是指算法本身提供了问题的精确解；如对N个数求和、求均值、求方差等，这些问题都适合使用精确迭代法解决。例l—5计算s=1十2+3+4十……+100其迭代方法如下：首先确定迭代变量s的初始值为0；其次确定迭代公式s+i→s；当i分别取值1,2,3,4,…,100时，重复计算迭代公式s+i→s，迭代100次后，即可求出s的精确值。流程图表示见书P11页迭代法通常用于数值运算的求解问题3．递推和递归法这是程序设计中常用的两种算法，都是利用某些公式的递推性。最常见的例子是计算级数，—般给出数列后项与前项的递推公式，要求计算数列通项。例如：(1)f1(n)=2+fl(n-1)，f1(1)＝1f1(n)＝{1．3，5，7，…}——这是首项为l公差为2的等差数列(等差级数)。(2)f2(n)＝2×f2(n-1)，f2(1)＝1——这是首项为1公比为2的等比数列。(3)f3(n)＝n×f3(n-1)，f3(1)=1——这个数列的通项f3(n)＝n！。(4)f4(n)=f4(n-1)+f4(n-2)，f4(1)=1，f4(2)=1;——这就是有名的斐波那契数列。特点：在数列的未知项与已知项之间存在着一定关系，借助于已知项和这一关系，就可逐项求出未知项。计算数列通常用递推和递归两种算法。①递推法：是指利用递推公式，由简到繁逐次迭代求解。例1—7求n!设n=15。∵n!＝1×2×……×n，其算法存在如下递推过程：f(0)＝0!＝lf(1)＝1!=1×0!=1f(2)＝2!＝2×1!＝2f(3)＝3!=3×2!=6……f(n)＝n!=n×(n-1)!=n×f(n-1)结论：递推法的关键是找到进行递推的通项公式②递归法：利用递推公式，由繁化简，用简单的问题和已知的操作运算来解决复杂的问题。例求n!f(1)＝lf(n)＝f(n-1)×n将所一个式子从n到n-1、再到n-2逐步递推化简得到：f(n)＝f(n-1)×n＝f(n-2)×(n-1)×n=…=f(1)×2×3×…×n(n＞1)每次化简，自变量减1，但要多乘一个因子，在化简的每一步，f(n-1),f(n-2),…等仍为未知量，直到化简为f(1)，因f(1)已知，f(n)便可由一个式子求乘法得到，这个计算算过程不是直接的，它包含两个过程：⑴由繁到简的递推化简；⑵由已知值f(1)经乘法运算回归到所求值。递归特征：如果一个过程直接或间接地有限次数地调用了它自身，则称这个该过程是递归的。其关键是必须有一个递归终止条件，即要有递归出口。③递归与递推的对比⑴递推是从已知的初始条件出发，逐次递推出最后所求的值，一般可利用循环结构实现，比较简单。⑵递归是从需要求解的函数本身出发，逐次上溯调用其本身的求解过程，直到递归的出口，然后再从里向外倒推回来，得到最终的值。它要求语言具有反复自我调用于程序的能力（用递归子程序实现）。⑶一般说来，一个递推算法总可以转换为—个递归算法。4．分治法在求解一个复杂问题时，应尽可能地把这个问题分解为较小部分，找出各