VC编程教程 第四章 算法策略.pptVIP

第四章 基本的算法策略 4.1 迭代算法 4.2 蛮力算法 4.3 分而治之算法 4.4 贪婪算法 4.1 迭代算法 4.1.1 递推法 4.1.2 倒推法 4.1.3 迭代法解方程 4．1．1 递推法 【例1】兔子繁殖问题 问题描述：一对兔子从出生后第三个月开始，每月生一对小兔子。小兔子到第三个月又开始生下一代小兔子。假若兔子只生不死，一月份抱来一对刚出生的小兔子，问一年中每个月各有多少只兔子。 问题分析：因一对兔子从出生后第三个月开始每月生一对小兔子，则每月新下小兔子的对儿数(用斜体数字表示)显然由前两个月的小兔子的对儿数决定。则繁殖过程如下： 一月 二月 三月 四月 五月 六月 …… 1 1 1+1=2 2+1=3 3+2=5 5+3=8 …… 算法1： main( ) { int i,a=1,b=1; print(a,b); for(i=1;i＜=10;i++) { c=a+b; print (c); a=b; b=c； } } 【例2】求两个整数的最大公约数。 数学建模：辗转相除法是根据递推策略设计的。 不妨设两个整数ab且a除以b商x余c；则a-bx=c，不难看出a、b的最大公约数也是c的约数（一个数能整除等式左边就一定能整除等式的右边），则a、b的最大公约数与b、c的最大公约数相同。同样方法推出b、c的最大公约数与……，直到余数为0时，除数即为所求的最大公约数。 算法设计：循环“不变式”第一次是求a、b相除的余数c，第二次还是求“a”“b” 相除的余数，经a=b,b=c操作，就实现了第二次还是求“a”“b” 相除的余数，这就找到了循环不变式。循环在余数c为0时结束。 4.1.2 倒推法 4.2 蛮力法 4.2.1 枚举法 4.2.2 其它范例 4．2．1 枚举法 main( ){? int x,y,z;????for(x=1;x=20;x=x+1)?????????????? ????????for(y=1;y=33;y=y+1)?????????? ????????{?z=100-x-y;???????????? ?????????if(z mod 3=0 and 5*x+3*y+z/3=100)???????????????????????????????????????????????{print(the cock number is,x)； print(the hen number is, y)； print(the chick number is z);}????????}} 算法分析：以上算法只需要枚举尝试20*33=660次。实现时约束条件又限定Z能被3整除时，才会判断“5*x+3*y+z/3=100”。这样省去了z不整除3时的算术计算和条件判断，进一步提高了算法的效率。 4.3 分而治之算法 4.3.1 分治算法框架 4.3.2 二分法 4.3.3 二分法变异 4.3.4 其它分治方法 4．3．1 分治算法框架 * 数学建模：y1=y2=1，yn=yn-1+yn-2，n=3，4，5，……。 算法如下： main（） { int a, b; input(a,b); if(b=0) {print(“data error”); return;} else { c = a mod b; while c0 { a=b; b=c; c=a mod b;} } print(b); } 所谓倒推法：是对某些特殊问题所采用的违反通常习惯的，从 后向前推解问题的方法。如下面的例题，因不同方面的需求而采用了倒推策略。 例1在不知前提条件的情况下，经过从后向前递推，从而求解问题。即由结果倒过来推解它的前提条件。又如例2由于存储的要求，而必须从后向前进行推算。另外，在对一些问题进行分析或建立数学模型时，从前向后分析问题感到比较棘手，而采用倒推法（如例3），则问题容易理解和解决。下面分别看这几个例子： 【例1】猴子吃桃问题 一只小猴子摘了若干桃子，每天吃现有桃的一半多一个， 到第10天时就只有一个桃子了，求原有多少个桃？ 数学模型：每天的桃子数为：a10=1, a9=(1+a10)*2, a8=(1+a9)*2,……a10=1， 递推公式为：ai=(1+ai+1)*2 I = 9,8,7,6……1 算法如下 ： main( ) { int i,s;