《计算机算法通俗教程》教案全套 第1-12章 算法概述-图论算法

授课内容算法概述学时2教学目标知识目标理解算法的基本概念、要素和特征掌握算法设计的基本步骤和方法学会算法的时间复杂度和空间复杂度分析方法了解算法在计算机科学中的重要地位能力目标能够运用算法思想分析和解决实际问题具备初步的算法设计和分析能力能够使用不同的工具描述算法重点与难点重点算法的基本概念和特征：理解算法的定义、要素和五大基本特征算法分析方法：掌握时间复杂度和空间复杂度的分析方法算法设计步骤：了解从问题分析到算法实现的完整流程算法的描述工具：熟悉各种算法描述方法的优缺点难点算法思想的实际应用：如何将抽象的算法思想应用于具体问题求解复杂度分析的理解：深入理解渐近时间复杂度的概念和计算方法教学内容第一部分：课程导入1、点名与签到2、课程重要性阐述结合实际应用场景讲解课程性质：理论与实践相结合的专业核心课程教学目标：培养学生算法设计和分析的核心能力学科地位：计算机学科的理论基础和核心内容企业需求：IT企业招聘程序员的必备技能考研与竞赛需求：算法是计算机考研、各类编程竞赛的核心考点

第二部分：新课讲解一、算法的定义核心定义算法是解决特定问题的有限、确定的计算步骤序列。它是解决问题的机械步骤，具有明确的输入、输出和执行规则。算法的基本特征1.

有穷性：算法必须在有限步骤内结束2.

确定性：每一步骤必须有明确的含义3.

可行性：每个步骤都必须是可执行的4.

输入：有零个或多个输入5.

输出：有一个或多个输出二、算法的特征1.

输入性2.

输出性3.

确定性4.有穷性5.可行性三、算法描述1、自然语言描述最简单的描述算法的方法是使用自然语言。使用自然语言来描述算法的优点是简单并且便于理解和阅读；缺点是不够严谨，并且对复杂的逻辑关系（例如：多重嵌套的分支或循环）很难进行清晰描述。2、流程图描述使用程序流程图描述算法的优点是简洁明了，便于表示复杂的逻辑结构，对于分支、循环的处理方案一目了然，便于对算法进行分析以及检查算法设计中的错误或疏漏之处。使用流程图描述的最大缺点是流程图的绘制比较麻烦，尤其是算法中存在多重嵌套的分支或循环时。3、伪代码描述伪代码是介于自然语言和计算机编程语言之间的描述语言，它结合了自然语言的方便性与编程语言强大的逻辑描述能力，是描述算法最常用的方式。伪代码的优点是书写方便灵活、描述能力强并且不受编程语言语法规则的限制。其缺点是严谨性略差，以及随着描述代码的增长可读性逐渐变差。四、算法评价1、时间复杂度概念时间复杂度的概念定义为：衡量算法运行时间随输入规模增长的变化趋势。它不计算具体的运行时间，而是分析操作次数的增长级别，以帮助我们在理论上比较不同算法的效率。2、表示符号时间复杂度描述的是渐进变化的趋势，它有三个表示符号：O（渐进上界）、Ω（渐进下界）和θ（确界）。3、计算方法在计算时间复杂度时，通常用n表示输入规模，而计算时一般会忽略关于n的低阶项和常数，例如：如果T(n)=3n2+2n+1，我们记时间复杂度为O(n2)。2、空间复杂度概念空间复杂度是对一个算法在运行过程中临时占用存储空间大小的一个度量，用于分析算法对内存的消耗随输入规模n的增长趋势。与时间复杂度一样，常见的空间复杂度有O(1)、O(n)、O(n2)

等。说明算法的空间复杂度在计算时一般不包括输入数据本身占用的空间。例如，排序算法的空间复杂度通常指除待排序数据外需要的额外空间。五、编程言与编程环境1、概述算法只是问题的解决方案，或者说是问题的解题原理，它本身与编程语言并无直接联系。本课程选择使用C++语言进行算法的编程实现，这样的好处为入门门槛比较低（学生已普遍学习过C语言）并且兼顾各种编程竞赛与学生工作面试的需求。2、编程环境对于C++而言，其可选的IDE有很多，常用的有Dev-C++、VisualStudio、Code::Blocks等。我们选择的编程环境是Dev-C++，它的最大优点是：简单并且免费。3、万能头文件使用Dev-C++还有一个好处，那就是它支持万能头文件。万能头文件的名字为“bits/stdc++.h”只要在程序的开始部分添加如下语句，程序中就不需要再包含任何其它头文件了。#include<bits/stdc++.h>第三部分：知识小结【学生活动】利用学习通进行课堂测试，检测学生本次课知识掌握情况。【课堂总结】教师总结本次课学习内容作业布置1、预习下节课的内容2、发布作业。教学反思授课内容简单算法学时2教学目标知识目标掌握整除、模除运算的规则与用法理解数字分离、数字合成的算法原理掌握素数判断、埃氏筛法基本思路掌握辗转相除法、数组下标巧用与桶排序原理能力目标提升数值类问题规律观察与归纳建模能力强化简单算法流程拆解与逻辑分析能力培养多类基础算法对比择优与应用实践能力重点与难点重点数字分离与数字合成基础算法流程素数判断思路与埃氏筛选法操作步骤辗转相除法求解最大公约数流程数组下标巧用思想及桶排序实现方法难点结合循环，实现多位数字自动分离统计理解筛法优化逻辑与桶排序适用边界教学内容第一部分：课程导入1、点名与签到2、课程重要性阐述本章承接算法基础理论，转入实操简单算法训练数值拆分、合成是编程刷题的通用底层基本功素数、公约数题型，是考试与竞赛高频考点内容巧用数组下标、桶排序，培养高效解题思维方式本章易上手、见效快，增强学生算法学习信心第二部分：新课讲解一、数字分离与合成1、分离原理所谓的数字分离，就是将一个整数，分解出其中的每一位。在C++中，数字分离依赖于二个除法运算符：整除和模除。实例inti=123,a,b,c;a=i%10; //得到个位数：3c=i/100; //得到百位数：1b=i%100/10; //得到十位数：2cout<<a<<""<<b<<""<<c<<endl;2、合成原理所谓的数字合成，就是已有整数的各位数字，将其合并成为一个整数。例如：已知百位数字为1，十位数字为2，个位数字为3，要求将其合成为一个整数123。算法原理为：((0*10+1)*10+2)*10+3。实例已有二个数字字符串，例如：“1234”和“5678”，试输出其和。chars1[]="1234";chars2[]="5678";intp1=0,p2=0; for(inti=0;s1[i]!='\0';i++) p1=p1*10+s1[i]-'0';for(inti=0;s2[i]!='\0';i++) p2=p2*10+s2[i]-'0';cout<<p1+p2<<endl;3、例题：计数问题【题目描述】试计算在区间1到n的所有整数中，数字x(0≤x≤9)共出现了多少次？例如，在1到11中，即在1，2，3，4，5，6，7，8，9，10，11中，数字1出现了4次。【程序】详见课本二、素数判断1、素数及其判断要判断n是否为素数，可以根据定义，让n除以2～n-1之间的每一个数，如果均不能整除，n就是素数。上述方案还可以优化为：让n除以2～n/2或者2～之间的每一个数。2、批量求素数概述所谓批量求素数，就是要找出某个范围之内的全部素数。比如：求2～100之间的全部素数。批量求素数的主要方法有：埃氏筛选法（埃拉托斯特尼筛法）和线性筛选法。实例用筛选法求出100以内的全部素数，并按每行五个数显示。为了使用埃氏筛选法求素数，我们要先定义一个数组：boola[101];在此数组中，我们使用a[i]的值表示i是否为素数。原理见课本介绍，整个求解过程如下图所示：三、最大公约数求最大公约数有很多种方法，最常用的是辗转相除法，也称为欧几里德算法。辗转相除法的具体步骤如下：①输入两个正整数m和n。②求出m除以n的余数r，即r=m%n。③如果余数r=0，则n就是最大公约数，结束。如果r≠0，则令m=n，n=r。转到第②步重新执行。④重复上述步骤，直到余数为0，此时的除数n就是最大公约数。四、桶排序1、概述对于正整数的排序，有一种很简单的排序方法：桶排序。2、桶排序原理第1步：准备“桶”如果要排序的这批数据范围在1～100之间，我们需要先准备100个桶（就是定义相应容量的数组），并且将其编号为1～100。第2步：将数据放入“桶”内检查待排序的数据，如果某个数据值为x，就将其放入编号为x的桶中。例如：如果某个数据值为1，就将其放入1号桶内；如果值为2，就将其放入2号桶内；依次类推。第3步：按从小到大（或从大到小）的顺序，依次将“桶”内数据输出。先检查1号桶：如果里面没有数据，则不输出；如果里面有一个数据，则输出则输出一个“1”；如果里面有二个数据，则输出二个“1”；依次类推。处理完1号桶后，按同样的规则依次处理2～100号桶。3、例题：考试成绩排序详见课本第三部分：知识小结【学生活动】利用学习通进行课堂测试，检测学生本次课知识掌握情况。【课堂总结】教师总结本次课学习内容作业布置1、预习下节课的内容2、发布作业。教学反思授课内容枚举法学时2教学目标知识目标理解枚举法的核心定义与基本思想掌握枚举法的适用场景与使用前提理解百钱买百鸡、火柴棒等式的枚举思路掌握枚举范围优化的基本方法能力目标提升问题解的范围界定与规律提炼能力强化枚举算法的逻辑分析与流程设计能力培养枚举方案优化与高效解题的实践能力重点与难点重点枚举法的核心思想与适用场景百钱买百鸡问题的枚举思路与代码实现火柴棒等式问题的枚举逻辑与优化方法枚举范围的合理界定与冗余优化技巧难点结合题目条件精准界定枚举范围掌握枚举算法的优化思路，减少冗余计算教学内容第一部分：课程导入1、点名与签到2、课程重要性阐述本章承接简单算法，学习实用的枚举法解题技巧枚举法是竞赛、考级中高频出现的基础算法枚举法思路简单，适配无明显规律的解题场景掌握枚举优化技巧，提升算法运行效率通过实例练习，强化算法设计与问题解决能力第二部分：新课讲解一、枚举法概述枚举法，也称为穷举法或暴力求解法，其思想是：虽然不能正面求出问题的解，但如果能够知道解的范围，就可以将所有可能的解逐一代入问题中进行验证，如果某个解满足问题中所有的限定条件，那么它就是一个正确的解。二、枚举法实例1、百钱买百鸡题目百鸡买百钱是我国古书《算经》中的数学问题：鸡翁一，值钱五，鸡母一，值钱三，鸡雏三，值钱一，百钱买百鸡，问鸡翁、鸡母、鸡雏各几何？分析针对x、y、z所有可能的取值逐一测试，使上述二个方程同时成立的x、y、z组合就是要求的解。在测试之前，需要先确定x、y、z的最大取值范围，如下：x的取值范围是0～100/5，y的取值范围是0～100/3，z的取值范围是0～3*100。程序见课本说明注意到鸡翁、鸡母、鸡雏总共100只，一旦确定鸡翁x和鸡母y的数值，鸡雏便只能购买100-x-y只。这样，我们就不需要枚举x、y、z的每一种组合，而只需要枚举x、y的每一种组合即可，从而避免了大量无意义的枚举。2、火柴棒等式题目给你n根火柴棒，你可以拼出多少个形如A+B=C的等式？等式中的A、B、C是用火柴棒拼出的整数（若该数非零，则最高位不能是0）。用火柴棒拼数字0～9的拼法如下图所示：注意：①加号与等号各自需要两根火柴棒；②如果A≠B，则A+B=C与B+A=C视为不同的等式（A,B,C≥0）；③n根火柴棒必须全部用上。分析本题的思路为：①计算某个数字所需火柴棒数量先将拼出数字0～9需要用到的火柴棒数量存进数组a里，然后再写一个函数，它能利用数组a求出拼出任意数字x所需的火柴棒数量。②找出使等式成立的A、B、C组合先枚举A和B的取值，并利用C=A+B计算出C。再计算出拼出A，B，C所需的火柴棒数之和，若它等于n−4，那么就算找到了一组合法解。③A、B的取值范围拼出数字1所需的火柴棒数最小，只需要2根。A最多是3位数。同理，B也最多是3位数，即A、B的取值均不超过1000。程序见课本。三、思维开拓这些题目在自洛谷网站，供上课学生们对其解法进行讨论。1、比例简化【题目描述】在社交媒体上，经常会看到针对某一个观点同意与否的民意调查以及结果。例如，对某一观点表示支持的有1498人，反对的有902人，那么赞同与反对的比例可以简单的记为1498:902。不过，如果把调查结果就以这种方式呈现出来，大多数人肯定不会满意。因为这个比例的数值太大，难以一眼看出它们的关系。对于上面这个例子，如果把比例记为5:3，虽然与真实结果有一定的误差，但依然能够较为准确地反映调查结果，同时也显得比较直观。现给出支持人数A，反对人数B，以及一个上限L，请你将A比B化简为A’比B’，要求在A’和B’均不大于L且A’和B’互质（两个整数的最大公约数是1）的前提下，A’/B’≥A/B且A’/B’-A/B的值尽可能小。【数据说明】对于100%的数据，1≤A≤1,000,000，1≤B≤1,000,000，1≤L≤100，A/B≤L。2、回文日期【题目描述】在日常生活中，通过年、月、日这三个要素可以表示出一个唯一确定的日期。牛牛习惯用8位数字表示一个日期，其中，前4位代表年份，接下来2位代表月份，最后2位代表日期。显然：一个日期只有一种表示方法，而两个不同的日期的表示方法不会相同。牛牛认为，一个日期是回文的，当且仅当表示这个日期的8位数字是回文的。现在，牛牛想知道：在他指定的两个日期之间包含这两个日期本身，有多少个真实存在的日期是回文的。一个8位数字是回文的，当且仅当对于所有的i(1≤i≤8)从左向右数的第i个数字和第9-i个数字（即从右向左数的第i个数字）是相同的。例如： 对于2016年11月19日，用8位数字20161119表示，它不是回文的。 对于2010年1月2日，用8位数字20100102表示，它是回文的。 对于2010年10月2日，用8位数字20101002表示，它不是回文的。【输入格式】两行，每行包括一个8位数字。第一行表示牛牛指定的起始日期。第二行表示牛牛指定的终止日期。保证date1和date2都是真实存在的日期，且年份部分一定为4位数字，且首位数字不为0。保证date1—定不晚于date2。【输出格式】一个整数，表示在date1和date2之间，有多少个日期是回文的。第三部分：知识小结【学生活动】利用学习通进行课堂测试，检测学生本次课知识掌握情况。【课堂总结】教师总结本次课学习内容作业布置1、预习下节课的内容2、发布作业。教学反思授课内容递归学时2教学目标知识目标理解递归的核心思想与“递推+回归”工作流程掌握斐波那契数列的递归求解方法理解备忘录技术的原理及应用场景掌握汉诺塔、数的计算的递归解题思路能力目标提升复杂问题递归分解与规律提炼能力强化递归算法逻辑分析与流程设计能力培养递归优化与时空权衡的工程实践能力重点与难点重点递归的核心思想与工作流程斐波那契数列的递归实现与优化方法备忘录技术的应用的核心要点汉诺塔问题的递归解题步骤与逻辑难点理解递归的递推与回归过程，梳理递归逻辑掌握备忘录技术的应用，实现递归优化教学内容第一部分：课程导入1、点名与签到2、课程重要性阐述本章承接枚举法，学习高效的递归算法思想递归是算法竞赛、考级中高频考点，实用性极强递归可简化复杂问题求解，适配多种典型场景掌握递归优化技巧，提升算法运行效率通过实例练习，深化算法设计与问题解决能力第二部分：新课讲解一、递归概述1、递归算法思想递归是一种编程方式，但同时还是一种算法思想。递归作为一种算法思想，其核心是把复杂的问题分解成简单的问题，逐级分解下去，直到问题的规模小到可以直接求解，然后再逐级向上回溯生成较为复杂问题的解，直到解决最初的问题为止2、递归的工作流程递归包含了“递推”和“回归”二个过程。递推：把复杂的问题分解为比原问题简单一些的子问题，以便于求解；回归：当获得简单问题的答案后，逐步返回，依次得到复杂问题的解。二、Fibonacci数列1、概述Fibonacci数列（斐波那契数列）是由古代意大利数学家莱昂纳多•斐波那契在研究兔子繁殖问题时提出来的。Fibonacci数列以如下递归的方式定义：F(0)=0F(1)=1F(n)=F(n-1)+F(n-2)（n≥2）2、编程求解Fibonacci数列的各项可以通过一个简单的循环来求解，也可以通过递归方式来求解。intfib(inti) //返回第i项的值{ if(i==0)return0; if(i==1) return1;returnfib(i-2)+fib(i-1);}3、消除重复求解在使用递归版本求解Fibonacci数列时，会存在针对同一子问题的重复求解问题，以下图为例进行说明。为了求fib(5)的值，需要分别计算fib(4)和fib(3)，而求fib(4)时，又需要计算fib(3)和fib(2)，这样fib(3)就被重复计算了二次。使用“备忘录”解决重复求解问题，就是建立一个数组，将fib函数的参数值i及其对应的求解结果记录下来。以后再要求计算fib(i)时，先查询一下“备忘录”中有没有fib(i)的值，若有则直接使用；若没有才需要进行计算，并将计算结果也记录到“备忘录”中。代码如下：inta[100]={0,1};//备忘录，a[i]存储fib(i)的返回值intfib(inti){ if(a[i]>0||i==0)returna[i];//备忘录内已有记录时 a[i]=fib(i-1)+fib(i-2); //初次求解，先保存结果 returna[i];}三、Hanoi塔问题1、问题介绍Hanoi塔（汉诺塔）问题是从一个古老的印度传说演变而来的，其问题是这样的：Hanoi塔由n个大小不同的圆盘和三根木柱a，b，c组成。开始时，这n个圆盘由大到小依次套在a柱上，如下图所示。要求把a柱上n个圆盘按下述规则移到c柱上： 一次只能移一个圆盘 圆盘只能在三个柱上存放 在移动过程中，不允许大盘压小盘试给出全部盘子的移动过程。2、算法分析我们先考虑最后一个盘子是如何移动的，可以简单分为三个步骤：（1）把n-1个盘子由A移到B；（2）把第n个盘子由A移到C；（3）把n-1个盘子由B移到C；3、程序见课本四、数的计算1、题目要求找出具有下列性质数的个数（包括输入的自然数n）。先输入一个自然数n（n≤1000），然后对此自然数按照如下方法进行处理：不作任何处理；在它的左边加上一个自然数，但该自然数不能超过原数的一半；加上数后，继续按此规则进行处理，直到不能再加自然数为止。【输入格式】一个自然数n（n≤1000）【输出格式】一个整数，表示满足条件的数的个数2、分析如果n=100，需要依次在前面添加1～50之一；然后，针对新添加的部分（1～50之一），再每次取其一半添加在其前面。显然，本过程是递归的。在递归过程中会存在重复求解相同子问题的情况，因此，需要使用“备忘录”技术来提高程序运行性能。3、程序详见课本第三部分：知识小结【学生活动】利用学习通进行课堂测试，检测学生本次课知识掌握情况。【课堂总结】教师总结本次课学习内容作业布置1、预习下节课的内容2、发布作业。教学反思授课内容排序学时4教学目标知识目标理解排序的核心概念及分类标准掌握冒泡、选择、快速排序的原理与步骤了解插入、归并等排序算法的核心特点掌握STL中sort函数的基本用法能力目标提升各类排序算法的逻辑分析与流程设计能力培养根据数据场景择优选取排序算法的实践能力强化排序算法的应用与问题解决能力重点与难点重点冒泡排序的原理、程序实现及提前退出技巧选择排序的核心思路与程序实现方法快速排序的分治思想与基准值划分流程STL中sort函数的使用及自定义排序规则难点快速排序中基准值的选择与递归分治逻辑的理解根据数据特征与需求，合理选择适配的排序算法教学内容第一部分：课程导入1、点名与签到2、课程重要性阐述本章承接递归算法，学习实用的排序算法知识排序在生活和编程中应用广泛，是算法学习的核心内容掌握排序算法是应对竞赛、考级的重要基础不同排序算法各有优劣，学会择优使用是核心能力通过本章学习，夯实算法设计与问题解决的实操基础第二部分：新课讲解一、排序问题概述1、排序的算法排序的算法竟然多达十几种！这些算法各有优缺点，没有一种是非常完美的。它们各自适用于不同的情况，因而都有存在的必要。2、相关概念比较排序和非比较排序比较排序是通过比较大小来决定数据间的相对次序；非比较排序则不是通过比较大小来决定数据间的相对次序。非比较排序包括计数排序、桶排序和基数排序，其余常见的排序算法都是比较排序。排序的稳定性排序分为稳定排序和不稳定排序二大类。稳定排序，就是如果a在b前面，而且a=b，排序之后a仍然在b的前面。不稳定排序：如果a在b的前面，而且a=b，排序之后a可能会出现在b的后面。二、冒泡排序1、概述冒泡排序（BubbleSort）是一种最基础的交换排序，其特点是比较和交换。冒泡排序模拟了水中的气泡溢出过程过程，通过不停地相邻交换，使得大的数据不停地向后移动，最终达到正确的位置。2、第一趟冒泡第一趟冒泡的目的，是将数列中的最大值通过交换移动到数列的最后面去。具体步骤为：（1）先检查前二个数，发现第一个数5小于后面的6，即它们是有序的，所以不需要进行任何处理，如下图(a)所示。（2）检查第2，3个数，发现前面的6大于后面的3，这时需要将它们交换位置，如下图(b)所示。后续数据的比较处理依次类推，最终，经过这一趟冒泡，最大值6交换到了数列的尾部。3、后续的冒泡过程后续冒泡过程与第一趟类似，每次都实现将前面未排序数据中的最大值移动此区域的尾部。4、特点总结n个数据的排序，需要进行n-1轮冒泡。对于第i轮冒泡，其比较次数为n-1-i次。5、核心程序constintn=10; //定义常量n，它代表10 inta[n]={8,2,5,34,6,12,65,22,16,55}; for(inti=0;i<n-1;i++) //外层循环n-1次{ for(intj=0;j<n-1-i;j++) //内层循环n-1-i次 { if(a[j]>a[j+1]) //需要将a[j]与a[j+1]交换 { inttemp; temp=a[j]; a[j]=a[j+1]; a[j+1]=temp; } } }6、例题：车厢重组题目在一个旧式的火车站旁边有一座桥，其桥面可以绕河中心的桥墩水平旋转。一个车站的职工发现桥的长度最多能容纳两节车厢，如果将桥旋转180度，则可以把相邻两节车厢的位置交换，用这种方法可以重新排列车厢的顺序。于是他就负责用这座桥将进站的车厢按车厢号从小到大排列。他退休后，火车站决定将这一工作自动化，其中一项重要的工作是编一个程序，输入初始的车厢顺序，计算最少用多少步就能将车厢排序。【输入数据】输入数据有两行，第一行是车厢总数N（不大于10000），第二行是N个不同的数表示初始的车厢顺序。【输出数据】一个数据，是最少的旋转次数。解析车厢重组的过程完全就是冒泡排序的过程，只是需要增加统计交换次数功能。程序详见课本说明这个例子同时展示了冒泡排序的提前退出功能。三、选择排序1、基本思想先从未排序的数据中选出最小的，然后直接与第1个数据交换位置。这样，就将最小元素移到了其正确的位置上去。再针对剩余数据，重复以上步骤，直到全部数据都有序为止。2、排序过程初始数据（数组a）： 563412第一趟：在a[0]～a[5]中选择最小者，然后与a[0]处的元素交换，结果：163452第二趟：在a[1]～a[5]中选择最小者，然后与a[1]处的元素交换，结果：123456第三趟：在a[2]～a[5]中选择最小者，然后与a[2]处的元素交换，结果：123456其余各趟依次类推。3、程序详见课本要点：针对最小元素，记录其下标，而不是最小元素的值。四、快速排序1、算法思想先从待排序数据中任取一个数据作为基准值，然后将大于基准值的数据全部移到基准值的后面，而将小于基准值的数据全部移到基准值的前面。这一操作完成之后，基准值就在正确的位置处。并且以基准值为分割线，在其左右形成了二个较小的未排序数据区。然后再对这二个子集进行同样的操作（递归处理），就可以完成全部数据的排序。在递归过程中，会层层减小子集的规模，当子集减小到只有一个元素时，就可以停止递归了。2、准备工作排序开始前，需要准备3个变量。一个用于存储基准值，另外二个是首尾指针，分别指向待排序数据区的首元素与末元素，如下图所示：3、第一轮处理先从尾指针开始，向前寻找第一个小于基准值的数据。然后，再从头指针开始，向后寻找第一个大于基准值的数据。整个过程如下图所示。然后，交换上述二个指针处的数据。操作完成之后，前后指针并未“碰头”（即未完成对全部数据的扫描），因此，还需要再继续处理。重复上述操作后，头指针与尾指针最终将“碰头”，如下图所示。将头/尾指针处的数据与作为基准值的那个数据交换，第一轮搜索与交换完成。4、后续处理这一轮搜索与交换结束后，基准值3到达了正确的位置处，但基准值前后的数据区仍为未排序区。只需要再针对这二段未排序区域重复进行上述操作（通过递归调用实现），就可以完成全部数据的排序。5、程序voidquick_sort(inta[],intleft,intright){ if(left>=right)return; intL=left,R=right; intkey=a[L]; while(L<R) { while(L<R&&a[R]>=key)R--; //从右向左找比key小的值 while(L<R&&a[L]<=key)L++; //从左向右找比key大的值 if(L<R) swap(a[L],a[R]); //交换二个值，if条件可不要 } swap(a[left],a[L]); //将基准key交换到正确位置处 qsort(a,left,L-1); //递归，再完成左半区间的排序 qsort(a,R+1,right); //递归，再完成右半区间的排序}6、例题：第k小整数题目给定一个长度为n的整数数列，以及一个整数k，请用快速选择算法求出数列从小到大排序后的第k个数。【输入格式】第一行包含两个整数n和k。（1≤n≤100000，1≤k≤n）第二行包含n个整数（所有整数均在1∼109范围内），表示整数数列。【输出格式】输出一个整数，表示数列的第k个数。解析这个题目，就是在快速排序过程中，不断检查一下第k个数应该位于基准值的哪一侧，从而只对第k个数所在的那一个子集进行排序，而另一个子集则不需要排序，从而节约时间。程序详见课本五、其它排序算法1、插入排序原理回忆一下打牌时抓牌的情景，为了方便打牌，抓牌时一般一边抓牌一边将牌按花色和大小插入到恰当的位置处。当抓完所有的牌时，手中的牌便是有序的，这排序方法就是插入排序。当读入一个元素时，在已经排序好的序列中，搜寻它的正确位置。找到之后，将插入点之后的元素后移一位，腾出一个空位，再将新元素放入即可。当全部数据读取完毕后，数组就是有序的。图示及程序详见课本2、归并排序原理“归并”的含义就是“合并”，它是通过将两个或两个以上的有序表不断合并成一个新的有序表的方式来实现排序的。图示分析详见课本3、基数排序与计数排序了解，详见课本六、STL中的排序函数1、概述STL中文名称为标准模板库，它是容器、算法和其它一些组件的集合。STL中的排序函数中，sort函数的使用频率最高。2、sort函数基本用法sort(start,end,排序方法);示例：inta[10]={9,6,3,8,5,2,7,4,1,0};sort(a,a+10);//第2个参数表示a[10]（最后元素的下一个元素）的地址3、详细分析及示例详见课本。第三部分：知识小结【学生活动】利用学习通进行课堂测试，检测学生本次课知识掌握情况。【课堂总结】教师总结本次课学习内容作业布置1、预习下节课的内容2、发布作业。教学反思授课内容查找学时2教学目标知识目标理解查找的核心概念及无序、有序查找的分类掌握顺序查找的原理、实现及监视哨优化技巧掌握二分查找的核心思想及循环、递归两种实现方法了解STL中常用查找函数的基本用法及使用前提能力目标提升查找算法的逻辑分析、流程设计与优化能力培养根据数据特征选择适配查找算法的实践能力强化查找算法的应用及结合STL函数解决实际问题的能力重点与难点重点顺序查找的实现流程及监视哨的优化原理二分查找的核心逻辑及循环、递归两种实现方式二分查找中左右边界的查找方法STL中binary_search、lower_bound等查找函数的使用难点理解二分查找的区间划分逻辑及边界条件判断灵活运用不同查找算法及STL函数解决实际查找问题教学内容第一部分：课程导入1、点名与签到2、课程重要性阐述本章承接排序算法，学习编程中常用的查找操作相关知识查找是数据处理的基础操作，在日常编程和竞赛中应用广泛掌握不同查找算法的特点，能显著提升数据查找的效率顺序、二分查找是竞赛、考级中高频考点，是后续复杂查找的基础学会使用STL查找函数，能简化编程流程，提升编程效率第二部分：新课讲解一、查找概述查找算法分为无序查找和有序查找二类。无序查找：被查找数列不需要有序（事先不需要进行排序）有序查找：被查找数列必须为有序数列（事先需要进行排序）二、顺序查找1、基本思想顺序查找属于无序查找，它不要求被查找的数列事先已排序。基本算法为：将数组中的元素逐个与给定值k相比较，若相等则表示查找成功；若扫描结束仍没有找到等于k的元素，则查找失败。2、程序在有n个元素的数组a中查找值为key的元素，成功时返回找到元素的索引，失败时返回-1。intSequenceSearch(inta[],intn,intkey){ for(inti=0;i<n;i++) if(a[i]==key)returni; return-1; //查找失败}3、监视哨监视哨是一个小技巧，可以减少顺序查找中的判断次数，从而大大提高程序效率。如果要在有n个元素的数组a中查找特定值key，我们需要这样定义数组：inta[n+1]={……,key};在数组尾部增加一个元素，并且将其值设置为key，此元素就是监视哨。这样，查找过程中将一定能够查找到一个值为key的元素，因此循环过程中只需要判断“a[i]==key”即可，而不需要再判断“i<n”。当找到key后，需要判断它是否是监视哨（数组尾部额外添加的那个元素）。若是，说明原数据中没有key，应返回-1；否则说明原数据中存在key。三、二分查找1、概述二分查找（BinarySearch）也称为折半查找，它是一种效率很高的查找方法。二分查找是最典型的有序查找，即它要求数据必须事先已排序。2、二分查找算法假设序列中元素是按升序排列的，按如下步骤进行查找操作：①将序列中间位置处的元素与x（待查找值）比较，如果两者相等，则查找成功。否则，进入下一步。②利用中间位置的元素将序列分成前、后两个子序列，如果中间位置的元素大于x，则下一步在前一子序列中查找，否则下一步在后一子序列中查找。③重复以上过程，直到找到x，或者子序列为空为止。整个过程如下图：3、二分查找程序intBinSearch(inta[],intleft,intright,intkey) { if(left>right)return-1; //查找失败 intmid=left+(right-left)/2; if(a[mid]==key)returnmid; //查找成功 if(a[mid]<key) //继续在后半区间a[mid+1→right]中查找 returnBinSearch(a,mid+1,right,key); else //继续在前半区间a[left→mid-1]中查找 returnBinSearch(a,left,mid-1,key);}4、查找左右边界针对重复的元素，就存在查找左边界（第一次出现的位置）和查找右边界（最后一次出现的位置）这二种要求。以在1，3，3，3，5中查找第一个3的出现位置为例分析。只需要对基础二分查找的查找过程稍加修改即可：未找到3时的处理方法不变，在找到3时进行如下处理：如果当前元素的前一个元素小于3，或者当前元素就是第1个元素，则结束查找。否则，放弃当前元素及其之后的元素，继续在当前元素之前的区间中查找。四、STL中的查找函数1、概述STL中总共有13个查找函数，下面介绍其中最常用的3个二分查找函数：binary_search、lower_bound和upper_bound。这些函数的使用都有一个前提，那就容器内是一个非递减序列（非降序列）。2、binary_search语法：binary_search(first,last,value,比较函数)binary_search试图在已排序的[first,last)中寻找元素value。如果[first,last)内有等价于value的元素，它会返回true，否则返回false。3、lower_bound与upper_boundlower_bound与upper_bound这二个函数用于查找边界位置。lower_bound返回一个非递减序列[first,last)中的第一个大于等于val的位置，或者说在有序序列范围内可以插入指定值而不破坏容器顺序的第一个位置。upper_bound返回一个非递减序列[first,last)中第一个大于val的位置，或者说在有序序列范围内插入value而不破坏容器顺序的最后一个位置。第三部分：知识小结【学生活动】利用学习通进行课堂测试，检测学生本次课知识掌握情况。【课堂总结】教师总结本次课学习内容作业布置1、预习下节课的内容2、发布作业。教学反思授课内容贪心算法学时2教学目标知识目标理解贪心算法的核心思想与适用场景掌握贪心选择性质和最优子结构的基本含义掌握最优装载、活动选择两类问题的贪心策略了解贪心算法不回溯、局部最优的典型特点能力目标提升多阶段决策问题的规律识别与建模能力强化贪心策略的逻辑分析与算法设计能力培养算法择优选用与实际问题求解能力重点与难点重点贪心算法的核心思想与基本步骤贪心选择性质与最优子结构的理解最优装载问题的贪心策略与实现步骤活动选择问题的贪心策略与实现步骤难点正确判断问题是否适合使用贪心算法为实际问题设计合理有效的贪心策略教学内容第一部分：课程导入1、点名与签到2、课程重要性阐述本章承接前面基础算法，进入贪心算法的系统学习贪心算法是竞赛、考级、面试中的高频常用算法贪心思路简洁高效，适合解决多阶段最优决策问题学会贪心思想能显著提升问题分析与算法设计能力本章通过典型实例，快速掌握贪心算法的实用技巧第二部分：新课讲解一、贪心算法概述1、算法思想贪心算法的策略是在每一步选择中，都选择当前看起来最优的选项。这种选择是基于局部最优的判断，而不考虑全局最优解。通过贪心策略，每一步都在当前情况下做出最优的选择，希望最终能够得到全局最优解。2、贪心选择性质贪心选择性质是使用贪心算法的前提之一，它要求必须保证每一步贪心策略所求得的解都是最优解的一部分。贪心选择性质一般使用交换论证法进行证明。3、最优子结构如果一个问题的最优解包含其子问题的最优解，称此问题具有最优子结构性质。这一性质也可以这样理解：问题的最优解可以通过一系列局部最优解的组合来得到。最优子结构一般通过反证法来证明。4、贪心算法的特点着眼当前，简单高效不回溯二、典型例题1、最优装载题目n个集装箱1，2，…，n装上轮船，集装箱i的质量为wi，轮船装载质量限制为C，要求在体积不受限制的情况下，将尽可能多的集装箱装上轮船。【输入格式】输入的第一个整数为测试样例的个数T，接下来有T个测试样例。每个测试样例的第一行是一个非负整数n（n≤1000）和一个非负整数C（C≤10000），分别表示集装箱的个数以及轮船的载重量。接下来有n行，每行一个非负数，表示每个集装箱的重量。【输出格式】对应每个测试样例输出一行，格式为"DV"。其中，D为轮船可以装载的集装箱数量的最大值，V为满足D最大时轮船的实际载重量。算法这个问题可以使用贪心算法，规则为：每次都挑选剩余集装箱中重量最轻的进行装载即可，此策略下很容易证明具有贪心选择性质和最优子结构。具体步骤为：①对所有集装箱按重量从小到大排序。②每次选择最轻的集装箱装船，然后判断是否超重。③重复上一步，直到超重停止。④处理并输出答案。程序见课本。2、活动选择题目学校在最近几天有n个活动，这些活动都需要使用学校的大礼堂，在同一时间，礼堂只能被一个活动使用。由于有些活动时间上有冲突，学校办公室人员只好让一些活动放弃使用礼堂而使用其他教室。现在给出n个活动使用礼堂的起始时间和结束时间，请你帮助办公室人员安排一些活动来使用礼堂，要求安排的活动尽量多。【输入格式】第一行一个整数n(n<=1000)；接下来的n行，每行两个整数，第一个是起始时间，第二个是结束时间。（起始时间<结束时间<=32767）【输出格式】输出最多能安排的活动个数。算法使用贪心算法进行选择，优先安排结束时间早的活动，此策略下很容易证明具有贪心选择性质和最优子结构。假设各活动的时间占用情况如下图所示。第一次选择按“结束时间最早”进行选择，即选择②。注意不能按“开始时间最早”进行选择，那样会选择①。第二次选择在与已选活动不冲突的情况下，按“结束时间最早”进行选择，因此选择③。说明：活动⑥虽然结束时间更早，但与上一个活动冲突而不能选择。后续选择规则同第二次选择。程序见课本。第三部分：知识小结【学生活动】利用学习通进行课堂测试，检测学生本次课知识掌握情况。【课堂总结】教师总结本次课学习内容作业布置1、预习下节课的内容2、发布作业。教学反思授课内容分治学时2教学目标知识目标理解分治算法的核心思想与基本步骤掌握分治算法适用问题的典型特征掌握二分答案的解题思路与实现方法了解最大子段和、循环赛日程表的分治解法能力目标提升复杂问题分解与规律归纳能力强化分治策略分析与算法设计能力培养分治与递归结合的问题求解能力重点与难点重点分治算法“分、治、合”的核心流程二分答案的思想、边界处理与适用场景最大子段和问题的分治求解方法分治算法与递归的结合使用要点难点合理划分子问题并正确合并子问题的解掌握二分答案中整数与实数区间的边界控制教学内容第一部分：课程导入1、点名与签到2、课程重要性阐述本章承接贪心算法，学习高效的分治算法思想分治是计算机解决大规模问题的核心策略之一二分答案、快排、归并排序都是分治的典型应用掌握分治能显著提升处理大数据问题的效率本章实例丰富，可快速强化算法建模与编程能力第二部分：新课讲解一、分治算法概述1、算法思想分治算法的设计思想是将一个难以求解的大问题分割成一些规模较小且性质相同的子问题，以便各个击破，分而治之。2、算法过程整个分治过程分为“分”和“治”二步。“分”就是分解问题，将一个规模较大的问题，分解为多个规模较小的子问题。“治”就是合并，通过合并子问题的解来求出原问题的解。二、二分答案1、概述有一类题目，我们无法正面求解其答案，但我们知道答案的区间范围，并且答案在其区间范围内具有单调性，这时就可以使用二分答案的方式来快速找出答案。2、切割绳子题目有n条绳子，每条绳子的长度已知且均为正整数。绳子可以以任意正整数长度切割，但不可以连接。现在要从这些绳子中切割出m条长度相同的绳段，求绳段的最大长度是多少。【输入格式】第一行是一个不超过100的正整数n第二行是一个不超过108的正整数m第三行是n个不超过106的正整数，表示每条绳子的长度【输出格式】绳段的最大长度，若无法切割，输出Failed。解析答案范围这个问题无法正面求解，但很容易找出答案的范围。答案的最小值min考虑最坏的情况，只使用一条绳子，并将其切割成m段。显然，这时应选择n条绳子中最长的那一条，将其长度除以m就是答案的最小值。答案的最大值max考虑最好的情况，就是n条绳子全部都能得到利用，没有任何切割“余料”。显然，答案的最大值是n条绳子长度之和除以m。②解题思路首先，计算出答案的中间值mid=（min+max）/2。然后，将n条绳子按每段长度为mid进行切割，看看总共能切割出多少段。如果能切割出的段数大于等于m，说明切割长度还可以再大一些，因此下一步将在[mid+1,max]之间搜索新的切割长度。如果切割出的段数小于m，说明切割长度过大，应该再调小一些，因此下一步将在[min,mid-1)之间搜索新的切割长度。按照上述步骤不停地进行搜索，每次搜索都能抛弃一半的搜索区间，很快就能找到一个切割长度t，在此尺寸下，n条绳子可以切割出m段；但若切割长度为t+1时，n条绳子就切割不出m段。这个t就是最终答案。程序详见课本。3、银行贷款题目当一个人从银行贷款后，在一段时间内他将不得不每月偿还固定的分期付款。这个问题要求计算出贷款者向银行支付的利率。假设利率按月累计。【输入格式】三个用空格隔开的正整数。第一个整数表示贷款的原值w0，第二个整数表示每月支付的分期付款金额w，第三个整数表示分期付款还清贷款所需的总月数m。【输出格式】一个实数，表示该贷款的月利率（用百分数表示），四舍五入精确到0.1%。数据保证答案不超过300.0%。解析这个问题用数学方法求解非常麻烦，但使用计算机求解就非常简单了。只需要先假设利率为某一个值，然后利用这个假定的利率与月付款金额w，计算出在m个月后总共还了多少钱。如果这个钱数大于贷款的原值w0，就说明利率高了，需要再调低一点；反之，如果这个钱数小于w0，就说明利率低了，需要再调高一点。经过反复尝试，就能找出正确的利率值。三、典型分治例题1、最大子段和题目给出一个长度为n的序列a，选出其中连续且非空的一段使得这段和最大。【输入格式】第一行是一个整数，表示序列的长度n，1≤n≤2×105。第二行有n个整数，第i个整数表示序列的第i个数字ai，-104≤ai≤104。【输出格式】输出一行，一个整数表示答案。解析将数组从中间分成两半，然后分别求出这两半区间内的最大子段和。考虑到最大子段不一定全在数组的左半区间或者右半区间，它也可能跨越二个子区间的分界线。因此，整个数组的最大子段和为以下三种情况中的最大者：左半区间中的最大子段和右半区间中的最大子段和跨越区间分界线的最大子段和程序详见课本。2、股票买卖内容见课本，采用课堂讨论，作为课堂练习。3、循环赛日程表内容见课本，主要采用课堂讨论。作业布置1、预习下节课的内容2、发布作业。教学反思授课内容搜索学时2教学目标知识目标理解搜索算法的核心思想与解空间树概念掌握回溯法的基本框架与剪枝优化方法掌握深度优先搜索与广度优先搜索的原理与区别了解栈和队列在搜索中的应用与迷宫问题解法能力目标提升复杂问题解空间建模与规律抽象能力强化搜索算法设计与剪枝优化的实践能力培养根据问题场景选择合适搜索策略的能力重点与难点重点回溯法的基本思想、算法框架与剪枝技巧深度优先搜索DFS的递归实现与回溯过程广度优先搜索BFS的队列实现与最短路径求解全排列、子集和、迷宫问题的搜索解法难点设计合理剪枝条件，减少无效搜索区分DFS与BFS的适用场景并正确实现教学内容第一部分：课程导入1、点名与签到2、课程重要性阐述本章承接分治算法，学习被称为万能解题法的搜索算法搜索是解决无直接规律问题的最常用核心方法回溯、DFS、BFS是竞赛与考级中的高频考点掌握搜索能大幅提升复杂问题的求解能力本章结合典型例题，系统学习搜索与优化的实用技巧第二部分：新课讲解一、搜索基础1、搜索概述搜索算法是计算机解题中常用的算法之一，又称为“万能解题法”。搜索与暴力枚举的解题思想是一致的，搜索可以说是一种组织条理的枚举，同时它还通过及时“剪枝”来避免无意义的搜索以提高效率。2、全排列与解空间树全排列给出3个数字“123”，要求输出它们的全排列。算法：通过枚举第一位、第二位、第三位上数字可能的取值，就可以生成全排列。解空间树解空间树是解空间的一种组织形式，此形式展示了解空间的逐步生成过程。使用搜索算法时，一个重要的问题就是构造出解空间树，然后按照某种顺序遍历这棵树来寻找问题的答案。3、深搜、广搜与回溯深度优先搜索深度优先搜索(DFS)，是从根节点开始，沿某一个分支尽可能深地向下搜索，触底之后，再回退一级，然后再沿此级节点的其余分支继续向下搜索。只有某个下级节点的所有分支全部搜索完成之后，才退回到上一级节点处。广度优先搜索广度优先搜索(BFS)，是从根节点开始，沿所有可能的分支同时向前搜索。它强调在所有可能的路径上“齐头并进”地向前搜索。搜索与回溯搜索与回溯算法简称回溯法，它是深搜最常见的一种形式。回溯与深搜没有本质上的区别，只是侧重点有所不同。回溯法以穷举所有可能解为核心目标，通过系统性尝试和撤回选择来筛选满足条件的解，常用于组合优化问题。二、回溯法1、基本思想为了求得问题的解，先选择某一种可能的情况向前探索，在探索过程中，一旦发现原来的选择是错误的，就退回一步重新选择，再继续向前探索。如此反复进行，直至得到解或证明无解。2、算法框架voidSearch(intk) //第k步操作{if(到达目的地){输出解;return;}for(i=1;i<=本步可选方案总数;i++)if(第i种选法能够满足条件) //剪枝{保存结果 //保存第k步的选择Search(k+1); //进入第k+1步回溯 //退回第k步的初始状态}}3、子集和问题问题给定有n个不同正整数的集合w=（w1，w2，…,wn）和一个正整数W，要求找出w的子集s，该子集中所有元素的和为W。例如，当n=4，w=（11,24,13,7），W=31时，满足要求的子集为（11,13,7）和（24,7）。解析本题的算法非常简单，就是先考虑集合的第1个数，它有选与不选二种况；然后再考虑第2个数，它也有选与不选二种情况，依次类推。这样针对n个数的选择共有2n种组合，只需要检查这2n种组合中，哪些组合的和等于W即可。以w=（11,13,24,7）为例，其解空间树如下图所示。在本题中，剪枝问题非常重要。由于n个元素有2n种组合，将全部路径都搜索一遍时间复杂度非常高，因此，要及时进行左子树剪枝与右子树剪枝。程序详见课本。三、迷宫类问题1、概述迷宫问题是经典的程序设计问题。最简单的迷宫可以表示为一个由方块组成的矩阵，其中每个方块或者为墙，或者为通道。针对迷宫，主要有二类问题：寻找出口和寻找最短路径。寻找出口从指定的位置开始，找到任意一个出口，从而走出迷宫。这个问题使用深度优先搜索和广度优先搜索两种算法均可。寻找最短路径指定入口与出口的位置，找出二者之间的最短路径。这个问题需要使用广度优先搜索，这样搜索出的第一条路径就是最短路径。2、使用广度优先搜索求最短路径搜索过程准备一个队列，先将入口单元格放入队列中，然后进行如下循环：while(队列非空){ 取出队首元素; if（若队首元素是出口） 已找到最短路径，结束 else 将队首元素周围是“路”的单元格都添加到队尾（已搜索过的除外）}这样，通过一个循环驱动，在每轮循环中，同时向所有的路径都前进一步。当发现有一条路径已到达出口时，这条路径就是最短的。图示以课本上的样例数据为例，搜索过程如下图所示：程序详见课本。3、使用深度优先搜索寻找出口如果只需要找到出口，使用深度优先的搜索即可，搜索过程如下。准备一个栈，并将入口单元格入栈，然后进行如下循环：while（栈非空）{ if(栈顶元素是出口){输出路径;结束;}else{ 针对栈顶元素，在其四周寻找一个从未走过并且是“路”的单元格 if(能找到上述单元格) 将其入栈; //这样下次循环将会针对此单元格再向前搜索 else 将栈顶元素出栈;//此元素是一条死路的末端，出栈使路径后退}第三部分：知识小结【学生活动】利用学习通进行课堂测试，检测学生本次课知识掌握情况。【课堂总结】教师总结本次课学习内容作业布置1、预习下节课的内容2、发布作业。教学反思授课内容动态规划学时4教学目标知识目标理解动态规划的核心思想与基本概念掌握最优子结构、无后效性、公共子问题三大特征掌握数字金字塔、01背包的状态定义与转移方程了解递归、递推及滚动数组优化的实现方式能力目标提升最优解问题的抽象建模与规律分析能力强化状态转移方程的推导与算法设计能力培养动态规划与其他算法择优选用的实践能力重点与难点重点动态规划三大核心特征与适用场景数字金字塔问题的状态转移与求解过程01背包问题的思路与状态转移方程递归、递推与滚动数组优化实现方法难点正确推导状态转移方程并理解其含义掌握01背包一维优化与逆序遍历原理教学内容第一部分：课程导入1、点名与签到2、课程重要性阐述本章承接搜索算法，学习求解最优解问题的高效方法动态规划是竞赛、考级与面试中的最高频考点之一可解决贪心、搜索难以处理的多阶段决策最优问题通过子问题复用与优化，大幅降低时间复杂度本章由浅入深，为后续复杂算法打下核心基础第二部分：新课讲解一、算法概述1、引例：数字金字塔下图是一个数字金字塔，要求寻找一条从最高点到底部任意处的路径，使路径上数字的和最大。每一步可以从当前点走到其左下方或者右下方。2、解题思路正确的解题思路为使用动态规划的思想，从原问题开始，逐步分解成子问题，待子问题求解之后，再逐步返回求出原问题的解，整个过程如下图所示。3、重要概念状态状态是指用于描述在某个阶段所面临的子问题的变量或者参数的集合。以数字金字塔为例，状态可以定义为：dp[i][j]。它表示从第i行第j列的位置出发，到达底部的最大路径和。其中：i表示当前所在的行，j表示当前所在的列。状态转移方程状态转移方程是描述状态之间关系的数学表达式，它定义了如何从一个或多个子问题的解推导出当前问题的解。以数字金字塔为例，其状态转移方程如下：4、动态规划算法与分治算法类似，动态规划的基本思想也是将要求解的问题分解成若干个子问题，先求子问题的解，然后从这些子问题的解得到原问题的解。5、三大特征能够使用动态规划解决的问题，需要具有三大特征：最优子结构、无后效性和公共子问题。最优子结构最优子结构是指原问题的最优解中需要包含其子问题的最优解，或者说原问题的最优解可以由子问题的最优解组合而成。无后效性无后效性是某阶段的状态一旦确定，此后过程的决策不再受此前各种状态及决策的影响。公共子问题在使用递归法自顶向下求解问题时，会产生一些重复的子问题。针对有公共子问题时消除重复求解的方案是使用“备忘录”技术。二、典型例题1、数字金字塔题目见前面的介绍编程模式动态规划类程序都有二种编程模式：递归法和递推法。递归模式递归模式的视角是从顶向下的，即从原问题开始，考虑如何分解成子问题。由于子问题与原问题具有相同的结构，所以可以递归调用原问题的处理函数来处理子问题。金字塔的递归模式核心代码如下：intn; //金字塔行数inta[31][31]; //存储金字塔中的数据intdp[31][31]; //备忘录,使用dp[i][j]保存pyramid(i,j)的返回值intpyramid(inti,intj) //返回从i行j列上的数字开始的最大路径和{ if(dp[i][j]!=-1)returndp[i][j];//此前已记录过参数(i,j)对应的计算结果 if(i==n-1) //已到达最后一行,注意从行号从0算起 dp[i][j]=a[i][j]; else dp[i][j]=a[i][j]+max(pyramid(i+1,j),pyramid(i+1,j+1)); returndp[i][j];}递推模式递推模式的视角是从底向上的，即从最末级的子问题开始，利用它们来推算出一个规模较大一点的子问题的解，然后再利用这些规模较大一点的子问题的解来推算出规模更大的子问题的解，直到推算出原问题的解。金字塔的递推模式核心代码如下：intn; //金字塔行数inta[31][31]; //存储金字塔中的数据intdp[31][31]; //存储递推结果for(inti=n-1;i>=0;i--)//计算最大路径和 for(intj=0;j<=i;j++) { if(i==n-1) dp[i][j]=a[i][j]; else dp[i][j]=a[i][j]+max(dp[i+1][j],dp[i+1][j+1]); }再针对剩余数据，重复以上步骤，直到全部数据都有序为止。2、股票买卖题目已知n天中每一天股票的价格，在最多允许买入和卖出股票各一次的情况下，要求计算所能获取的最大利润。注意股票只能先买入后卖出。【输入格式】第一行，一个正整数n，表示天数；1=<n<=105。第二行，n个正整数，表示n天内股票的价格。每个价格不超过104。【输出格式】一个整数，表示最大利润。解析本题中每天都面临二种操作：买入股票和卖出股票。由于不能确定应该买入还是卖出，我们只能在每天都将这二种操作枚举一下。对于买入，需要和之前的买入价格对比一下，如果今天的价格更低，就进行买入，否则不需要买入。因此，我们需要一个变量来记录遇到过的最低价格。对于卖出，我们简单地记录卖出之后能获得的利润即可。如果今天卖出比之前卖出获得的利润更高，就卖出；否则不卖出。程序intn,p;intminPrice=20000000; //最低购入价格intmaxProfit=-1; //最高收益cin>>n;for(inti=0;i<n;i++) //采用递推方式计算最优解{ cin>>p; if(minPrice>p)minPrice=p; //记录遇到过的最低购入价格 if(p-minPrice>maxProfit)maxProfit=p-minPrice; //记录最大收益}cout<<maxProfit<<endl;三、01背包问题1、背包问题概述什么是背包问题背包问题是一个著名的组合优化问题，是动态规划的典型应用之一。背包问题可描述为：有N件物品，每件物品的重量和价值各不相同。现有一个背包，它的容量为W(即装入物品的总重量不超过W)，如何选择装入物品，使背包内物品的价值最大。多种多样的背包问题背包问题有三种基本形式：01背包问题、完全背包问题和多重背包问题。01背包问题是上述三种形式中最简单一种，其特点是有n件物品可供选择，每件物品只能选择一次。因为每件物品要么最终装入背包（记为1），要么不装入背包（记为0），故称为01背包。解法01背包问题可以使用动态规划或搜索来解，其中使用动态规划来解是最优的。2、01背包问题的递归解法思路考虑最后一件物品，它只有放入选与不选二种选择。如果不选，则原问题变为n-1件物品放入背包的最大价值问题。如果选择，则它放入背包之后，背包内的价值增加了，但同时可用容量变小了。原问题变为n-1件物品放入一个容量稍小一些的背包的最大价值问题。状态转移方程用f[i][v]表示前i件物品放入容量为v的背包中的最大价值，则01背包问题的状态转移方程为：f[i][v]=max(f[i-1][v],f[i-1][v-w[i]]+c[i])f[i-1][v]：表示第i件物品不装入背包，将背包的容量v全部用于装前i-1件物品时能装入的最大价值。程序intw[30],c[30]; //分别存储每件物品的重量和价值intPackage(intsum,intv,intn){ if(n==1)returnv>=w[0]?sum+c[0]:sum; //仅剩余一件物品时 if(v<w[n-1])returnPackage(sum,v,n-1); //背包装不下第n件物品时 returnmax(Package(sum+c[n-1],v-w[n-1],n-1),Package(sum,v,n-1)); }3、01背包问题的递推解法思路使用递推法的解题过程，相当于在逐行填写如下表所示一张表格。背包容量物品件数123456778101(重量2,价值1）01111111112(重量3,价值4）01445555553(重量4,价值6）4(重量8,价值9）程序intw[31],c[31]; //分别存储每件物品的重量和价值intf[31][201];//f[i][v]表示前i件物品装入容量为v的背包中的最大价值for(inti=1;i<=n;i++) //循环计算每一件物品{for(intv=1;v<=m;v++)if(w[i]<=v)//第i件物能够放入背包内时 f[i][v]=max(f[i-1][v],f[i-1][v-w[i]]+c[i]);else //第i件物品无法放入背包内时 f[i][v]=f[i-1][v];}4、01背包问题的递推优化解法问题的提出当物品数量n很大时，上面表格会有很多行，要占用大量内存。那么，能否优化一下此表格，以减少内存占用呢？解决方案我们观察单元格的计算公式：f[i][v]=max(f[i-1][v],f[i-1][v-w[i]]+c[i])在计算第i行上的数据时，只使用了第i-1行上的数据，第i-2行及之前的行上的数据并没有用到，当然也就不需要存储了。由此，我们可以将表10-1所示的表格压缩为只一行，即简化成了一个一维数组。程序intw[31],c[31]; //分别存储每件物品的重量和价值intf[201]; //滚动数组for(inti=1;i<=n;i++) //循环计算每一件物品{for(intv=m;v>=w[i];v--) //注意必须反向循环 f[v]=max(f[v],f[v-w[i]]+c[i]);}第三部分：知识小结【学生活动】利用学习通进行课堂测试，检测学生本次课知识掌握情况。【课堂总结】教师总结本次课学习内容作业布置1、预习下节课的内容2、发布作业。教学反思授课内容高精度运算学时2教学目标知识目标理解高精度运算的概念与适用场景掌握高精度数据的字符串输入与数组逆序存储方法掌握高精度加减乘除的基本运算原理了解高精度与低精度运算的区别和实现思路能力目标提升超大整数问题的存储与处理能力强化模拟手工运算的算法设计能力培养高精度程序编写与调试优化能力重点与难点重点高精度数的逆序存储与位数对齐方法高精度加法、减法、乘法的实现步骤高精度与低精度混合运算的处理技巧进位、借位、前导零的处理规则难点高精度乘法的位数对齐与进位处理高精度除法的模拟过程与余数处理教学内容第一部分：课程导入1、点名与签到2、课程重要性阐述本章解决普通数据类型无法存储的超大整数运算问题高精度是算法竞赛、编程考级的高频必考内容学会用数组模拟数字，突破计算机数值范围限制掌握加减乘除全套高精度算法，提升底层编程能力为大数处理、密码学、阶乘等问题提供基础实现方案第二部分：新课讲解一、高精度运算概述1、什么是高精度运算非常大的数据，超过了编程语言内置数据类型的最大表示范围时（一般指整数，超过了longlong的表示范围），必须自行存储与运算，就是高精度运算。2、高精度数据的存储高精度数据一般以字符串的方式读取，读取后分离出各位数字并反向存放于数组中，如下图所示。二、高精度加法1、高精度加高精度原理二个高精度数相加是通过完全模拟手工加法来实现的，在手工加法中，将二个数从个位开始逐位相加，并考虑低位向前的进位即可。核心代码inta[100],b[100],c[101]; //全局数组，已初始化为0intx=0; //记录进位for(i=0;i<len1||i<len2; i++)//从个位开始，逐位相加{ c[i]=a[i]+b[i]+x; //两数相加 x=c[i]/10; //计算进位 c[i]%=10;}c[i]=x; //最高位的进位if(c[i]==0)i--; //如果最高位没有进位，则和的实际有效位数减一while(i>=0)cout<<c[i--]; //输出结果2、高精度加低精度原理将低精度数加到高精度数的个位上，而后不断向前进位即可。以“987+556”为例，我们将“987”视为高精度数，首先将它的各位数字分离并存储至数组，结果为：a[0]=7，a[1]=8，a[2]=9。然后，再进行如下计算：将a[0]加上556，得到563，扣除进位值56，得a[0]=3。将a[1]加上进位值56，得到64，再扣除向上的进位值6，得a[1]=4。将a[2]加上进位值6，得a[2]=15。注意，a[2]中的值虽然大于9，但可以不用再向前进位。因如果将a[2]、a[1]、a[0]依次输出到屏幕，这些数字“粘接”在一起之后就是正确结果：1543。核心代码见课本。三、高精度减法1、高精度减高精度原理模拟手工减法，从个位开始逐位相减。减法需要解决二个问题：不够减及借位。为了便于统一处理，要求被减数必须大于等于减数。如果被减数小于减数，需要先输出“-”，然后交换二者。在完成某一位的相减之前，需要先判断是否够减，若不减需要提交借位。{ for(intj=0;j<n-1-i;j++) //内层循环n-1-i次 { if(a[j]>a[j+1]) //需要将a[j]与a[j+1]交换 { inttemp; temp=a[j]; a[j]=a[j+1]; a[j+1]=temp; } } }核心代码strings1,s2;cin>>s1>>s2; //输入被减数、减数inti=s1.length()-s2.length();if(i<0||i==0&&s1<s2)//被减数小时，输出负号并交换s1与s2{ cout<<'-'; swap(s1,s2);}….for(i=0;i<=len1||i<=len1; i++){ if(a[i]<b[i]) //预先判断是否够减 { a[i]+=10; //不够减，向高位借1当10 a[i+1]--; } c[i]=a[i]-b[i]; //对应位相减 }while(c[i]==0&&i>0)i--;//删除结果中的前导0（结果为0保留一个0）while(i>=0)cout<<c[i--];//输出结果2、高精度减低精度原理将高精度数的个位减去低精度数，然后不断从低位向高位借位，直到每一位数字都大于等于0。核心代码见课本。四、高精度乘法1、高精度乘高精度原理仍然是模拟手工乘法，以图11-3为例进行介绍，运算过程如下：要点如果二个乘数分别为m位与n位，则结果最长为m+n位。a[i]与b[j]相乘的结果，应该记入到c[i+j]。核心代码for(inti=0;i<len1;i++)//乘法遵循交换律，不区分被乘数与乘数{ intx=0; //用于存放进位 for(intj=0;j<len2;j++) { c[i+j]+=a[i]*b[j]+x;//原有内容+当前乘积+进位 x=c[i+j]/10; c[i+j]%=10; } c[i+len2]=x; //结果中最高位向前的进位}inti=len1+len2;//结果的最高位数while(c[i]==0&&i>0)i--; //删除前导0while(i>=0) cout<<c[i--];//输出乘积2、高精度乘低精度原理将高精度数的各位数字与低精度数分别相乘，然后再针对运算结果中的每一位数字处理向前进位（将低位数中10以上的部分加到上一位上）即可。核心代码见课本。五、高精度除法1、高精度除以低精度原理模拟手工除法，以567÷53为例进行介绍（我们假设567为高精度数据），其运算过程如下图所示。被除数的存储除法操作是从被除数的高位开始运算的，因此在存储时并不需要反转方向。核心代码for(i=0;i<len;i++) //按位相除{ x=x*10+s[i]-48; //x内为上一步操作的余数 c[i]=x/b; //本步操作的商 x%=b;