第三章 蛮力法

《第三章 蛮力法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三章算法设计第三章算法基本工具和优化技巧利用算法的基本机制——循环和递归设计算法利用算法的基本操作提高算法效率的技巧利用数组提高算法质量建立高效的数学模型3．1循环与递归3．3算法优化基本技巧3．2算法与数据结构3．4优化算法的数学模型3．1．1循环设计要点3．1．2递归设计要点3．1．3递归与循环的比较3．1循环与递归3．1．1循环设计要点1．设计中要注意算法的效率2．“自顶向下”的设计方法3．由具体到抽象设计循环结构循环体的特点是：“以不变应万变”。所谓“不变”是指循环体内运算的表现形式是不变的，而每次具体的执行内容却是不尽相同的。在循环体内用不变的运算表现形

2、式去描述各种相似的重复运算。1．循环设计中要注意算法的效率【例1】求1/1!-1/3!+1/5!-1/7!+…+（-1）n+1/(2n-1)!分析：此问题中既有累加又有累乘，准确地说累加的对象是累乘的结果。数学模型1：Sn=Sn-1+（-1）n+1/(2n-1)!算法设计1：多数初学者会直接利用题目中累加项通式，构造出循环体不变式为：S=S+（-1）n+1/(2n-1)!需要用二重循环来完成算法，算法1如下：算法如下：求（-1）n+1for(j=1;j<=i+1;j=j+1)sign=sign*(-1);s=s+sign/t;}print(“Snm=”,s);

3、}main(){inti,n,j,sign=1;floats,t=1;input(n);s=1；for(i=2;i<=n;i=i+1){t=1;求阶乘for(j=1;j<=2*i-1;j=j+1)t=t*j;sign=1;算法分析：以上算法是二重循环来完成，但算法的效率却太低是O（n2）。其原因是，当前一次循环已求出7！，当这次要想求9！时，没必要再从1去累乘到9，只需要充分利用前一次的结果，用7！*8*9即可得到9！，模型为An=An-1*1/((2*n-2)*(2*n-1)。另外运算sign=sign*(-1);总共也要进行n*(n-1)/2次乘法，这也是没

4、有必要的。下面我们就进行改进。数学模型2：Sn=Sn-1+（-1）n+1An；An=An-1*1/((2*n-2)*(2*n-1))main(){inti,n,sign;floats,t=1;input(n);s=1；sign=1;for(i=2;i<=n;i=i+1)或for(i=1;i<=n-1;i=i+1){sign=-sign;{sign=-sign;t=t*(2*i-2)*(2*i-1)};t=t*2*i*(2*i+1)};s=s+sign/t;}s=s+sign/t;}print(“Sum=”,s);}算法说明2：构造循环不变式时，一定要注意循环变量的意

5、义，如当i不是项数序号时（右边的循环中）有关t的累乘式与i是项数序号时就不能相同。算法分析：按照数学模型2，只需一重循环就能解决问题算法的时间复杂性为O（n）。2．“自顶向下”的设计方法自顶向下的方法是从全局走向局部、从概略走向详尽的设计方法。自上而下是系统分解和细化的过程。【例2】编算法找出1000以内所有完数例如，28的因子为1、2、4、7，14，而28=1+2+4+7+14。因此28是“完数”。编算法找出1000之内的所有完数，并按下面格式输出其因子：28it’sfactorsare1，2，4，7，14。1）这里不是要质因数，所以找到因数后也无需将其从数据中“

6、除掉”。2）每个因数只记一次，如8的因数为1，2，4而不是1，2，2，2，4。（注：本题限定因数不包括这个数本身）1）顶层算法for(i=0;i

7、=i）i是“完数”;4）考虑输出格式——判断i是否“完数”算法考虑到要按格式输出结果，应该开辟数组存储数据i的所有因子，并记录其因子的个数，因此算法细化如下：定义数组a，s=1;k=0;for(j=2;j