《青岛市科技馆信息学奥林匹克中级班内容》由会员分享，可在线阅读，更多相关《青岛市科技馆信息学奥林匹克中级班内容（139页珍藏版）》请在金锄头文库上搜索。
1、奥赛辅导之一：数据结构、算法的引入与程序设计“程片数据结构算法”，这是著名计算机科学家N.Wirth提出的程序公式。实际上编程解决各种各样的实际问题，只学习掌握好Pascal、C等程序设计语言是远远不够的，另外还必须具备数据结构和算法的相关知识。前者主要主要讲述客观世界中纷繁复杂的平物及其内在的联系如何有效地在计算机中进行表示，后者斗要讲解建立在这种表示基础上的些常用的解决实际问题的思想、方法和步骤。二者是一个相辅相成的统一体，是缺一不可的两个方面。有了它以后，我们才能比较顺利地编写程序。、数据结构数据(dataelement)是计算机化的信息，是计算机处理的某本对象。数据元素(dataele
2、ment)也叫结点(node)或记录(record)，是数据的基本单位。数据项(dateitem)是数据不可分割的最小单位，是由一个或多个字符组成的具有独立含义的数据标识单位。数据对象(dataobject)指性质相同的数据元系的共合，是数据的一个子知。数据结构(datastrncture)指相互之间存在一种或多种特定关系的数据元素的免合，数据之间的关系称作结构。数据结构包括数据的逻辑结构和数据的存储结构。l 数据的逻辑结构计算机所处理的数据一般都存在看某种内在的、特殊的关系，绝对孤立或杂乱无章的数据是不存在的。这种数据本身以及它们内在的相互之间的逻辑关系，叫做数据的逻辑结构。它是进行数据处理
3、的依据，同时也是在计算机中对数据进行存储和加工处理的基础。 数据的逻铅结构可以表示成一个二元组：B=(D,S)其中D是由结点（数据元系）构成的媒合；S是关千D 中结点之间关系的共合。两者必须是有穷的。 D中结点的数据类型初等类和（只包含一个初等项的）和组合类别（包含多个初等项的）。(I)初等类型：实际上是Pascal的基本数据类型。具体包括：整数类形(Short.liit,mteger、Longlnt、Byte、Word)、实数类型(Single、Real、Double、Extented、Comp)、布尔类tl(Boolean)、字符类型(Char)、指针类型、枚举类型和了界类型。(2)组合类
4、型：指Pascal中的构造类犁。具体包括：数组类犁、栠合类型、记录类犁和文件类型。 s中的关系是根据对实际问题的分析，升经过高度抽象后化后所得到的结点之间的相互关系。通常分为匹种关系：集合结构（数据元素之间除了同属千一个共合外，无任何其它关系。）、线性结构（数据元素之间存在若一对的线性关系。）、树型结构（数据元素之间存在消对多的层次关系。）、图结构或网状结构（数据元系之间存在石多对多的任意关系。）。 数据结构既不同于数据类型，也不同千数据对象，它不仅要描述数据对象的数据类型，而且要描述数据对象各元系之间的相互关系。2.数据的存储结构是数据的逻辑结构在计算机中的存储方式。方法主要有顺序存储和链式
5、存储两种。(I)顺序存储结构：指借助元素在存储中的相对位置来表示数据元素之间的逻辑关系。该存储方式使得在逻钳上相互关联的数据元素，在物理存储结构中是相邻的。在Pascal中一般采用数组来实现。(2)链式存储结构：侣助元素存储地卅的指针(Pointer)表示数据元素之间逻辑关系的存储方式。此存储方式使得在逻辑上相互关联的数据元系，在物理存储结构中不一定相邻，其逻铝关系用一个或多个指针变撮指示。在实际中到底用哪种方式实现物理存储，要根据具体悄况来定。3.数据的运算数据的运算是定义在数据的逻铅结构士的，而运算的实现要在数据的存储结构：进行。常用的运算主要有：插入、删除、更新、排序、杳找等。二、算法l
6、、什么是算法算法(Algorithm)是解题的步骤，即为了解决某个问题而采用的一系列方法和步骤的总称，是关于问题解决力法的精确描述。在此处我们所说的算法是计算机可以实现的算法。算法数据结构程序，求解一个给定的可计算或可解的问题，不同的人可以编写出不同的程序，来解决同一个问题，这里存在两个问题：一是与计算方法密切相关的算法问题；二是程序设计的技术问题。算法和程序之间存在密切的关系。算法是一组有穷的规则，它们规定了俘决某一特定类型问题的一系列运算，是对解题方案的准确与完整的描述。制定一个算法，一般要经过设计、确认、分析、编码、测试、调试、计时等阶段。对算法的学习包括土个力面的内容：设计算法。算法设
7、计工作是不可能完全自动化的，应学习了解已经被实践证明是有用的一些基木的算法设计方法，这些基木的设计方法不仅适用丁计算机科学，而且适用于电气工程、运筹学等领域：表示算法。描述算法的为法有多种形式，例如自然语言和算法语言，各自有适用的环境和特点：确认算法。算法确认的目的是使人们确信这一算法能够正确无误地工作，即该算法具有可计算性。正确的算法用计算机算法语言描述，构成计算机程序，计算机程序在计算机上运行，得到算法运算的结果：分析算法。 算法分析是对一个算法需要多少计算1讨间和存储空间作定整的分析。分析算法可以预测这一算法适合在什么样的环境中有效地运行，对解决间一问题的不同算法的有效性作出比较：验证算
8、法。用计算机语言描述的算法是否可计算、有效合理，须对程序进行测试，测试程序的工作山调试和作时空分布图组成。2、算法的特性算法的特件包括：确定性。算法的每一种运算必须有确定的意义，该种运算应执行何种动作应无二义性，目的明确：）能行性。要求算法中有待实现的运算都是基本的，每种运算至少在原理上能出人用纸和笔在有限的时间内完成：输入。一个算法有0个或多个输入，在算法运算开始之前给出算法所需数据的初值，这些输入取自特定的对象桨合；输出。作为算法运算的结果，一个算法产生一个或多个输出，输出是同输入有某种特定关系的型；有穷性。一个算法总是在执行了有穷步的运算后终止，即该算法是可达的。满足前四个特性的一组规则
9、不能称为算法，只能称为计算过程，操作系统是计算过程的一个例子，橾作系统用来管理计算机资源，控制作Iv.的运行，没有作业运行时，计算过程并不停止，而是处千等待状态，3、算法的描述算法的描述方法可以归纳为以卜几种：(I)自然语言：(2)图形，如N-S图、流程阳，图的描述与算法语言的描述对应；(3)算法语言，即计算机语言、程序设计语言、伪代码；(4)形式语言，用数学的方法，可以避免自然语言的二义性。用各种算法描述方法所描述的同一算法，该算法的功用是一样的，允许在算法的描述和实现方法上有所不同。人们的生产活动和日常生活离不开算法，都在自觉不自觉地使用算法，例如人们到商店购买物品，会首先确定购买哪些物品
10、，准备好所需的钱，然后确定到哪些商场选购、怎样去商场、行走的路线，若物品的质量好如何处理，对物品不满意又怎样处理，购买物品后做什么等。以上购物的算法是用自然语言描述的，也可以用其他描述为法描还该算法。例写出解决如下问题的算法及程序。2个客人合用一个柴碗：3个客人合用一个汤碗：4个客人合用一个饭碗。共用了65个碗，请帮助主人算一卜共来了多少个客人。解：x为客人数朵(l )X赋值0:(2)X+12=X: (3)X/2+x/3+x/4的和Y;(4)如果Y=65则客人为X结果输出：否则转2。Program ex(input,output); Var X,y:integer; F:Boolean; Be
11、gin X:=0;f:=false; Repeat X:=x+l2; If x div 2+x div 3+x div 4=65 then begin writetotal:,x);f:=true;end; until f; end. 4、算法的复杂性算法的复杂性是算法效率的度量，在评价算法性能时，复杂性是一个重要的依据。算法的复杂性的程度与运行该算法所需要的计算机资源的多少有关，所需要的资源越多，表明该算法的复杂性越商；所需要的资源越少，表明该算法的复杂性越低。计算机的资源，最重要的是运算所需的时间和存储程序和数据所需的空间资源，算法的复杂性有时间复杂性和空间复杂性之分。时间复杂度：在运行算
12、法时所耗费的时间为fln)（即n的函数）。空间复杂度：实现算法所占用的空间为g(n)（也为n的函数）。称O(f(n)）和O(g(n)）为该算法的复杂度。算法在计算机上执行运算，需要一定的存储空间存放描述算法的程序和算法所需的数据，计算机完成运算任务需要一定的时间。根据不同的算法写出的程序放在计算机上运算时，所需要的时间和空间是不同的，罚法的复杂性是对算法运符所需时间和空间的一种度最。不同的计算机其运算速度相差很大，在衡量一个算法的复杂性要注意到这点。对丁任意给定的问题，设计出复杂性尽可能低的算法是在设计算法时考虑的一个重要目标。另外，当给定的问题已有多种算法时，选择其中复杂性最低者，是在选用算
13、法时应遵循的一个重要准则。因此，算法的复杂性分析对算法的设计或选用有若重要的指导意义和实用价值。在讨论算法的复杂性时，有两个问题要弄清楚：(I)一个算法的复杂性用怎样的一个狱来表达：(2)怎样计算一个给定算法的复杂性。找到求解一个问题的算法后，接若就是该算法的实现，至丁是否可以找到实现的方法，取决千算法的可计算性和计算的复杂性，该问题是否存在求解算法，能否捉供算法所需要的时间资源和空间资源。、程序设计所谓程片设计实质上就是数据结构的选用和算法设计这两者的有机组合。1.程序程序是对所要解决的间题的各个对象和处理规则的描述，或者说是数据结构和算法的描述，因此有人说，数据结构算法程序。2.程序设计程
14、序设计就是设计、编制和调试程序的过程。3.结构化程序设计结构化程序设计是利用逐步求精的力法，按一套程式化的设计准则（任何问题都可出顺序结构、选择结构和循环结构三种结构来实现）进行程序的设计。由这种方法产生的程序是结构良好的。所谓“结构良好”是指：(1)易千保证和验证其正确性：(2)易于阅读、易于理解和易于维护。按照这种方法或准则设计出来的程序称为结构化的程序。“逐步求精”是对一个复杂问题，不是一步就编成一个可执行的程序，而是分步进行。第一步编出的程序最为抽象：第二步编出的程序是把第一步所编的程序（如过程、函数等）细化，较为抽象；第1步编出的程序比第曰步抽象级要低；直到最后，第n步编出的程序即为
15、可执行的程序。所谓“抽象程序”是指程予所描述的解决问题的处理规则，是由那些“做什么“操作组成，而不涉及这些操作“怎样做“以及解决问题的对象具有什么结构，不涉及构造的每个局部细节。这一方法原理就是：对一个问题（或任务），程序人员应立足丁全局，考虑如何解决这一问题的总体关系，而不涉及其局部细节。在确保全局的正确性之后，再分别对每一局部进行考虑，每个局部又将是一个间题或任务，因而这一方法是自顶而下的，问时也是逐步求精的。采用逐步求精的优点是：(1)便千构造程序。由这种方法产生的程序，其结构清晰、易读、易写、易理解、易调试、易维护；(2)适用千大任务、多人员设计，也便千软件管理。逐步求精方法有多种具体
16、做法，例如流程图方法、基于过程或函数的方法。例求两自然数，其和是667，最小公倍数与最大公约数之比是120:1（例如(II 5,552)、(232,435)）。解两个自然数分别为m和667-m（区m:S333)。处理对象：m（自然数）、l（两数的最小公倍数）、g（两数的最大公约数） 。处理步骤：对m从2到333检杳l与g的商为120，且余数为0时，打印m与667-m。第一层抽象程序：Program TwoNum; Var m,l,g:integer; Begin for m:=l to 333 do begin l:=lcm(m,667-m); 求最小公倍数）g:=gcd(m,667-m); 求最大公约数if (l=g*120)and(I mod g=O)then writeln(m:5,667-m:5); end; End. 第二层考虑函数1cm（最小公倍数）、gcd（最大公约数）的细化。最大公约数问题是对参数a、b,找到一个数1能整除a与b,i就是gcd的函数值。Function gcd(a,b:ini.eger):integer; var i:integer; begin for
