分治法求最大值最小值
a.为一个分治算法编写伪代码，该算法同时求出一个n元数组的最大元素和最小元素的值。
b.假设n=2k,为该算法的键值比较次数建立递推关系式并求解。
c.请拿该算法与解同样问题的蛮力算法做一个比较。
解答：
a.同时求出原数组最大值和最小值，先将原数组一分为二，再找出划分的两个部分的最值，然后再合并最值，找划分的两个部分的最值就递归地在这两个部分中用同样的方法找最大值和最小值，然后只需要给出最小规模的确切解法作为递归出口就可以了。
算法MaxMin(A[f…l],Max,Min)
//该算法利用分治法求得数组A中的最大值和最小值
//输入：数值数组A[f..l]
//输出：最大值Max和最小值Min
if l?f=0 //只有一个元素时
Max←A[f]；Min←A[f];
else
if l－f=1 //有两个元素时
if A[f]>A[l] //基本操作是作比较
Max←A[f] ,Min←A[l]
else Max←A[l] ,Min←A[f]
else //有大于两个元素时
MaxMin(A
[f…(f+l
2)]
,Max1,Min1);//递归解决前一部分
MaxMin(A
[(f+l
2)…l]
,Max2,Min2); //递归解决后一部分
Max←max {Max1,Max2};//从两部分的两个最大值中选择大值
Min←min {Min1,Min2};//从两部分的两个最小值中选择小值 return Max,Min;
b.假设n=2k,比较次数的递推关系式:
C(n)=2C(n
2
)+2 ,n>2
C(1)=0, C(2)=1
C(n)=C(2k)=2C(2k-1)+2
=2[2C(2k-2)+2]+2
=22C(2k-2)+22+2
=23C(2k-3)+23+22+2
...
=2k-1C(2)+2k-1+2k-2+...+2 //C(2)=2 =2k-1+2k-1+2k-2+...+2 //等比数列求和
=2k-1+2k-2 //2k=n， 2k-1=n
2
=3n
?2
2
b.蛮力法的算法如下：
算法ForceMaxMin(A[l..r])
//用蛮力法得到数组A的最大值和最小值
//输入：数值数组A[l…r]
//输出：最大值Max和最小值Min
Max=Min=A[l];
for i=l+1 to r do
if A[i]>Max Max←A[i];
else if A[i] Min←A[i] return Max,Min c.作比较 ForceMaxMin的时间复杂度T(n)=2n?2 算法MaxMin的时间复杂度为3n ?2，ForceMaxMin的时间复杂度为2n-2，都属于Θ(n)， 2 但MaxMin的速度要比ForceMaxMin的稍快一点。 算法练习题-分章节-带答案 算法练习题---算法概述 一、选择题 1、下面关于算法的描述，正确的是（） A、一个算法只能有一个输入 B、算法只能用框图来表示 C、一个算法的执行步骤可以是无限的 D、一个完整的算法，不管用什么方法来表示，都至少有一个输出结果 2、一位爱好程序设计的同学，想通过程序设计解决“韩信点兵”的问题，他制定的如下工作过程中，更恰当的是（） A、设计算法，编写程序，提出问题，运行程序，得到答案 B、分析问题，编写程序，设计算法，运行程序，得到答案 C、分析问题，设计算法，编写程序，运行程序，得到答案 D、设计算法，提出问题，编写程序，运行程序，得到答案 3、下面说法正确的是（） A、算法+数据结构=程序 B、算法就是程序 C、数据结构就是程序 D、算法包括数据结构 4、衡量一个算法好坏的标准是（）。 A、运行速度快 B、占用空间少 C、时间复杂度低 D、代码短 5、解决一个问题通常有多种方法。若说一个算法“有效”是指( )。 A、这个算法能在一定的时间和空间资源限制内将问题解决 B、这个算法能在人的反应时间内将问题解决 C、这个算法比其他已知算法都更快地将问题解决 D、A和C 6、算法分析中，记号O表示（），记号Ω表示（）。 A.渐进下界 B.渐进上界 C.非紧上界 D.非紧下界 7、以下关于渐进记号的性质是正确的有：（） A.f(n)(g(n)),g(n)(h(n))f(n)(h(n)) =Θ=Θ?=Θ B.f(n)O(g(n)),g(n)O(h(n))h(n)O(f(n)) ==?= C. O(f(n))+O(g(n)) = O(min{f(n),g(n)}) D.f(n)O(g(n))g(n)O(f(n)) =?= 班级：高二（ ）班 姓名：____________ 教学目标： 1．使学生理解函数的最大值和最小值的概念，掌握可导函数f (x )在闭区间上所有点（包括端点a ，b ）处的函数中的最大（或最小）值必有的充分条件； 2．使学生掌握用导数求函数的极值及最值的方法和步骤． 教学重点： 利用导数求函数的最大值和最小值的方法． 教学过程： 一、问题情境 1．问题情境．函数极值的定义是什么？ 2．探究活动．求函数f (x )的极值的步骤． 二、建构数学 1．函数的最大值和最小值． 观察图中一个定义在闭区间[]b a ,上的函数)(x f 的图象． 图中)(1x f ,35(),()f x f x 是极小值，24(),()f x f x 是极大值． 函数)(x f 在[]b a ,上的最大值是)(b f ，最小值是3()f x ． 一般地，在闭区间[]b a ,上连续的函数)(x f 在[]b a ,上必有最大值与最小值． 说明： （1）在开区间(,)a b 内连续的函数)(x f 不一定有最大值与最小值． 如函数x x f 1)(=在),0(+∞内连续，但没有最大值与最小值； （2）函数的最值是比较整个定义域内的函数值得出的；函数的极值是比较极值点附近函数值得出的； (3)函数在其定义区间上的最大值、最小值最多各有一个，而函数的极值可能不止一个，也可能没有一个． 2．利用导数求函数的最值步骤： 由上面函数)(x f 的图象可以看出，只要把连续函数所有的极值与定义区间端点的函数值进行比较，就可以得出函数的最值了． 设函数)(x f 在[]b a ,上连续，在(,)a b 内可导，则求)(x f 在[]b a ,上的最大值与最小值的步骤如下： 昆明理工大学信息工程与自动化学院学生实验报告 （ 201 — 201 学年 第 1 学期 ） 课程名称：算法分析与设计 开课实验室： 年 月 日 一、上机目的及内容 1.上机内容 给定有n 个整数（可能有负整数）组成的序列（a 1,a 2,…,a n ），求改序列形如 ∑=j k k a 1 的子段和的 最大值，当所有整数均为负整数时，其最大子段和为0。 2.上机目的 （1）复习数据结构课程的相关知识，实现课程间的平滑过渡； （2）掌握并应用算法的数学分析和后验分析方法； （3）理解这样一个观点：不同的算法能够解决相同的问题，这些算法的解题思路不同，复杂程度不同，解题效率也不同。 二、实验原理及基本技术路线图（方框原理图或程序流程图） （1）分别用穷举法、分治法和动态规划法设计最大子段和问题的算法； （2）对所设计的算法采用大O 符号进行时间复杂性分析； （3）上机实现算法，并用计数法和计时法分别测算算法的运行时间； （4）通过分析对比，得出自己的结论。 穷举法是用一个二维数组将从i 到j 的和都记录下来，再比较各元素的大小，时间复杂性为O （n 2），分治法的设计思想是不断将问题为子问题，然后求解子问题，最后对解进行合并，时间复杂性为O(nlog n )，动态规划法的设计思想是将问题划分为若干个子问题，时间复杂度为O(n)。 分治法流程图： 穷举法流程图： 动态规划法流程图： 三、所用仪器、材料（设备名称、型号、规格等或使用软件） 1台PC 及VISUAL C++6.0软件 四、实验方法、步骤（或：程序代码或操作过程） 程序代码： //穷举法 #include 例说求函数的最大值和最小值的方法 例1.设x 是正实数，求函数x x x y 32+ +=的最小值。 解：先估计y 的下界。 55)1(3)1(5)21(3)12(222≥+- +-=+-+ ++-=x x x x x x x y 又当x =1时，y =5，所以y 的最小值为5。 说明 本题是利用“配方法”先求出y 的下界，然后再“举例”说明这个下界是可以限到的。“举例”是必不可少的，否则就不一定对了。例如，本题我们也可以这样估计： 77)1(3)1(7)21(3)12(222-≥-+ +-=-++ ++-=x x x x x x x y 但y 是取不到-7的。即-7不能作为y 的最小值。 例2. 求函数1 223222++--=x x x x y 的最大值和最小值。 解 去分母、整理得：(2y -1)x 2+2(y +1)x +(y +3)=0. 当2 1≠y 时，这是一个关于x 的二次方程，因为x 、y 均为实数，所以 ?=[2(y +1)]2-4(2y -1)(y +3)≥0, y 2+3y --4≤0, 所以 -4≤y ≤1 又当3 1-=x 时，y =-4;x =-2时，y =1.所以y min =-4，y max =1. 说明 本题求是最值的方法叫做判别式法。 例3.求函数152++-=x x y ，x ∈[0,1]的最大值 解：设]2,1[1∈=+t t x ，则x =t 2-1 y = -2(t 2-1)+5t = -2t 2+5t +1 原函数当t =169,45=x 即时取最大值8 33 例4求函数22 3,5212≤≤+--=x x x x y 的最小值和最大值 解：令x -1=t ( 121≤≤t ) 则t t t t y 4142+=+= y min =5 1,172max =y 例5.已知实数x ,y 满足1≤x 2+y 2≤4,求f (x )=x 2+xy +y 2的最小值和最大值 解：∵)(2 122y x xy +≤ ∴6)(23 ),(2222≤+≤++=y x xy y x y x f 又当2==y x 时f (x ,y )=6，故f (x ,y )max =6 又因为)(2122y x xy +- ≥ 方法技巧练——最大值与最小值问题 1.数字排列中的最大值与最小值。 解决数字排列中的最大值与最小值问题,要清楚:一个自然数,数位越多,这个数越大;数位越少,这个数 越小。 (1)一个六位的自然数,各个数位上的数字之和是13,这个自然数最大是( 940000),最小是( 100039)。 (2)一个八位的自然数,各个数位上的数字之和是21,这个自然数最大是( 99300000),最小是( 10000299)。 2.根据近似数推断精确数的最大值与最小值。 根据近似数推断精确数的最大值与最小值,要把两种情况考虑完整:这个精确数可能比近似数大,是经过“四舍”得到的;这个精确数也可能比近似数小,是经过“五入”得到的。再结合数值最大与最小的原则确定每一位上的数字。 (1)一个自然数,省略万位后面的尾数得到的近似数是93万,最大是多少?最小是多少? 最大:934999 最小:925000 【提示】“四舍五入”后是93万,“四舍”→万位上的数是3→千位上最大是4,其余各位最大是9→最大数。“五入”→万位上的数是2→千位上最小是5,其余各位最小是0→最小数。 (2)一个整数的近似数是200万,这个数最大是多少?最小是多少? 最大:2004999 最小:1995000 3.两个数的和一定,积的最大值与最小值。 (1)两个数的和是26,这两个数分别是多少时,积最大? 13+13=26 13×13=169 答:积最大是169。 (2)两个数的和是43,这两个数相乘,积最大是多少? 21+22=43 并且两个加数最接近 21×22=462 答:积最大是462。 (3)两个数的和是52,这两个数相乘,积最大是多少? 26+26=52 26×26=676 答:积最大是676。 (4)用1,4,5,8这四个数字组成两个无重复数字的两位数,再把这两个数相乘,积最大是多少?最小是多少? 积最大:先确定两个因数的十位8,5,再根据两个因数的相近原理确定个位81×54=4374 积最小:先确定两个因数的十位1,4,再根据两个因数的相近原理确定个位15×48=720 答:积最大是4374,最小是720。 小学奥数最大值最小值问题汇总 1．三个自然数的和为15，这三个自然数的乘积最大可能是_______。 3．一个长方形周长为24厘米，当它的长和宽分别是_______厘米、_______厘米时面积最大，面积最大是_______平方厘米。 4．现在有20米的篱笆，利用一堵墙围一个长方形鸡舍，要使这个鸡舍面积最大，长应是_______米，宽应是_______米。 5．将16拆成若干个自然数的和，要使和最大，应将16拆成_______。 6．从1，2，3，…，2003这些自然数中最多可以取_______个数，才能使其中任意两个数之差都不等于5。 7．一个两位小数保留整数是6，这个两位小数最大是_______，最小是_______。 8．用1克、2克、4克、8克、16克的砝码各一个和一架天平，最多可以称出_______种不同的整数的重量。 9．有一架天平，左右都可以放砝码，要称出1～80克之间所有整克数的重量，如果使砝码个数尽可能少，应该用_______的砝码。 10．如下图，将1～9这9个数填入圆圈中，使每条线上的和相等，使和为A，A最大是_____。二、解答题（30分） 1．把19分成若干个自然数的和，如何分才能使它们的积最大？ 2．把1～6这六个数分别填在下图中三角形三条边的六个圆圈内，使每条边上三个圆圈内的数的和相等，求这个和的最大值与最小值。 3．自行车的前轮轮胎行驶9000千米后要报废，后轮轮胎行驶7000千米后要报废。前后轮可在适当时候交换位置。问一辆自行车同时换上一对新轮胎，最多可行驶多少千米？ 4．如下图，有一只轮船停在M点， 现需从OA岸运货物到OB岸，最后停在N点，这只船应如何行走才能使路线最短？ 5．甲、乙两厂生产同一型号的服装，甲厂每月生产900套，其中上衣用18天，裤子用12天；乙厂每月也生产900套，但上衣用15天，裤子也要用15天。两厂合并后，每月最多可以生产多少套衣服？ 6．现在有若干千克苹果，把苹果装入筐中，要求能取出1~63千克所有整千克数的苹果，并且每次都是整筐整筐地取出。问：至少需要多少个空筐？如何装？ B卷（50分）一、填空题（每题2分，共20分） 1．在六位数865473的某一位数码后面再插入一个该数码，能得到的七位数中最小的是_____。 2．用1～8这八个数码组成两个四位数，要使这两个数的差尽量小，这个差是______。 3．三个质数的和是100，这三个质数的积最大是______。 4．有一类自然数，自左往右它的各个数位上的数字之和为8888，这类自然数中最小的 (1)求最大量的最大值：让其他值尽量小。例：21棵树载到5块大小不同的土地上，要求每块地栽种的棵数不同，问栽树最多的土地最多可以栽树多少棵?解析：要求最大量取最大值，且量各不相同，则使其他量尽可能的小且接近，即为从“1”开始的公差为“1”的等差数列，依次为1、2、3、4，共10棵，则栽树最多的土地最多种树11棵。(2)求最小量的最小值：让其他值尽量大。例：6个数的和为48，已知各个数各不相同，且最大的数是11，则最小数最少是多少?解析：要求最小数的最小值，则使其他量尽可能的大， 函数的最大值和最小值教案 1.本节教材的地位与作用本节主要研究闭区间上的连续函数最大值和最小值的求法和实际应用,分两课时,这里是第一课时,它是在学生已经会求某些函数的最值,并且已 经掌握了性质:“如果f(x)是闭区间[a,b]上的连续函数,那么 f(x)在闭区间[a,b]上有最大值和最小值” ,以及会求可导函数的极值之后进行学习的,学好这一节,学生将会求更多的函数的 最值,运用本节知识可以解决科技、经济、社会中的一些如何使成本最低、产量最高、效益最大等实际问题.这节课集中体现了数形结合、理论联系实际等重要的数学思想方法,学好本节,对于进一步完善学生的知识结构,培养学生用数学的意识都具有极为重要的意义. 2.教学重点会求闭区间上连续开区间上可导的函数的最值. 3.教学难点高三年级学生虽然已经具有一定的知识基础,但由于对求函数极值还不熟练,特别是对优 化解题过程依据的理解会有较大的困难,所以这节课的难点是理解确定函数最值的方法. 4.教学关键本节课突破难点的关键是:理解方程f′(x)=0的解,包含有指定区间内全部可能的极值点. 【教学目标】根据本节教材在高中数学知识体系中的地位和作用,结合学生已有的认知水平,制定本节如下的 教学目标: 1.知识和技能目标 (1)理解函数的最值与极 值的区别和联系. (2)进一步明确闭区间[a,b]上的连续函数 f(x),在[a,b]上必有最大、最小值. (3)掌握用导数法求上述 函数的最大值与最小值的方法和步骤. 2.过程和方法目标(1)了解开区间内的连续函数或闭区间上的不连续函数不一定有 最大、最小值. (2)理解闭区间上的连续函数最值存在的可能 位置:极值点处或区间端点处. (3)会求闭区间上连续,开区 间内可导的函数的最大、最小值. 3.情感和价值目标 (1) 认识事物之间的的区别和联系. (2)培养学生观察事物的能力,能够自己发现问题,分析问题并最终解决问题. (3)提高 学生的数学能力,培养学生的创新精神、实践能力和理性精神. 【教法选择】根据皮亚杰的建构主义认识论,知识是个体在 与环境相互作用的过程中逐渐建构的结果,而认识则是起源于主 客体之间的相互作用. 本节课在帮助学生回顾肯定了闭区间 上的连续函数一定存在最大值和最小值之后,引导学生通过观察 闭区间内的连续函数的几个图象,自己归纳、总结出函数最大值、最小值存在的可能位置,进而探索出函数最大值、最小值求解的 方法与步骤,并优化解题过程,让学生主动地获得知识,老师只是 进行适当的引导,而不进行全部的灌输.为突出重点,突破难点, 这节课主要选择以合作探究式教学法组织教学. 【学法指导】对于求函数的最值,高三学生已经具备了良好的知识基础,剩下 的问题就是有没有一种更一般的方法,能运用于更多更复杂函数 的求最值问题?教学设计中注意激发起学生强烈的求知欲望,使 得他们能积极主动地观察、分析、归纳,以形成认识,参与到课堂 实验名称： 最大子段和问题 实验目的： 了解最大子段和问题 实验环境： 操作系统：Windows XP Professional SP3 机器配置：Intel Pentium4 CPU 3.0GHz , 512MB 内存 开发工具：eclipse 实验内容： 1. 求数列的最大子段和(要求时间复杂为nlogn) (算法设计与分析 吕国英 清华大学出 版社 135页 4..3.3 二分法变异) （分治法） （也可用动态规划算法 参看递归王晓东计算机算法设计与分析第三版p61页） 算法的设计思想： 在对分治法德算法分析中注意到，若记???? ? ? <=<==∑=j i k k a n j i i b ][max ][，1<=j<=n,则所求的 最大子段和为： ][1max ][1max 1max ][1max j b n j k a j i n j k a n j i j i k j i k <=<== <=<=<=<==????? ?<=<=<=∑ ∑== 分为两种情况： （1）、当b[j-1]>0时，b[j]=b[j-1]+a[j]。 （2）、当b[j-1]<0时，b[j]=a[j]。 由此可得计算b[j]的动态规划递归式为： b[j]=max }{][],[]1[j a j a j b +-,1<=j<=n 由分析可知：次算法一共比较了n 次，故： T(n)=O(n) 据此可以写出如下程序： 实验步骤： 程序代码如下： package s; public class Po{ public static void main(String[] args) { int[] a=new int[10]; int[] b=new int[10]; int[] x=new int[10]; int start=0; int end = 0; System.out.print("数组为:");//随机赋值 for(int i =0;i<10;i++){ a[i]=(int)(Math.random()*100-50); System.out.print(a[i]+" "); } System.out.print("\n"); tem(a,x,b); int max=maxSum(a,b,end); System.out.print("最大子段和为:"); System.out.println(max); System.out.print("结束位置为:"); System.out.println(findend(a,b,end)); int begin=findStart(a,b,start,end); System.out.print("开始位置为："); System.out.println(begin); systemout(x,start,end,a,b); } public static void tem(int a[],int x[],int b[]) {int n=a.length-1; int sum=0; b[0]=x[0]; 最大值和最小值问题 3.2.2 最大值、最小值问题教学过程：一、复习引入： 1.极大值：一般地，设函数f(x)在点x0附近有定义，如果对x0附近的所有的点，都有f(x)＜f(x0)，就说f(x0)是函数f(x)的一个极大值，记作y极大值=f(x0)，x0是极大值点 2.极小值：一般地，设函数f(x)在x0附近有定义，如果对x0附近的所有的点，都有f(x)＞f(x0).就说f(x0)是函数f(x)的一个极小值，记作y极小值=f(x0)，x0是极小值点 3.极大值与极小值统称为极值注意以下几点：（?。┘?值是一个局部概念由定义，极值只是某个点的函数值与它附近点的函数值比较是最大或最小并不意味着它在函数的整个的定义域内最大或最小（??）函数的极值不是唯一的即一个函数在某区间上或定义域内极大值或极小值可以不止一个（?＃┘?大值与极小值之间无确定的大小关系即一个函数的极大值未必大于极小值，如下图所示，是极大值点，是极小值点，而 > （?ぃ┖?数的极值点一定出现在区间的内部，区间的端点不能成为极值点而使函数取得最大值、最小值的点可能在区间的内部，也可能在区间的端点二、讲解新课： 1.函数的最大值和最小值观察图中一个定义在闭区间上的函数的图象．图中与是极小值，是极大值．函数在上的最大值是，最小值是．一般地，在闭区间上连续的函数在上必有最大值与最小值．说明：⑴在开区间内连续的函数不一定有最大值与最小值．如函数在内连续，但没有最大值与最小值；⑵函数的最值是比较整个定义域内的函数值得出的；函数的极值是比较极值点附近函数值得出的．⑶函数在闭区间上连续，是在闭区间上有最大值与最小值的充分条件而非必要条件． (4)函数在其定义区间上的最大值、最小值最多各有一个，而函数的极值可能不止一个，也可能没有一个⒉利用导数求函数的最值步骤: 由上面函数的图象可以看出，只要把连续函数所有的极值与定义区间端点的函数值进行比较，就可以得出函数的最值了．设函数在上连续，在内可导，则求在上的最大值与最小值的步骤如下：⑴求在内的极值；⑵将的各极值与、比较得出函数在上的最值三、讲解范例：例1求函数在区间上的最大值与最小值例2已知x,y为正实数，且满足，求的取值范围例 分治法求最大子段和问题 共有四种方法： 算法一； 算法二； 算法三、Divide and Conquer 算法四源代码、On-line Algorithm 算法一源代码： /*Given (possibly negative) integers A1, A2, …, AN, find the maximum value. 找最大子段和*/ #include For personal use only in study and research; not for commercial use 线段差的最大值与线段和的最小值问题 有关线段差的最大值与线段和的最小值问题的主要应用原理是：1、两点这间线段最短。2、三角形的任意两边之和大于第三边（找和的最小值）。3、三角形的任意两边之差小于第三边（找差的最大值）。 作图找点的关键：充分利用轴对称，找出对称点，然后，使三点在一条直线上。即利用线段的垂直平分线定理可以把两条线段、三条线段、四条线段搬在同一条直线上。证明此类问题，可任意另找一点，利用以上原理来证明。 一两条线段差的最大值： （1）两点同侧：如图，点P在直线L上运动，画出一点P，使︱PA－PB︱取最大值。作法：连结AB并延长AB交直线L于点P。点P即为所求。︱PA－PB︱=AB 证明：在直线L上任意取一点P。，连结PA、PB，︱PA－PB︱＜AB （2两点异侧：如图，如图，点P在直线L上运动，画出一点P，使︱PA－PB︱取最大值。作法：1、作B关于直线L的对称点B。 B 2、连结AB并延长AB交直线L于点P。点P即为所求。︱PA－PB︱=AB 证明：在直线L上任意取一点P。，连结PA、PB、PB。︱PA－PB︱=︱PA－PB︱＜AB （三角形任意两边之差小于第三边） 二、两条线段和的最小值问题： （1））两点同侧：如图，点P在直线L上运动，画出一点P使P A＋PB取最小值。 （三角形的任意两边之和大于第三边（找和的最小值），P A＋PB=AB （2）两点异侧：如图，点P在直线L上运动，画出一点P使P A＋PB取最小值。 （两点之间线段最短） 三、中考考点： 08年林金钟老师的最后一题：如图，在矩形ABCO中，B（3，2），E（3，1），F（1，2）在X轴与Y轴上是否分别存在点M、N，使得四边形EFNM的周长最小？若存在，请求出周长的最小值，若不存在，请说明理由。 提示：EF长不变。即求F N＋NM＋MF的最小值。利用E关于X轴的对称点E，F的对称点F，把这三条线段搬到同一条直线上。 导数在函数求最大值和最小值中的应用 例1．求函数f (x )＝5x ＋ . 解析：由3040x x +??-? ≥≥得f (x )的定义域为－3≤x ≤4，原问题转化为求f (x )在区间[－3, 4]上的最值问题。 ∵ y ’＝f ’(x ) ＝5 在[－3，4]上f ’(x )＞0恒成立, ∴ f (x )在[－3，4]上单调递增． ∴ 当x ＝－3时y min ＝－15－7， 当x =4时y max =20＋27， ∴ 函数的值域为[－15－7，20＋27]. 例2．设32f (a )，f (－1) 小学奥数最大值最小值问题汇总 1. _____________________________________________________ 三个自然数的和为15，这三个自然数的乘积最大可能是 _______________ 。 3. _________________________________________________ —个长方形周长为24厘米，当它的长和宽分别是_____________________ 厘米、_______ 厘米时面积最大，面积最大是__________ 平方厘米。 4. 现在有20米的篱笆，利用一堵墙围一个长方形鸡舍，要使这个 鸡舍面积最大，长应是_________ 米，宽应是 _________ 米。 5 .将16拆成若干个自然数的和，要使和最大，应将16拆成__________ 。 6 .从1, 2 , 3,…，2003这些自然数中最多可以取 ____________ 个数，才能使其中任意两个数之差都不等于5。 7. __________________________________________________ —个两位小数保留整数是6,这个两位小数最大是____________________ ，最小是________ O 8. 用1克、2克、4克、8克、16克的砝码各一个和一架天平，最 多可以称出________ 种不同的整数的重量。 9. 有一架天平，左右都可以放砝码，要称出1?80克之间所有整克 数的重量，如果使砝码个数尽可能少，应该用__________ 的砝码。10 .如下图，将1?9这9个数填入圆圈中，使每条线上的和相等，使和为 A，A最大是_______ 。二、解答题（30分） 1. 把19分成若干个自然数的和，如何分才能使它们的积最大？ 平均情况:设待查找的元素在数组中的概率为P，不在数组中的概率为1-P,若出现在数组中每个位置的概率是均等的为p/n T(n)=P1D1+P2D2+...+PiDi+(1-P)Dn+1 =p/2+n(1-p/2) 1.叙述分治算法和动态规划算法的基本思想，并比较两种算法的异同。答:分治法将待求解的问题划分成K个较小规模的子问题,对这K个子问题分别求解,再将子问题的解合并为一个更大规模的问题的解,自底向上逐步求出原问题的解. 动态规划将待求解的问题分解成若干的子问题，自底向上地通过求解子问题的解得到原问题的解。动态规划将每个子问题只求解一次并将其解保存在一个表格中,当需要再次求解此子问题时,只是简单的通过查表过的该子问题的解,避免了大量的重复计算. 异同：分治法求解的问题分解后的子问题都是独立的，而使用动态规划求解的问题分解后得到的子问题往往不是相互独立的。 分治法是自顶向下用递归的方法解决问题，而动态规划则是自底向上非递归解决问题。 1.简述分治算法求解过程的三个阶段。 答:（1）划分：既然是分治，当然需要把规模为n的原问题划分为k个规模较小的子问题，并尽量使这k个子问题的规模大致相同。 （2）求解子问题：各子问题的解法与原问题的解法通常是相同的，可以用递归的方法求解各个子问题，有时递归处理也可以用循环来实现。 （3）合并：把各个子问题的解合并起来，合并的代价因情况不同有很大差异，分治算法的有效性很大程度上依赖于合并的实现。 2.叙述分治法的基本思想，并分析分治法与减治法二者的区别。 答：分治法将待求解的问题划分成K个较小规模的子问题,对这K个子问题分别求解,再将子问题的解合并为一个更大规模的问题的解,自底向上逐步求出原问题的解. 区别：分治法是把一个大问题划分成若干个子问题，分别求解各个子问题，然后把子问题的解进行合并并得到原问题的解。减治法同样是把一个大问题划分成若干个子问题，但是这些子问题不需要分别求解，只需求解其中的一个子问题，因而也无需对子问题的解进行合并。 3.设计分治算法求一个数组中最大元素的位置，建立该算法时间复杂性的 递推式并给出其复杂性的大O表示。 答：设数组a1,a2...an int maxpos(a[],i,j); {if(i==j) return i; mid=(i+j)/2; lmaxpos=maxpos(a,i,mid); rmaxpos=maxpos(a,mid+1,j); if(a[lmaxpos]>=a[rmoxpos]) return lmaxpos; else return rmaxpos;} T(1)=O(n) n=1; T(n)=2T(n/2)+O(1) n>1; 二次函数的最大值和最小值问题 ————————————————————————————————作者: ————————————————————————————————日期: 二次函数的最大值和最小值问题 高一数学组主讲人-－---－－－－蒋建平 本节课的教学目标: 重点：掌握闭区间上的二次函数的最值问题 难点:理解并会处理含参数的二次函数的最值问题 核心: 区间与对称轴的相对位置 思想: 数形结合、分类讨论 一、复习引入 1、二次函数相关的知识点回顾。 （１）二次函数的顶点式： (2）二次函数的对称轴： （3)二次函数的顶点坐标： 2、函数的最大值和最小值的概念 设函数)(x f 在0x 处的函数值是)(0x f ,如果不等式)()(0x f x f ≥对于定义域内任意x 都成立,那么)(0x f 叫做函数)(x f y =的最小值。记作)(0min x f y = 如果不等式)()(0x f x f ≤对于定义域内任意x 都成立，那么)(0x f 叫做函数)(x f y =的最小值。记作)(0max x f y = 二、新课讲解:二次函数最大值最小值问题探究 类型一:无限制条件的最大值与最小值问题 例1、(１)求二次函数322 ++-=x x y 的最大值 ． (2)求二次函数x x y 422-=的最小值 . 本题小结：求无条件限制时二次函数最值的步骤 1、配方，求二次函数的顶点坐标。 2、根据二次函数的开口方向确定是函数的最大值还是最小值。 3、求出最值。 类型二:轴定区间定的最大值与最小值问题 例2、(1)求函数])1,3[(,232-∈-+=x x x y 的最大值 ，最小值 . (2）求函数])3,1[(232∈-+=x x x y 的最大值 ，最小值 . (３)求函数])2,5[(232 --∈-+=x x x y 的最大值 与最小值 . 本题小结:求轴定区间定时二次函数最值的步骤 1、配方,求二次函数的顶点坐标或求对称轴,画简图。 2、判断顶点的横坐标(对称轴）是否在闭区间内。 ３、计算闭区间端点的值,并比较大小。 类型三:轴动区间定的最大值与最小值问题 例3、求函数)(32R a ax x y ∈++=在]1,1[-上的最大值。 函数的最大值和最小值时 Revised by BLUE on the afternoon of December 12,2020. 2006年江西省高中青年教师优质课比赛参赛教案§函数的最大值和最小值(第1课时)江西省临川第一中学游建龙（344100） 二ＯＯ六年九月十三日 §函数的最大值和最小值 【教材分析】 1．本节教材的地位与作用 本节是在学生已经会求某些函数的最值，并且已经掌握了性质：“如果f(x)是闭区间[a，b]上的连续函数，那么f(x)在闭区间[a，b]上有最大值和最小值”，以及会求可导函数的极值之后进行学习的，学好这一节，学生将会求更多的函数的最值，运用本节知识可以解决科技、经济、社会中的一些如何使用料最省、效益最大等实际问题．这节课集中体现了数形结合、理论联系实际等重要的数学思想方法，对于完善学生的知识结构，培养学生用数学的意识都具有极为重要的意义． 2．教学重点 会求闭区间上连续开区间上可导的函数的最值． 3．教学难点 确定函数最值的方法，并会求函数的最值． 【教学目标】 根据本节教材在高中数学知识体系中的地位和作用，结合学生已有的认知水平，制定本节如下的教学目标： 1．知识和技能目标 （1）理解函数的最值与极值的区别和联系． （2）进一步明确闭区间[a，b]上的连续函数f(x)，在[a，b]上必有最大、最小值． （3）掌握用导数法求上述函数的最大值与最小值的方法和步骤． 2．过程和方法目标 （1）了解开区间内的连续函数不一定有最大、最小值． （2）会求闭区间上连续，开区间内可导的函数的最大、最小值． 3．情感和价值目标 （1）认识事物之间的的区别和联系． （2）培养学生观察事物的能力，能够自己发现问题，分析问题并最终解决问题． 【教法选择】 根据皮亚杰的建构主义认识论，知识是个体在与环境相互作用的过程中逐渐建构的结果，而认识则是起源于主客体之间的相互作用． 本节课引导学生自己通过观察函数的图象，归纳、总结出最大值、最小值求解的方法与步骤，让学生自己主动地获得知识，老师只是进行适当的引导，而不是进行全部的灌输．【学法指导】 对于求函数的最值，高三学生已经具备了良好的知识基础，剩下问题是有没有一种更一般的方法，能运用于更多更复杂的函数求最值问题教学设计中注意激发起学生强烈的求知欲望，使得他们能积极主动地观察、分析、归纳，以形成认识，参与到课堂活动中，充分发挥他们作为认知主体的作用． 1. )(n T 给定数组a[0:n-1],试设计一个算法,在最坏情况下用n+[logn]-2次比较找出 a[0:n-1] 中的元素的最大值和次大值. (算法分析与设计习题 2.16 ) （分治法） a 、 算法思想 用分治法求最大值和次大值首先将问题划分，即将划分成长度相等的两个序列，递归求出左边的最大值次大值，再求出右边的的最大值次大值，比较左右两边，最后得出问题的解。 b 、复杂度分析： 把问题划分为左右两种的情况，需要分别递归求解，时间复杂度可如下计算： 有递推公式为： T(n)=1 n=1 T(n)= 2T(n/2)+1 n>1 所以，分治算法的时间复杂度是n+[logn]-2，当n 为奇数时，logn 取上线，当n 为偶数时，logn 取下线。//不知道为什么会-2！ C 、代码实现： #include if(lcmax>rmax) { max=lmax; cmax=lcmax; } else { max=lmax; cmax=rmax; } else if(rcmax>lmax) { if(rmax==rcmax) { max=rmax; cmax=lmax; } else { max=rmax; cmax=rcmax; } } else { max=rmax; cmax=lmax; } } } int main() { int n; int max,cmax; printf("输入数组长度"); scanf("%d",&n); printf("输入数组:\n"); for(int i=0;i 二次函数的最大值和最小值问题 高一数学组主讲人---------蒋建平 本节课的教学目标： 重点：掌握闭区间上的二次函数的最值问题 难点：理解并会处理含参数的二次函数的最值问题 核心： 区间与对称轴的相对位置 思想： 数形结合、分类讨论 一、复习引入 1、二次函数相关的知识点回顾。 （1）二次函数的顶点式： （2）二次函数的对称轴： （3）二次函数的顶点坐标： 2、函数的最大值和最小值的概念 设函数)(x f 在0x 处的函数值是)(0x f ，如果不等式)()(0x f x f ≥对于定义域内任意x 都成立，那么)(0x f 叫做函数)(x f y =的最小值。记作)(0min x f y = 如果不等式)()(0x f x f ≤对于定义域内任意x 都成立，那么)(0x f 叫做函数)(x f y =的最小值。记作)(0max x f y = 二、新课讲解：二次函数最大值最小值问题探究 类型一：无限制条件的最大值与最小值问题 例1、(1)求二次函数322 ++-=x x y 的最大值 . (2)求二次函数x x y 422-=的最小值 . 本题小结：求无条件限制时二次函数最值的步骤 1、配方，求二次函数的顶点坐标。 2、根据二次函数的开口方向确定是函数的最大值还是最小值。 3、求出最值。 类型二：轴定区间定的最大值与最小值问题 例2、(1)求函数])1,3[(,232-∈-+=x x x y 的最大值 ,最小值 . (2)求函数])3,1[(232∈-+=x x x y 的最大值 ,最小值 . (3)求函数])2,5[(232--∈-+=x x x y 的最大值 与最小值 . 本题小结：求轴定区间定时二次函数最值的步骤 1、配方，求二次函数的顶点坐标或求对称轴，画简图。 2、判断顶点的横坐标（对称轴）是否在闭区间内。 3、计算闭区间端点的值，并比较大小。 类型三：轴动区间定的最大值与最小值问题 例3、求函数)(32 R a ax x y ∈++=在]1,1[-上的最大值。算法练习题-分章节-带答案
最大值与最小值教案
算法分析与设计 实验三 最大子段和问题
例说求函数的最大值和最小值的方法
方法技巧练——最大值与最小值问题
小学奥数最大值最小值问题归纳
函数的最大值和最小值教案.doc
最大子段和动态规划法
最大值和最小值问题
分治法求最大子段和问题
线段差的最大值与线段和的最小值问题
导数在函数求最大值和最小值中的应用解读
小学奥数最大值最小值问题汇总
算法(复习题)1
二次函数的最大值和最小值问题
函数的最大值和最小值时
算法分析考试题
二次函数的最大值和最小值问题
相关主题
文本预览