第1章 计算机软件技术基础概论

Click to edit Master title style,Click to edit Master text styles,Second Level,Third Level,Fourth Level,Fifth Level,计算机软件技术基础,孙雪,自动化学院信息自动化教研部,64900511,教学目的和任务：,1,、本课程的任务是在,基础,方面，要求学生掌握常用数据结构的基本概念及其不同的实现方法；在技能方面，通过系统学习能够在不同存储结构上实现不同的运算，并对算法设计的方式和技巧有所体会。,2,、设置本课程的目的在于为后继的专业课打基础，能够使用计算机软件方法解决问题的能力，同时也为从事计算机软件的开发提供基础知识。本课程先修课为,C,语言。,参考教材：,学习教材：,计算机软件技术基础,作者：,李淑芬 等,编著,出版社：机械工作出版社，,2009,年,8,月第一版,参考教材：,数据结构,(C,语言版,),严蔚敏、吴伟民,清华大学出版社,（3）计算机软件基础，孟彩霞编，西安电子科技大学出版社,学时安排（,44,学时）,授课：,38,学时,实验：,6,学时,实验安排,：,7,周、,11,周、,15,周,周三,1-2,节，,实验楼,610,；,4,答疑时间,每周三：,15,：,0016,：,30,；,地点：,北,D3020,室,学习中有问题要及时解决，希望同学们勤于思考，多提问题，这样才能进步。,教学进度安排（,44,学时）,课程介绍（,1,学时）,第一章 计算机软件技术基础概论（,3,学时）,第二章 数据结构概述（,2,学时）,第三章 线性结构（,10,学时,+4,学时实验）,第四章 树（,6,学时）,第六章 查找（,6,学时）,第七章 排序（,8,学时,+2,学时实验）,复习,(2,学时,),课程要求：,教学内容重点分为,1,、掌握数据结构的基础知识。包括线性表、栈和队列、树、二叉树和图的部分概念。,2,、掌握查找及排序相关的概念、算法和应用。,课程要求：,（,1,）基本要求,掌握基本原理；熟悉主要算法特点；了解常用算法的设计思想与结构。,注意：理论性强，比较枯燥。学好理论，才能在实际程序设计灵活应用。,（,2,）学习方法,a.,知识：需要记忆、积累、联想、对比,抓重点,b.,技能：需要训练、经验、方法、技巧,抓特点,c.,思路：逻辑思维、形象思维,（,3,）认真完成书后作业和补充习题。,考核方式：笔试（考试课）,成绩评定：,笔试（,70%,）和平时成绩（,30%,）,平时成绩包括：,测验：,10%,考勤作业：,10%,实验：,10%,第,1,章,计算机软件技术基础概论,计算机基础,计算机软件基础,计算机软件技术的发展,软件的设计方法,程序设计基本算法与应用,1.1,计算机基础,P1,计算机的发展,ENIAC 4,个阶段,电子管、晶体管、集成电路、大规模和超大规模集成电路,计算机的组成：硬件、软件,计算机的应用,系统软件、应用软件,（,1,）,科学计算（,Science Computer,）,（,2,）数据处理（,Data Processing,）,（,3,）过程控制（,Process Control,）,（,4,）计算机辅助系统,Computer Aided System,（,5,）人工智能（,AIArtificial Intelligence,）,1.1,计算机基础,P3,1.2,计算机软件基础,P5,软件是指计算机,程序,、程序所使用的,数据,以及有关的,文档资料,的集合，即软件,=,程序,+,数据,+,文档。,P5,分类,系统软件、应用软件,系统软件是,直接控制和协调,计算机、通信设备及其他外部设备的软件，这类软件一般紧靠硬件，是用户与计算机之间的第一层界面。,应用软件是指用户借助系统软件而开发编制的用来解决各种实际问题的软件。,1.2,计算机软件基础,P6,计算机语言,计算机语言是用来书写计算机可以执行的程序的。主要是计算机程序设计语言,（,1,）机器语言（,Machine Language,）,（,2,）汇编语言（,Assemble Language,）,（,3,）高级语言（,High Level Language,）,1.3,计算机软件技术的发展,P6,三个时代,（,1,）程序设计时代（,1946-1955,）,（,2,）软件时代（,1955-1970,）,（,3,）软件工程时代（,1970-,至今）,1.4,软件的设计方法,P7,主要方法有三种：面向,数据流,的软件设计方法、面向,数据结构,的软件设计方法和面向,对象,的软件设计方法。,面向数据流：结构化设计,图,1-2,变换型,DFD,1.4,软件的设计方法,P8,面向数据结构的软件设计方法，是用,数据结构,作为程序设计的基础。最适合于在,详细设计,阶段,面向对象的软件设计方法就是把面向对象的思想应用到软件工程中，并指导开发维护软件。,图,1-3,事务型,DFD,1.5,程序设计基本算法与应用,P8,迭代法：不断用变量的旧值递推新值的过程,方程求根,数值近似求解。确定一合适迭代公式，选一初始近似值以及解的误差，循环处理实现迭代过程，终止条件：前后两次得到的近似值之差的绝对值,=,预先给定的误差。,1.5,程序设计基本算法与应用,P8,实例,1,：利用牛顿迭代法求方程的根。方程为,ax,3,+bx,2,+cx+d=0,，系数,a,b,c,d,由主函数输入。求,x,在,1,附近的一个实根，求出根后由主函数输出。,#include,math.h,#include,float,fun(float,float,float,float,);,void main(),float,a,b,c,d,;,printf(a,b,c,d,=);,scanf(%f,%f,%f,%f,&a,&b,&c,&d,);,printf(x,=%10.7fn,fun(a,b,c,d),);,float,fun(float,a,float,b,float,c,float,d),float x=1,y;,do,y=x;,x=x-(a*,x+b,)*,x+c,)*x+d)/(3*a*x+2*b)*,x+c,);,while(fabs(x-y,)=0.0000001);,return(x,);,递推法：,斐波那契数列（,P16,页）,从已知的初始条件出发，逐次递推出最后所求的值,1.5,程序设计基本算法与应用,P10,实例,2,，我们可以使用“递推”法来输出,费波那契（,Fibonacci,）数列,的前,20,项值。,Fibonacci,系列是：第,0,个元素为,0,，第,1,个元素为,1,，后面每一个元素都是前面两个元素值的和，即,0,1,1,2,3,5,8,13,21,34,55,递推公式：,f(0)=0,；,f(1)=1,；,f(n,)=f(n-2)+f(n-1),（,n1,）,1.5,程序设计基本算法与应用,P10,C,语言表示为,：（输出前,20,项）,int,f20,；,f0=0;,f1=1;,for(,int,i=0;i1),fi,=fi-2+fi-1;/*,递推公式*,/,printf(“Fibonacci%d,=%,dn”,i,fi,);,1.5,程序设计基本算法与应用,P10,递归法：,直接或间接调用它自身。从函数本身出发，逐次上溯调用其本身求解过程，至递归出口，再从里向外倒推回来，得到最终的值。,1.5,程序设计基本算法与应用,P10,实例,3,编写计算斐波那契（,Fibonacci,）数列的第,n,项函数,fib,（,n,）。,fib(0)=0;,fib(1)=1;,fib(n,)=fib(n-1)+fib(n-2),（当,n1,时）,1.5,程序设计基本算法与应用,P10,写成递归函数有：,int,fib(int,n),if(n=0)return 0;,if(n=1)return 1;,if(n1)return fib(n-1)+fib(n-2);,1.5,程序设计基本算法与应用,P10,递归算法的执行过程分为递推和回归两个阶段。由于递归引起一系列函数调用，可能会有一些重复计算，,递归算法的执行效率相对较低。,例：二阶,Fibonacci,数列的定义如下：,F0=1,F1=1,F2=2,F3=3,F4=5,Fi,=Fi-1+Fi-2,i1,。试用递归和非递归两种方法写出计算,Fn,的函数。并分别计算运行时间。,示例：,1.5,程序设计基本算法与应用,P10,穷举法,：对可能是解得众多候选解按某种顺序进行逐一枚举和检查，从中找出复合要求的解。,百钱买百鸡（,P11,页）,1.5,程序设计基本算法与应用,P11,实例,4,：百钱买百鸡问题,一百个铜钱买了一百只鸡，其中公鸡一只,5,钱、母鸡一只,3,钱，小鸡一钱,3,只，问一百只鸡中公鸡、母鸡、小鸡各多少。,1.5,程序设计基本算法与应用,P11,设一百只鸡中公鸡、母鸡、小鸡分别为,x,，,y,，,z,，问题化为三元一次方程组：,1.5,程序设计基本算法与应用,P11,x,的取值范围为,1,20,y,的取值范围为,1,33,z,的取值范围为,3,99,，步长为,3,对于这个问题我们可以用穷举的方法，遍历,x,y,z,的所有可能组合，最后得到问题的解。,1.5,程序设计基本算法与应用,P11,/,百钱买百鸡,#include,void main(),int,x,y,z,;,for(x,=1;x=20;x+),for(y,=1;y=33;y+),z=100-(x+y);,if(z%3=0&x*15+y*9+z=300),printf(cock,=%d hen=%d chicken=%,dn,x,y,z,);,1.5,程序设计基本算法与应用,P11,回溯法：也叫试探法。,例,5,：有一,3,行,3,列的表格,现将,0-9,这,9,个数填入当中,使每行,每列,每斜线上三个数之和都相等,要求用回溯法做。,我们后面讲到树的遍历查找问题就可以用到回溯法。,1.5,程序设计基本算法与应用,P12,贪心法：不追求最优解，只希望得到较为满意解的方法。,如：平时购物找钱的例子。,如：装箱问题,1.5,程序设计基本算法与应用,P14,分治法：将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。,动态规划法：,分解若干子问题求解,1.5,程序设计基本算法与应用,P14,