信息算法知识梳理

算法与程序设计1．算法：为解决某一问题设计的确定的有限的步骤。2．算法的主要特征：有穷性、确定性、可行性、有0个或多个输入、有一个或多个输出3．算法的描述方法：自然语言，流程图，伪代码或程序。4．流程图符号起止框输入输出框处理框判断框流程线5．常量：在程序执行过程中事先设置、其值不发生改变的量。6．变量：在程序执行过程中，取值可以改变的量，对应计算机内部的存储单元。（1）每个变量都有一个名字作为标记，不同程序设计语言对变量的命名规则个不相同。（在Vb程序中,变量的命名,只能由字母、数字和下划线三类字符组成，但第一个字符必须是字母）（2）从变量中读取数据后，变量的值不发生改变。（3） 变量的赋值：a=2或a一2（4） 变量赋值的特点：取之不尽，赋值即覆盖（5） 数据类型数据类型名说明性质Integer整数型-32768—32767范围内的任何整数Long长整型-2147483648-2147483647范围内的任何整数Single单精度实数型绝对值在1.40E-45~3.40E38内的实数，有效数字约6~7位Double双精度实数型绝对值在-4.94E324~3.40E308内的实数，有效数字约14~15位String字符串型一段文字与符号Boolean逻辑型判断的结果：值为真（True）或假（False）Date日期型日期和时间

7．运算符类别运算符运算结果优先级算术运算符八、*、/、mod、+、-数值*/\mod+-关系运算符＞、＜、＞=、〈二、二、＜＞True或False相同逻辑运算符not、and、orTrue或FalseNot>and>or8．三类运算符的优先级：算术运算符＞关系运算符＞逻辑运算符9.主要函数：取整函数Int()、求算术平方根函数sqr()、求绝对值函数abs()10．算法的三种结构：顺序结构、分支结构、循环结构。丿1顺序结构双分支结构直到型循环结构当型循环结构11•默写分支结构的语句代码丿1顺序结构双分支结构直到型循环结构当型循环结构11•默写分支结构的语句代码双分支结构单分支结构if条件thenif条件then语句组A语句组Aelseendif语句组Bendif

11．默写循环结构的两种语句代码for循环变量=初值to终值step步长循环体next循环变量循环次数=int((终值-初值)/步长值)+1Dowhile循环条件Dowhile循环条件循环体Loopdo循环体loopuntil循环条件12．循环结构中要注意：循环初始状态、循环体、循环条件。13．计数器：在算法执行过程中，用来记录某种事件发生次数的变量。计数器的初值通常为0(2)在循环体中的计数语句i=i+114.累加器：在算法执行过程中，用来生成并存储数据累加和的变量累加器的初值通常为0(2)在循环体中的累加语句s=s+a15．累乘器：在算法执行过程中，用来生成并存储数据累乘积的变量。累乘器的初值通常为1(2)在循环体中的累乘语句s=s*a16．解析算法：用解析的方法找出表示问题的前提条件与结果之间关系的数学表达式，并通过表达式的计算来实现问题求解。【解析算法实例1】输入已知三角形三条边的长a、b、c,利用海伦公式求三角形面积。开始输入三角形三条

边长abcs〜(a+b+c)/2x・开始输入三角形三条

边长abcs〜(a+b+c)/2x・sqr(s*(s-a)*(s-b)*(s-c))输出x结束DimaasintegerDimbasintegerDimcasintegerDimxassingle| a = InputBox("a:")| b = InputBox("b:")| c = InputBox("c:")| s = (a+b+c)/2x=Sqr(s*(s-a)*(s-b)*(s-c))Printx17．枚举算法：列出各种可能的情况并逐一进行检验，根据检验的结果执行相应的操作。“枚”就是一个一个；“举”就是列举。核心：不遗漏不重复。枚举算法充分利用了计算机“运行速度快、不知疲倦”的优势。（1）结构特点：循环中嵌套分支结构列举 由循环结构实现检验——由分支结构实现算机“运行速度快、不知疲倦”的优势。（1）结构特点：循环中嵌套分支结构列举 由循环结构实现检验——由分支结构实现初始状态J叫否继续列举FT准备列举下一个2）设计步骤1）确定列举的范围：不能随意扩大和缩小范围，否则会造成重复或漏解2）明确检验的条件：根据检验的对象来设定条件，以及检验后所执行的相关操作。3）确定循环控制的方式和列举的方式：借助循环变量的变化来列举，或通过输入。枚举算法实例】若一个三位数x=100*a+10*b+c（a、b、c都是个位数），满足找出三位数中所有的水仙花数。dimxasintegerdimaasintegerdimbasintegerdimcasintegerx=100DoWhilex<=999a=Int(x/100)b=Int((xMod100)/10)c=xMod10Ifa八3+b八3+c八3=xThenPrintxEndIfx=x+1Loop

18．数组：一种特殊的变量，在内存中的位置是连续的，用于存储一批类型、作用相同的数据。几个相关概念：数组名、数组元素、数组元素名、数组元素下标、数组元素值。数组必须先声明后使用。Dim〈数组名〉(下标)As〈数据类型〉例1：Dima(3)asinteger定义了a(0),a(l),a(2),a(3)四个变量是数组类型例2：DimSc(3to6)AsString定义了Sc(3),Sc(4),Sc(5)和Sc(6)，并且每个元素都是字符串型的数组实例】输入10个数字，依次存放到数组中，再将其逆序输出。iTO.i>=1.上-结束Dimd(1To10)iTO.i>=1.上-结束PrivateSubCommandlClick()i=1DoWhilei<=10a=InputBox("请输入数字："，i)d(i)=ai=i+1Loopi=10DoWhilei>=1Printd(i)i=i-1LoopEndSub19．冒泡排序的算法思想从最下面一个元素起，自下而上地比较相邻两个元素中的数据，将较小的数值交换到上面一个元素。重复这一过程，直到处理完最后两个元素中的数据，称为一遍加工。此时，最小的数据已经上升到第一个元素的位置。然后对余下的i-1个元素重复上述过程。由于每一遍加工都是将最小的元素像气泡一样浮至顶端，故称为冒泡排序。例：有一组数据23、61、24、15、89，问第二轮冒泡的第一次交换后数据排序的结果如何？

冒泡过程：原始数据2361241589第一轮冒泡（交换3次）1589152489156124891523612489第二轮冒泡（第1次父换）2489246189答：第二轮冒泡的第一次交换后数据排序结果为15、23、24、61、89接输出部分

20．选择排序的算法思想（找最值——擂台法）（1）从第一个元素起，自上而下找出最小数，并记录下它的位置，将最小数交换到第一个元素中。完成第一遍加工。（2）然后对余下的i-1个元素重复上述过程。（3）在每一遍加工中，只需交换一次位置即可上例中的这组数据23、61、24、15、89，用选择排序的过程如下：原始数据2361241589第一遍加工1561242389第二遍加工1523246189〖冒泡排序与选择排序的比较〗选择排序实际上是一种优化了的排序方法，它和冒泡排序的区别在于减少了交换的次数，在每一遍的加工过程中，选择排序采用的方法是通过遍历，记录下最值的位置，最后再将最值所在位置的数据与待排元素所在的位置进行交换，因此每一遍加工只需交换依次位置。大大减少了算法的复杂度。i=1Fiv=n-lk=iF<=nTk=jd(j)<d(k)F交换d（i）与d（k）中的数据j=j+1i=1Fiv=n-lk=iF<=nTk=jd(j)<d(k)F交换d（i）与d（k）中的数据j=j+1j=i+1i=i+1DoWhilei<=n-1k=ij=i+1DoWhilej<=nIfd(j)<d(k)Thenk=jEndIfj=j+1Loopt=d(i)d(i)=d(k)d(k)=ti=i+1Loop

21．擂台法实例：已知数组d中已经存放了10个数，输出其中的最大值先假设d[1]中的数值是最大值，令k-d[1]。用d[2]与k比较，若d[2]大，则令k-d[2],否则继续比较，直至d[10]如果还需输出最大值所在的位置，则还需跟踪数组元素的下标。如下图右。i=2Fi<=10Fd(i)>kT输出k结束i=i+1k=d(i)k=d(1)F.i<=10Fd(i)>kTn=i开始]输出k,n/(结束)i=2,n=1k=d(1)i=2Fi<=10Fd(i)>kT输出k结束i=i+1k=d(i)k=d(1)F.i<=10Fd(i)>kTn=i开始]输出k,n/(结束)i=2,n=1k=d(1)i=i+1k=d(i)22．顺序查找的算法思想：按照数组元素的先后次序，从第一个元素开始遍历，逐个检验是否和查找的数据相等。例：在包含10个数字的数组中顺序查找一个符合要求的数。X10输出0Yd[i]=n输出iX1-1开始/X10输出0Yd[i]=n输出iX1-1开始/输An/（结束）Key=inputbox(“”i=1Dowhilei<=nIfd(i)=KeyThenPrintiExitsubEndIfi=i+1loopIfi=n+1ThenPrint"在数组中没有找到"EndIf23．对分查找的算法思想：先取数组中间的元素和关键字比较，若不相等则