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

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数列
1
定义Fibonacci数列的递归数学模型：
递归法求Fibonacci数列
1 n=0,1
F(n-1)+F(n-2) n>1
F(n)=
递归的终止条件
递归公式
int Fib(int n)
{ if (n<0)
{ printf("error!"); exit(0); }
else
if (n <= 1) return 1;
else return Fib(n-1)+Fib(n-2);
}
2-1 递归法求Fibonacci数列
2
用递归法求Fibonacci数列
Fib(4)
return +
Fib(3)
Fib(2)
return +
Fib(2)
Fib(1)
return +
Fib(1)
Fib(0)
return +
Fib(1)
Fib(0)
return 1
return 1
return 1
return 1
return 1
n=4时，递归法进行了多少次函数调用？
1
1
2
1
1
1
3
2
5
n=20时, 要进行21891次递归调用
讨论: 求Fibonacci数列的迭代法和递归法谁好？
2-1 递归法求Fibonacci数列
3
第2讲 分治法和二分搜索算法
本讲内容：
(1) 分治法的基本思想
(2) 二分搜索技术
4
分治法的基本思想
分治法的思想: 分而治之。将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同，(如果子问题的规模仍然不够小，则再划分为k个子问题), 然后递归的求解这些子问题，最后用适当的方法将各子问题的解合并成原问题的解。
原问题(规模为n)
子问题1
子问题2
子问题k
…
子问题1
子问题2
子问题k
…
相同
类型
合并解
子问题1
子问题2
子问题k
…
子问题1
子问题2
子问题k
…
5
分治法的适用条件
分治法所能解决的问题一般具有以下几个特征：
该问题的规模缩小到一定的程度就可以容易地解决
该问题可以分解为若干个规模较小的相同问题
该问题所分解出的各个子问题是相互独立的
利用分解出的子问题的解可以合并为该问题的解
分治法的基本思想
6
前提条件：有一组数已经按从小到大(或从大到小)排序
目标：输入一个数x，在这组数查找是否有x
二分搜索的步骤：
1、确定三个关键下标的初值：bott=0, top=8, mid=(bott+top)/2;
2、判断要找的数x是否等于a[mid]
① x==a[mid] 找到，结束
x<a[mid] 在a[bott]—a[mid-1]之间继续查找x
top=mid-1; mid=(bott+top)/2;
③ x>a[mid] 在a[mid+1]—a[top]之间继续查找x
bott=mid+1; mid=(bott+top)/2;
-15
-6
0
7
9
23
54
82
101
mid
bott
top
a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8]
2-2 二分搜索算法
7
二分搜索实例:设在数组a中顺序放了以下9