《分治算法和二分搜索算法课件》由会员分享，可在线阅读，更多相关《分治算法和二分搜索算法课件（12页珍藏版）》请在金锄头文库上搜索。
1、1Fibonacci数列数列: 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 ; i1 F(n)=递归的终止条件递归的终止条件递归公式递归公式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 递归法求Fibonacc
2、i数列分治算法和二分搜索算法3用递归法求用递归法求Fibonacci数列数列Fib(4)return + Fib(3)Fib(2)return + Fib(2)Fib(1)return + Fib(1)Fib(0)return + Fib(1)Fib(0)return 1return 1return 1return 1return 1n=4时，递归法进行了多时，递归法进行了多少次函数调用？少次函数调用？112111325n=20时时, 要进行要进行21891次递归调用次递归调用讨论讨论: 求求Fibonacci数列的数列的迭代法和递归法谁好？迭代法和递归法谁好？2-1 递归法求Fibonacc
3、i数列分治算法和二分搜索算法4第2讲 分治法和二分搜索算法 本讲内容：本讲内容： (1) 分分治法的基本思想治法的基本思想 (2) 二分搜索技术二分搜索技术 分治算法和二分搜索算法5分治法的基本思想分治法的思想分治法的思想: : 分而治之。将一个规模为分而治之。将一个规模为n n的问题分解为的问题分解为k k个个规模较小的子问题，这些子问题互相独立且与原问题相同，规模较小的子问题，这些子问题互相独立且与原问题相同，( (如果子问题的规模仍然不够小，则再划分为如果子问题的规模仍然不够小，则再划分为k k个子问题个子问题), ), 然然后递归的求解这些子问题，最后用适当的方法将各子问题的解后递归的
4、求解这些子问题，最后用适当的方法将各子问题的解合并成原问题的解。合并成原问题的解。原问题原问题(规模为规模为n)子问题子问题1子问题子问题2子问题子问题k子问题子问题1子问题子问题2子问题子问题k相同相同类型类型合合并并解解子问题子问题1子问题子问题2子问题子问题k子问题子问题1子问题子问题2子问题子问题k分治算法和二分搜索算法6分治法的适用条件分治法的适用条件分治法所能解决的问题一般具有以下几个特征：分治法所能解决的问题一般具有以下几个特征：n该问题的规模缩小到一定的程度就可以容易地解决该问题的规模缩小到一定的程度就可以容易地解决n该问题可以分解为若干个规模较小的相同问题该问题可以分解为若干
5、个规模较小的相同问题n该问题所分解出的各个子问题是相互独立的该问题所分解出的各个子问题是相互独立的n利用分解出的子问题的解可以合并为该问题的解利用分解出的子问题的解可以合并为该问题的解分治法的基本思想分治算法和二分搜索算法7前提条件：有一组数已经按从小到大前提条件：有一组数已经按从小到大(或从大到小或从大到小)排序排序目标：输入一个数目标：输入一个数x，在这组数查找是否有在这组数查找是否有x二分搜索的步骤：二分搜索的步骤：1、确定三个关键下标的初值：、确定三个关键下标的初值：bott=0, top=8, mid=(bott+top)/2;2、判断要找的数、判断要找的数x是否等于是否等于amid
6、 x=amid 找到，结束找到，结束xamid 在在amid+1atop之间继续查找之间继续查找x bott=mid+1; mid=(bott+top)/2;-15-6079235482101midbotttopa0 a1 a2 a3 a4 a5 a6 a7 a82-2 二分搜索算法分治算法和二分搜索算法8二分搜索实例二分搜索实例:设在数组设在数组a中顺序放了以下中顺序放了以下9个元素：个元素：检索检索x=9, 9=a4, 一次比较就成功一次比较就成功, 最好情况最好情况-15-6079235482101a0 a1 a2 a3 a4 a5 a6 a7 a8检索检索x=-15, -15a4, -
7、15a4, 101a6, 101a7, 101=a8, 4次比较次比较, 成功成功检索检索x=8, 8a1, 8a2, 8a3, 4次比较次比较, 不成功不成功2-2 二分搜索算法分治算法和二分搜索算法9#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, &ai); printf(“输入要查找的数输入要查找的数 x:); scanf(%d, &x);
8、result=find(a, x, 0, N-1); if (result= -1) printf(%d is not found.n, x); else printf(Find %d=a%dn, x, result);迭代法的程序代码迭代法的程序代码/ 符号常量定义，便于修改数组的大小符号常量定义，便于修改数组的大小/ 函数调用函数调用/ 函数声明函数声明2-2 二分搜索算法分治算法和二分搜索算法10int find(int a , int x, int bott, int top) int mid; while(bott=top) mid=(bott+top)/2; if(x=amid)
9、return(mid); else if(xamid，2. 搜索不成功，搜索不成功，-1midbott = mid + 1，返回，返回 find(a,x,bott,top)返回返回find(a,x,mid+1,top)2. 如果如果x top，返回，返回分治算法和二分搜索算法12int 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;分治算法和二分搜索算法
