回溯法英文

一、算法的基础知识1．用计算机解决问题的步骤：① 分析问题② 算法设计③ 描述算法④ 编程实现从上面的求解问题过程可以看出，关键在于前三步的解决：第一步就是解决模型的数据结构，第二步是解决问题的算法，第三步是形式化地描写算法。2．算法的定义： 算法是一组有穷的规则，它们规定了解决某一特定类型问题的一系列运算。算法可以理解为：程序（数据处理）+ 数据结构（数据组织）。3．算法的性质： ① 有限性 ② 确定性 ③ 输入输出(可以没有输入，但一定有输出) ④ 可行性 常见的算法有：穷举法、迭代法、递推法、递归法、回溯法、深度及广度搜索法、动态规划、构造法等等。 2.N-S图：1973年，美国学者I.Nassi和B.Shneiderman提出了一种用图形表示算法的方法，称为N-S流程图。N-S图包括顺序、选择和循环三种基本结构。3.程序设计语言：计算机中的语言分为低级语言和高级语言，而低级语言又分为机器语言和汇编语言。机器语言是一种CPU的指令系统，它是CPU可以识别的一系列有0和1这种二进制代码组成的指令。它依赖于机器，不同类型的计算机有不同的机器语言，机器语言的程序有许多机器指令组成，每条指令由操作码和地址码组成，数据和指令都放在不同的地址单元中。汇编语言它是一种符号语言，为了克服机器语言固有的缺陷，20世纪50年代中期出现，将难以记忆和辨别的机器语言操作码用有意义的英文单词作为“助记符”来代替0、1进行编程。高级语言，不再面向机器，而是接近人类的自然语言。常见的还有C/C++，Pascal,Basic,Java等。 数据类型、常量、变量及说明方法数据类型确定了该类型数据项的表示、取值范围以及所能参与的运算。在pascal语言中，无论常量还是变量都必须属于一个确定的数据类型。Pascal 提供了丰富的数据类型，可以分为三大类：① 简单类型：分为标准类型（整型、实型、字符型和布尔型）和自定义类型（枚举型和子界型）② 构造类型：分为数组类型、集合类型、记录类型和文件类型③ 指针类型这些数据类型中除了指针类型是动态数据类型外，其他的都是静态数据类型。另外，我们把整型、字符型、布尔型、枚举型和子界型称为顺序类型。 另：数据结构 -栈 队列– 并查集– 堆– 字母树 线段树 平衡树 动态树– 块状链表– 后缀数组– ……栈– 先进后出* 队列– 先进先出* 常见的应用有哪些？– 表达式求值– 搜索* 深搜* 广搜– 优化* 集合用代表元表示– representative?Getfather(x)* 初始的时候，所有元素各自成为一个集合– for i?1 to N* father[i]?i* 判断是否在同一集合– 代表元是否相同* return Getfather(x)=Getfather(y)* 合并两个集合– 将其中一集合的代表元指向另一集合代表元* father[Getfather(x)]?y并查集* 如何寻找代表元？– Getfather(x)* if father[x]=x– return x* return Getfather(father[x])* 如何优化？– 路径压缩* Getfather(x)– if father[x]=x>>return x– father[x]?Getfather(father[x])– return father[x]* 用途– 用于寻找最值* 大根堆、小根堆* 小根堆性质– 是一棵完全二叉树* i的父亲是谁？– idiv 2* i的左右儿子是谁？– 2i和2i+1– 树上的每棵子树，儿子的值不小于根堆排序– 建堆– 取出根– 删除根– 反复取、删的过程时间效率– O(Nlog N)块状数组* 增加一下题目内容– 询问区间最大值– 询问区间和– 询问区间内的和最大连续串– 可以修改一个数– 可以将一串连续的数变为一个值– 可以将一串连续的数旋转一下* 块状数组?块状链表– 可以将一串连续的数翻转一下可能有些难