计算机操作系统第三章.ppt

计算机操作系统第三章
第一页，课件共54页
第三章 算法基本工具和优化技巧
利用算法的基本机制——循环和递归设计算法
利用算法的基本操作提高算法效率的技巧
利用数组提高算法质量
建立高效的数学模型
3．1 循环与递归 3．3 算法优化基本技巧
3．2 算法与数据结构 3．4 优化算法的数学模型
第二页，课件共54页
3．1．1 循环设计要点
3．1．2 递归设计要点
3．1．3 递归与循环的比较
3．1 循环与递归
第三页，课件共54页
3．1．1 循环设计要点  1．设计中要注意算法的效率  2．“自顶向下”的设计方法  3．由具体到抽象设计循环结构
第四页，课件共54页
循环体的特点是：“以不变应万变”。
所谓“不变”是指循环体内运算的表现形式是不变的，而每次具体的执行内容却是不尽相同的。在循环体内用不变的运算表现形式去描述各种相似的重复运算。
1．循环设计中要注意算法的效率
第五页，课件共54页
【例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如下：
第六页，课件共54页
算法如下：
\求（-1）n+1\
for(j=1;j<=i+1;j=j+1)
sign = sign *(-1);
s=s+ sign/t;
}
print(“Snm=”,s);
}
main( )
{int i,n,j,sign=1;
float s,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;
第七页，课件共54页
算法分析：
以上算法是二重循环来完成 ，但算法的效率却太低是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次乘法，这也是没有必要的。下面我们就进行改进。
第八页，课件共54页
数学模型2：Sn=Sn-1+（-1）n+1An； An=An-1 *1/((2*n-2)*(2*n-1))
main( )
{int i,n, sign;
float s,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);
}
第九页，课件共54页
算法说明2：构造循环不变式时，一定要注意循环变量的意义，如当i不是项数序号时（右边的循环中）有关t的累乘式与i是项数序号时就不能相同。算法分析：按照数学模型2，只需一重循环就能解决问题算法的时间复杂性为O（n）。
第十页，课件共54页