计算机基础第6章程序设计基础.ppt
计算机基础,第一章 概述第二章 数据在计算机内的表示 第三章 计算机硬件第四章 操作系统和文件管理 第五章 多媒体技术基础 第六章 程序设计基础第七章 信息系统概述第八章 计算机网络基础知识 第九章 计算机安全,计算机基础,第六章 程序设计基础 第一节 程序与程序语言 第二节 算法与算法设计 第三节 程序设计风格,第六章 程序设计基础,程序和软件有何不同?,第六章 程序设计基础,第一节 程序与程序语言,10 R=520 L=2*3.14*R30 S=3.14*R*R40 PRINT R,L,S50 END,软件,程序,语言,语言规则,计算机语言是编写程序、制作软件的工具,4,计算机程序中规定了计算机完成某项工作的操作步骤,每一步骤均由计算机能理解的指令或语句描述,这些指令和语句告诉计算机“做什么”和“怎样做”。,程序是处理某个事物的一系列操作步骤。,一、程序概述,10 R=520 L=2*3.14*R30 S=3.14*R*R40 PRINT R,L,S50 END,第六章 程序设计基础,第一节 程序与程序语言,5,程序=数据结构+算法,编写程序需要两个方面的描述:,数据结构 对数据的描述:指定适合问题求解的数据组成形式(数据类型)。例如,计算圆面积公式:s=r2 s不能为整数,而是实数。算法 对操作的描述:指定操作的步骤。1。输入r的值 2。按s=3.14*r*r计算圆面积,第六章 程序设计基础,第一节 程序与程序语言,6,二、程序设计,程序设计数据结构算法方法工具,数据结构:数据组织形式。对求解问题的数据的描述,影响程序的复杂程度。算法:解题步骤。对求解问题的过程描述。决定程序的正确性和解题效率。程序设计方法:能编写“好”程序的方法。程序设计工具:可改善设计环境,方便和加快程序开发过程的开发工具。,第六章 程序设计基础,第一节 程序与程序语言,三、程序设计语言,面向过程语言面向对象语言,FORTRANBASICCPASCALCOBOLLISP,C+C#Visual CVisual BASICVisual J+,第六章 程序设计基础,第一节 程序与程序语言,程序设计语言是规则和符号的集合,用于编写计算机程序的语言,包含语法、语义和语用三个方面。程序设计语言的基本成分有:数据成分,用于描述程序所涉及的数据;运算成分,用以描述程序中所包含的运算;控制成分,用以描述程序中所包含的控制;传输成分,用以表达程序中数据的传输,第六章 程序设计基础,第一节 程序与程序语言,计算机语言:是规则和符号的集合,是与计算机交流的工具程序:求解问题的指令序列软件:程序的集合,学习语言 设计程序 制作软件,概念:,第六章 程序设计基础,第一节 程序与程序语言,10,第一代:机器语言(2进制机器指令,机器能直接执行)第二代:汇编语言(符号代替机器语言,需要翻译)第三代:高级语言(英语和数学语言代替机器语言,需要翻译),第六章 程序设计基础,第一节 程序与程序语言,程序设计语言的发展,11,机器语言(Machine Languages):由计算机直接使用的二进制编码指令构成的语言。提供最基本的计算机操作-加、减、比较、搬移操作数等。-每种计算机都有自己专用的机器指令集合。-计算机唯一理解的语言是机器语言。-机器语言的指令必须由“0”和“1”的字符串组成,因为组成计算机内部电路的电子器件只有两种状态:关或开。关“0”、开”1”。,第六章 程序设计基础,第一节 程序与程序语言,00000000 1011100000000000 0010010100000000 0000010100000000 01010100,A=37+84,机器语言 二进制机器指令,机器能直接执行。,送数到AX寄存器被加数 37加法加数 84,第六章 程序设计基础,第一节 程序与程序语言,13,符号/汇编语言(Symbolic/Assembly language)用符号或助记符表示不同的机器语言指令。-需要使用汇编程序将助记符翻译成等价的机器语言。-每种类型的计算机都有自己的机器语言,所以有多少种机器,就有多少种汇编语言和翻译程序。,第六章 程序设计基础,第一节 程序与程序语言,MOV AX,37 送数37到AX寄存器 ADD AX,84 AX寄存器内容+84送到寄存器AX,汇编语言 用符号代替机器语言,需要翻译。,A=37+84,第六章 程序设计基础,第一节 程序与程序语言,15,高级语言(High-level languages):高级程序设计语言与人类的思维和交流方式更接近。使用高级语言,程序设计员就能够用类似于英语的语句编写指令。-由于计算机只能执行机器码,所以需要翻译程序把用高级语言编写的程序翻译成机器码。-高级语言适用于许多不同的计算机。,第六章 程序设计基础,第一节 程序与程序语言,A=37+84,高级语言 英语和数学语言代替机器语言,需要翻译。,第六章 程序设计基础,第一节 程序与程序语言,17,语言的翻译器(Language Translator):将汇编语言或高级语言翻译成机器码的程序。-三种类型的翻译器:汇编器 编译器 解释器,汇编或高级语言编写的程序,机器码程序,翻译器,第六章 程序设计基础,第一节 程序与程序语言,18,高级语言程序的运行过程,高级语言源程序,机器语言,翻 译,解释器:针对解释式程序设计语言,使用边解释边执行的方式。,编译器:将源程序代码全部转换成计算机能识别的目标代码,连接成可执行程序后,可反复执行。,第六章 程序设计基础,第一节 程序与程序语言,第六章 程序设计基础,第一节 程序与程序语言,20,C语言中的编译、连接,编译命令,连接命令,第六章 程序设计基础,第一节 程序与程序语言,四、程序设计全过程,分析问题,建立数学模型确定数据结构确定算法,描述算法编制程序,调试程序运行结果,第六章 程序设计基础,第一节 程序与程序语言,程序设计过程:,语言处理系统,第六章 程序设计基础,第一节 程序与程序语言,23,分析问题,建立模型,问题:输入三角形的三条边,输出三角形的面积。,分析:若输入的三条边a,b,c能构成三角形,则计算三角形面积area的公式为:,第六章 程序设计基础,第一节 程序与程序语言,24,确定数据结构和算法,数据结构:三角形的边长a,b,c和面积area均采用实数,算法:1.输入三角形的三条边a,b,c 2.计算s=0.5*(a+b+c)3.计算面积 4.输出三角形面积area,第六章 程序设计基础,第一节 程序与程序语言,第六章 程序设计基础,第一节 程序与程序语言,26,选择语言编制程序,main()/*用C语言编写程序*/float a,b,c,s,area;/*定义三角形边长和面积为实型变量*/scanf(“%f,%f,%f”,/*输出三角形的三条边和面积*/,平方根函数,第六章 程序设计基础,第一节 程序与程序语言,27,上机调试运行程序,第六章 程序设计基础,第一节 程序与程序语言,28,两次运行结果:,第六章 程序设计基础,第一节 程序与程序语言,计算机基础,第六章 程序设计基础 第一节 程序与程序语言 第二节 算法与算法设计 第三节 程序设计风格,第六章 程序设计基础,一、什么是算法,算法是为解决问题而采取的方法和步骤。,决定了算法的执行顺序,算术运算、逻辑运算、比较运算和数据传送,第六章 程序设计基础,第二节 算法与算法设计,31,例:从一组正整数中找到最大的数。(正整数个数2,3,N),例如,12,8;12,8,13;12,8,13,9;12,8,13,9,11,.,方法1:第一步:比较第一个数和第二个数;第二步:比较第一个数和第三个数;第三步:比较第二个数和第三个数;,这个方法好吗?,第六章 程序设计基础,第二节 算法与算法设计,32,方法2:第零步:将最大值置为零;第一步:如果当前数大于最大值,那么将最大值置为当前数,否则保留原最大值;第二步:重复第一步直至所有数全比较完。,Best!,第六章 程序设计基础,第二节 算法与算法设计,举例:插入排序法问题,有一个从小到大的数值序列,将一个新数插入到序列中。,24,?,6.2算法与算法设计,第六章 程序设计基础,12,19,26,37,48,5,9,24,24,举例:插入排序法问题,有一个从小到大的数值序列,将一个新数插入到序列中。,24,24,24,24,24,6.2算法与算法设计,第六章 程序设计基础,算法:开始 i=1 新数与序列第i个元素比较 如果(新数比第i个元素大)i 加 1 如果(i大于m)执行步骤 否则 执行步骤 否则 执行步骤 从第i到第m个元素后移一个位置 将新数置于序列第i个位置 结束,6.2算法与算法设计,第六章 程序设计基础,例如:已知研究生选课情况,安排课程考试的日程,要求在尽可能短的时间内完成考试。,课程之间的关系:同一研究生选修的课程之间有某种“冲突”关系,同一个研究生选修的课程不能按排在同一时间内考试。,6.2算法与算法设计,第六章 程序设计基础,用着色法求解该问题:每门课程作为一个顶点顶点的每一种颜色代表一个考试时间,用尽可能少的颜色为图的顶点着色,着上相同颜色的顶点可以按排在同一时间考试,选课:1:ABE 2:CD 3:CEF 4:DFA 5:BF,A,B,C,D,E,F,6.2算法与算法设计,第六章 程序设计基础,A,B,D,C,E,F,6.2算法与算法设计,第六章 程序设计基础,A,B,D,C,E,F,同一研究生选修的课程用一种颜色的边连接,选课:1:ABE 2:CD 3:CEF 4:DFA 5:BF,使相邻的顶点着上不同的颜色;,A,C,B,D,E,F,6.2算法与算法设计,第六章 程序设计基础,得到如下一种考试日程:第一天:算法分析(A),计算机图形学(C)第二天:形式语言(B),模式识别人工智能(D)第三天:计算机网络(E)第四天:人工智能(F),6.2算法与算法设计,第六章 程序设计基础,二、算法的基本特征,第六章 程序设计基础,第二节 算法与算法设计,算法设计的原则,1、正确性:对于一切合法的输入数据都能得出满足要求的结果。,2、可读性:算法应该易理解,便于交流,3、健壮性:当输入非法数据时,算法应恰当地作出反应或进行相应处理。,4、高效率与低存储量需求:算法执行时间较少,算法执行所需存储空间较小。,第六章 程序设计基础,第二节 算法与算法设计,三、算法的表示,第六章 程序设计基础,第二节 算法与算法设计,自然语言流程图N-S流程图伪代码计算机语言,1.流程图,用规定的一系列图形、流程线和文字说明算法中的基本操作和控制流程。流程图的基本元素包括:表示相应操作的框;带箭头的流程线;框内外必要的文字说明。,第六章 程序设计基础,第二节 算法与算法设计,(1)图形符号,第六章 程序设计基础,第二节 算法与算法设计,(2)用流程图表示算法,例:求给定半径R的圆面积和圆周长。,这是一个数学问题。算法:圆面积 S=*R2圆周长 L=2*R这是顺序程序结构。,顺序,第六章 程序设计基础,第二节 算法与算法设计,例:求给定数R的绝对值。,选择,这是分支程序结构,第六章 程序设计基础,第二节 算法与算法设计,T里保存:1+2+3+K的连加和。重复进行某种运算,运算对象有规律地变化。采用循环结构。,例:给定K值,求1到 K连加和。T=1+2+3+K。1 I 0 T T+I T(I=1,2,3,K),循环,第六章 程序设计基础,第二节 算法与算法设计,2.NS图,由于流程图中的流程线可以任意转向,所以传统流程图无法保证程序的结构化,造成了程序设计中的一系列问题。两位美国学者于1973年提出了表示程序结构的N-S图。,第六章 程序设计基础,第二节 算法与算法设计,(1)图形符号,顺序结构,第六章 程序设计基础,第二节 算法与算法设计,选择结构,第六章 程序设计基础,第二节 算法与算法设计,循环结构:while循环,第六章 程序设计基础,第二节 算法与算法设计,循环结构:do-while循环,第六章 程序设计基础,第二节 算法与算法设计,(2)用N-S流程图表示算法,例:求给定半径R的圆面积和圆周长。,第六章 程序设计基础,第二节 算法与算法设计,选择,例:求给定数R的绝对值。,第六章 程序设计基础,第二节 算法与算法设计,例:给定K值,求T=1+2+3+K。,循环,第六章 程序设计基础,第二节 算法与算法设计,3.伪代码,伪代码是描述算法常用的工具之一;类似英语的表示形式;部分英语和部分结构化代码的组合。,第六章 程序设计基础,第二节 算法与算法设计,伪代码描述算法的一般组成:,算法头:算法的名字。目的、条件和返回值:目的:有关算法要做什么的简短说明 前置条件:列出算法所有前驱条件 后置条件:指出算法产生的影响 返回值:算法返回的结果或无返回值 语句序号:表示语句之间的附属关系。,第六章 程序设计基础,第二节 算法与算法设计,例:用伪代码描述在一数列中找最小值的算法。,Algorithm(算法):Finding SmallestPurpose(目的):在一数列中找最小值Pre(前置条件):List of numbers(数列)Post(后置条件):NoneReturn(返回值):The smallest,3,2,4,1,6,a:,S,3,2,1,算法:设数列中第一个数为最小值S,然后用后续数依次与S比较,若比S小,则用该数替换原S的值,全部比较完成后S即最小值。,第六章 程序设计基础,第二节 算法与算法设计,1.Set smallest to the first number2.Loop(not end of list)2.1 if(next number smallest)2.2.1 set smallest to next number 2.2 end if3.end loop4.return smallestEnd Finding Smallest,第六章 程序设计基础,第二节 算法与算法设计,1.数列ai(i=1,5)2.a1 S,2 i3.while(i5)3.1 if(aiS)then ai S endif 3.2 i+1 i end while 4.return S,伪代码不一定按上述严格的格式,且可以使用汉字,只要把算法表达清楚即可。,第六章 程序设计基础,第二节 算法与算法设计,任何算法都可以由顺序结构、选择结构和循环结构这三种基本结构组合来实现。,四、三种基本结构,第六章 程序设计基础,第二节 算法与算法设计,选择结构,第六章 程序设计基础,第二节 算法与算法设计,循环结构,三种基本结构的特点:一个入口,一个出口,不出现死循环和死语句,第六章 程序设计基础,第二节 算法与算法设计,死循环,死语句,例如:,第六章 程序设计基础,第二节 算法与算法设计,用顺序结构描述将华氏温度F转换成摄氏温度C的流程。算法:C=5/9*(F-32)。,1、顺序结构设计,顺序结构中,按语句的自然顺序依次执行。,第六章 程序设计基础,第二节 算法与算法设计,67,第六章 程序设计基础,第二节 算法与算法设计,用顺序结构描述两个值(a=1,b=2)交换的流程。,1,2,b,a,1,2,1,c,第六章 程序设计基础,第二节 算法与算法设计,69,第六章 程序设计基础,第二节 算法与算法设计,选择结构,又称为分支结构。根据选择结构中判断的结果,选择执行相应的语句。,2、选择结构及其程序设计,用选择结构描述求两个数中的最大值的流程,第六章 程序设计基础,第二节 算法与算法设计,71,第六章 程序设计基础,第二节 算法与算法设计,用选择结构描述检查某年是否闰年的流程。N年为闰年满足下列条件之一:1.N能被400整除2.N能被4整除,但不能被100整除,第六章 程序设计基础,第二节 算法与算法设计,73,第六章 程序设计基础,第二节 算法与算法设计,循环结构,当循环控制条件为真时反复执行循环体中的语句,直到循环控制条件为假时为止。,累加器,计数器,用循环结构描述求10个学生成绩之和的流程。,3、循环结构及其程序设计,用T累计10个学生的成绩(K),用I记录累加的次数(I=1,2,10),第六章 程序设计基础,第二节 算法与算法设计,75,第六章 程序设计基础,第二节 算法与算法设计,用循环结构描述求10到100之间所有不能被3整除的整数的流程,对10到100之间所有数逐一验证,凡满足“不能被3整除”的整数即可输出。,第六章 程序设计基础,第二节 算法与算法设计,77,第六章 程序设计基础,第二节 算法与算法设计,用选择结构描述检查某成绩级别的流程。成绩N的级别:A级-N90B级90N80C级80N60D级N60,第六章 程序设计基础,第二节 算法与算法设计,79,第六章 程序设计基础,第二节 算法与算法设计,循环嵌套结构:一个循环结构的循环体中又出现另一个循环结构。,外循环内循环,I=1,输出1 J=1,输出1I=2,输出2 J=1,输出1 J=2,输出2I=3,输出3 J=1,输出1 J=2,输出2 J=3,输出3,第六章 程序设计基础,第二节 算法与算法设计,在屏幕上显示边长为 m 的正方型要求:从键盘输入 m 值,输出 m 行每行 m 个*号。例:输入 m=4,输出的图形如下:*,算法:1.输入 m 2.重复打印 m 行,每行打印 m 个*,第六章 程序设计基础,第二节 算法与算法设计,输出M行,每行M个*号,第六章 程序设计基础,第二节 算法与算法设计,I=1:J=1 输出*J=2 输出*J=3 输出*J=4 输出*换行I=2:J=1,2,3,4*I=4:J=1,2,3,4*,屏幕显示过程,第六章 程序设计基础,第二节 算法与算法设计,84,第六章 程序设计基础,第二节 算法与算法设计,从键盘输入n值,输出n行用*号组成等腰三角形。例:输入 n=4,输出的图形如下:*,*k=1,n-1=3个空,2*1-1=1个*k=2,n-2=2个空,2*2-1=3个*k=3,n-3=1个空,2*3-1=5个*k=4,n-4=0个空,2*4-1=7个*,共n行,其中第K行由n-k个空格和2k-1个*组成,第六章 程序设计基础,第二节 算法与算法设计,分析:1、输出 n 行。2、图形的第 k 行(1=k=n)由 n-k个空格和 2k-1个*组成。算法设计:1.输入 n;2.外层循环n行。内层循环,每行先输出n-k个空格 再输出2k-1个*换行 内层循环结束 外层循环结束,第六章 程序设计基础,第二节 算法与算法设计,第六章 程序设计基础,第二节 算法与算法设计,88,第六章 程序设计基础,第二节 算法与算法设计,基本思想首先根据问题的部分条件预估计出答案的范围在预估计的答案范围内,对所有可能的情况逐一验证。若某个情况使验证符合题目的全部条件,则该情况是本题目的一个答案。,五、常见算法穷举法,第六章 程序设计基础,第二节 算法与算法设计,分析:假设a、b分别代表父亲和儿子的年龄,x年后a=2b。根据人的寿命,x取值为:1,2,150,问题:今年父亲30岁、儿子6岁,在父亲有生之年中,多少年后父亲的年龄是儿子的2倍?,算法:1.考察x可能的范围:x=1,2,150;2.30+xa,6+xb3.若a=2b,则输出x。,第六章 程序设计基础,第二节 算法与算法设计,X年后,父亲和儿子的年龄,第六章 程序设计基础,第二节 算法与算法设计,92,第六章 程序设计基础,第二节 算法与算法设计,分析:本书从1至5编号。假设a,b两个人分别借这5本书中的1本。当a=i时,表示a借了编号为i的书。则a、b的取值范围为:1=a、b=5。满足题意的一种借阅方法是,2个人所借的书的编号不相同时(a!=b)。,问题:小明有5本新书,要借给、两位小朋友,若每人每次只能借一本,则可有多少种不同的借法?,算法:1.考察a可能的范围:a=1,2,3,4,5;2.考察b可能的范围:b=1,2,3,4,5;3.验证a,b的所有取值,若a!=b,则输出a,b。,第六章 程序设计基础,第二节 算法与算法设计,a=1:b=1 不输出 b=2 输出1,2 b=3 输出1,3 b=4 输出1,4 b=5 输出1,5a=2:b=1 输出2,1 b=2 不输出 b=3 输出2,3 b=4 输出2,4 b=5 输出2,5,第六章 程序设计基础,第二节 算法与算法设计,95,第六章 程序设计基础,第二节 算法与算法设计,例:抓交通肇事犯 一辆卡车违犯交通规则,撞人后逃跑。现场有三人目击事件,但都没有记住车号,只记下车号的一些特征:甲说:牌照的前两位数字是相同的;乙说:牌照的后两位数字是相同的,但与前两位不同;丙是位数学家,说:四位的车号刚好是一个整数的平方。请根据以上线索求出车号。,第六章 程序设计基础,问题分析与算法设计:按照题目的要求造出一个前两位数(i)相同、后两位数(j)相同且相互间又不同的整数。得到:(1)0=31)使用穷举法,尝试i、j的所有可能。,第六章 程序设计基础,循环I取值从1到9 循环J取值从0到9 如果I不等于J 求车牌后四位:I*1000+I*100+J*10+J 如果后四位开方是整数 输出后四位 结束 结束 循环J结束循环I结束,第六章 程序设计基础,第六章 程序设计基础,二、二分法,第六章 程序设计基础,a,b,x1=(a+b)/2,x2,x*,x3,x,用二分法方程的根,例 用二分法求 x3+4x-10=0 在(1,2)内的根,要求绝对误差不超过0.005。解:f(1)=-50-(1,2)+x1=1.5 f(1.5)0(1,1.5)x2=1.25 f(1.25)0(1.25,1.375)x41.313 f(1.313)0(1.360,1.368)x8=1.364,第六章 程序设计基础,输入区间初值:a、b 如果f(a)*f(b)0,则执行 循环 求中点:(a+b)/2 y 如果f(y)*f(a)0,则y a 如果f(y)*f(b)0,则y b 如果|a-b|0.005,执行 循环结束 输出y,第六章 程序设计基础,由初始的已知条件,先计算出第(N1)步的结果,再利用前面已知的(N1)项结果,按照递推公式(或遵照递推规则),推出第N步结果。递推法是程序设计中最常用的方法之一,使用递推法必须有明确的递推初始值和递推公式。,三、递推法,第六章 程序设计基础,例:求菲波那奇数列第N项的值。数列递推通项公式为:1 2 n n-1 n-2(n=3)即:1、1、2、3、5、8、13、21、根据递推通项公式,可用递推法编写程序,计算第N项的值。,第六章 程序设计基础,输入N,1 U1,1 U2,3 I,U1+U2 UU2 U1U U2I+1 I,输出U,N 2,I=N,第六章 程序设计基础,递推算法求10的阶乘。求解过程:0!=1 1!=1*0!2!=2*1!=2 3!=3*2!=6 4!=4*3!=24 5!=5*4!=120 6!=6*5!=720 7!=7*6!=5040 8!=8*7!=40320 9!=9*8!=367880 10!=10*9!=3628800,第六章 程序设计基础,计算机基础,第六章 程序设计基础 第一节 程序与程序语言 第二节 算法与算法设计 第三节 程序设计风格,第六章 程序设计基础,好程序标准:可读性好、可靠性好、可维护性结构化程序设计方法主要包括:1.采用三种基本结构编制程序(结构化程序);2.采用模块化结构(自顶向下,逐步求精);3.尽量不使用无条件转向语句。4.控制结构只有一个入口和一个出口,控制结构之间接口简单,逻辑清晰。5.采用结构化程序设计语言编程,注意程序设计风格,一、结构化程序设计方法,第六章 程序设计基础,第三节 程序设计风格,求:ax2+bx+c=0 的根,二、自顶向下,逐步求精的设计方法,求解的问题可以分成三个小问题(模块):模块M1(输入原始数据);模块M2(求根);模块M3(输出结果)。,1、从顶层考虑模块划分,第六章 程序设计基础,第三节 程序设计风格,2.模块细化,M1模块、M3模块较简单不必细化;M2模块求根,当a=0时,求解一元一次方程,a0时求解一元二次方程。故M2再细化为M21和M22模块。,第六章 程序设计基础,第三节 程序设计风格,M2模块细化,第六章 程序设计基础,第三节 程序设计风格,3.模块集成,a=0,Y,N,X1=-c/b,输出结果,开始,输入数据,结束,M1,M2,M3,d=b2-4ac,d=0,x2=sqrt(d)/(2a),x2=sqrt(-d)/(2a),x1=-b/(2a),Y,N,第六章 程序设计基础,第三节 程序设计风格,源程序文档化 有意义的符号名:FindRoot、JSJKeXue、写好注释:序言性注释、注解性注释 采用缩进格式 数据说明标准化 数据说明的顺序 同类数据排序 对重要数据进行注释,三、编程风格,源程序文档化数据说明标准化语句规范化输入输出格式化,第六章 程序设计基础,第三节 程序设计风格,语句规范化 编程思路不要追求技巧,要直截了当 避免使用临时变量 尽量使用库函数、公共函数 使用括号避免二义性 对不好的程序要重新写,避免反复修改 输入输出格式化 输入格式要简单、自由 对输入数据要进行检验 对输入数据给出必要的提示 输入风格要一致 输出数据要进行注释。,第六章 程序设计基础,第三节 程序设计风格,1.程序与程序设计语言。2.算法与算法设计。3.常见算法。,本章应掌握的内容,计算机基础,