分治算法和二分搜索算法

《分治算法和二分搜索算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、Fibonacci数列:1,1,2,3,5,8,13…迭代法求Fibonacci数列的前20项#includevoidmain(){inti,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('');}}迭代法在已知数列前2项的基础上,从第3项开始,依次向后计算,得出数列的每一项思考:怎样用递归的方法求解？2

2、-1递归法求Fibonacci数列定义Fibonacci数列的递归数学模型：递归法求Fibonacci数列1n=0,1F(n-1)+F(n-2)n>1F(n)=递归的终止条件递归公式intFib(intn){if(n<0){printf("error!");exit(0);}elseif(n<=1)return1;elsereturnFib(n-1)+Fib(n-2);}2-1递归法求Fibonacci数列用递归法求Fibonacci数列Fib(4)return+Fib(3)Fib(2)return

3、+Fib(2)Fib(1)return+Fib(1)Fib(0)return+Fib(1)Fib(0)return1return1return1return1return1n=4时，递归法进行了多少次函数调用？112111325n=20时,要进行21891次递归调用讨论:求Fibonacci数列的迭代法和递归法谁好？2-1递归法求Fibonacci数列第2讲分治法和二分搜索算法本讲内容：(1)分治法的基本思想(2)二分搜索技术分治法的基本思想分治法的思想:分而治之。将一个规模为n的问题分解为k个规模

4、较小的子问题，这些子问题互相独立且与原问题相同，(如果子问题的规模仍然不够小，则再划分为k个子问题),然后递归的求解这些子问题，最后用适当的方法将各子问题的解合并成原问题的解。原问题(规模为n)子问题1子问题2子问题k…子问题1子问题2子问题k…相同类型合并解子问题1子问题2子问题k…子问题1子问题2子问题k…分治法的适用条件分治法所能解决的问题一般具有以下几个特征：该问题的规模缩小到一定的程度就可以容易地解决该问题可以分解为若干个规模较小的相同问题该问题所分解出的各个子问题是相互独立的利用分解出的

5、子问题的解可以合并为该问题的解分治法的基本思想前提条件：有一组数已经按从小到大(或从大到小)排序目标：输入一个数x，在这组数查找是否有x二分搜索的步骤：1、确定三个关键下标的初值：bott=0,top=8,mid=(bott+top)/2;2、判断要找的数x是否等于a[mid]①x==a[mid]找到，结束xa[mid]在a[mid+1]—a[top]之间继续查找xbott=mi

6、d+1;mid=(bott+top)/2;-15-6079235482101midbotttopa[0]a[1]a[2]a[3]a[4]a[5]a[6]a[7]a[8]2-2二分搜索算法二分搜索实例:设在数组a中顺序放了以下9个元素：检索x=9,9==a[4],一次比较就成功,最好情况-15-6079235482101a[0]a[1]a[2]a[3]a[4]a[5]a[6]a[7]a[8]①②③③④②③④检索x=-15,-15

7、01,101>a[4],101>a[6],101>a[7],101==a[8],4次比较,成功检索x=8,8a[1],8>a[2],8>a[3],4次比较,不成功2-2二分搜索算法#include#defineN10intfind(inta[],intx,intbott,inttop)；voidmain(){inti,x,a[N],result;printf("输入数组a:");for(i=0;i

8、(“输入要查找的数x:");scanf("%d",&x);result=find(a,x,0,N-1);if(result==-1)printf("%disnotfound.",x);elseprintf("Find%d==a[%d]",x,result);}迭代法的程序代码//符号常量定义，便于修改数组的大小//函数调用//函数声明2-2二分搜索算法intfind(inta[],intx,intbott,inttop){intmid;while(bott<=