第2讲分治算法和二分搜索算法ppt课件

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 递归法求Fibonacci数列4第2讲 分治法

3、和二分搜索算法 本讲内容：本讲内容： (1) (1) 分治法的根本思想分治法的根本思想 (2) (2) 二分搜索技术二分搜索技术 5分治法的根本思想分治法的思想分治法的思想: : 分而治之。将一个规模为分而治之。将一个规模为n n的问题分解为的问题分解为k k个个规模较小的子问题，这些子问题相互独立且与原问题一样，规模较小的子问题，这些子问题相互独立且与原问题一样，( (假设子问题的规模依然不够小，那么再划分为假设子问题的规模依然不够小，那么再划分为k k个子问题个子问题), ), 然后递归的求解这些子问题，最后用适当的方法将各子问题的然后递归的求解这些子问题，最后用适当的方法将各子问题的解合

4、并成原问题的解。解合并成原问题的解。原问题原问题(规模为规模为n)子问题子问题1子问题子问题2子问题子问题k子问题子问题1子问题子问题2子问题子问题k一样一样类型类型合并解合并解子问题子问题1子问题子问题2子问题子问题k子问题子问题1子问题子问题2子问题子问题k6分治法的适用条件分治法的适用条件分治法所能处理的问题普通具有以下几个特征：分治法所能处理的问题普通具有以下几个特征：该问题的规模减少到一定的程度就可以容易地处该问题的规模减少到一定的程度就可以容易地处理理该问题可以分解为假设干个规模较小的一样问题该问题可以分解为假设干个规模较小的一样问题该问题所分解出的各个子问题是相互独立的该问题所分

5、解出的各个子问题是相互独立的利用分解出的子问题的解可以合并为该问题的解利用分解出的子问题的解可以合并为该问题的解分治法的根本思想7前提条件：有一组数曾经按从小到大前提条件：有一组数曾经按从小到大(或从大到小或从大到小)排序排序目的：输入一个数目的：输入一个数x，在这组数查找能否有，在这组数查找能否有x二分搜索的步骤：二分搜索的步骤：1、确定三个关键下标的初值：、确定三个关键下标的初值：bott=0, top=8, mid=(bott+top)/2;2、判别要找的数、判别要找的数x能否等于能否等于amid x=amid 找到，终了找到，终了xamid 在在amid+1atop之间继续查找之间继续

6、查找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, -15a4, 101a6, 101a7, 101=a8, 4次比较次比较, 胜利胜利检索检索x=8, 8a1, 8a

7、2, 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); result=find(a, x, 0, N-1); if (result= -1) printf(%d is not found.n,

8、 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) 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小那