二分法[上学期]
图片预览
文档简介
课件27张PPT。二分法什么是二分法？所谓二分法，又名分而治之方法，其根本思想是一个规模比较大的、难以直接解决的问题，分割成一些规模较小的子问题，这些子问题互相独立且与原问题相同或者相似；然后将这些子问题各个击破，分而治之。
请同学们仔细品味上面一段话，等到我们这个课程完成之后在回过头来看……二分法的运用：
和数列有关的问题有关于数列的问题新大纲教导我们：要把和计算机有关的算法融入到数学课程的各个相关部分，有利于学生认识数学的本质 。
我们传统的关于数列的观点（高中数学课本上的）就是一些数以某种规律排列着，大多数情况下给出了通项或者递推公式。而在实际情况中，更多时候数列只是一串毫无规律的数，如何发现他们之间的规律就需要我们自己去发展或利用已有的算法。数列问题之一.对一个有限数列排序给定a1,a2,a3….an，找一个算法把它们从小到大排列。
最简单的方法大家可以想到：先找最小的，再找第二小的……这样每次寻找的过程中要做的比较次数最坏情况下是n(n-1)/2，当n特别大（比如说>10000时）,在目前大多数PC机上速度慢得可怜。
有没有更好的方法？有！二分法二分排序还是刚才那个问题，现在我们给出一种解决方案：快速排序（又称二分排序）
快速排序的基本思想是基于分治策略的。 二分排序分三步走：
1、分解(Divide)：将输入的序列ap..ar划分成两个非空子序列ap..aq和aq+1..ar，使ap..aq中任一元素的值不大于aq+1..ar中任一元素的值。?
2、递归求解(Conquer)：通过递归调用快速排序算法分别对ap..aq和aq+1..ar进行排序。
3、合并(Merge)：由于对分解出的两个子序列的排序是就地进行的，所以在ap..aq和aq+1..ar都排好序后不需要执行任何计算ap..ar就已排好序。
这个解决流程是符合分治法的基本步骤的。因此，快速排
法是分治法的经典应用实例之一。 ? 二分排序程序的实现我们可以参考附录。附录1数列问题之二：对特殊数列的检索问题描述：假设一个有序的数列（从小到大排序），现在要求设计一种算法，使得给出数列中的一个元素的值，确定它在数列中的位置。
这个问题目前最好的算法是O（logn）的，又称二分检索，二分检索二分法检索又称折半检索，是一种效率较高的检索方法，使用这种方法检索时，要求字典元素在顺序表中按关键码排序。
二分法检索的基本思想是∶设字典中元素从小到大有序地存放在数组中，首先将给定值key与字典中间位置上元素的关键码比较，如果相等，则检索成功；否则，若key小，则在字典前半部分中继续进行二分法检索，否则在字典后半部分中继续进行二分法检索。这样，经过一次比较就缩小一半的查找区间，如此进行下去，直到检索成功或检索失败 。二分检索
关于二分排序和二分检索的进一步内容可以参阅：
《算法艺术与信息学竞赛》，刘汝佳、黄亮，清华大学出版社。
《算法导论（第二版）》，Thomas.H.Cormen等，高等教育出版社。附录2二分法的运用：
方程求解问题方程求解假设给定一个连续函数f（我们现在只须知道，多项式函数都是连续函数），对于任意的x都可以知道f(x)的值，并且知道f在[a,b]间有且仅有一个零点，问确定这个零点的方法？
如果二次方程，我们有求解方法……三次四次也可以找到根式解……可是五次及以上的方程并非全部解的表示都能找到了（Galois的结果）……那怎么办呢？……方程求解Galois证明的只是没办法找到解的根式表示，其实我们如果不要求精确值，只是求近似值，方法是有很多的，这里介绍的是二分法。
介值定理：连续函数f在[a,b]上，若有f(a)f(b)<0，那么必然存在ｃ属于[a,b]，f(c)=0。
这是我们计算方法的根基。
方程求解基本思想：比较f(a)和f(b)的大小，如果f(a)和f(b)的符号相反，那么在(x , y)之间一定存在一个数使f=0即方程的一个解。取a,b的中点r，如果f(r)与f(x)异号，解肯定在(a,r)之间，否则解在(r,b)之间，问题转化为一个长度为原区间1/2的子问题（还记得我们已开始说的分而治之么？）重复直到|f(r)|其实方程求解问题是计算数学中数值计算方面的重要部分，二分法的好处是实现起来简便，但是收敛到零点的速度不够快。目前通用的算法是先用二分法求解近似值，再用Newton-Raphson法迭代快速收敛。这些内容都在教材以外。有兴趣的同学可以阅读相关书籍。方程求解这里推荐和方程求解有关的书籍：
林成森 ，《数值计算方法（上册）》第二章：解非线性方程的数值方法 ，科学出版社 ，2000附录3 我们到现在为止对于二分法的应用已经有了一个初步的认识，分而治之的思想不但在数学和计算机科学上有显著的地位，在经济学、管理科学和运筹学上，这种思想也起了很重要的作用。总结课后题1、设计算法，求一个有限数列中第k大的元素（k给定）。
2、求出下列方程的所有实数解（精确到0.01)
x^3+x^2-1=0
e^x-x-2=0
x^4+x^2+1=0课后题3、用计算机解决以下问题（该题目颇有难度，可以供学有余力的同学课余思考）
（见附录文件）附录4附录1、快速排序PASCAL实现：
Procedure Quick_Sort(p,r:TPosition;var L:TList); {快速排序} var q:TPosition; begin if L[p..r]足够小 then Sort(p,r,L) {若L[p..r]足够小则直接对L[p..r]排序} else begin q:=Partition(p,r,L); {将L[p..r]分解为L[p..q]和L[q+1..r]两部分} Quick_Sort(p,q,L); {递归排序L[p..q]} Quick_Sort(q+1,r,L); {递归排序L[q+1..r]} end; end; BACK附录2、二分查找C语言实现：
int BinSearch(SeqList R，KeyType K) ????? { //在有序表R[1..n]中进行二分查找，成功时返回结点的位置，失败时返回零 ??????? int low=1，high=n，mid； //置当前查找区间上、下界的初值 ??????? while(low<=high){ //当前查找区间R[low..high]非空 ????????? mid=(low+high)/2； ????????? if(R[mid].key==K) return mid； //查找成功返回 ????????? if(R[mid].kdy>K) ???????????? high=mid-1; //继续在R[low..mid-1]中查找 ????????? else ???????????? low=mid+1； //继续在R[mid+1..high]中查找 ???????? } ??????? return 0； //当low>high时表示查找区间为空，查找失败 ?????? } //BinSeareh BACK附录3、方程求解实现Pascal实现：
fun_ction f(x:real):real;
{
f:=x*x*x-x*x-2; {具体函数式在这里给出}
}
fucntion search(a,b:real):real; {主程序中调用search(a,b)则寻找出[a,b]区间的唯一解}
Begin
if abs(a-b) if f(a)*f(b)<0 then begin
mid=(a+b)/2
if f(mid)=0 then search:=mid
else if ((f(mid)*f(a)<0)) then search:=search(a,mid) {判断求解区间在[a,mid]中}
else search:=search(mid,b);{判断求解区间在[mid,b]中}
end;
end.
Begin
writeln(search(a,b));
end.
BACK附录4、练习题3题目：Advanced Causal Measurements (ACM/ICPC Waterloo Local 2004）
特别注意：本题只供课外参考，老师不对解答负责。
Description
Causality is a very important concept in theoretical physics. The basic elements in a discussion of causality are events. An event e is described by its time of occurrence t, and its location, x, and we write e = (t,x). For our concerns, all events happen in the one dimensional geometric space and thus locations are given by a single real number x as a coordinate on x-axis. Usually, theoretical physicists like to define the speed of light to be 1, so that time and space have the same units (actual physical units frighten and confuse theorists). One event e1 = (t1,x1) is a possible cause for a second event e2 = (t2,x2) if a signal emitted at e1 could arrive at e2. Signals can't travel faster than the speed of light, so this condition can be stated as: 附录4、练习3（续）e1 is a possible cause for e2 iff t2 >= t1+|x2-x1|
Thus an event at (-1,1) could cause events at (0,0), (1,2), and (1,3), for example, but could not have caused events at (1,4) or (-2,1). Note that one event can cause several others. Recently, scientists have observed several unusual events in the geometrically one dimensional universe, and using current theories, they know how many causes were responsible for these observations, but they know nothing about the time and space coordinates of the causes. You asked to write a program to determine the latest time at which the earliest cause could have occurred (i.e. the time such that at least one cause must have occurred on or before this time). Somewhat surprisingly, all the observed events have both space and time coordinates expressed by integer numbers in the range -1000000 <= t, x <= 1000000. The figure on the right illustrates the first case from input: the earliest single event as a possible cause of all four events.
附录4、练习题3（续）Input
The first line of input is the number of cases which follow. Each case begins with a line containing the number n of events and the number m of causes, 1 <= n, m <= 100000. Next follows n lines containing the t and x coordinates for each event.
Output
Output consists of a single line for each case in the format as in the sample output, giving the latest time at which the earliest cause could have occurred, this will be an integer as our time units are not divisible.
Sample Input
4 4 1 1 -1 1 3 1 4 2 6 4 2 1 -1 1 3 1 4 2 6 4 3 1 -1 1 3 1 4 2 6 4 4 1 -1 1 3 1 4 2 6
Sample Output
Case 1: -2 Case 2: 0 Case 3: 0 Case 4: 1 BACK谢谢！
请同学们仔细品味上面一段话，等到我们这个课程完成之后在回过头来看……二分法的运用：
和数列有关的问题有关于数列的问题新大纲教导我们：要把和计算机有关的算法融入到数学课程的各个相关部分，有利于学生认识数学的本质 。
我们传统的关于数列的观点（高中数学课本上的）就是一些数以某种规律排列着，大多数情况下给出了通项或者递推公式。而在实际情况中，更多时候数列只是一串毫无规律的数，如何发现他们之间的规律就需要我们自己去发展或利用已有的算法。数列问题之一.对一个有限数列排序给定a1,a2,a3….an，找一个算法把它们从小到大排列。
最简单的方法大家可以想到：先找最小的，再找第二小的……这样每次寻找的过程中要做的比较次数最坏情况下是n(n-1)/2，当n特别大（比如说>10000时）,在目前大多数PC机上速度慢得可怜。
有没有更好的方法？有！二分法二分排序还是刚才那个问题，现在我们给出一种解决方案：快速排序（又称二分排序）
快速排序的基本思想是基于分治策略的。 二分排序分三步走：
1、分解(Divide)：将输入的序列ap..ar划分成两个非空子序列ap..aq和aq+1..ar，使ap..aq中任一元素的值不大于aq+1..ar中任一元素的值。?
2、递归求解(Conquer)：通过递归调用快速排序算法分别对ap..aq和aq+1..ar进行排序。
3、合并(Merge)：由于对分解出的两个子序列的排序是就地进行的，所以在ap..aq和aq+1..ar都排好序后不需要执行任何计算ap..ar就已排好序。
这个解决流程是符合分治法的基本步骤的。因此，快速排
法是分治法的经典应用实例之一。 ? 二分排序程序的实现我们可以参考附录。附录1数列问题之二：对特殊数列的检索问题描述：假设一个有序的数列（从小到大排序），现在要求设计一种算法，使得给出数列中的一个元素的值，确定它在数列中的位置。
这个问题目前最好的算法是O（logn）的，又称二分检索，二分检索二分法检索又称折半检索，是一种效率较高的检索方法，使用这种方法检索时，要求字典元素在顺序表中按关键码排序。
二分法检索的基本思想是∶设字典中元素从小到大有序地存放在数组中，首先将给定值key与字典中间位置上元素的关键码比较，如果相等，则检索成功；否则，若key小，则在字典前半部分中继续进行二分法检索，否则在字典后半部分中继续进行二分法检索。这样，经过一次比较就缩小一半的查找区间，如此进行下去，直到检索成功或检索失败 。二分检索
关于二分排序和二分检索的进一步内容可以参阅：
《算法艺术与信息学竞赛》，刘汝佳、黄亮，清华大学出版社。
《算法导论（第二版）》，Thomas.H.Cormen等，高等教育出版社。附录2二分法的运用：
方程求解问题方程求解假设给定一个连续函数f（我们现在只须知道，多项式函数都是连续函数），对于任意的x都可以知道f(x)的值，并且知道f在[a,b]间有且仅有一个零点，问确定这个零点的方法？
如果二次方程，我们有求解方法……三次四次也可以找到根式解……可是五次及以上的方程并非全部解的表示都能找到了（Galois的结果）……那怎么办呢？……方程求解Galois证明的只是没办法找到解的根式表示，其实我们如果不要求精确值，只是求近似值，方法是有很多的，这里介绍的是二分法。
介值定理：连续函数f在[a,b]上，若有f(a)f(b)<0，那么必然存在ｃ属于[a,b]，f(c)=0。
这是我们计算方法的根基。
方程求解基本思想：比较f(a)和f(b)的大小，如果f(a)和f(b)的符号相反，那么在(x , y)之间一定存在一个数使f=0即方程的一个解。取a,b的中点r，如果f(r)与f(x)异号，解肯定在(a,r)之间，否则解在(r,b)之间，问题转化为一个长度为原区间1/2的子问题（还记得我们已开始说的分而治之么？）重复直到|f(r)|
林成森 ，《数值计算方法（上册）》第二章：解非线性方程的数值方法 ，科学出版社 ，2000附录3 我们到现在为止对于二分法的应用已经有了一个初步的认识，分而治之的思想不但在数学和计算机科学上有显著的地位，在经济学、管理科学和运筹学上，这种思想也起了很重要的作用。总结课后题1、设计算法，求一个有限数列中第k大的元素（k给定）。
2、求出下列方程的所有实数解（精确到0.01)
x^3+x^2-1=0
e^x-x-2=0
x^4+x^2+1=0课后题3、用计算机解决以下问题（该题目颇有难度，可以供学有余力的同学课余思考）
（见附录文件）附录4附录1、快速排序PASCAL实现：
Procedure Quick_Sort(p,r:TPosition;var L:TList); {快速排序} var q:TPosition; begin if L[p..r]足够小 then Sort(p,r,L) {若L[p..r]足够小则直接对L[p..r]排序} else begin q:=Partition(p,r,L); {将L[p..r]分解为L[p..q]和L[q+1..r]两部分} Quick_Sort(p,q,L); {递归排序L[p..q]} Quick_Sort(q+1,r,L); {递归排序L[q+1..r]} end; end; BACK附录2、二分查找C语言实现：
int BinSearch(SeqList R，KeyType K) ????? { //在有序表R[1..n]中进行二分查找，成功时返回结点的位置，失败时返回零 ??????? int low=1，high=n，mid； //置当前查找区间上、下界的初值 ??????? while(low<=high){ //当前查找区间R[low..high]非空 ????????? mid=(low+high)/2； ????????? if(R[mid].key==K) return mid； //查找成功返回 ????????? if(R[mid].kdy>K) ???????????? high=mid-1; //继续在R[low..mid-1]中查找 ????????? else ???????????? low=mid+1； //继续在R[mid+1..high]中查找 ???????? } ??????? return 0； //当low>high时表示查找区间为空，查找失败 ?????? } //BinSeareh BACK附录3、方程求解实现Pascal实现：
fun_ction f(x:real):real;
{
f:=x*x*x-x*x-2; {具体函数式在这里给出}
}
fucntion search(a,b:real):real; {主程序中调用search(a,b)则寻找出[a,b]区间的唯一解}
Begin
if abs(a-b)
mid=(a+b)/2
if f(mid)=0 then search:=mid
else if ((f(mid)*f(a)<0)) then search:=search(a,mid) {判断求解区间在[a,mid]中}
else search:=search(mid,b);{判断求解区间在[mid,b]中}
end;
end.
Begin
writeln(search(a,b));
end.
BACK附录4、练习题3题目：Advanced Causal Measurements (ACM/ICPC Waterloo Local 2004）
特别注意：本题只供课外参考，老师不对解答负责。
Description
Causality is a very important concept in theoretical physics. The basic elements in a discussion of causality are events. An event e is described by its time of occurrence t, and its location, x, and we write e = (t,x). For our concerns, all events happen in the one dimensional geometric space and thus locations are given by a single real number x as a coordinate on x-axis. Usually, theoretical physicists like to define the speed of light to be 1, so that time and space have the same units (actual physical units frighten and confuse theorists). One event e1 = (t1,x1) is a possible cause for a second event e2 = (t2,x2) if a signal emitted at e1 could arrive at e2. Signals can't travel faster than the speed of light, so this condition can be stated as: 附录4、练习3（续）e1 is a possible cause for e2 iff t2 >= t1+|x2-x1|
Thus an event at (-1,1) could cause events at (0,0), (1,2), and (1,3), for example, but could not have caused events at (1,4) or (-2,1). Note that one event can cause several others. Recently, scientists have observed several unusual events in the geometrically one dimensional universe, and using current theories, they know how many causes were responsible for these observations, but they know nothing about the time and space coordinates of the causes. You asked to write a program to determine the latest time at which the earliest cause could have occurred (i.e. the time such that at least one cause must have occurred on or before this time). Somewhat surprisingly, all the observed events have both space and time coordinates expressed by integer numbers in the range -1000000 <= t, x <= 1000000. The figure on the right illustrates the first case from input: the earliest single event as a possible cause of all four events.
附录4、练习题3（续）Input
The first line of input is the number of cases which follow. Each case begins with a line containing the number n of events and the number m of causes, 1 <= n, m <= 100000. Next follows n lines containing the t and x coordinates for each event.
Output
Output consists of a single line for each case in the format as in the sample output, giving the latest time at which the earliest cause could have occurred, this will be an integer as our time units are not divisible.
Sample Input
4 4 1 1 -1 1 3 1 4 2 6 4 2 1 -1 1 3 1 4 2 6 4 3 1 -1 1 3 1 4 2 6 4 4 1 -1 1 3 1 4 2 6
Sample Output
Case 1: -2 Case 2: 0 Case 3: 0 Case 4: 1 BACK谢谢！