基本的算法策略.ppt

第四章基本的算法策略4.1迭代算法4．1．1递推法算法1：4.1.2倒推法【例】猴子吃桃问题
一只小猴子摘了若干桃子，每天吃现有桃的一半多一个，
到第10天时就只有一个桃子了，求原有多少个桃？
数学模型：每天的桃子数为：a10=1,a9=（1+a10）*2,a8=（1+a9）*2,……a10=1，
递推公式为：ai=（1+ai+1）*2I=9,8,7,6……1
算法如下：
main()
{inti,s;
s=1;
for(i=9;i>=1;i=i-1)
s=(s+1）*2
print(s)；
}

4.2蛮力法4．2．1枚举法【例】解数字迷：ABCAB
×A
DDDDDD
算法设计1：按乘法枚举
1)枚举范围为：
A：3——9（A=1，2时积不会得到六位数）,B：0——9,
C：0——9六位数表示为A*10000+B*1000+C*100+A*10+B，
共尝试800次。
2)约束条件为：
每次尝试，先求5位数与A的积，再测试积的各位是否相
同，若相同则找到了问题的解。
测试积的各位是否相同比较简单的方法是，从低位开始，
每次都取数据的个位，然后整除10，使高位的数字不断变
成个位，并逐一比较。算法1如下：
main（）
{intA,B,C,D,E,E1,F,G1,G2,i;
for(A=3;A<=9;A++)
for(B=0;B<=9;B++)
for(C=0;C<=9;C++)
{F=A*10000+B*1000+C*100+A*10+B;
E=F*A；E1=E;G1=E1mod10;
for(i=1;i<=5;i++)
{G2=G1;E1=E1/10;G1=E1mod10;
if(G1<>G2)break;}
if(i=6)print(F，”*”，A，”=”，E);
}
}4.3分而治之算法4．3．1分治算法框架说明：
有时问题分解后，不必求解所有的子问题，也就不必作第三步的操作。比如折半查找，在判别出问题的解在某一个子问题中后，其它的子问题就不必求解了，问题的解就是最后（最小）的子问题的解。分治法的这类应用，又称为“减治法”。
多数问题需要所有子问题的解，并由子问题的解，使用恰当的方法合并成为整个问题的解，比如合并排序，就是不断将子问题中已排好序的解合并成较大规模的有序子集。2．适合用分治法策略的问题
当求解一个输入规模为n且取值又相当大的问题时，用蛮力策略效率一般得不到保证。若问题能满足以下几个条件，就能用分治法来提高解决问题的效率。
1）能将这n个数据分解成k个不同子集合，且得到k个子集合是可以独立求解的子问题，其中1＜k≤n；
2）分解所得到的子问题与原问题具有相似的结构，便于利用递归或循环机制；
在求出这些子问题的解之后，就可以推解出原问题的解；4．3．2二分法【例1】金块问题：老板有一袋金块(共n块)，最优秀的雇员得到其中最重的一块，最差的雇员得到其中最轻的一块。假设有一台比较重量的仪器，我们希望用最少的比较次数找出最重的金块。算法设计1：
比较简单的方法是逐个的进行比较查找。先拿两块比较重量，留下重的一个与下一块比较，直到全部比较完毕，就找到了最重的金子。算法类似于一趟选择排序，
算法如下：
maxmin(floata[],intn)
{max==min=a[1];for(i=2;i<=n;i++)if(max<a[i])max=a[i];
elseif(min>a[i])min=a[i];}
算法分析1：
算法中需要n-1次比较得到max。最好的情况是金块是由小到大取出的，不需要进行与min的比较，共进行n-1次比较。最坏的情况是金块是由大到小取出的，需要再经过n-1次比较得到min算法设计2:
在含n（n是2的幂（n>=2））个元素的集合中寻找极大元和极小元。用分治法（二分法）：
1）将数据等分为两组（两组数据可能差1），
2）递归分解直到每组元素的个数≤2，可简单地找
到最大（小）值。
3）回溯时将分解的两组解大者取大，小者取小，
合并为当前问题的解。算法2递归求取最大和最小元素
floata[n];
maxmin（inti,intj,float&fmax,float&fmin）{intmid;floatlmax,lmin,rmax,rmin;
if(i=j){fmax=a[i];fmin=a[i];}
elseif(i=j-1)
if(a[i]<a[j]){fmax=a[j]；fmin=a[i];}
else{fmax=a[i];fmin=a[j];}
else{mid=(i+j)/2;maxmin（i，mid，lmax，lmin）;maxmin（mid+1，j，rmax，rmin）;if(lmax>rmax)fmax=lmax;
elsefmax=rmax;if(lmin>rmin)fmin=rm