当前位置:首页 >> 高中教育 >>

算法知识梳理


算法与程序设计
1.算法:为解决某一问题设计的确定的有限的步骤。 2.算法的主要特征: 有穷性、确定性、可行性、有 0 个或多个输入、有一个或多个输出。 3.算法的描述方法:自然语言,流程图,伪代码或程序。 4.流程图符号:

起止框

输入输出框

处理框

判断框

流程线

5.常量:在程序执行过程中事先设置、其值不发生改变的量。 6.变量:在程序执行过程中,取值可以改变的量,对应计算机内部的存储单元。 (1)每个变量都有一个名字作为标记,不同程序设计语言对变量的命名规则个不 相同。(在 Vb 程序中,变量的命名, 只能由字母、数字和下划线三类字符组成,但第一 个字符必须是字母) (2)从变量中读取数据后,变量的值不发生改变。 (3)变量的赋值:a = 2 或 a ← 2

(4)变量赋值的特点:取之不尽,赋值即覆盖 (5) 数据类型
数据类型名 Integer Long Single Double 说明 整数型 长整型 单精度实数型 双精度实数型 性质 -32768-32767 范围内的任何整数 -2147483648-2147483647 范围内的任何整数 绝对值在 1.40E-45~3.40E38 内的实数,有效数字约 6~7 位 绝对值在-4.94E324~3.40E308 内的实数,有效数字约 14~15 位

String Boolean Date

字符串型 逻辑型 日期型

一段文字与符号 判断的结果:值为真(True)或假(False) 日期和时间

1

7.运算符 类别 算术运算符 关系运算符 逻辑运算符 运算符 ^、* 、/、mod、+ 、>、<、>=、<=、=、<> not、and、or 运算结果 数值 True 或 False True 或 False 优先级 ^ > * / > mod > + 相同 Not>and>or

8.三类运算符的优先级:算术运算符>关系运算符>逻辑运算符 9.主要函数:取整函数 Int() 、求算术平方根函数 sqr() 、求绝对值函数 abs() 10.算法的三种结构:顺序结构、分支结构、循环结构。
开始 语句1

是 A框

条件

否 B框

条件 是 A框



语句2

??
语句n 结束

双分支结构

单分支结构

顺序结构 顺序结构

循环条件 T 循环体

F

循环体 F 循环条件 T

当型循环结构 11.默写分支结构的语句代码 双分支结构 if 条件 then 单分支结构 if 条件

直到型循环结构

then

语句组 A else 语句组 B end if

语句组 A end if

2

11.默写循环结构的两种语句代码 for 循环变量=初值 循环体 next 循环变量 to 终值 step 步长

循环次数=int((终值-初值)/步长值)+1 ======================== Do while 循环条件 循环体 Loop do 循环体 loop until 循环条件

12.循环结构中要注意:循环初始状态、循环体、循环条件。 13.计数器:在算法执行过程中,用来记录某种事件发生次数的变量。 (1)计数器的初值通常为 0 (2)在循环体中的计数语句 i = i + 1 14. 累加器:在算法执行过程中,用来生成并存储数据累加和的变量。 (1)累加器的初值通常为 0 (2)在循环体中的累加语句 s = s + a 15.累乘器:在算法执行过程中,用来生成并存储数据累乘积的变量。 (1)累乘器的初值通常为 1 (2)在循环体中的累乘语句 s = s * a 16.解析算法:用解析的方法找出表示问题的前提条件与结果之间关系的数学表达式, 并通过表达式的计算来实现问题求解。 【解析算法实例 1】输入已知三角形三条边的长 a、b、c,利用海伦公式求三角形面积。
开始 输入三角形三条 边长a b c s←(a+b+c)/2 x←sqr(s*(s-a)*(s-b)*(s-c)) 输出x 结束

Dim a as integer Dim b as integer Dim c as integer Dim x as single a = InputBox("a:") b = InputBox("b:") c = InputBox("c:") s = (a + b + c) / 2 x = Sqr(s * (s - a) * (s - b) * (s - c)) Print x
3

17. 枚举算法: 列出各种可能的情况并逐一进行检验, 根据检验的结果执行相应的操作。 “枚”就是一个一个; “举”就是列举。核心:不遗漏不重复。枚举算法充分利用了计 算机“运行速度快、不知疲倦”的优势。
初始状态

(1)结构特点:循环中嵌套分支结构 ? 列举——由循环结构实现 ? 检验——由分支结构实现
是否继续列举 T 条件 T
?? ??

F

F

准备列举下一个

(2)设计步骤 1)确定列举的范围:不能随意扩大和缩小范围,否则会造成重复或漏解 2)明确检验的条件:根据检验的对象来设定条件,以及检验后所执行的相关操作。 3)确定循环控制的方式和列举的方式:借助循环变量的变化来列举,或通过输入。

【枚举算法实例】若一个三位数 x=100*a+10*b+c(a、b、c 都是个位数) ,满足 a3+b3+c3=x,则 x 称为水仙花数。找出三位数中所有的水仙花数。
开始 x=100 F

x<=999 T a=int(x/100)

b=int((x mod 100)/10) c=x mod 10 a^3+b^3+c^3=x T 输出x x=x+1 F

dim x as integer dim a as integer dim b as integer dim c as integer x = 100 Do While x <= 999 a = Int(x / 100) b = Int((x Mod 100) / 10) c = x Mod 10 If a ^ 3 + b ^ 3 + c ^ 3 = x Then Print x End If x = x + 1 Loop

结束
4

18.数组:一种特殊的变量,在内存中的位置是连续的,用于存储一批类型、作用相同 的数据。几个相关概念:数组名、数组元素、数组元素名、数组元素下标、数组元素值。
数组必须先声明后使用。 Dim<数组名>(下标)As<数据类型> 例 1:Dim a(3) as integer 定义了 a(0),a(1),a(2),a(3)四个变量是数组类型 例 2: Dim Sc(3 to 6) As String 定义了 Sc(3), Sc(4), Sc(5)和 Sc(6),并且每个元素都是字符串型的

【数组实例】输入 10 个数字,依次存放到数组中,再将其逆序输出。
开始 i←1 i<=10 T 输入a d[i]←a i←i+1 F

i←10 i>=1 T 输出d[i] i←i-1 F

Dim d(1 To 10) Private Sub Command1_Click() i = 1 Do While i <= 10 a = InputBox("请输入数字:", i) d(i) = a i = i + 1 Loop i = 10 Do While i >= 1 Print d(i) i = i - 1 Loop End Sub

结束

19.冒泡排序的算法思想 (1)从最下面一个元素起,自下而上地比较相邻两个元素中的数据,将较小的数 值交换到上面一个元素。重复这一过程,直到处理完最后两个元素中的数据,称为一遍 加工。此时,最小的数据已经上升到第一个元素的位置。 (2)然后对余下的 i-1 个元素重复上述过程。 (3)由于每一遍加工都是将最小的元素像气泡一样浮至顶端,故称为冒泡排序。 例:有一组数据 23、61、24、15、89,问第二轮冒泡的第一次交换后数据排序的结 果如何?
5

冒泡过程: 原始数据 23 61 24 15 15 第一轮冒泡 (交换 3 次) 15 第二轮冒泡 (第 1 次交换) 24 15 23 15 61 61 24 24 24 24 61 89 89 89 89 89 89 89

答:第二轮冒泡的第一次交换后数据排序结果为 15、23、24、61、89

i=1

i<=n-1 T j=n

F

j >= i+1 T F d(j) < d(j-1)
T

F

交换d (j)与d (j-1)中的数据

i=1 Do While i <= n-1 j=n Do While j >= i+1 If d(j) < d(j - 1) Then t = d(j) d(j) = d(j - 1) d(j - 1) = t End If j=j-1 Loop i=i+1 Loop

j = j-1

i=i+1

接输出 部分

6

20.选择排序的算法思想(找最值——擂台法) (1)从第一个元素起,自上而下找出最小数,并记录下它的位置,将最小数交换 到第一个元素中。完成第一遍加工。 (2)然后对余下的 i-1 个元素重复上述过程。 (3)在每一遍加工中,只需交换一次位置即可 上例中的这组数据 23、61、24、15、89,用选择排序的过程如下: 原始数据 第一遍加工 第二遍加工 23 15 15 61 61 23 24 24 24 15 23 61 89 89 89

〖冒泡排序与选择排序的比较〗选择排序实际上是一种优化了的排序方法,它和冒 泡排序的区别在于减少了交换的次数,在每一遍的加工过程中,选择排序采用的方法是 通过遍历,记录下最值的位置,最后再将最值所在位置的数据与待排元素所在的位置进 行交换,因此每一遍加工只需交换依次位置。大大减少了算法的复杂度。
i=1

i<=n-1

F

k=i

j=i+1 F

j <= n T d(j) < d(k)
T

F

i=1 Do While i <= n-1 k=i j=i+1 Do While j <=n If d(j) < d(k) Then k=j End If j=j+1 Loop t = d(i) d(i) = d(k) d(k) = t i=i+1 Loop

k=j

j=j+1

交换 d (i) 与 d (k) 中的数据

i=i+1

7

21.擂台法实例:已知数组 d 中已经存放了 10 个数,输出其中的最大值 (1)先假设 d[1]中的数值是最大值,令 k← d[1] 。 (2)用 d[2]与 k 比较,若 d[2]大,则令 k← d[2],否则继续比较,直至 d[10] 如果还需输出最大值所在的位置,则还需跟踪数组元素的下标。如下图右。
开始 k=d(1) i=2
开始 k=d(1) i=2 , n=1

i<=10

F

i<=10

F F

d(i)>k T k=d(i)

F

d(i)>k T k=d(i) n=i

i=i+1
i=i+1

输出 k 结束

输出 k, n 结束

8

22.顺序查找的算法思想:按照数组元素的先后次序,从第一个元素开始遍历,逐个检 验是否和查找的数据相等。 例:在包含 10 个数字的数组中顺序查找一个符合要求的数。

Key = inputbox(“”) i=1 Do while i<=n If d(i) = Key Then print i Exit sub End If i=i+1 loop If i = n + 1 Then Print "在数组中没有找到" End If

23.对分查找的算法思想:先取数组中间的元素和关键字比较,若不相等则缩小近一半 的查找范围,在剩下的元素中继续查找。 由于对分查找每查找一次,查找范围就缩小一半,因此对分查找的效率要远高于顺 序查找,但它的前提是:待查找的数据必须是有序的。

9

start

i =1,j=n

i<=j t m=int((i+j)/2)

f

找 不 到

d(m)=key f t d(m)<key

t

f 找 到 输 出 m j=m-1 end

i =m+1

Key = inputbox(“”) i=1 j=n Do While i <= j If d(m) = Key Then print m Exit sub End If If d(m) < Key Then Else End If Loop Print "在数组中没有找到"
10


相关文章:
算法知识点总结
算法设计不分析》知识点总结 1.算法的渐进时间复杂度分析,能够对给定的代码段(伪代码段)进行时间复 杂度分析,能够对用关于问题规模 n 的函数表示的时间复杂度...
算法知识梳理
知识管理系统、问题与案例 45页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 算法知识梳理 隐藏>> 算法与程序设计...
算法分析与设计知识点总结
算法分析与设计知识点总结_计算机软件及应用_IT/计算机_专业资料。算法分析与设计知识点总结第一章 概述 算法的概念:算法是指解决问题的一种方法或过程,是由若干条...
算法分析知识整理
Explore 算法只对起始点可达的点 visit,包括 previsit 和 postvisit 标记 Explore(v)会生成以 v 为根的子搜索树 DFS 算法是对 G 中所有的点用 explore for ...
《算法初步》知识点总结
算法初步》知识点总结 1、在数学中,算法通常是指按照一定规则解决某一类问题的明确和有限的步骤.现在,算法 通常可以编成计算机程序,让计算机执行并解决问题. 算法...
算法设计与分析知识点
第一章 算法概述 1、算法的五个性质:有穷性、确定性、能行性、输入、输出。 算法的五个性质: 算法的五个性质 2、算法的复杂性取决于: 算法的复杂性取决于:...
信息算法知识梳理
信息算法知识梳理 隐藏>> 算法与程序设计 1.算法:为解决某一问题设计的确定的有限的步骤。 2.算法的主要特征: 有穷性、确定性、可行性、有 0 个或多个输入、...
算法基本语句知识点及典型例题
算法基本语句知识点及典型例题_数学_高中教育_教育专区。基本算法语句一、输入、输出语句和赋值语句 (1)输入语句 ①输入语句的一般格式 INPUT“提示内容” ;变量...
算法初步知识点归纳
算法初步知识点归纳_数学_高中教育_教育专区。第一章算法初步 1.1.1 算法的概念 1、算法概念: 在数学上, 现代意义上的 “算法” 通常是指可以用计算机来解决...
更多相关标签:
议论文文体知识梳理 | 鸿门宴知识点梳理 | 文言文知识点梳理 | 知识梳理 | 说明文文体知识梳理 | 小学数学知识点梳理 | 两学一做知识点梳理 | 初中美术学科知识梳理 |