03 第三章 问题求解与算法.pptx

第1页：大学计算机—计算的思想和方法课程封面

《大学计算机—计算的思想和方法》课程封面，标示教材名称、第3版与编著者信息。

第2页：课程简介

• 课程定位计算机公共教学核心课程大学通识教育类核心课程
• 教学目标
  • 培养学生信息素养
  • 培养学生计算思维
  • 传授计算科学知识
• 授课对象
  • 非计算机类各专业本科生
    • 第1章绪论
    • 第2章计算与计算机
    • 第3章问题求解与算法
    • 第4章数据与数据结构
    • 第5章计算机程序
    • 第6章计算机网络
    • 第7章计算科学前沿

第3页：第3章 问题求解与算法

• 3.1 问题与问题求解
• 3.2 算法与算法分析
• 3.3 算法设计及算法分类
• 3.4 搜索问题与查找算法
• 3.5 排序问题及排序算法
• 3.6 网络搜索问题

知识要点：问题，问题求解，问题归约，与或图，基元问题，问题求解系统，问题求解策略，算法式，启发式，问题解决过程，抽象，数学模型，数学建模，哥尼斯堡七桥问题计算机求解问题概念模型。

第4页：3.1 问题与问题求解

• 人类问题求解的思维过程
• 领域问题及形式化描述
  • 问题的形式化表示
  • 问题归约表示
  • 问题求解策略
  • 问题求解系统
• 问题抽象与数学建模
• 计算机求解问题模型
  • 问题解决过程
  • 计算计问题求解概念模型

第5页：人类问题求解的思维过程

• 问题及其来源
  • 问题是指需要解决还没有解决的事。
  • 来源
    • 社会实践、科学研究中发现和提出问题
    • 他人的任务
• 问题求解
  • 问题求解是人们为寻求问题答案，对问题及其所处的环境，根据知识和经验、条件、约束而进行的一系列思维活动。
  • 问题千差万别！问题求解策略不同，手段和方法各异
• 问题求解思维过程

第6页：问题分析

• 对问题给出的条件、目标和任务进行研究，明确问题的基本含义。
• 问题分析通常借助于数学、逻辑学等方法，例如：问题归约、问题抽象、数学建模等，其结果是问题的形式化，或建立一个抽象的问题模型，使问题的描述更加严谨。

第7页：提出假设

• 当问题分析清楚后，接下来是要寻找问题的答案，而答案和求解方法都是未知的。
• 提出假设就是在问题和答案之间寻找解决问题的方法和途径

第8页：检验假设

• 对提出的假设，进行验证，来检查其是否正确。
• 实践检验
  • 对问题给定相应的数据，检查假设的结果，看是否正确，从而来判断假设的真伪。
  • 许多物理、化学、生物实验就是这种模式。
• 理论验证
  • 假设是不可实验的

第9页：领域问题及形式化描述

• 问题的要素
  • 现实，已经具备的条件基础
  • 目标，对预期结果的描述或一种要求
• 问题形式化问题=｛现实，目标｝题解=目标－现实=｛A1，A2，…，An｝

第10页：问题归约表示

• 问题归约
  • 对于复杂的问题，直接进行问题求解往往是困难的
  • 问题归约就是对问题进行归纳和简化，从而把一个复杂问题转换为相对简单的问题。
• 三要素
  • 目标：即问题的初始描述。
  • 算子集：用来将给定问题变换为若干子问题的操作。
  • 基元问题集：已有解或其解十分明显可以直接描述的问题。

第11页：与或图

• “或”节点，原来问题被变换为若干子问题，而只需要解决其中之一便可解决原问题，代表这些子问题的节点称为相对于原问题的“或”节点。
• “与”节点，如果原问题被变换为缺一不可（均需解决）的若干子问题，那么代表这些子问题的节点称为相对于原问题节点的“与”节点，

第12页：问题求解策略--1算法式

• 算法式是指按照逻辑来求解问题的策略。如果问题有解，算法式一定可以得到问题的答案或解。
• 例如
  • 解一个6个字母的字谜，只要将这6个字母进行全排列，一定可以找到这个字。为了找到这个字，最坏情况下需要尝试720中不同的排列。
• 常用的算法式策略有：枚举、递归等方法
• 缺点：费时

第13页：问题求解策略--2启发式

• 根据以往解决问题的经验形成一些经验规则。启发式不能保证一定得到答案。
• 例如
  • 计算机突然不能上网。可能是网线没接好，也可能是网络协议问题，或者是病毒造成的。
• 常用的启发式策略
  • 手段目的分析，是指不断地将当前状态和目标状态进行比较，然后采取措施尽可能地缩小这两个状态之间的差异。
  • 顺向工作，也称顺向推理，是指从问题的已知条件出发，通过逐步扩展已有的信息直到问题解决的一种策略。
  • 逆向工作，又称逆向推理，是指从问题的目标状态出发，将问题解决的目标分解成若干子目标，直至使子目标按逆推途径与给定的条件建立直接联系或等同起来。

第14页：问题求解系统

• 求解问题就是要求解一个问题的结果，或找出一种从现实到目标的行动序列，并予以执行。
• 问题求解状态图
  • 状态
  • 活动
• 问题的解活动序列A2-A4-A6

第15页：例3-1汉诺塔问题

例3-1汉诺塔问题：（Tower of Hanoi Problem）

• 例3-1汉诺塔问题（Tower of Hanoi Problem）
• 在印度，有一个古老传说。在世界中心贝拿勒斯的圣庙里，安放着一块黄铜板，板上插着三根宝石针。梵天（印度教的主神勃拉玛）在创造世界的时候，在其中一根针上从下往上放下了由大到小的64个金片。这就是所谓梵塔，又称汉诺塔。
• 不论白天黑夜，都有一个值班的僧侣按照梵天不渝的法则，把这些金片在三根针上移来移去：一次只能移一片，并且要求不管在哪根针上，小片永远在大片的上面。当所有的64片都从梵天创造世界时所放的那根针上移到另外一根针上时，世界就将在一声霹雳中消灭，梵塔、庙宇和众生都将同归于尽。

第16页：汉诺塔问题求解策略

• 汉诺塔问题（Tower of Hanoi Problem）
• 启发式求解策略
  • 先把上面的N-1个盘子从第1根柱子上搬移到第2根柱子上，
  • 然后把第1根柱子上最下面的盘子搬移到第3根柱子上
  • 然后把第2根柱子上的N-1个盘子搬到第3根柱子上

第17页：汉诺塔问题解

• 汉诺塔问题（Tower of Hanoi Problem）

第18页：提出问题

• 发现问题，提出问题

本页主体为图片内容，文字版要点待对照原课件补充。

第19页：问题分析方法之--抽象

• 抽象的概念
  • 抽象（Abstraction），就是从众多的事物中抽取出共同的、本质性的特征，而舍弃其非本质的特征。
  • 抽象是一种重要的思维方法。
  • 共同特征是指那些能把一类事物与他类事物区分开来的特征，这些具有区分作用的特征又称本质特征。
  • 例如，对苹果、香蕉、葡萄等比较，它们共同的特性就是水果，从而抽象出水果这一概念。
• 抽象的层次性
  • 例如，对于在校大学生这一群体，从低到高，我们可以抽象为：大学生（具有高等学校学历）、学生（学习状态）、年轻人（按照年龄属性）、人（社会属性）、动物（生物学特征）、生物（生物学特征）、物质（按哲学观点）等。
  • 从不同的层次去认识和观察事物，是人们分析问题和思维的一部分。

第20页：事物抽象的方法

• 分离，就是暂不考虑研究对象与其它对象的联系，把要研究的对象单独的抽取出来进行考察，研究其属性。
• 提纯，就在研究对象的错综复杂的属性和联系中，去掉那些与研究目标关系不大的内容，更好的揭示其本质特征。
• 简略，提纯本身就是一种简化，简略是抽象的最后环节，它是对研究对象抽象结果的一种表达。目的都是要表达研究对象的本质性特性，从而产生一类新的概念。

第21页：数学模型

• 数学模型，对实际问题的数学抽象，用数学符号、数学式子、程序、框图等对实际问题本质属性的抽象而又简洁的刻划，用以描述客观事物的特征、内在联系及发展和运动规律。
• 通过数学模型，可以解释某些客观现象，预测未来发展规律，或能为控制某一现象的发展提供某种意义下的优化策略。

第22页：数学建模

• 数学模型是现实问题的抽象，数学模型用数学语言描述了现实问题的特征及其内部联系或与外界的联系。
• 应用知识从实际问题中进行抽象、提炼出数学模型的过程称为数学建模（Mathematical Modeling）

第23页：哥尼斯堡七桥问题

• 18世纪初，在普鲁士的哥尼斯堡（德国时期旧称哥尼斯堡Koenigsberg，现为俄罗斯的加里宁格勒，1946年由德国划入前苏联）的一个公园里，普雷格尔河从中穿过，河中有两个小岛，有七座桥把两个岛与河岸联系起来
• 有人提出一个问题：一个步行者怎样才能不重复、不遗漏地一次走完七座桥。

第24页：七桥问题的数学抽象

• 1736年，29岁的欧拉向圣彼得堡科学院递交了关于哥尼斯堡七桥问题的论文—“与位置几何相关的一个问题的解”。在论文中，欧拉将七桥问题抽象出来，把每一块陆地考虑成一个点，连接两块陆地的桥以线表示。并由此得到了如图一样的几何图形

第25页：图论

• 欧拉把问题归结为如图的“一笔画”问题，证明上述走法是不可能的，即从任意一点出发不重复的走遍每一座桥，最后再回到原点是不可能的。
• 在解答问题的同时，欧拉开创了数学的一个新的分支—图论（GraphTheory）。图论的创立，为人们问题求解提供了一种新的数学理论和工具。

第26页：模型的分类--1按特性分（1）

• 静态模型和动态模型
  • 静态模型是指要描述的系统各量之间的关系是不随时间的变化而变化的，即与时间变量无关，一般都用代数方程来表达。
  • 动态模型是指描述系统各量之间随时间变化而变化的规律的数学表达式，一般用微分方程或差分方程来表示。
• 连续时间模型和离散时间模型
  • 时间变量是在一定区间内变化的模型称为连续时间模型，用微分方程描述
  • 将时间变量离散化，所获得的模型称为离散时间模型，用差分方程描述

第27页：模型的分类--1按特性分（2）

• 参数模型与非参数化模型
  • 参数模型是指可以采用有限个参数进行描述的数学模型，并给定模型参数的值域。
  • 非参数模型是指系统的数学模型中非显式地包含可估参数。
• 集中参数模型和分布参数模型
  • 集中参数模型是指描述系统的特征、动态不随空间坐标变化的模型，通常把系统看作一个整体，只研究输入与输出之间的拟合关系，而对系统内部的过程和机理不予考虑，即把所有要素都看作属于空间一个点。
  • 分布参数模型则是描述系统特征、动态随空间坐标变化的模型。

第28页：模型的分类--1按特性分(3)

• 随机性模型和确定性模型
  • 确定性模型中变量间的关系是确定的
  • 随机性模型中变量之间的关系是以统计值或概率分布的形式给出的
• 线性模型和非线性模型
  • 线性模型中各量之间的关系是线性的，可以应用叠加原理，即几个不同的输入量同时作用于系统的响应，等于几个输入量单独作用的响应之和。
  • 非线性模型中各量之间的关系不是线性的，不满足叠加原理。

第29页：模型的分类--2按数学方法

• 几何模型
• 图论模型
• 微分方程模型
• 线形规划
• 非线性规划模型
• 概率论模型
• 等

第30页：模型的分类--3按应用领域

• 经济学数学模型
• 管理学数学模型
• 社会学数学模型
• 地质学数学模型
• 气象学数学模型
• 天文学数学模型
• 工程学数学模型
• 生物学数学模型
• 医学数学模型等此阿，还有许多特殊的问题模型，如：交通运输问题模型、经济决策模型等。

第31页：数学建模的基本步骤

• 模型准备
• 模型假设
• 模型建立
• 模型求解
• 模型分析
• 模型检验
• 模型应用

第32页：计算机问题求解

• 数学模型可以对问题进行严谨的形式化描述
• 计算机系统可以实现问题求解的自动化
  • 计算机的海量存储、高速度，高精度、自动运行和不知疲倦
  • 设备智能化
  • 计算机在各种各样的问题求解中正在发挥越来越重要的作用

第33页：计算机问题求解概念模型

• 计算机问题求解概念模型

本页主体为图片内容，文字版要点待对照原课件补充。

第34页：举例1：阿基米德分牛问题

• 太阳神有一牛群，由白、黑、花、棕四种颜色的公、母牛组成。在公牛中，白牛数多于棕牛数，多出之数相当于黑牛数的1/2+1/3；黑牛数多于棕牛数，多出之数相当于花牛数的1/4+1/5；花牛数多于棕牛数，多出之数相当于白牛数的1/6+1/7。在母牛中，白牛数是全体黑牛数的1/3+1/4；黑牛数是全体花牛数1/4+1/5；花牛数是全体棕牛数的1/5+1/6；棕牛数是全体白牛数的1/6+1/7。
• 问这牛群是怎样组成的？

第35页：问题分析

• 这是一个看起很复杂的问题，问题包含了许多约束条件，求解的量也很多。
• 为了更好的理解问题的含义，引入数学变量，设：白、黑、花、棕四种颜色的公牛、母牛数量分别为x1,x2,x3,x4和y1,y2,y3,y4，这样可以将要求的问题解表示成一个表格

第36页：数学建模

• 在公牛中
  • 白牛数多于棕牛数，多出之数相当于黑牛数的1/2+1/3；
  • 黑牛数多于棕牛数，多出之数相当于花牛数的1/4+1/5；
  • 花牛数多于棕牛数，多出之数相当于白牛数的1/6+1/7。
• 在母牛中
  • 白牛数是全体黑牛数的1/3+1/4；
  • 黑牛数是全体花牛数1/4+1/5；
  • 花牛数是全体棕牛数的1/5+1/6；
  • 棕牛数是全体白牛数的1/6+1/7。
• 根据问题的约束条件，可以建立下列约束关系

第37页：3.1 问题与问题求解

• 3.1 问题与问题求解
• 3.2 算法与算法分析
• 3.3 算法设计及算法分类
• 3.4 搜索问题与查找算法
• 3.5 排序问题及排序算法
• 3.6 网络搜索问题

知识要点：算法，算法描述，流程图，N-S流程图，伪代码，算法分析，算法复杂性，P问题，NP问题，NP完全问题，NP难度问题，时间复杂性。

第38页：3.2 算法与算法分析

• 算法及其描述
  • 算法的特征
  • 算法描述
  • 算法的正确性
• 算法复杂性分析
  • 时间复杂性分析
  • P问题与NP问题
  • 空间复杂性

第39页：算法及其特征

• 算法的概念
  • 算法（Algorithm）一词最早出现在数学中，原意是关于数字的运算法则。
  • 算法指问题求解的方法及求解过程的描述，是一个精心设计的计算序列，用以解决一类特定的问题。
• 算法的特征
  • 确定性：算法中的每一条指令必须有确定的含义，不能产生二义性。
  • 可行性：算法描述的步骤在计算机上是可行的。
  • 有穷性：一个算法必须在执行有穷步后结束，每一步必须在有穷的时间内完成。
  • 输入：一个算法可以有零个或多个输入。
  • 输出：算法执行过程中或结束后要有输出结果，或者产生相应的动作指令。

第40页：算法描述--1自然语言描述

• 用自然语言将问题的求解步骤清晰的表述出来即可。在步骤描述上，要求语言简练，层次清晰。
• 为表述方便，每一步可以加上标号，例如Step1，Step2…等
• 对于复杂的步骤，可以进行进一步展开，如Step1.1,Step1.2等

第41页：自然语言描述举例

• 举例

本页主体为图片内容，文字版要点待对照原课件补充。

第42页：自然语言描述的特点

• 采用自然语言描述算法可以较好的描述问题的大的求解思路，对于比较精细的求解步骤自然语言在描述上比较困难。
  • 例如，对于判断、分支、重复，特别是这些逻辑的嵌套，自然语言描述时显得不够清晰直观。
• 更具体的细节可以使用流程图和伪代码来描述。

第43页：算法描述--2流程图描述

• 流程图（Flow Diagram）
  • 由图框和流程线组成的图形，图框表示各种类型的操作，图框中的文字和符号表示操作的内容，流程线表示操作的先后次序。
  • 流程图可以很好的表达顺序、分支和重复逻辑，可以较好的描述数据处理、算法描述及系统功能描述等
• 流程图常用图形符号

第44页：流程图举例

• 优点
  • 简单直观，可很好的表达顺序、分支和重复逻辑结构，可以很自然的将算法流程图转化成计算机程序。
• 不足
  • 对于复杂的算法，流程图手工绘制和修改都比较麻烦

第45页：N-S流程图

• 1973年，美国学者I.Nassi和B.Shneiderman提出了一种新的流程图形式，这种流程图完全去掉了流程线，算法的每一步都用一个矩形框来描述，在框内还可以包含其他框的流程图形式。即由一些基本的框组成一个大的框，这种流程图又称为N-S结构流程图，又称“盒图”
• NS图有三种基本结构，分别表示：顺序、选择和循环

第46页：N-S流程结构

• NS图有三种基本结构，分别表示：顺序、选择和循环

第47页：N-S流程结构（举例）

• 举例
• 输入10个数，求最大值，并输出

本页主体为图片内容，文字版要点待对照原课件补充。

第48页：N-S流程图特点

• NS图把整个程序写在一个大框图内，这个大框图由若干个小的基本框图构成。虽然去掉了流程线，但可读性较差。
• 为结构化编程设计，不便于表达面向对象的编程思想（受时代局限）

第49页：算法描述--3伪代码描述

• 伪代码（Pseudocode）
  • 是一种介于自然语言和计算机程序设计语言（Pascal、C语言等）之间的文字和符号来描述算法的工具，并以编程语言的书写形式来描述算法。
  • 伪代码没有严格的语法规则，只是遵循简单的书写约定
• 伪代码不是用户和分析师的工具，而是设计师和程序员的工具

第50页：伪代码一般的书写形式

• 每一条指令占一行，指令后不跟任何符号（Pascal和C中语句要以分号结尾）；
• 书写上的“缩进”表示程序中的分支程序结构，用缩进取代传统Pascal中的begin和end语句和C中的“{”和“}”来表示程序的块结构可以大大提高代码的清晰性；同一模块的语句有相同的缩进量，次一级模块的语句相对与其父级模块的语句缩进；
• 变量名和保留字不区分大小写
• 赋值语句用符号←表示，x←exp表示将exp的值赋给x
• 使用与程序设计语言类似的关键字表达选择、循环结构
  • If,if eles,switch
  • while,do while,for
• 数组元素的存取有数组名后跟“[下标]”表示，结构变量或对象采用变量名后加点和域名方式访问

第51页：举例--输入三个数，输出其最大值

• 问题求解算法的伪代码描述

本页主体为图片内容，文字版要点待对照原课件补充。

第52页：算法描述方法的比较

• 自然语言
  • 适合描述大的求解思路
  • 细节描述上比较麻烦
• 流程图
  • 精确描述，适合描述实现细节
  • 流程图绘制和修改麻烦
• 伪代码
  • 折中了自然语言和流程图的优点，在大的求解思路和具体细节上都可以使用

第53页：算法分析

• 传统意义下，就是对算法进行正确性、时间复杂性和空间复杂性的分析，从而来评价算法的优劣，或估计算法实现后的运行效果。
• 其他评价指标
  • 在网络化环境下，一个图形图像压缩算法，压缩比就是一种重要的算法性能指标
• 算法分析通常是对同一类问题的不同求解算法之间的性能比较

第54页：算法正确性分析

• 计算三角形面积算法
• 算法的正确性层次
  • 对于一组数据能够得出正确的结果。
  • 对于精心挑选的、苛刻的测试用例算法可以得到正确的结果。
  • 对于一切合法的输入数据，算法得到的结果都是正确的。

第55页：时间复杂性

• 算法的时间复杂性（Time Complexity）是指根据该算法编写的程序在运行过程中，从开始到结束所需要的时间。
• 从算法中选取一种对于所研究的问题来说是基本运算的操作作为元操作，以该元操作重复执行的次数作为算法的时间度量。例如，排序类算法，用数据的比较和移动作为元操作。

第56页：时间复杂性分析

• 定义：设f(n)和g(n)是从自然数集到非负实数集的两个函数，如果存在一个自然数n0和一个常数c>0，使得n≥n0，f(n)≤cg(n)，则记为f(n)=O(g(n))，称g(n)是f(n)的上界；如果是n≥n0，f(n)<cg(n)，称g(n)是f(n)的严格上界，记为f(n)=o(g(n))。
• 一个算法中元操作重复执行的次数与求解问题的规模（问题长度）n呈某个函数关系T(n)
  • 设T(n)是算法的执行时间，n是问题规模，f(n)为n的函数，若T(n)=O(f(n))，则称f(n)为算法的时间复杂性上界。时间复杂性通常用O(f(n))来表示
• 算法的执行时间与问题长度无关，则该算法的时间复杂度记为O(1)，表示常数时间复杂度

第57页：时间复杂性分析（举例）

• 举例
• ①语句（3）～（6）的运行时间为常数时间，均为O(1),则总时间为O(1)
• ②语句（2）为循环控制语句，执行次数为n-i-1，每次循环执行时间为（3）～（6)的时间，因此，总的时间为(n-i-1)·O(1)。
• ③语句（1）为外重循环，执行次数为n-1次，第i次时间消耗为(n-i-1)·O(1)
• 因此有：

第58页：算法时间复杂度与求解问题长度的关系

• 假设计算机执行一次基本操作需要的时间为1ms
• 常见算法时间复杂度

第59页：常见时间复杂度函数

• 函数关系

本页主体为图片内容，文字版要点待对照原课件补充。

第60页：计算机速度对求解问题长度的影响

• 计算机速度对求解问题长度的影响

本页主体为图片内容，文字版要点待对照原课件补充。

第61页：举例--TSP

举例--TSP：（Traveling Salesman Problem）问题

• 举例--TSP（Traveling Salesman Problem）问题
• 19世纪初，爱尔兰数学家、物理学家、天文学家哈密顿提出：有n个城市，城市之间的距离都是已知的，现有一旅行商从某个城市出发到每个城市旅行，途中只能经过每个城市一次，最终回到出发点，求最短的一条路径。
• 问题分析
  • 1.从某城市出发，最后回到该城市
  • 2.每个城市只能访问一次
  • 3.所走路程最近
• 解决上述问题，最简单的方法就是列出所有的路径，计算每条路径的长度，然后取一个最小值。

第62页：TSP问题模型

• TSP问题要从图G的所有路线中求取最小成本的一条路线，而从初始点出发的路线数量共有(n-1)!条，即等于除初始结点外的n-1个结点的排列数，因此TSP问题是一个排列问题
• 通过枚举(n-1)!条路线，从中找出一条具有最小成本的路线的算法，其计算时间显然为O(n!)。
• 例如：

第63页：小蜜蜂采蜜的启示

• 2010年10月25日，英国一项最新研究说，在花丛中飞来飞去的小蜜蜂显示出了轻易破解“旅行商问题”的能力，如能理解蜜蜂的解决方式，将有助于人们改善交通规划和物流等领域的工作。
• 英国伦敦大学皇家霍洛韦学院等机构的研究人员对蜜蜂在花丛间采蜜的行为进行了研究：
  • 蜜蜂每天都要在蜂巢和花朵间飞来飞去，为了采蜜而在不同花朵间飞行是一件很耗精力的事情，因此实际上蜜蜂每天都在解决“旅行商问题”。
  • 他们利用人工控制的假花进行了实验，结果显示，不管怎样改变花的位置，蜜蜂在稍加探索后，很快就可以找到在不同花朵间飞行的最短路径。

第64页：TSP问题的应用

• 如何规划最合理高效的道路交通，以降低成本，减少拥堵。
• 如何更好地规划物流，以减少运营成本。即：一个物流配送公司，将n个客户的订货沿最短路线全部送到，如何确定最短路线。
• 在互联网环境中如何更好地设置交换（Switch）和路由（Router）节点，以更高效地让信息流动。

第65页：空间复杂性

• 算法的空间复杂度是指算法运行中对存储空间的需求，记作：S(n)=O(f(n))
• 交换两个变量a和b内的值
  • temp=a;
  • a=b;
  • b=temp；其中，temp是一个临时变量。

第66页：空间复杂性（续）

• 不增加临时变量
  • a=a+b;
  • b=a-b;
  • a=a-b;

第67页：P问题与NP问题

• P问题
  • 问题求解算法的时间复杂度是该问题实例规模n的多项式函数，则这种可以在多项式时间内解决的问题属于P（Polynomial，多项式）类问题，通俗地称所有复杂度为多项式时间的问题为易解问题
• 非确定性（Non-Deterministic）问题
  • 有些计算问题是确定性的，只要按照公式推导，按部就班的一步步来，就可以得到结果。
  • 无法按部就班的计算得到。比如，找大质数的问题。有没有一个公式，可以一步步推算出下一个质数应该是多少呢？这样的公式是没有的。
• NP问题，非确定性多项式问题
  • 非确定问题通常存在这样的算法，它不能直接告诉答案是什么，但可以计算某个可能的结果是否正确。这个可以验证“猜算”的答案正确与否的算法，假如可以在多项式（polynomial）时间内计算出来，就叫做非确定性多项式问题，即NP问题。

第68页：NP问题的分类

• NP完全（NP-complete）问题
  • 如果这个问题的所有可能答案，都是可以在多项式时间内进行正确与否的验算的话，就叫非确定多项式完全问题，即NP-Complete问题。
• NP难度（NP-hard）问题
  • 非确定性多项式完全问题可以用穷举法得到答案，一个个检验下去，最终便能得到结果。
  • 但是这样算法的复杂程度，是指数关系，因此计算的时间随问题的复杂程度成指数的增长，很快便变得不可计算了，这就是NP-hard问题。

第69页：举例--NP-hard问题

• 美国的数据加密标准DES（Data Encryption Standard）。DES采用长度为64位密钥（实际密钥56位，8位用于奇偶校验），对64位二进制数据加密，得到64位密文数据。

第70页：3.2 算法与算法分析

• 3.1 问题与问题求解
• 3.2 算法与算法分析
• 3.3 算法设计及算法分类
• 3.4 搜索问题与查找算法
• 3.5 排序问题及排序算法
• 3.6 网络搜索问题

知识要点：算法设计，穷举法，递推法，递归法，回溯法，迭代法，分治法，贪心法，动态规划法。

第71页：3.3 算法设计及算法分类

• 穷举法
• 递推法
• 递归法
• 回溯法
• 迭代法
• 分治法
• 贪心法
• 动态规划法

第72页：穷举法

• 穷举法，又称暴力算法，顾名思义就是对于要求解的问题，列举出问题解空间的所有可能的情况，并逐个测试，找出符合问题条件的解，从而得到问题的解。
• 通常情况是，穷举法为一个NP-hard问题，即非确定性多项式难解问题

第73页：例3-4百钱买百鸡问题

• 问题：公元5世纪末，我国古代数学家张丘建在他的《算径》中提出了著名的“百钱买百鸡问题”：鸡翁一，值钱五，鸡母一，值钱三，鸡雏三，值钱一，百钱买百鸡，问翁、母、雏各几何？

第74页：问题分析与建模

• 问题：公元5世纪末，我国古代数学家张丘建在他的《算径》中提出了著名的“百钱买百鸡问题”：鸡翁一，值钱五，鸡母一，值钱三，鸡雏三，值钱一，百钱买百鸡，问翁、母、雏各几何？

第75页：算法

• 算法描述

本页主体为图片内容，文字版要点待对照原课件补充。

第76页：算法分析

• 上述算法是一个三重循环，最内层的条件判断需要执行19*32*97次，即58976次。
• 在条件判断中，利用了整数的求模运算，如果将鸡雏的个数设为3z，可以避免该项判断，且可减少内重循环次数。

第77页：算法二

• 将鸡雏的个数设为3z，可以避免该项判断，且可减少内重循环次数。

第78页：例3-5：0-1背包问题

• 给定n种物品和一个背包，物品i的重量是Wi，其价值为Vi，背包的容量为Wm。应如何选择装入背包的物品，使得装入背包中物品的总价值最大？

第79页：问题分析

• 所谓0-1背包问题，是指在选择装入背包的物品时，对每种物品i只有2种选择，即装入背包或不装入背包。不能将物品i装入背包多次，也不能只装入物品i的一部分。
• 采用穷举法，将物品放入背包所有可能的情况包括放置1件,2件,3件，…，n件，共2n-1种不同的选择方案。
• 对每种方案都计算一遍，再考虑背包的最大存放重量Wm，在满足条件的情况下，计算包内物品的总价值，求解总价值最大的情况。

第80页：算法设计

• 使用一个n位二进制的计数器，来表示n件物品放入背包的情况，若第i位为0表示第i件物品未放入背包，为1表示第i件放入背包。所有的选择方案正好构成n位二进制数的所有二进制状态，去掉一个全0，对应数字1～2n-1。
• 根据物品情况计算物品的总重量，若没有超过包的限重，记录此情况下的总价值，使用提高门槛法判断此情况是否为已测试条件下总价值最大，若是则记录下此时的总价值，从第1种情况开始，逐个测试，直到测试完2n-1种的情况为止

第81页：算法描述

• 0-1背包问题算法

本页主体为图片内容，文字版要点待对照原课件补充。

第82页：问题的解空间

• 穷举法的基本思想就是遍历这颗树，枚举所有的情况，进行判断，如果重量不超过Wm,且价值最大的方案就是问题的解。
• 在实际遍历时，有很多情况是没有意义的，此时，可以中途停止对某些不可能得到最优解的子空间的进一步搜索，从而提高搜索效率
• n种物品，树的高度为n，共有2n-1个节点，构成一颗满二叉树。

第83页：递推法

• 递推算法是一种根据递推关系进行问题求解的方法。
  • 基本思想是把一个复杂的庞大的计算过程转化为简单过程的多次重复，该类算法利用了计算机速度快和自动化的特点。
  • 通过已知条件，利用特定的递推关系可以得出中间推论，直至得到问题的最终结果。
• 递推关系，递推关系可以抽象为一个简单的数学模型
  • 给定一个数的序列a0,a1,…,an,…若存在整数n0，使当n>n0时，可以用等号（或大于号、小于号）将an与其前面的某些项ai（0<i<n)联系起来，这样的式子称为递推公式，又称递推关系。

第84页：顺推法与逆推法

• 顺推法，从已知条件出发，按照递推关系一步步地递推，直至求出问题的最终结果。
• 逆推法，在不知道初始条件的情况下，从问题的结果出发，经递推关系逐步推算出问题的解，这个问题的解也是问题的初始条件。

第85页：例3-6:斐波纳契数列

例3-6:斐波纳契数列：（Fibonacci Sequence）

• 例3-6:斐波纳契数列（Fibonacci Sequence）
• 斐波纳契数列（Fibonacci Sequence），又称黄金分割数列: 1、1、2、3、5、8、13、21、……
• 斐波那契数列是意大利数学家列昂纳多·斐波那契（Leonardo Fibonacci）（1170年～1240年）首先研究的，斐波那契数列是一个奇妙的数列，随着数列项数的增加，前一项与后一项之比越来越逼近黄金分割的数值0.6180339887…

第86页：问题分析

• 递推公式
  • F0=1，F1=1，Fn=F(n-1)+F(n-2)（n>=2，n∈N*）
• 问题分析
  • 从斐波那契数列的定义可知，斐波那契数列的第1项为1，第2项也为2，递推关系是当前项等于前2项之和。因此，通过顺推可以得到

第87页：求斐波拉契数列的顺推算法

• 算法3-5求斐波拉契数列的顺推算法
• //求斐波那契数列第10项的值并输出
• f[0]=1
• f[1]=2
• n=2
• while (n<10)
• {
• f[n]=f[n-1]+f[n-2]
• n=n+1
• }
• write(f[9])

第88页：例3-7:卡车穿越沙漠问题

• 一辆重型卡车要穿过800公里的沙漠，已知卡车每公里耗油1升，卡车总载油能力为400升，显然卡车装满一次油是无法穿越沙漠的，因此卡车司机需要在沿途建立几个储油点，使卡车能够顺利穿越沙漠。
• 要让卡车以消耗最少的汽油穿越沙漠，试问司机沿途最少需要建立几个储油点？每个储油点需要存储多少汽油？

第89页：问题分析

• 设沿途设置n个储油点，用倒推法来解决这个问题，从终点向起点倒推，可以逐一求出每个储油点的位置及储存量。

第90页：分析

• （1）为了消耗最少的汽油，最后一个储油点应该离终点400公里，且此处储油400升，即储油点m=1处离终点dist[1]=400公里，储油量oil[1]=400升。
• （2）为了在m=1处储存400升汽油，卡车最少从储油点m=2处开两趟载满油的车到储油点m=1处，则储油点m=2处储油量oil[2]=400*2=800升，其中，400升用于储存在m=1处，400升用于从m=2到m=1处的油料运输。要将400生油从储油点m=2处运送到到储油点m=1处，则从m=2到m=1处至少需开两趟，需要开三次路程，因此有dist[2]=dist[1]+400/3公里。

第91页：分析（续1）

• （3）为了在储油点m=2处储存800升汽油，卡车最少从储油点m=3处开三趟载满油的车到储油点m=2处，则储油点m=3处储油oil[3]=400*3=1200升，其中，800升用于储存在m=2处，400升用于从m=3到m=2处的油料运输。储油点m=3处到储油点m=2处至少开三趟需要开五次路程，因此，dist[3]=dist[2]+400/5公里。

第92页：分析（续2）

• （4）依次类推，为了在m=k处储存oil[k]=k*400升汽油，则储油点m=k+1处储油oil[k+1]=(k+1)*400，其中400升用于往返运送的消耗。要在m=k处储存k*400升油，从m=k+1处至m=k处至少需要k+1趟，最后一次无需返回m=k+1处，因此两地往返最小需2(k+1)-1=2k+1次路程，则储油点离终点dist[k+1]=dist[k]+400/(2*k+1)。

第93页：分析（续3）

• （5）最后一个储油点为m=n，它至起点的距离为800-dist[n]，储油为oil[n]=n*400升，为了在m=n处储n*400升汽油，卡车最少从起点开n+1趟满载车至m=n处，需要开2(n+1)-1=2n+1次路程，总耗油量为(800-dist[n])*(2n+1)，即起点储油量为oil[n]+(800-dist[n])*(2n+1) =n*400+(800-dist[n])*(2n+1)。

第94页：储油点部署问题逆推算法

• 算法3-6储油点部署问题逆推算法
• //问题求解逆推算法
• k=1;
• dist[1]=400;

  第95页：递归法

  • 在问题求解思想上，递推是从已知条件出发，一步步的递推出未知项，直到问题的解。
  • 从思想上讲，递归也是递推的一种（即：逆推法），只不过它是对待解问题的递推，直到把一个复杂的问题递推为简单的易解问题。
  • 然后再一步步的返回去，从而得到原问题的解。

  第96页：求N!递归法描述

  • 求n!的递归定义
  • 递推求解

  本页主体为图片内容，文字版要点待对照原课件补充。

  第97页：例3-8：求斐波那契数列值的递归算法

  • 算法3-8求斐波那契数列递归算法
  • //函数fib返回第n(n>1)个斐波那契数列的值
  • int fib(int n)
  • {
  • if (n = =0）
  • return(1)
  • else
  • if (n= =1)
  • return(2)
  • else return (fib(n-1)+fib(n-2))
  • }

  第98页：例3-9：Hanoi塔问题递归算法

  • // N为盘子数目,三根柱子分别为from，to和temp，分别表示起始柱子，目标柱子和临时柱子
  • void hanoitower(n,from,to,temp)
  • {
  • if (n>0) {
  • //把from柱子上的n-1格盘子搬移到temp柱子上，用to柱做临时柱子
  • hanoitower(n-1,from,temp,to);
  • movedisk(from,to);
  • //把temp柱子上的n-1格盘子搬移到to柱子上，用from柱做临时柱子
  • hanoitower(n-1,temp,to,from);
  • }
  • }

  第99页：回溯法

  • 在现实世界中，许多问题不是通过确定的计算公式得到的，只能通过试探、回溯的方法来求解。
  • 回溯法试图在问题的所有解空间树中，从根节点开始，按照深度优先的方法对树进行搜索。当搜索到某一个节点时，判断该节点是否包含在问题的解集中，如果在，继续深度搜索。如果不在，则回溯到该节点的父节点开始下一个试探。如果确定了某个节点不在解集中，逐层向父节点回溯。
  • 回溯法
    • “试探－失败返回－再试探”的问题求解方法，例如：某迷宫问题

  第100页：老鼠走迷宫

  • 一只实验室的小老鼠被用来做迷宫智力实验。科学家在迷宫的一角放上一块奶酪，小老鼠要在最快时间内找到奶酪。图片来源：百度百科

  第101页：例3-10：八皇后问题

  • 1850年，数学家高斯（Gauss）提出了这一问题，即：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。

  第102页：数学建模

  • 数学建模

  本页主体为图片内容，文字版要点待对照原课件补充。

  第103页：求解思路

  • 设棋盘的横坐标为i，纵坐标为j。当某个皇后占了位置(i,j)时，在这个位置的垂直方向、水平方向和对角线方向都不能再放其它皇后。定义三个整型数组：a[8]，b[15]，c[15]。
  • 数组a[8]标识各列是否放置了皇后，如果a[j]=0，表示第j列没有皇后，a[j]=1表示第j列已经放置了皇后；

  第104页：求解思路（续）

  • 数组b[15]标识主对角线（左上至右下）是否放置了皇后，共15条主对角线，主对角线上格子的坐标满足i-j+7依次是14～0，正好对应b[15]数组的15个元素下标，若(i,j)位置的主对角线无皇后，则b[i-j+7]=0，有皇后则b[i-j+7]=1；
  • 数组c[15]标识从对角线是否放置了皇后，共有15条从对角线，每条从对角线上格子的坐标满足i+j依次为0～14，对应c[15]数组的15个元素下标，如果某条从对角线上已经有皇后，则为c[i+j]=1，否则为0。

  第105页：求解八皇后问题的回溯算法

  • //试探第i个皇后，即第i行要放置的皇后位置
  • void queen(int i) {
  • for(j=0;j<8;j++) {

    第106页：回溯法pk穷举法

    • 从本质上讲，回溯法也是一种穷举法，也是通过“枚举－判断”来寻找问题的解，不同的是，穷举法每次枚举的都是问题的一个完整解，而回溯法每次测试的是解的一部分。
    • 例如，在走迷宫问题中，当遇到岔路时，枚举其中的一条路，来验证是否满足约束条件（即查看该路是否可以通行），如果满足，该路就加入到已有的部分解集中，从而得到更大的部分解集。如果一条路不能满足约束条件，则选择下一条路，如果没有可选的路，则回溯到该岔路的上一个路口。持续该过程，直到部分解集扩展为原问题的一个解，即找到一条到出口的通路。利用递归编程，可以找出所有的问题解。

    第107页：迭代法

    • 迭代法又称辗转法，是一种不断用变量的旧值递推新值的过程，跟迭代法相对应的是直接法（或者称为一次解法），即一次性解决问题。
    • 严格的讲，和递归法一样，迭代法是一种编程技术

    第108页：例3-11：使用辗转相除法求两数的最大公

    • 例3-11：使用辗转相除法求两数的最大公约数
    • 辗转相除法，又称欧几里得算法
    • 两个整数的最大公约数（亦称公因子）是能够同时整除它们的最大的正整数。

    第109页：求两数的最大公约数的辗转相除法减法实现

    • 算法3-11a求两数的最大公约数的辗转相除法减法实现
    • //辗转相除法求两数a和b的最大公约数g
    • int gcd(a,b)
    • {
    • while (a!=0 && b!=0) {
    • if（a>b）
    • a=a-b
    • else
    • b=b-a;
    • }
    • if (a!=0)
    • return a
    • else
    • return b
    • }

    第110页：两数的最大公约数的辗转相除法模除实现

    • 算法3-11b求两数的最大公约数的辗转相除法模除实现
    • //辗转相除法求两数a和b的最大公约数g
    • int gcd(a,b)
    • {
    • t = a % b;
    • while (t!=0){
    • a=b;
    • b=t;
    • t=a%b;
    • }
    • return b
    • }

    第111页：例3-12求一元非线性方程f

    例3-12求一元非线性方程f：(x)=0的解

    • 例3-12求一元非线性方程f(x)=0的解
    • 分析
      • 求方程解最简单的方法是二分法（Bisectionmethod），又称二分区间法。
      • 其基本思想是：设f(x)在区间[a,b]上为连续函数，如果f(a)·f(b)<0，则f(x)在区间[a,b]上至少有一个根。如果f(x)在[a,b]是单调递增或单调递减的，则f(x)在区间[a,b]上只存在一个实根，

    第112页：求方程f(x)=0在区间[a,b]内的根

    求方程f(x)=0在区间[a,b]内的根：的迭代算法算法3-12求方程f(x)=0在区间[a,b]内的根的迭代算法Step1：求a，b的中点坐标x=(a+b)/2。Step2：计算f(x)。Step3：若|f(x)|<ε（ε为一个指定的极小值，控制求解精度，如10-4），则转Step6，否则继续下面的迭代计算。Step4：修改有根区间4.1若f(x)与f(a)同号，说明x更接近方程的根，此时a←x，b不变；4.2若f(x)与f(b)同号，此时a不变,b←x；Step5：转Step1Step6：输出x，即方程的近似解。Step7：结束。

    • 求方程f(x)=0在区间[a,b]内的根的迭代算法算法3-12求方程f(x)=0在区间[a,b]内的根的迭代算法Step1：求a，b的中点坐标x=(a+b)/2。Step2：计算f(x)。Step3：若|f(x)|<ε（ε为一个指定的极小值，控制求解精度，如10-4），则转Step6，否则继续下面的迭代计算。Step4：修改有根区间4.1若f(x)与f(a)同号，说明x更接近方程的根，此时a←x，b不变；4.2若f(x)与f(b)同号，此时a不变,b←x；Step5：转Step1Step6：输出x，即方程的近似解。Step7：结束。

    第113页：分治法

    • 各个击破，分而治之（Divide and Conquer）
    • 特征
      • 问题可以分解为若干个规模较小的相同问题
      • 问题分解出的各个子问题是相互独立的，即子问题之间不包含公共子问题。
      • 问题规模缩小到一定程度时可以容易地解决
      • 问题分解出的子问题的解可以合并为该问题的解

    第114页：例3-13

    • 问题
      • 给定一个长度为n的整数数组，编写一个求出其最大值和最小值的分治算法
    • 分析
      • 当数组中只有1个数时，可以直接给出结果，如果有2个数时，则一次比较即可得出结果。
      • 当n>2时，我们可以将数组分成两个元素个数较小的数组，分别求解他们的最大和最小值，最后比较两个数组的解来得到原问题的解

    第115页：求数组中最大最小值的分治算法

    求数组中最大最小值的分治算法：// a[0..n]：数组，s：子问题数组开始下标，e：子问题数组结束下标// max：数组中元素的最大值，min：数组中元素的最小值maxmin(a,s,e,*max,*min){if (e-s<=1) {

    第116页：贪心法

    • 贪婪法的基本思想是：从当前情况出发根据某个优化目标做最优选择，而不考虑各种可能的整体情况，从而避免了为找最优解要穷尽所有可能的问题求解方法。
    • 在贪心算法中，选取一个量度标准作贪婪处理所得到该量度意义下的最优解并不一定是问题的最优解，可能是次优解。

    第117页：例3-14：用贪心法求解0-1背包问题

    • 0-1背包问题：给定n种物品和一个背包，物品i的重量是Wi，其价值为Vi，背包的容量为Wm。应如何选择装入背包的物品，使得装入背包中物品的总价值最大？
    • 求解0-1背包问题，采用穷举法可以找到最优解，但时间复杂度为O(2n)，是一个NP难解问题。

    第118页：贪心法求解0-1背包问题

    • 贪心算法的基本思路：为了使包内物品的总价值最大，先计算出所有物品的单位价值，
    • 然后从单位价值由高到低的顺序依次选择物品放入背包，在不超过背包限重的情况下尽可能放更多的物品。

    第119页：贪心法求解0-1背包问题（举例）

    • 举例
    • 物品列表
    • 按局部贪心方法，各物品单位价值从高到低分别6、2、7、4、5、3、1，
      • 选取物品6、物品2、物品7、物品1，总重量恰好100，总价值为120。
      • 而事实上这并不是最优解，最优解是物品6、物品2、物品4，总重量虽然为90，但总价值是130。

    第120页：背包问题

    • 背包问题：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。
    • 背包问题与0-1背包问题类似，所不同的是在选择物品i装入背包时，可以选择物品i的一部分，而不一定要全部装入背包，1≤i≤n。

    第121页：贪心法求背包问题的基本思想

    • 首先计算每种物品单位重量的价值Vi/Wi，
    • 然后，依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。
    • 若将这种物品全部装入背包后，背包内的物品总重量未超过Wmax，则选择单位重量价值次高的物品并尽可能多地装入背包。
    • 依此策略一直地进行下去，直到背包装满为止。

    第122页：算法3-15求解背包问题的贪心算法

    算法3-15求解背包问题的贪心算法：Knapsack (n, maxweight,v[],w[],x[]){Sort(n,v,w);

    第123页：其他背包问题

    • 完全背包问题：有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的体积是c，价值是w。将哪些物品装入背包可使这些物品的体积总和不超过背包容量，且价值总和最大。
    • 多重背包问题：有N种物品和一个容量为V的背包。第i种物品最多有n件可用，每件体积是c，价值是w。求解将哪些物品装入背包可使这些物品的体积总和不超过背包容量，且价值总和最大。
    • 分组背包问题：有N件物品和一个容量为V的背包。第i件物品的费用是c，价值是w。这些物品被划分为若干组，每组中的物品互相冲突，最多选一件。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

    第124页：3.3 算法设计及算法分类

    • 3.1 问题与问题求解
    • 3.2 算法与算法分析
    • 3.3 算法设计及算法分类
    • 3.4 搜索问题与查找算法
    • 3.5 排序问题及排序算法
    • 3.6 网络搜索问题

    知识要点：搜索，关键字，主关键字，次关键字，顺序查找，折半查找，平均查找长度。

    第125页：3.4 搜索问题与查找算法

    • 搜索问题
    • 顺序查找
    • 折半查找

    第126页：搜索问题

    • 在人们的生活和工作中
      • 到教室找一个同学
      • 在商场，找一样商品
      • 在书店、图书馆，找一本书
      • 在网络中，查找信息
    • 搜索（Search），就是指仔细查找、搜寻的意思
      • 搜索的对象
      • 搜索的范围

    第127页：基本概念

    • 文件（File），若干条结构相同的记录构成，文件一般存储在外存储器中，用于永久的保存信息。
    • 记录，是由若干相关字段取值构成的数据整体。
    • 字段（Field）是最小的不可分割的数据单位，每个字段都有一个特定的数据类型。
    • 关键字（Keyword），就是记录中的一个字段，用它来标志和控制一条记录。
      • 主关键字，能够唯一的标志与控制一个记录的关键字称为主关键字
      • 其它的称为辅关键字（次关键字）

    第128页：基本概念（举例）

    • 举例
    • 图书数据文件

    本页主体为图片内容，文字版要点待对照原课件补充。

    第129页：搜索问题的抽象

    • 给定一个文件（或表）F={R1,R2,…,Rn}，其中Ri是以Ki（i=1,2,…,n）为主关键字的记录。现给定一个主关键字K，在文件F中确定具有主关键字K的记录R的地址或序号i，使得Ki=K。
    • 结果有两种可能：一种是找到了主关键字值为K的记录Ri，称为查找成功；第二种情况是，没有找到主关键字值为K的记录，称为“查找失败”。

    第130页：搜索算法

    • 生活中的查找
      • 如何查找的？
      • 查找的方法已经随着生活经验存在于我们的大脑中
    • 顺序查找
    • 折半查找
    • 查找类算法性能评价
      • 时间复杂性
      • 查全率
      • 查准率

    第131页：顺序查找

    • 顺序查找就是在要查找范围内，对一个个对象进行比较，看是否是需要查找的对象
    • 顺序查找算法
      • 从最后一条记录开始，按照记录的逻辑次序，将给定的关键字K和当前记录的关键字逐个比较，若某个记录的关键字和给定值相等，则查找成功，返回成功记录的序号；
      • 反之，直到比较完第一条记录，找不到与给定值相等的记录，则查找失败，返回查找失败标记。

    第132页：算法3-17线性表顺序查找算法

    • 数据结构：
    • 算法描述：//在线性表st中查找关键字k，n为元素个数。//若查找成功，返回其在表中的序号，否则返回0int SearchSequential(st[],n,k){st[0] = k;

      第133页：算法分析--1

      • 查找类算法元操作—比较运算。
      • 平均查找长度（Average Search Length，ACL）是指为为查找关键字，确定记录在查找表中的位置，关键字需和表中元素比较次数的期望值。

      第134页：算法分析--2

      • 查找结果
        • 成功
        • 不成功
      • 假设查找成功和不成功的概率相等，应有Pi=1/2n。对于不成功的比较次数均为n+1。
      • 因此，有：

      第135页：折半查找

      • 若文件（或表）中的记录是按照关键字有序的，假定关键字值满足K1≤K2≤…≤Kn
      • 折半查找的基本思想
        • 首先选取表的中间元素，设序号为m=⌊(1+n)/2
        • ，元素Rm将数据表分成大致相等的两部分{R1,R2,…,Rm-1}和{Rm+1,Rm+2,…,Rn}。先对Km和K作比较，比较结果有三种情况：
        • K=Km：查找成功，返回元素序号m。
        • K<Km：折半查找子表{R1,R2,…,Rm-1}。
        • K>Km：折半查找子表{Rm+1,Rm+2,…,Rn}。

      第136页：折半查找算法

      折半查找算法：//在线性表st中折半查找关键字k，若成功返回其在表中的位置，否则返回0int Serach_Binary(st[],n, k){low = 1; high = n;while (low<=high) {m = (low+high)/2;if (k = = st[m] )return m;elseif (k<st[m] )high = m-1;else low = m+1}return 0;}

      • 折半查找算法//在线性表st中折半查找关键字k，若成功返回其在表中的位置，否则返回0int Serach_Binary(st[],n, k){low = 1; high = n;while (low<=high) {m = (low+high)/2;if (k = = st[m] )return m;elseif (k<st[m] )high = m-1;else low = m+1}return 0;}

      第137页：折半查找算法（举例）

      • 举例
      • 查找的关键字为K=6，折半查找过程

      第138页：算法分析

      • 二叉检索树的高度（层数）和元素的数目n满足关系

      第139页：算法分析（续）

      • 查找成功的平均检索长度
      • 例如：对于n=27-1=127，顺序查找查找成功的平均检索长度为64，而折半查找查找成功的平均检索长度为6。

      第140页：3.4 搜索问题与查找算法

      • 3.1 问题与问题求解
      • 3.2 算法与算法分析
      • 3.3 算法设计及算法分类
      • 3.4 搜索问题与查找算法
      • 3.5 排序问题及排序算法
      • 3.6 网络搜索问题

      知识要点：排序，稳定排序，内部排序，选择排序，交换排序，插入排序，归并排序，基数排序，外部排序。

      第141页：3.5 排序问题及排序算法

      • 排序问题
      • 选择排序
      • 交换排序
      • 插入排序
      • 归并排序
      • 基数排序

      第142页：排序问题

      • 排序（Sorting），就是把任意文件（或表）按照指定的关键字排列成一个有序文件（或表）的过程，有时又称作“分类”。
      • 例如：
        • 将一堆数由小到大或由大到小排列；
        • 在站队时，按身高由高到低或由低到高排列等；
        • 玩扑克牌（多关键字的排序问题），出牌慢，为什么？

      第143页：排序问题的抽象

      • 假如给定一个记录序列（或表）F={R1,R2,…,Rn}，其中Ri（i=1,2,…,n）为序列中的第i个记录，关键字为Ki。所谓排序就是对记录序列中的记录重新排序成一个新的序列F' = {R1' ,R2' ,…,Rn' }，使得它们的关键字值满足非减（或非增）的顺序。即对任意的i<j（i,j=1,2,…,n），有Ki'
        • Kj'（或Ki'≥Kj'）。

      第144页：基本概念

      • 稳定排序：当初始时序列中Ki=Kj，且i<j时，排序后记录Ri仍然在记录Rj前，这样的排序称为稳定排序。
      • 内部排序：是指被排序的记录较少，在整个排序过程中，所有的记录和中间结果都放在内存中。
      • 外部排序：当被排序的记录数量较大时，记录不能一次全部放在内存中，在整个排序过程中，必须对记录在内存和外存之间来回传递和交换

      第145页：内部排序的分类

      • 排序算法的基本操作
        • 比较
        • 移动
      • 按照排序效率分类
        • 简单排序，时间复杂度为O(n2)
        • 高效排序，时间复杂度为O(nlog2n)
        • 基数排序，时间复杂度为O(d·n)
      • 按照排序过程划分
        • 选择排序
        • 交换排序
        • 插入排序
        • 归并排序
        • 基数排序。

      第146页：选择排序

      • 基本思想：从被排序的文件（或表）中依次选出关键字最小、次小、…的记录，从而实现排序。
      • 根据算法效率
        • 简单选择排序，时间复杂性为O(n2)
        • 树形选择排序（锦标赛排序），O(nlog2n)
        • 堆排序，O(nlog2n)

      第147页：简单选择排序

      • 从1..n个记录中选出关键字最小的记录，和R1交换，最小的记录放到第1个单元。
      • 从2..n个记录中选出关键字最小的记录，和R2交换，次小的记录放到第2个单元。
      • 依次进行，共需要n-1遍，最大的记录留在第n个单元。

      第148页：简单选择排序算法

      简单选择排序算法：//对表f进行简单选择排序，n为元素个数int SimpleSelectionSort(*f, n){for (i=1; i<n; i++) {j = SelectionMin(f,i, n);

      第149页：简单选择排序算法（举例）

      • 举例
      • F = {21，30，19，20，35，11，75}, n=7
      • 简单选择排序过程
        • 第1次循环i=1, j=6,则R1和R6交换
        • 第2次循环i=2, j=3,则R2和R3交换。。。
        • 第6次循环i=6,
      • 排序结果F’ = {11，19，20，21，30，35，75}

      第150页：算法分析

      • 简单选择排序，共进行n-1遍
      • 第i遍，从n-i+1个数中选择一个最小的数。从n-i+1个数中选择最小的数需要n-i次比较运算
      • 因此简单选择排序总的比较次数为n(n-1)/2。时间复杂度为O(n2)。

      第151页：交换排序

      • 交换类排序（Exchange Sorting）就是将两两元素进行比较，如果发生逆序，即Ri>Rj（i<j），则将两个元素交换，最后得到一个非递减的序列（正序）。
      • 交换分类有标准交换、成对交换和穿梭交换三种，比较著名的交换类排序有冒泡排序和快速排序。

      第152页：冒泡排序

      • 冒泡排序（Bubbles Sorting）属于标准交换分类
      • 基本思想
        • 第1遍：首先将Rn和Rn-1进行比较，若发生逆序，则交换；否则，比较Rn-1和Rn-2，直到R2和R1比较。这样，第一遍结束后，将把关键值最小的元素移到了第一个单元。最小的元素就像“气泡”一样冒到了顶上，共比较n-1次。
        • 第2遍：和第1遍一样，依次将Rn和Rn-1进行比较、Rn-1和Rn-2，直到R3和R2比较。这样，第2遍结束后，将把关键值次小的元素移到了第2个单元。共比较n-2次
        • 继续上述过程，逐遍进行，在进行i遍时，在前i-1遍得到的结果中，Rn,Rn-1,Rn-2,…,Ri+1和Ri依次两两比较，如发生逆序，则交换位置。

      第153页：算法3-20冒泡排序

      算法3-20冒泡排序：（Bubbles Sorting）算法//对表f进行冒泡排序，n为元素个数int BubbleSort(*f, n){for (i=1; i<n; i++) {flag = True;for (j=n; j>i; j--) {if ( f[j].key < f[j-1].key ) {

      第154页：算法3-20冒泡排序（举例）

      • 举例
      • F = {21，30，19，20，35，11，75}, n=7
      • 冒泡排序过程
        • 第1遍：{11，21，30，19，20，35，75}
        • 第2遍：{11，19，21，30，20，35，75}
        • 第3遍：{11，19，20，21，30，35，75}
        • 第4遍：未交换，退出循环
      • 排序结果F’ = {11，19，20，21，30，35，75}

      第155页：算法分析

      最好情况下（原始序列为正序，

      ：非递减，R1

      最坏情况下（原始序列为逆序，

      ：非递增，R1≥R2≥…≥Rn）

      第156页：快速排序

      • 快速排序（Quick Sort）方法是由英国计算机科学家霍尔（Charles Antony Richard Hoare，1934年1月11日～）于1962年提出的，后来又有许多人提出了修正方案，这类方法统称为快速排序（分类）。1980年图灵奖得主
      • 基本思想
        • 按照一定原则选择某个元素作为控制记录（轴元素），首先把控制元素移动到其正确的位置，使得元素序列中所有比它小的元素都在它的前面，所有比它大的元素都在它的后面。
        • 按照同样的原则处理左右两个子序列，控制记录不再移动位置。
      • 时间复杂性
        • 最坏情况：O(n2)
        • 最好情况：O(nlog2n)

      第157页：插入排序

      • 插入排序（Insert Sorting），是指将一个记录插入到一个已经排序好的有序序列中，从而得到一个新的、记录个数加1的有序序列。
      • 基本思想（1）初始序列为｛R1｝，只有一个元素的序列一定是有序的。（2）依次将R2，R3，…，Rn插入到上次的有序序列中，分别得到长度为2,3,..,n的有序序列，从而实现长度为n的记录序列的排序。

      第158页：插入排序算法

      插入排序算法：//对顺序表f作直接插入排序，n为元素个数int InsertSort(*f){for (i=2; i<= n; i++)InsertR(f,i-1,f[i]);}//将记录r插入到长度为i的有序表中，得到长度为i+1的有序表int InsertR(*f, int i, r){f[0] = r；//设置“哨兵”，元素从1号位置开始存放j = i;while (r<f[j]) {f[j+1] = f[j];

      第159页：插入排序算法（举例）

      • 举例
      • 输入顺序：21，30，19，20，35，11，75
      • 插入排序过程
        • 第1遍：{21}
        • 第2遍：{ 21，30}
        • 第3遍：{19，21，30}
        • 第4遍：{19，20，21，30}
        • 第5遍：{19，20，21，30，35}
        • 第6遍：{11，19，20，21，30，35}
        • 第7遍：{11，19，20，21，30，35，75}
      • 排序结果F’ = {11，19，20，21，30，35，75}

      第160页：算法分析

      • 最好情况
        • 原始记录序列本身是非递减有序的（称为“正序”），则在插入过程（Insert过程）中只进行一次比较，不发生数据的移动，
        • 因此，总的比较次数为n-1次，数据移动的次数为0。
      • 最坏情况
        • 如果原始记录序列是非递增有序的（称为“逆序”），则在插入记录Ri过程（Insert过程）中需进行i+1次比较（包括一次和“哨兵”的比较），数据移动i+1次（包括长度为i的有序表往后移动一个位置和将R移到正确的位置—第1个单元）
        • 总的比较次数和移动次数均为

      第161页：其他插入排序

      • 折半插入排序（binary insertion sort）,采用折半查找方法寻找插入点位置，从而提高效率。
      • 希尔排序（Shell Sort），是针对直接插入排序算法的改进，是将整个有序序列分割成若干小的子序列分别进行插入排序，该方法又称缩小增量排序，由美国人Donald Shell（1924年3月1日～,）于1959年提出，因而得名。

      第162页：归并排序

      • 把两个或多个有序文件（或表）合并成一个有序文件（或表）的过程称归并（Merge）。当归并文件有k个时，称为k路归并
      • 归并排序（Merge Sorting）--重复利用归并思想对任意文件（或表）进行排序的过程

      第163页：二路归并排序

      • （1）将文件（或表）F={R1,R2,…,Rn}中的每一个记录看作一个文件（或表），它们都是有序的（仅含一个记录）。
      • （2）把子文件（或子表）按照相邻的位置分成若干对（如果文件或子表个数是奇数，最后一个单独一组）。
      • （3）对每对中的子文件（或子表）进行二路归并。归并后，每个子文件都是有序的，且子文件的个数减少一半。
      • （4）重复步骤（2）~（4），直到归并成一个有序文件为止。

      第164页：二路归并排序（举例）

      • 举例
      • 2路归并过程

      本页主体为图片内容，文字版要点待对照原课件补充。

      第165页：二路归并算法

      二路归并算法：// a、b为两个有序序列，长度分别为m和n，将他们合并成一个长度为m+n的有序序列cint Merge2( a[],b[],c[]){m = a.length; n = b.length;i=1; j=1; k=1;while (i<=m && j<=n) {if (a[i].key<b[j].key)c[k] = a[i++];elsec[k] = b[j++];k++;}if (i<=m)

      第166页：基数排序

      • 基数排序是一种借助于多关键字排序的思想实现的对单个逻辑关键字进行排序的方法。
      • 多关键字，例如

      第167页：十进制基数分类

      • 假定被分类的关键字值是十进制整数，将每位数字视为一个关键字，个位为最低关键字，十位为次低关键字，以此类推。
      • 进行十进位基数分类的过程是：
        • 把输出分成10个桶（0桶，1桶，…，9桶），
        • 整个分类过程分成d遍（d为被分类数字的最多位数）。

      第168页：分类过程

      • 第一遍：首先对最低关键字（个位）、进行桶分类，对序列中的每一个数由前向后将最低位数字相同的数字依次放在对应的上述10个桶中（如个位为6的放在6桶中），直到所有数字都分完。
      • 第二遍：把上一遍各桶内的数字，按照从0桶,1桶，…，9桶的编号次序，同一桶内按由上倒下的次序收集起来，作为第二遍的输入，再按次关键字（十位）的状态把各个数分别放入0,1,2,…,9对应的桶内。
      • 然后再把各个桶内的数字收集起来作为第三遍的输入，继续上述过程，直到按照最高关键字的状态把所有数再分到对应的桶内。
      • 最后，按照0桶，1桶，2桶，…，9桶的顺序把各桶内的数据收集起来（同一桶内按由上倒下的次序收集）就得到所要的结果。

      第169页：分类过程（举例）

      • 举例
      • 设要分类的记录的关键字值为{26，56，11，68，80，34，75，52，86}

      第170页：举例（续）

      • 收集第一遍桶分类结果{80，11，52，34，26，56，86，68}

      第171页：3.5 排序问题及排序算法

      • 3.1 问题与问题求解
      • 3.2 算法与算法分析
      • 3.3 算法设计及算法分类
      • 3.4 搜索问题与查找算法
      • 3.5 排序问题及排序算法
      • 3.6 网络搜索问题

      知识要点：搜索引擎，PageRank算法，网页重要性度量，正向链接，反向链接。

      第172页：3.6 网络搜索问题

      • 搜索引擎及其工作原理
        • 搜索引擎的概念及分类
        • 全文搜索引擎工作原理
        • 网页索引数据库
      • PageRank排序算法
      • 搜索引擎的启示

      第173页：搜索引擎的概念

      • 搜索引擎产生的背景
        • 20世纪90年代，互联网发展开始进入民用阶段，Internet上信息资源及服务器数量急剧增加
        • 普通网络用户想找到自己所需的信息简直如同大海捞针
      • 搜索引擎（Search Engine）是指根据一定的策略、运用特定的计算机程序从互联网上搜集网页、图片、ftp文件等各类信息，在对信息进行组织和处理后，为用户提供检索服务的系统。

      第174页：搜索引擎的产生

      • 1990年，McGill University学生Alan Emtage等人发明Archie（档案检索系统），被称为搜索引擎的鼻祖。
        • WorldWideWeb尚未出现
        • Archie是第一个自动索引互联网上匿名FTP网站文件的程序，用户输入精确的文件名，Archie会告诉用户哪一个FTP地址可以下载该文件。它只是一个可搜索的FTP文件名列表，还不是真正的搜索引擎。
      • 1993年，出现蜘蛛程序（Spider）程序。第一个“蜘蛛”程序由麻省理工学院学生Matthew Gray开发，现代意义上的搜索引擎开始初露端倪
        • 开始它只用来统计互联网上的服务器数量，
        • 后来发展为能够捕获网址（URL）

      第175页：搜索引擎的发展--1第一代搜索引擎

      • 1994年4月，美国斯坦福大学电机工程系博士生大卫·费罗（David Filo）和杨致远（Jerry Yang），共同创办超级目录索引Yahoo！，建立了自己的网络指南信息库。分类目录包括：政治、经济、文化、科技、房地产、教育、艺术、娱乐、体育等各方面
      • 目录（Directory）搜索引擎，或主题查询型搜索引擎，按照主题建立分类索引，形成一个树形分类体系结构
      • 2002年10月9日，雅虎放弃了网站目录搜索，改为默认Google的搜索结果，标志着第一代搜索引擎的寿终正寝

      第176页：搜索引擎的发展--2第二代搜索引擎

      • 第一代搜索引擎的问题
        • 人工分类整理搜索目录，网页数量剧增，人工根本无法处理。
        • 只能针对工作人员输入的关键词和描述进行搜索，无法针对网页内容进行搜索
      • 使用蜘蛛程序取代人工分类和输入关键词、描述的方式，自动在网络上寻找资料，并自动将取得的结果存入资料库中

      第177页：第二代搜索引擎的代表

      • 谷歌（Google）搜索引擎
        • 1998年9月7日，美国斯坦福大学博士生拉里·佩奇（LarryPage）和赛吉·布林（SergeyBrin）创立谷歌（Google）。
        • 1999年6月，通过站点www.google.com开始向互联网用户提供搜索服务，为信息内容供应商（综合性或专业性网站）提供联合品牌的网络搜索解决方案。
        • Google推出PageRank、动态摘要、网页快照等功能革新，改变了搜索引擎的定义。
      • 2000年1月，百度（Baidu）在北京中关村成立
      • 2004年，雅虎结束了与Google的合作，推出了自己的第二代搜索引擎，重新进入搜索市场。在国内，百度逐渐取代新浪、搜狐，成为最主要的中文第二代搜索引擎。

      第178页：搜索引擎的分类

      • 分类目录
      • 全文索引
      • 元搜索引擎
      • 垂直搜索引擎
      • 集合式搜索引擎
      • 门户搜索引擎
      • 免费链接列表

      第179页：搜索引擎--1分类目录

      • 分类检索、目录索引等，是因特网上最早提供WWW资源查询的服务
      • 通过搜集和整理因特网的资源，根据搜索到网页的内容，将其网址分配到相关分类主题目录的不同层次的类目之下，形成像图书馆目录一样的分类树形结构索引。
      • 目录索引无需输入检索信息，只要根据网站提供的主题分类目录，层层点击进入，便可查到所需的网络信息资源。

      第180页：搜索引擎--2全文搜索引擎

      • 拥有自己的检索程序（Indexer），俗称“蜘蛛”（Spider）程序或“机器人”（Robot）程序，自建网页数据库，搜索结果直接从自身的数据库中调用。如：Google和百度
      • 租用其他搜索引擎的数据库，并按自定的格式排列搜索结果，如Lycos搜索引擎
      • 自动信息搜集
        • 定期搜索，Google一般是28天
        • 提交网站搜索，即网站拥有者主动向搜索引擎提交网址

      第181页：搜索引擎--3元搜索引擎

      • 1995年出现元搜索引擎（Meta Search Engine），本身并不直接面向用户提供服务，而是向其他搜索引擎提供全文网页搜索服务
      • 元搜索引擎就是通过一个统一的用户界面帮助用户在多个搜索引擎中选择和利用合适的（甚至是同时利用若干个）搜索引擎来实现检索操作，将结果返回给用户。图片来源：百度百科

      第182页：搜索引擎—4其它搜索引擎

      • 垂直搜索引擎
        • 专注于特定的搜索领域和搜索需求（例如：房源搜索，机票搜索、旅游搜索、生活搜索、小说搜索、视频搜索等）
        • 垂直搜索需要的硬件成本低
      • 集合式搜索引擎
        • 类似元搜索引擎，区别在于它并非同时调用多个搜索引擎进行搜索，而是由用户从提供的若干搜索引擎中选择
      • 门户搜索引擎
        • 自身既没有分类目录也没有网页数据库，其搜索结果完全来自其他搜索引擎的一类搜索
      • 免费链接列表（Free For All Links，FFA），指一般只简单地滚动链接条目，部分有简单的分类目录，规模要比Yahoo！等目录索引小很多。

      第183页：全文搜索引擎工作原理

      • 全文搜索引擎的构成

      本页主体为图片内容，文字版要点待对照原课件补充。

      第184页：全文搜索引擎的构成

      • （1）搜索器，负责从Web上抓取网页，为提高网页搜集速度，通常可以启动上百个搜集器同时工作。搜集器同时对搜集回来的网页内容进行分析处理，包括调用切词软件以提取关键词和摘要、提取网页URL、记录网页元信息（如作者、修改日期、长度等），并将这些内容存入原始数据库。
      • （2）索引器，将原始数据库的内容重新组织，建立索引数据库，以提高检索效率。
      • （3）检索器，根据查询项和索引数据库的内容，找到匹配的网页后，进行相关度计算并排序，然后通过用户接口返回给用户。
      • （4）用户接口，接受用户的查询请求，将它转发给检索器。

      第185页：网页索引数据库

      • 搜索器（蜘蛛程序）蜘蛛程序获得网页等资源信息保存到原始数据库
      • 根据特定的权值计算方法进行计算，得到网页中每一个关键词的权值，存入网页索引数据库，并建立索引数据表，以实现快速查询。

      第186页：举例—搜索引擎的使用

      • 用户接口—搜索条件输入页面

      本页主体为图片内容，文字版要点待对照原课件补充。

      第187页：举例（续）

      • 用户接口—搜索结果页面

      本页主体为图片内容，文字版要点待对照原课件补充。

      第188页：网页搜索中的查找和排序

      • 网页搜索的问题
        • 搜索结果页面多。不同于传统的查找类算法
        • 结果如何排序？
      • 基于链接的评价
        • 一个网页的重要性取决于它被其它网页链接的数量，特别是一些已经被认定是“重要”的网页的链接数量。
        • 互联网商业化因素，这种评价体制在某种程度上缺乏客观性。
      • 基于访问大众性的评价
        • 多数人选择访问的网站就是最重要的网站
        • 趋众性特点，这种评价体制与基于链接的评价有着同样的缺点

      第189页：网页排名的PageRank排序算法

      • 拉里·佩奇（Larry Page）于1997年在斯坦福大学读研究生时开发
      • PageRank思想
        • 基于接入链接的数量和重要性对网页进行评级，也就是通过网络的集体智慧确定哪些网站最有用
        • PageRank根据网站的外部链接和内部链接的数量和质量来衡量网站的价值，每个到页面的链接都是对该页面的一次投票（Vote），被链接的越多，就意味着被其他网站投票越多。

      第190页：网页链接关系

      • 正向链接，一种是网页到其它网页的超链接
      • 反向链接，其他网页到该网页的超链接

      第191页：PageRank值及其计算

      • 计算思想
        • 假定所有网页的排名是相同的，并且根据这个初始值，算出各个网页的第一次迭代排名，
        • 然后再根据第一次迭代排名算出第二次的排名。
        • 从理论上证明了不论初始值如何选取，这种算法都保证了网页排名的估计值能收敛到他们的真实值。
      • 可能的问题
        • 可能导致死循环
        • 二维矩阵相乘的问题，可以用迭代的方法解决这个问题

      第192页：搜索引擎的启示

      • 互联网正在成为人们创新的重要源泉
      • PR值的计算法则导致了人们对链接的着魔。人们忙于争夺、交换甚至销售链接
      • Google修改PR值计算规则
        • 来自缺乏内容的“link farm”（链接工厂）网站的链接将不会提供页面的PageRank
        • 从PageRank较高的页面得到链接但是内容毫不相关，也不会提供页面的PageRank
        • 降低对PageRank的更新频率

      第193页：本章小结

      3.1 问题与问题求解问题，问题求解

      ，问题归约，与或图，基元问题，问题求解系统，问题求解策略，算法式，启发式，问题解决过程，计算机求解问题概念模型。

      3.2 算法与算法分析算法，算法描述

      ，流程图，N-S流程图，伪代码，算法分析，算法复杂性，P问题，NP问题，NP完全问题，NP难度问题，时间复杂性。

      3.3 算法设计及算法分类算法设计，穷举法

      ，递推法，递归法，回溯法，迭代法，分治法，贪心法，动态规划法。

      3.4 搜索问题与查找算法搜索，关键字

      ，主关键字，次关键字，顺序查找，折半查找，平均查找长度

      3.5 排序问题及排序算法排序，稳定排序

      ，内部排序，外部排序，选择排序，交换排序，插入排序，归并排序，基数排序，十进制基数分类

      3.6 网络搜索问题搜索引擎

      ，PageRank算法，网页重要性度量，正向链接，反向链接，PR值

      第194页：问题思考

      • 问题求解是一类泛在问题，在计算学科中讲问题求解，有何特别意义？
      • 从问题的解空间讲，枚举法和回溯法有何不同？
      • 排序和检索是两类基元问题，从搜索引擎的发展和PageRank算法，你得到了怎样的启示？

      第195页：本章结束

      本章结束：Unit 1 Web基础谢谢大家

      • Unit 1 Web基础谢谢大家