《计算机软件技术基础复习过程.ppt》由会员分享，可在线阅读，更多相关《计算机软件技术基础复习过程.ppt（25页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、计算机软件技术基础学习与考核学习与考核教师讲授为主教师讲授为主上机实验：上机语言上机语言c语言语言考核方式：平时成绩平时成绩20%+上机实验、完成实验上机实验、完成实验报告报告20%+期末考试成绩期末考试成绩60%2绪论绪论计算机硬件及其发展计算机软件数据结构、操作系统、数据库与软件工程3计算机硬件及发展计算机硬件及发展l l发展历史发展历史 电子管电子管 晶体管晶体管 集成电路集成电路 超大规模集超大规模集成电路成电路l l发展路线及规律发展路线及规律 速度慢速度慢 速度快速度快 体积大容量小体积大容量小 体积小容量大体积小容量大 外设少、简单外设少、简单 外设繁多、复杂外设繁多、复杂 二进
2、制处理原则二进制处理原则 软件从短小、精干、讲究效率到复杂可靠、兼容性强、结构性好软件从短小、精干、讲究效率到复杂可靠、兼容性强、结构性好4计算机软件计算机软件l l软件的概念软件的概念软件的概念软件的概念软件是：与一系统（尤指计算机系统）有关的程序、步软件是：与一系统（尤指计算机系统）有关的程序、步骤和有关文件编制的完整集合。特指特定类型计算机骤和有关文件编制的完整集合。特指特定类型计算机所使用的程序的总称，连同与计算机或程序有关的资所使用的程序的总称，连同与计算机或程序有关的资料，例如手册、图表和操作指令。料，例如手册、图表和操作指令。功能：针对一个系统（计算机），合理组织工作。功能：针对
3、一个系统（计算机），合理组织工作。程序设计语言的发展程序设计语言的发展程序设计语言的发展程序设计语言的发展l经历：机器语言，汇编语言，高级语言，面向对象语经历：机器语言，汇编语言，高级语言，面向对象语言言软件的发展：语言的发展软件的发展：语言的发展-操作系统的出现操作系统的出现-数据库的出现数据库的出现-网络的出现网络的出现5数据结构、操作系统、数据库与软件工程数据结构、操作系统、数据库与软件工程l数据结构：描述数据及数据元素之间的关系，数据在数据结构：描述数据及数据元素之间的关系，数据在计算机系统中的存储方式及数据的运算。计算机系统中的存储方式及数据的运算。软件技术基础的基础软件技术基础的基
4、础软件技术基础的基础软件技术基础的基础l操作系统：方便用户有效利用各种软、硬件资源的程操作系统：方便用户有效利用各种软、硬件资源的程序的集合序的集合 建造工作环境、平台建造工作环境、平台建造工作环境、平台建造工作环境、平台l数据库：可以共享相关数据，以一定组成方式的集合数据库：可以共享相关数据，以一定组成方式的集合 进行数据信息处理的强大应用。进行数据信息处理的强大应用。进行数据信息处理的强大应用。进行数据信息处理的强大应用。l软件工程：软件设计的基本过程，思想和方法。软件工程：软件设计的基本过程，思想和方法。6第一章算法第一章算法2022/11/25算法的基本概念算法的基本概念算法设计的基本
5、方法算法设计的基本方法算法的复杂度分析算法的复杂度分析C语言简介语言简介7算法的基本概念算法的基本概念算法的基本特征算法的基本特征（1 1）能行性）能行性（2 2）确定性）确定性（3 3）有穷性）有穷性（4 4）拥有足够的情报）拥有足够的情报算法是指解题方案的准确而完整的描述。算法是指解题方案的准确而完整的描述。8算法与程序算法与程序相同点相同点相同点相同点：都是解决问题的方法和步骤：都是解决问题的方法和步骤：都是解决问题的方法和步骤：都是解决问题的方法和步骤描述方法描述方法描述方法描述方法：程序使用程序设计语言：程序使用程序设计语言：程序使用程序设计语言：程序使用程序设计语言 算法使用框图或
6、其他语言算法使用框图或其他语言算法使用框图或其他语言算法使用框图或其他语言联系联系联系联系：程序用某种程序设计语言来实现算法：程序用某种程序设计语言来实现算法：程序用某种程序设计语言来实现算法：程序用某种程序设计语言来实现算法 9怎样表示一个算法怎样表示一个算法1 1、用自然语言表示算法、用自然语言表示算法2 2、用流程图表示算法、用流程图表示算法3 3、用伪代码表示算法、用伪代码表示算法4 4、用机器语言表示算法、用机器语言表示算法10算法设计基本方法算法设计基本方法在数据结构中常见的问题在数据结构中常见的问题在数据结构中常见的问题在数据结构中常见的问题创建、插入、删除、更新、检索、排序创建
7、、插入、删除、更新、检索、排序创建、插入、删除、更新、检索、排序创建、插入、删除、更新、检索、排序注意：每个问题都有一种和多种算法注意：每个问题都有一种和多种算法注意：每个问题都有一种和多种算法注意：每个问题都有一种和多种算法 找到效率最高的；找到效率最高的；找到效率最高的；找到效率最高的；以最容易理解的方式设计；以最容易理解的方式设计；以最容易理解的方式设计；以最容易理解的方式设计；设计的算法不容易出错或出错情况较少。设计的算法不容易出错或出错情况较少。设计的算法不容易出错或出错情况较少。设计的算法不容易出错或出错情况较少。11算法的基本要素算法的基本要素(1)(1)(1)(1)对数据对象的
8、运算和操作：对数据对象的运算和操作：对数据对象的运算和操作：对数据对象的运算和操作：a).a).算术运算，加、减、乘、除等运算；算术运算，加、减、乘、除等运算；b).b).逻辑运算，逻辑运算，“与与”、“或或”、“非非”等运算；等运算；c).c).关系运算，关系运算，“大于大于”、“小于小于”、“等于等于”、“不不等于等于”等运算；等运算；d).d).数据传输，主要包括赋值、输入、输出等操作；数据传输，主要包括赋值、输入、输出等操作；(2)(2)(2)(2)算法的控制结构算法的控制结构算法的控制结构算法的控制结构 12算法设计基本方法算法设计基本方法l列举法列举法 基本思想：根据提出的问题，列
9、举所有可能的根据提出的问题，列举所有可能的情况，并用问题中给定的条件检验哪些是需要情况，并用问题中给定的条件检验哪些是需要的。的。l特点：算法简单；工作量大13举例：举例：举例：举例：设每只母鸡值设每只母鸡值设每只母鸡值设每只母鸡值3 3 3 3元，每只公鸡值元，每只公鸡值元，每只公鸡值元，每只公鸡值2 2 2 2元，两只小元，两只小元，两只小元，两只小鸡值鸡值鸡值鸡值1 1 1 1元。现要用元。现要用元。现要用元。现要用100100100100元买元买元买元买100100100100只鸡，设计买鸡方案。只鸡，设计买鸡方案。只鸡，设计买鸡方案。只鸡，设计买鸡方案。方案一方案一假设买母鸡假设买母
10、鸡i只，公鸡只，公鸡j只，只，小鸡小鸡k只。只。procedure baijifor i=0 to 100 dofor j=0 to 100 dofor k=0 to 100 dom=i+j+kn=3i+2j+0.5kif(m=100)and(n=100)thenoutput I,j,kreturn方案二方案二procedure baijifor i=0 to 33 dofor j=0 to 50-1.5i dok=100-i-jIf(3i+2j+0.5k=100)thenoutput I,j,kreturn142、归纳法、归纳法l基本思想基本思想 通过列举少量的特殊情况，经过分析，最后找出一
11、通过列举少量的特殊情况，经过分析，最后找出一般的关系。般的关系。152、递归法、递归法基本思想基本思想 为了降低问题的复杂度，总是将问题组成为了降低问题的复杂度，总是将问题组成分解，最后归纳为一个最简单的问题，当解决分解，最后归纳为一个最简单的问题，当解决这个简单问题后，再沿着就原来分解的逆过程这个简单问题后，再沿着就原来分解的逆过程逐步进行综合，这就是递归。逐步进行综合，这就是递归。16例题：用递归方法求例题：用递归方法求n n！l递归公式表示：递归公式表示：17程序程序#include int main()int fac(int n);int n;int y;printf(“input a
12、n integer number”);scanf(“%d”,&n);y=fac(n);printf(“%d!=%dn”,n,y);Return 0;int fac(int n)int f;if(n0)printf(“n0,data error!”);else if(n=0|n=1)f=1;else f=fac(n-1)*n;return(f);18减半递推技术减半递推技术 所谓所谓所谓所谓“减半减半减半减半”，是指将问题的规模减半；所谓，是指将问题的规模减半；所谓，是指将问题的规模减半；所谓，是指将问题的规模减半；所谓“递推递推递推递推”，就是重复减半的过程。就是重复减半的过程。就是重复减半的
13、过程。就是重复减半的过程。举例：设两个二阶矩阵为举例：设两个二阶矩阵为举例：设两个二阶矩阵为举例：设两个二阶矩阵为 需要需要需要需要8 8 8 8次乘法次乘法次乘法次乘法两个矩阵相乘只需要两个矩阵相乘只需要两个矩阵相乘只需要两个矩阵相乘只需要7 7 7 7次乘法次乘法次乘法次乘法设设设设 n=2 n=2 n=2 n=2k k k k ，n=2n=2k k 阶矩阵相乘，所需要的阶矩阵相乘，所需要的阶矩阵相乘，所需要的阶矩阵相乘，所需要的乘法次数乘法次数乘法次数乘法次数M(k)M(k)M(k)M(k)M(k)=7M(k-1)=7M(k)=7M(k-1)=72 2 M(k-2)=7 M(k-2)=7
14、k k M(0)M(0)=7 =7k knn2.812.8119回溯法回溯法回溯法回溯法基本思想：通过对问题的分析，找出一个解决问题的线索，然后沿着这个线索逐步试探，对于每一步的试探，若试探成功，就得到问题的解，若试探失败，就逐步回退，换别的路线再进行试探。201.3 1.3 算法的复杂度分析算法的复杂度分析l l算法的时间复杂度算法的时间复杂度算法的时间复杂度算法的时间复杂度(算法的工作量算法的工作量算法的工作量算法的工作量)采用算法在执行过程中所需基本运算的执行采用算法在执行过程中所需基本运算的执行采用算法在执行过程中所需基本运算的执行采用算法在执行过程中所需基本运算的执行次数来度量算法的
15、工作量。次数来度量算法的工作量。次数来度量算法的工作量。次数来度量算法的工作量。l l相关因素：相关因素：相关因素：相关因素：(1)(1)(1)(1)基本运算次数还与问题的规模基本运算次数还与问题的规模基本运算次数还与问题的规模基本运算次数还与问题的规模n n n n有关。算法有关。算法有关。算法有关。算法的工作量的工作量的工作量的工作量=f(n)=f(n)=f(n)=f(n)(2)(2)(2)(2)当取决于某一个特性输入时，有两种方法来当取决于某一个特性输入时，有两种方法来当取决于某一个特性输入时，有两种方法来当取决于某一个特性输入时，有两种方法来衡量工作量：衡量工作量：衡量工作量：衡量工作
16、量：平均性态平均性态平均性态平均性态 最坏情况复杂性最坏情况复杂性最坏情况复杂性最坏情况复杂性 21举例：采用顺序搜索法，在长度为举例：采用顺序搜索法，在长度为举例：采用顺序搜索法，在长度为举例：采用顺序搜索法，在长度为n n n n的一维数组中的一维数组中的一维数组中的一维数组中查找值为查找值为查找值为查找值为x x x x的元素的元素的元素的元素平均性态分析：平均性态分析：平均性态分析：平均性态分析：设需要查找的设需要查找的设需要查找的设需要查找的x x x x出现在数组中每个位置上的可能性一样，概率出现在数组中每个位置上的可能性一样，概率出现在数组中每个位置上的可能性一样，概率出现在数组
17、中每个位置上的可能性一样，概率为为为为q/nq/nq/nq/n，x x x x不在数组中的概率为不在数组中的概率为不在数组中的概率为不在数组中的概率为1-1-1-1-q q比较次数比较次数平均情况下比较次数平均情况下比较次数平均情况下比较次数平均情况下比较次数22 最坏情况是发生在需要查找的最坏情况是发生在需要查找的最坏情况是发生在需要查找的最坏情况是发生在需要查找的x x x x是数组中的最是数组中的最是数组中的最是数组中的最后一个元素或后一个元素或后一个元素或后一个元素或x x x x不在数组中的时候，此时显然不在数组中的时候，此时显然不在数组中的时候，此时显然不在数组中的时候，此时显然（2 2）最坏情况复杂度）最坏情况复杂度23算法的空间复杂度算法的空间复杂度 一般指执行这个算法所需要的内存空间，包括算法程序所占的空间、输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间。24此课件下载可自行编辑修改，仅供参考！此课件下载可自行编辑修改，仅供参考！感谢您的支持，我们努力做得更好！谢谢感谢您的支持，我们努力做得更好！谢谢