分治算法和二分搜索算法.ppt

《分治算法和二分搜索算法.ppt》由会员分享，可在线阅读，更多相关《分治算法和二分搜索算法.ppt（12页珍藏版）》请在三一办公上搜索。

1、Fibonacci数列:1,1,2,3,5,8,13,迭代法求Fibonacci数列的前20项,#include void main()int i,f1=1,f2=1,f3;printf(%8d%8d,f1,f2);for(i=3;i=20;i+)f3=f1+f2;f1=f2;f2=f3;printf(%8d,f3);if(i%4=0)putchar(n);,迭代法在已知数列前2项的基础上,从第3项开始,依次向后计算,得出数列的每一项,思考:怎样用递归的方法求解？,2-1 递归法求Fibonacci数列,定义Fibonacci数列的递归数学模型：,递归法求Fibonacci数列,递归的终止条件

2、,递归公式,int Fib(int n)if(n0)printf(error!);exit(0);else if(n=1)return 1;else return Fib(n-1)+Fib(n-2);,2-1 递归法求Fibonacci数列,用递归法求Fibonacci数列,Fib(4),n=4时，递归法进行了多少次函数调用？,n=20时,要进行21891次递归调用,讨论:求Fibonacci数列的迭代法和递归法谁好？,2-1 递归法求Fibonacci数列,第2讲 分治法和二分搜索算法,本讲内容：(1)分治法的基本思想(2)二分搜索技术,分治法的基本思想,分治法的思想:分而治之。将一个规模为

3、n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同，(如果子问题的规模仍然不够小，则再划分为k个子问题),然后递归的求解这些子问题，最后用适当的方法将各子问题的解合并成原问题的解。,原问题(规模为n),分治法的适用条件,分治法所能解决的问题一般具有以下几个特征：该问题的规模缩小到一定的程度就可以容易地解决该问题可以分解为若干个规模较小的相同问题该问题所分解出的各个子问题是相互独立的利用分解出的子问题的解可以合并为该问题的解,分治法的基本思想,前提条件：有一组数已经按从小到大(或从大到小)排序目标：输入一个数x，在这组数查找是否有x,二分搜索的步骤：1、确定三个关键下标的初值：

4、bott=0,top=8,mid=(bott+top)/2;,2、判断要找的数x是否等于amid,x=amid 找到，结束xamid 在amid+1atop之间继续查找x bott=mid+1;mid=(bott+top)/2;,a0 a1 a2 a3 a4 a5 a6 a7 a8,2-2 二分搜索算法,二分搜索实例:设在数组a中顺序放了以下9个元素：,检索x=9,9=a4,一次比较就成功,最好情况,a0 a1 a2 a3 a4 a5 a6 a7 a8,检索x=-15,-15a4,-15a1,-15=a0,3次比较,成功,检索x=101,101a4,101a6,101a7,101=a8,4次比

5、较,成功,检索x=8,8a1,8a2,8a3,4次比较,不成功,2-2 二分搜索算法,#include#define N 10int find(int a,int x,int bott,int top)；void main()int i,x,aN,result;printf(n 输入数组 a:n);for(i=0;iN;i+)scanf(%d,迭代法的程序代码,/符号常量定义，便于修改数组的大小,/函数调用,/函数声明,2-2 二分搜索算法,int find(int a,int x,int bott,int top)int mid;while(bott=top)mid=(bott+top)/2

6、;if(x=amid)return(mid);else if(xamid)top=mid-1;else bott=mid+1;return(-1);,/计算中间位置的下标,/若x等于amid，表示找到,/x不等于amid的情况,/x小则查找数组中较小的一半,/x大则查找数组中较大的一半,/找到x，返回mid的值,/没找到时返回-1,迭代法的程序代码,/满足条件时进行二分搜索,2-2 二分搜索算法,2-2 用递归函数实现二分搜索算法,分析：若使用递归算法，需要获得递归的终止条件和递推关系,递归函数的终止条件：,1.搜索成功，,递归函数的递推关系：,1.如果xamid，,2.搜索不成功，,-1,m

7、id,bott=mid+1，返回,find(a,x,bott,top),返回find(a,x,mid+1,top),2.如果xamid，,返回find(a,x,bott,mid-1),即x=amid，返回,即 bott top，返回,int find(int a,int x,int bott,int top)int mid;if(bott=top)mid=(bott+top)/2;if(x=amid)else if(xamid)else,递归法的程序代码,x大则查找数组中较大的一半,x小则查找数组中较小的一半,/没找到时返回-1,/找到x，返回mid的值,return mid;,return find(a,x,bott,mid-1);,return find(a,x,mid+1,top);,return-1;,