第9章 贪心法

算法与生活教案章节一：引言教学目标：1. 让学生了解算法在生活中的重要性。

2. 培养学生对算法的兴趣和好奇心。

教学内容：1. 介绍算法的定义和特点。

2. 举例说明算法在生活中的应用。

教学步骤：1. 引入话题：讨论日常生活中遇到的问题，如排序、查找等。

2. 介绍算法的定义：算法是解决问题的一系列步骤。

3. 讲解算法的特点：有穷性、确定性、可行性。

4. 举例说明算法在生活中的应用：地图导航、购物网站推荐等。

章节二：排序算法教学目标：1. 让学生了解排序算法的概念和作用。

2. 培养学生掌握排序算法的应用。

教学内容：1. 介绍排序算法的定义和分类。

2. 讲解冒泡排序算法的基本思想和步骤。

3. 分析冒泡排序算法的优缺点。

教学步骤：1. 引入话题：讨论日常生活中遇到的排序问题。

2. 介绍排序算法的定义：将一组数据按照特定顺序排列的算法。

3. 讲解冒泡排序算法：比较相邻元素，交换位置，重复执行直到排序完成。

4. 演示冒泡排序算法的实现。

5. 分析冒泡排序算法的优缺点：简单易懂，但效率较低。

章节三：查找算法教学目标：1. 让学生了解查找算法的概念和作用。

2. 培养学生掌握查找算法的应用。

教学内容：1. 介绍查找算法的定义和分类。

2. 讲解线性查找算法的基本思想和步骤。

3. 分析线性查找算法的优缺点。

教学步骤：1. 引入话题：讨论日常生活中遇到的查找问题。

2. 介绍查找算法的定义：在一组数据中查找特定元素的过程。

3. 讲解线性查找算法：从数据的一端开始，逐个比较直到找到或遍历完。

4. 演示线性查找算法的实现。

5. 分析线性查找算法的优缺点：简单易懂，但效率较低。

章节四：递归算法教学目标：1. 让学生了解递归算法的概念和特点。

2. 培养学生掌握递归算法的应用。

教学内容：1. 介绍递归算法的定义和特点。

2. 讲解递归算法的实现和应用。

3. 分析递归算法的优缺点。

教学步骤：1. 引入话题：讨论日常生活中遇到的可以分解为更小问题的问题。

新版骗分导论THE NEW GUIDE OF CHEATING IN INFORMATICS OLYMPIAD目录第1章绪论第2章从无解出发2.1 无解情况2.2 样例——白送的分数第3章“艰苦朴素永不忘”3.1 模拟3.2 万能钥匙——DFS第4章骗分的关键——猜想4.1 听天由命4.2 猜测答案4.3 寻找规律4.4 小数据杀手——打表第5章做贪心的人5.1 贪心的算法5.2 贪心地得分第6章C++的福利6.1 快速排序6.2 “如意金箍棒”第7章“宁为玉碎，不为瓦全”第8章实战演练第9章结语第1章绪论在Oier中，有一句话广为流传：任何蒟蒻必须经过大量的刷题练习才能成为大牛乃至于神牛。

这就是著名的lzn定理。

然而，我们这些蒟蒻们，没有经过那么多历练，却要和大牛们同场竞技，我们该怎么以弱胜强呢？答案就是：骗分那么，骗分是什么呢？骗分就是用简单的程序（比标准算法简单很多，保证蒟蒻能轻松搞定的程序），尽可能多得骗取分数。

让我们走进这本《新版骗分导论》，来学习骗分的技巧，来挑战神牛吧！第2章从无解出发2.1 无解情况在很多题目中都有这句话：“若无解，请输出-1.”看到这句话时，骗分的蒟蒻们就欣喜若狂，因为——数据中必定会有无解的情况！那么，只要打出下面这个程序：printf(“-1”);就能得到10分，甚至20分，30分！举个例子：NOIP2012第4题，文化之旅题目描述Description有一位使者要游历各国，他每到一个国家，都能学到一种文化，但他不愿意学习任何一种文化超过一次（即如果他学习了某种文化，则他就不能到达其他有这种文化的国家）。

不同的国家可能有相同的文化。

不同文化的国家对其他文化的看法不同，有些文化会排斥外来文化（即如果他学习了某种文化，则他不能到达排斥这种文化的其他国家）。

现给定各个国家间的地理关系，各个国家的文化，每种文化对其他文化的看法，以及这位使者游历的起点和终点（在起点和终点也会学习当地的文化），国家间的道路距离，试求从起点到终点最少需走多少路。

解题思路多代入法二叉树度叶子结点就是没有孩子的结点，其度为0，度为二的结点是指有两个子数的结点。

注意树的度和图的度区别叶子结点二叉排序树完全二叉树若设二叉树的深度为h，除第h 层外，其它各层(1～h-1) 的结点数都达到最大个数，第h 层所有的结点都连续集中在最左边，这就是完全二叉树。

完全二叉树——只有最下面的两层结点度小于2，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树；最优二叉树（就是哈弗曼树）平衡二叉树平衡二叉树，又称AVL树。

它或者是一棵空树，或者是具有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子树和右子树的高度之差之差的绝对值不超过1.。

满二叉树满二叉树——除了叶结点外每一个结点都有左右子叶且叶结点都处在最底层的二叉树,。

除最后一层无任何子节点外，每一层上的所有结点都有两个子结点（最后一层上的无子结点的结点为叶子结点）。

也可以这样理解，除叶子结点外的所有结点均有两个子结点。

节点数达到最大值。

所有叶子结点必须在同一层上.本题主要考查一些特殊二叉树的性质。

若二叉树中最多只有最下面两层的结点度数可以小于2，并且最下面一层的叶子结点都依次排列在该层最左边的位置上，则这样的二叉树称为完全二叉树，因此在完全二叉树中，任意一个结点的左、右子树的高度之差的绝对值不超过1。

二叉排序树的递归定义如下：二叉排序树或者是一棵空树；或者是具有下列性质的二叉树：(1)若左子树不空，则左子树上所有结点的值均小于根结点的值；(2)若右子树不空，则右子树上所有结点的值均大于根结点的值；(3)左右子树也都是二叉排序树。

在n个结点的二叉树链式存储中存在n+1个空指针，造成了巨大的空间浪费，为了充分利用存储资源，可以将这些空链域存放指向结点在遍历过程中的直接前驱或直接后继的指针，这种空链域就称为线索，含有线索的二叉树就是线索二叉树。

最优二叉树即哈夫曼树。

排序各种排序的大致思路？各种排序适用于什么情况？各种排序的时间，空间复杂度？快速排序1.快速排序（Quicksort）是对冒泡排序法的一种改进，它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列；在对一个基本有序的数组进行排序时适合采用快速排序法。

陈嫒算法与数据结构第三版课后答案算法与数据结构-C语言描述（第三版）第1章绪论1、解释以下概念：逻辑结构，存储结构，操作，数据结构，数据结构的表示，数据结构的实现，抽象数据类型，算法，算法的时间代价，算法的空间代价，大O表示法，贪心法，回溯法，分治法。

答：(1)逻辑结构（数学模型）：指数据元素之间地逻辑关系。

具体解释：指数学模型（集合，表，树，和图）之间的关系。

描述方式：B=<K,R>,K是节点的有穷集合，R是K上的一个关系。

(2)存储结构（物理结构）：数据的逻辑结构在计算机存储器中的映射（或表示）。

(3)操作（行为）：指抽象数据类型关心的的各种行为在不同的存储结构上的具体算法（或程序）。

(4)数据结构：传统观念：数据结构是计算机中表示（存储）的、具有一定逻辑关系和行为特征的一组数据。

②根据面向对象的观点：数据结构是抽象数据类型的物理实现。

(5)数据结构的表示：(6)数据结构的实现：(7)抽象数据类型：(8)算法：是由有穷规则构成（为解决其中一类问题）的运算序列。

-算法可以有若干输入（初始值或条件）。

-算法通常又有若干个输出（计算结果）。

-算法应该具有有穷性。

一个算法必须在执行了有穷步之后结束。

-算法应该具有确定性。

算法的每一步，必须有确切的定义。

-算法应该有可行性。

算法中国的每个动作，原则上都是能够有机器或人准确完成的。

(9)算法的时间代价：(10)算法的空间代价：(11)大O表示法：-更关注算法复杂性的量级。

-若存在正常数c和n0，当问题的规模n>=cf(n), 则说改算法的时间（或空间）代价为O（f(n)）(12)贪心法：当追求的目标是一个问题的最优解是，设法把整个问题的求解工作分成若干步来完成。

在其中的每一个阶段都选择都选择从局部来看是最优的方案，以期望通过各个阶段的局部最有选择达到整体的最优。

例如：着色问题：先用一种颜色尽可能多的节点上色，然后用另一种颜色在为着色节点中尽可能多的节点上色，如此反复直到所有节点都着色为止；(13)回溯法有一些问题，需要通过彻底搜索所有的情况寻找一个满足一些预定条件的最优解。

1. 关于算法：（1）算法语言无所谓，只要能看懂。

考试用C++出题，但答题随意(可以用C/C++、Java、Pascal、自然语言等等，看得懂就可以)。

（2）如果要求自己独立地写算法（而不是填空），请注意写算法思想，并加上足够的注释（3）对于算法中直接使用的类和函数（例如栈、队列的函数），应该先写ADT，并说明函数功能、入口参数、出口参数2. 考试范围和重点不考11.3存储管理，不考12.3空间树结构，不考12.4.1决策树、12.4.2博弈树。

各章节以下面的内容为复习重点，尤其是___________、黑体字或★标出部分为重中之重。

其中黑体字为根据新教材本届考试增加的内容。

考试时如果涉及到本大纲没有列出的内容，那么试卷中会给出足够的定义和性质。

第1章概论（教材中本章作者为许卓群）一. 重要概念1. 数据类型2. 抽象数据结构3. 数据结构4. 存储结构5. 算法6. 算法度量(时间代价、空间代价)7. 数据结构的选择和评价二. 方法1. 根据二元组画出图示逻辑结构(注意边的方向)2. 根据要求设计数据结构3. 算法度量的大O表示法的简化法则（不要求掌握大Ω、大Θ表示法）第2章线性表（教材中本章作者为许卓群）一. 概念1. 线性表2. 单链表3. 双链表4. 循环表5. 栈6. 队列7. 循环队列二. 方法1. 线性表的运算(指针操作的正确性)2. 循环队列队列的实现★3. 表达式求值(中缀表达式转后缀表达式的算法、后缀表达式求值算法)4. 栈的性质，用栈来生成序列第3章字符串（教材中本章作者为许卓群）一. 概念1. 串2. 模式匹配二. 方法1. 串的基本操作2. 串的存储★ 3. 串的KMP快速模式匹配算法(next数组)，求特征next数组（N数组）和利用next数组完成匹配的方法第4章二叉树（教材中本章作者为杨冬青）一. 概念1. 二叉树2.二叉树的前序、中序、后序周游3. 二叉排序树4. 穿线树(中序、前序、后序)5. Huffman树、Huffman编码6. 堆、堆排序二. 方法1．二叉树的链式存储（1）二叉链表（2）带父指针的三重链表2. 二叉树的顺序存储完全二叉树的顺序存储★3. 使用栈(前、中、后序)周游二叉树(注意，不要使用带GOTO语句的机械消除递归的方法)、使用队列层次地周游二叉树，在周游过程中寻找某个结点或进行某种操作 (结合应用，例如穿线树，或把快速排序转换成非递归形式)4. 二叉检索树的插入与删除5. 构造Huffman树，利用Huffman树进行编码、解码6. 堆排序的建堆过程第5章树（教材中本章作者为杨冬青）一. 概念1. 树、森林2. 树、森林的先根周游、后根周游、层次周游二. 方法1. 树林与二叉树相互转换2．森林的链式存储(1) 转换为相应的二叉树，用二叉链表表示(2) 父指针表示法(3) 子结点表表示法3. 森林的顺序存储不必死记各种顺序存储方法，要了解原理。

2020知到（智慧树）《人工智能基础导学》章节单元测试答案绪论单元测试•第1部分•总题数: 101.【单选题】 (10分)1956年达特茅斯会议上，学者们首次提出“artificial intelligence（人工智能）”这个概念时，所确定的人工智能研究方向不包括：A.研究如何用计算机来模拟人类智能B.研究智能学习的机制C.研究人类大脑结构和智能起源D.研究如何用计算机表示人类知识2.【单选题】 (10分)在现阶段，下列哪项尚未成为人工智能研究的主要方向和目标：A.研究如何用计算机模拟人类智能的若干功能，如会听、会看、会说B.研究如何用计算机延伸和扩展人类智能C.研究机器智能与人类智能的本质差别D.研究如何用计算机模拟人类大脑的网络结构和部分功能3.【单选题】 (10分)下面哪个不是人工智能的主要研究流派？A.模拟主义B.经验主义C.连接主义D.符号主义4.【单选题】 (10分)从人工智能研究流派来看，西蒙和纽厄尔提出的“逻辑理论家”方法用，应当属于：A.连接主义，经验主义B.经验主义，行为主义C.符号主义，连接主义D.理性主义，符号主义5.【单选题】 (10分)从人工智能研究流派来看，明斯基等人所推荐的“人工神经网络”方法用计算机模拟神经元及其连接，实现自主识别、判断，应当属于：A.符号主义，连接主义B.连接主义，经验主义C.理性主义，符号主义D.经验主义，行为主义6【判断题】 (10分)“鸟飞派”指的是人类研究人工智能必须要完全符合智能现象的本质A.错B.对7【判断题】 (10分)人工智能受到越来越多的关注，许多国家出台了支持人工智能发展的战略计划A.错B.对8【判断题】 (10分)人工智能将脱离人类控制，并最终毁灭人类A.错B.对9【判断题】 (10分)人工智能目前仅适用于特定的、专用的问题A.错B.对10【判断题】 (10分)通用人工智能的发展正处于起步阶段A.错B.对第一章单元测试•第1部分•总题数: 101.【单选题】 (10分)以下组合最能全面包括所有知识表示形式的是A.符号主义、经验主义、连接主义B.符号主义、特征表示、语义向量C.产生式系统、特征表示、连接主义D.谓词逻辑、经验主义、网络权重2.【单选题】 (10分)以下用谓词表示的命题错误的是A.大亮的老师擅长打羽毛球和网球：good_at(teacher(大亮)，羽毛球)⋀ good_at(teacher(大亮)，网球)B.我爸爸喜欢吃鸡蛋并且我妈妈喜欢吃西红柿：like_eat(father(我)，鸡蛋) ∨like_eat(moth er(我)，西红柿)C.小博不在实验室：¬in(小博，实验室)D.老王的生日在4月：birthday（老王，4月）3.【单选题】 (10分)哪种知识表示的样本数据的特征表示，就对应了某种知识。

《算法及其分析》课后选择题答案及详解第1 章——概论1.下列关于算法的说法中正确的有（）。

Ⅰ.求解某一类问题的算法是唯一的Ⅱ.算法必须在有限步操作之后停止Ⅲ.算法的每一步操作必须是明确的，不能有歧义或含义模糊Ⅳ.算法执行后一定产生确定的结果A.1个B.2个C.3个D.4个2.T(n)表示当输入规模为n时的算法效率，以下算法效率最优的是（）。

A.T(n)=T(n-1)+1，T(1)=1B.T(n)=2nC.T(n)= T(n/2)+1，T(1)=1D.T(n)=3nlog2n答案解析：1.答：由于算法具有有穷性、确定性和输出性，因而Ⅱ、Ⅲ、Ⅳ正确，而解决某一类问题的算法不一定是唯一的。

答案为C。

2.答：选项A的时间复杂度为O(n)。

选项B的时间复杂度为O(n)。

选项C 的时间复杂度为O(log2n)。

选项D的时间复杂度为O(nlog2n)。

答案为C。

第3 章─分治法1.分治法的设计思想是将一个难以直接解决的大问题分割成规模较小的子问题，分别解决子问题，最后将子问题的解组合起来形成原问题的解。

这要求原问题和子问题（）。

A.问题规模相同，问题性质相同B.问题规模相同，问题性质不同C.问题规模不同，问题性质相同D.问题规模不同，问题性质不同2.在寻找n个元素中第k小元素问题中，如快速排序算法思想，运用分治算法对n个元素进行划分，如何选择划分基准？下面（）答案解释最合理。

A.随机选择一个元素作为划分基准B.取子序列的第一个元素作为划分基准C.用中位数的中位数方法寻找划分基准D.以上皆可行。

但不同方法，算法复杂度上界可能不同3.对于下列二分查找算法，以下正确的是（）。

A.intbinarySearch(inta[],intn,int x){intlow=0,high=n-1;while(low<=high){intmid=(low+high)/2;if(x==a[mid])returnmid;if(x>a[mid])low=mid;elsehigh=mid;}return –1;}B.intbinarySearch(inta[],intn,int x) { intlow=0,high=n-1;while(low+1!=high){intmid=(low+high)/2;if(x>=a[mid])low=mid;elsehigh=mid;}if(x==a[low])returnlow;elsereturn –1;}C.intbinarySearch(inta[],intn,intx) { intlow=0,high=n-1;while(low<high-1){intmid=(low+high)/2;if(x<a[mid])high=mid;elselow=mid;}if(x==a[low])returnlow;elsereturn –1;}D.intbinarySearch(inta[],intn,int x) {if(n>0&&x>=a[0]){intlow= 0,high=n-1;while(low<high){intmid=(low+high+1)/2;if(x<a[mid])high=mid-1;elselow=mid;}if(x==a[low])returnlow;}return –1;}答案解析：1.答：C。

九章算法前⾔第⼀天的算法都还没有缓过来，直接就进⼊了第⼆天的算法学习。

前⼀天⼀直在整理Binary Search的笔记，也没有提前预习⼀下，好在Binary Tree算是⾃⼰最熟的地⽅了吧（LeetCode上⾯Binary Tree的题刷了4遍，⽬前95%以上能够Bug Free）所以还能跟得上，今天听了⼀下，觉得学习到最多的，就是把Traverse和Divide Conquer分开来讨论，觉得开启了⼀⽚新的天地！今天写这个博客我就尽量把两种⽅式都写⼀写吧。

Outline:⼆叉树的遍历前序遍历traverse⽅法前序遍历⾮递归⽅法前序遍历分治法遍历⽅法与分治法Maximum Depth of Binary TreeBalanced Binary Tree⼆叉树的最⼤路径和 (root->leaf)Binary Tree Maximum Path Sum II (root->any)Binary Tree Maximum Path Sum (any->any)⼆叉查找树Validate Binary Search TreeBinary Search Tree Iterator⼆叉树的宽度优先搜索Binary Tree Level-Order Traversal课堂笔记1.⼆叉树的遍历这个应该是⼆叉树⾥⾯最基本的题了，但是在⾯试过程中，不⼀定会考递归的⽅式，很有可能会让你写出⾮递归的⽅法，上课的时候⽼师也提到过，应该直接把⾮递归的⽅法背下来。

这⾥我就不多说了，直接把中序遍历的两种⽅法贴出来吧，最后再加⼊⼀个分治法（这也是第⼀次写，感觉很棒呢，都不需要太多的思考）。

1.1 前序遍历traverse⽅法（Bug Free）：vector<int> res;void helper(TreeNode* root) {if (!root) return;res.push_back(root->val);if (root->left) {helper(root->left);}if (root->right) {helper(root->right);}}vector<int> preorderTraversal(TreeNode *root) {if (!root) {return res;}helper(root);return res;}1.2 前序遍历⾮递归⽅法（Bug Free）：vector<int> preorderTraversal(TreeNode *root) {vector<int> res;if (!root) {return res;}stack<TreeNode*> s;s.push(root);while (!s.empty()) {TreeNode* tmp = s.top();s.pop();res.push_back(tmp->val);// 这⾥注意：栈是先进后出，所以先push右⼦树if (tmp->right) {s.push(tmp->right);}if (tmp->left) {s.push(tmp->left);}}return res;}1.3 前序遍历分治法（Java实现）：vector<int> preorderTraversal(TreeNode *root) {vector<int> res;if (!root) {return res;}//Dividevector<int> left = preorderTraversal(root->left);vector<int> right = preorderTraversal(root->right);//Conquerres.push_back(root->val);res.insert(res.end(), left.begin(), left.end());res.insert(res.end(), right.begin(), right.end());return res;}这三种⽅法也是⽐较直观的，前两个⽐较基础，我就不详细叙述了，但是分治法是值得重点说⼀说的。