第1章算法与C语言概述

1,第1章算法与C语言概述,程序设计的基本概念算法C语言概述,2,11程序设计的基本概念,程序设计的基本步骤与程序设计语言程序设计方法,111程序设计的基本步骤与程序设计语言,1程序与计算机程序程序就是对一系列操作过程的描述。例11求解一元二次方程。步骤1：为计算机提供一元二次方程的三个系数；步骤2：用数学公式计算方程的第一个解；步骤3：用数学公式计算方程的第二个解；步骤4：输出方程的两个解；步骤5：程序结束。为求解一个计算任务，我们会告诉计算机按照特定操作顺序完成一系列的指令，这一系列指令的集合就是计算机程序。,111程序设计的基本步骤与程序设计语言,2程序设计的基本步骤分析问题设计算法编写程序运行程序分析结果编写文档,111程序设计的基本步骤与程序设计语言,3程序设计语言（1）第一代机器语言机器语言就是由二进制0、1代码形式构成的指令。不同的计算机系统具有不同的指令系统。如PC机中，表示相加运算的指令代码就是01001。,111程序设计的基本步骤与程序设计语言,3程序设计语言（2）第二代汇编语言汇编语言中的语句就是机器指令的符号化形式。即用十进制数据和英文缩写词来取代二进制形式的机器指令。例如：指令代码01001可改写成ADD二进制数据1001可改写成9计算机不能直接识别汇编语言中的语句，需要翻译成二进制形式的机器指令。这种翻译一般称为“汇编”，所用软件称为“汇编程序”。,111程序设计的基本步骤与程序设计语言,3程序设计语言（3）第三代高级语言高级语言是面向用户的、独立于计算机硬件的编程语言。计算机不能直接识别高级语言中的语句，需要翻译成二进制形式的机器指令。这种翻译一般分为称为“编译”和“解释”两种方式。所用软件称为“编译程序”和“解释程序”，如图所示。,111程序设计的基本步骤与程序设计语言,3程序设计语言（4）第四代非过程化语言使用非过程化语言编程时只需告诉计算机“做什么”而不是“怎样做”即不需要描述算法实现的细节,112程序设计方法,1结构化程序设计方法（1）结构化程序设计原则自顶向下逐步细化模块化限制使用goto语句（2）三种基本结构顺序结构选择结构循环结构顺序结构表示程序中的各操作是按照它们出现的先后顺序执行的。,112程序设计方法,1结构化程序设计方法选择结构对于要先做判断后进行选择的问题就要使用选择结构。选择结构分为三种形式：单分支选择双分支选择多选择分支,112程序设计方法,1结构化程序设计方法循环结构分为两种形式：当型循环直到型循环当型循环表示先进行条件判断，当满足给定的条件后才执行循环体，并且在循环终端处流程自动返回到循环入口处；如果条件不满足，则退出循环体直接到达循环出口处。直到型循环表示从循环入口处直接执行循环体，在循环终端处判断条件。如果条件不满足，返回入口处继续执行循环体，直到条件为真时再退出循环到达循环出口处，是先执行循环后进行条件判断。,112程序设计方法,1结构化程序设计方法（3）结构化程序特点结构内不存在死循环每种结构都有且仅有一个入口每种结构都有且仅有一个出口结构内的每一部分都有机会被执行到2面向对象程序设计方法例12从键盘输入数据n，计算其对应的平方根。intn;floatresult;scanf(%d,112程序设计方法,2面向对象程序设计方法（1）对象在现实世界中，对象就是我们认识世界的基本单元。它可以是人，也可以是物，还可以是一件事。对象作为现实世界中的一个实体，主要特性如下：每一个对象必须有一个标记名称以便区别于其它对象。用状态或属性可以描述对象具有的特征。对象含有一组操作，每个操作都决定对象的一种行为。对象操作与对象属性是不可分离的。（2）类就是对一组具有共同的属性特征和行为特征的对象所进行的抽象，类和对象之间的关系是抽象和具体的关系。,112程序设计方法,1结构化程序设计方法（1）结构化程序设计原则自顶向下逐步细化模块化限制使用goto语句（2）三种基本结构顺序结构选择结构循环结构顺序结构表示程序中的各操作是按照它们出现的先后顺序执行的。,112程序设计方法,2面向对象程序设计方法表11学生类中的一个对象实例对象状态：对象的状态是全部静态属性的动态值集合。,112程序设计方法,2面向对象程序设计方法（4）对象特征模块性继承性动态链接易维护性封装性,17,12算法,121算法的概述122算法的表示123常用算法的简介人类求解问题的两种方式：推理方式算法方式,121算法的概述,算法：一个有穷规则的集合，其规则规定一个解决某一特定类型问题的操作序列。算法特征：有穷性确定性输入项输出项有效性,122算法的表示,1使用自然语言描述算法例14使用自然语言描述：12399100。求解方法：使用循环结构来表示100次相加运算。其中，使用两个变量sum和n，变量sum表示累和变量，初始值为0，每次加一个“加数”；变量n表示“加数”，初始值为1，取值范围是1至101，为累和变量sum准备数据，而变量n的值为101时退出循环。步骤1：假设sum的初值为0；步骤2：假设n的初值为1；步骤3：如果n100时，则执行步骤4，否则转出执行步骤7；步骤4：计算sum加i的值后，重新赋值给sum；步骤5：计算n加1的值后，重新赋值给n；步骤6：转去执行步骤3；步骤7：输出sum的值；步骤8：算法结束。,122算法的表示,2使用传统流程图描述算法圆角矩形表示算法的“开始”和“结束”；平行四边形表示输入操作和输出操作。菱形表示表示条件判断；直角矩形表示算法中的具体操作；箭头表示算法的操作流程；圆圈表示连接其它流程图符号，具有汇合的功能。,122算法的表示,2使用传统流程图描述算法传统流程图有如下三类共5种。顺序结构如图1-4所示。选择结构如图1-5所示。,122算法的表示,2使用传统流程图描述算法循环结构如图1-6所示。,122算法的表示,2使用传统流程图描述算法传统流程图的主要优点：形象直观，各种操作容易理解，也不会产生二义或歧义性算法出错时容易发现并修改。传统流程图的主要缺点：所占篇幅较大且不易绘制，由于使用流程线导致算法过于灵活，不受阻挠限制，常使流程转向混乱，最终造成程序的阅读和修改困难，更不利于结构化程序的具体实现。,122算法的表示,2使用传统流程图描述算法例15使用传统流程图描述：12399100。,122算法的表示,3使用NS流程图描述算法顺序结构如图1-8所示。选择结构如图1-9所示。,122算法的表示,3使用NS流程图描述算法循环结构如图1-10所示。,122算法的表示,3使用NS流程图描述算法NS流程图的主要优点：简单且易学易用，具有较好的可读度，尤其适合描述循环和条件结构的算法。另外，NS流程图的设计意图易理解，从而为编程、查错、选择测试用例、软件维护等提供方便。NS流程图的主要缺点：不容易进行手工修改，在嵌套过多时不容易绘制。例16使用NS流程图描述：12399100。,122算法的表示,4使用伪代码描述算法例17使用伪代码描述累和算法：12399100。算法描述如下：beginsum=0n=1while(n=100)sum=sum+nn=n+1printsumend,122算法的表示,3使用NS流程图描述算法例18两个变量内容的交换.。求解方法：使用三个变量a，b，t，其中变量a和b的值由键盘输入，变量t作为暂存单元，通过三次赋值操作完成交换。画出NS流程图：,122算法的表示,3使用NS流程图描述算法例19取绝对值。求解方法：使用一个变量n，并选择结构来进行判断。若变量n的值大于0，则输出n的值，否则输出n的值。画出NS流程图：,122算法的表示,3使用NS流程图描述算法例110计算10!。求解方法：使用循环结构来表示10次相乗运算。其中，使用两个变量f和n，变量f表示累乗变量，初始值为1，每次乗一个“乗数”；变量n表示“乗数”，初始值为1，取值范围是1至11，为累乗变量f准备数据，而变量n的值为11时退出循环。画出NS流程图：,122算法的表示,3使用NS流程图描述算法例111求裴波纳契数列中的前10个数据。斐波那契数列是指：0、1、1、2、3、5、8、13、21、34，数学定义如下：F（0）0F（1）1F（n）F（n-1）F（n2）（n2）求解方法：使用循环结构和迭代算法。其中，循环控制变量k从2至10取值，在取值为2至9时求裴波纳契数，取值为10时结束循环；另外三个变量为f1，f2，f，其中f1的初始值为0，f2的初始值为1，f的值是f1和f2的和，迭代过程如下：f=f1+f2，f1=f2，f2=f,122算法的表示,3使用NS流程图描述算法例111求裴波纳契数列中的前10个数据。画出NS流程图：,122算法的表示,3使用NS流程图描述算法例112求两个正整数的最大公约数。求解方法：最大公约数就是两个正整数共有约数中最大的一个，下面介绍欧几里德算法（又称为辗转相除法），其主要操作如下：步骤1：输入两个正整数，并放入变量m和n中；步骤2：求出m除以n的余数放入变量r中；步骤3：如果r为0，则执行步骤7，否则执行步骤4；步骤4：操作m=n，n=r；步骤5：求出m除以n的余数放入变量r中；步骤6：执行步骤3；步骤7：n就是所求的结果，输出结果。,122算法的表示,3使用NS流程图描述算法例112求两个正整数的最大公约数。画出NS流程图：,122算法的表示,例113判断素数。素数是一个大于1的自然数，除了1和它本身外，不能被其他自然数整除，换言之就是素数除了1和它本身以外不再有其他的因数。求解方法：由键盘输入一个大于1的自然数n,，使用一个变量k，其取值范围从2至n1，用循环结构来判断所有的k值是否是n的因数。若有因数，则输出不是素数的信息，并结束算法；若没有因数，则输出是素数的信息。,122算法的表示,例113判断素数。画出NS流程图：,38,13C语言概述,131C语言的发展及特点132C语言程序的构成及程序的书写格式123程序调试步骤134用VC系统实现C程序的操作过程,131C语言的发展及特点,1C语言的发展过程表12C语言标准,131C语言的发展及特点,2C语言的主要特点简洁紧凑、灵活方便运算符丰富数据类型丰富运算表达方式多样允许访问物理地址并控制硬件目标代码质量高可移植性好表达力强,132C语言程序的构成及程序书写格式,1C语言程序示例例114求解一个一元二次方程。#include#includeintmain()floata,b,c;floatx1,x2;scanf(%f,%f,%f,132C语言程序的构成及程序书写格式,例115编写函数计算12399100。#includeintmain()ints(intm);intm=100;printf(sum=%dn,s(m);return0;ints(intm)intsum=0;intn=1;while(n=m)sum=sum+n;n=n+1;returnsum;,132C语言程序的构成及程序书写格式,2C语言程序的构成（1）C语言属于函数式语言，即程序由函数构成，为非常适合程序的结构化描述。C程序中的函数共有三种类型，如表13所示。表13函数分类,132C语言程序的构成及程序书写格式,2C语言程序的构成（2）函数构成一个函数由两部分构成，即：声明部分和函数体。函数说明部分包括四部分：函数类型（返回值的类型）函数名函数参数参数类型函数体是由花括号包围起来的部分，以表示函数的操作，其中包含变量定义和操作描述两部分。,132C语言程序的构成及程序书写格式,2C语言程序的构成（2）函数构成例115函数构成示例。intmax(x,y)/声明部分/函数体开始intx,y;/变量定义/操作描述/函数体结束说明：任何C程序都是从main()处开始执行的。C程序书写格式自由。语句和变量定义的后而必须使用分号表示结束。C程序使用函数调用来实现进行输入输出，如scanf()。C语言用/或/*/做注释。,132C语言程序的构成及程序书写格式,3C程序的书写要求说明：一个变量定义或语句最好占用一行。由花括号包围起来的部分可表示程序的某层结构，最好使用缩进书写，将相关语句按层次排列成左对齐。低层次的语句要比高层次的语句缩进若干空格后对齐书写，以便看起来直观清晰，增加程序可读性。,133程序调试步骤,输入程序编译程序连接程序运行程序,134用VC系统实现C程序的操作过程,（1）新建源程序文件进入VC窗口后，选择“文件”菜单中的“新建”命令。,134用VC系统实现C程序的操作过程,（2）指定文件类型选择“文件”标签中的“C+SourceFile”选项。将文件存到D盘，并指定合理的文件名如P21.cpp。,134用VC系统实现C程序的操作过程,（3）编译源程