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

计算机操作系统第三章
第1页，本讲稿共54页
第三章 算法基本工具和优化技巧
利用算法的基本机制——循环和递归设计算法
利用算法的基本操作提高算法效率的技巧
利用数组提高算法质量
建立高效的数学模型
3．1 循环与递归 ，本讲稿共54页
1）顶层算法
for(i=0;i<n;i=i+1)
{找第i行上最小的元素t及所在列minj;
检验t是否第minj 列的最大值，是则输出这个鞍点;}
2）找第i行上最小的元素t及所在列minj
t=a[i][0]; minj=1;
for(j=1;j<n;j=j+1)
if(a[i][j]<t)
{t=a[i][j];
minj=j;}
第13页，本讲稿共54页
3）进一步细化——判断i是否“完数”算法
s=1
for(j=2;j<i;j=j+1)
if (i mod j=0) (j是i的因素) s=s+j;
if （s=i） i是“完数”;
第14页，本讲稿共54页
4）考虑输出格式——判断i是否“完数”算法
考虑到要按格式输出结果，应该开辟数组存储数据i的所有因子，并记录其因子的个数，因此算法细化如下：
定义数组a，s=1; k=0;
for(j=2;j<i;j=j+1)
if (i mod j=0) (j是i的因素)
{s=s+j; a[k]=j;k=k+1;}
if （s=i）
{按格式输出结果}
第15页，本讲稿共54页
算法如下：
main( )
{int i,k,j,s,a[20];
for(i=1;i<=1000;i++)
{s=1; /*两个赋初值语句s=1,k=0
k=0; 一定要位于外部循环的内部*/
for(j=2;j<i;j++)
if (i mod j)==0)
{s=s+j; a[k]=j; k++;}
if(i==s)
{print(s, “it’s factors are :”,1);
for(j=0;i<k;j++)
print(“,”,a[k]);
}
}
}
第16页，本讲稿共54页
【例3】求一个矩阵的鞍点 (即在行上最小而在列上最大的点)。 算法设计：
1）在第一行找最小值，并记录其列号。
2）然后验证其是否为所在列的最大值，如果是，则找到问题的解；否则，则继续在下一行找最小值 …… 。
第17页，本讲稿共54页
for(i=0;i<n;i=i+1)
{找第i行上最小的元素t及所在列minj;
检验t是否第minj 列的最大值，是则输出这个鞍点;}
t=a[i][0]; minj=1;
for(j=1;j<n;j=j+1)
if(a[i][j]<t)
{t=a[i][j];
minj=j;}
1）顶层算法
2）找第i行上最小的元素t及所在列minj
第18页，本讲稿共54页
3）检验t是否第minj 列的最大值，是，则输出这个鞍点;
for(k=0;k<n;k=k+1)
if(a[k][minj]>t) break;
if(k<n) continue;
print(“the result is a[“,i ，“][” ,minj, “]=”，t);
考虑到会有无解的情况，设置标志量kz，kz=0代表无解，找到一个解后，kz被赋值为1，就不再继续找鞍点的工作。请读者考虑是否有多解的可能性吗？若有，请改写算法，找出矩阵中所有的鞍点。
第19页，本讲稿共54页
算法如下：
buck( )
{int a[10][10]; int i,j,k,minj,t,n=10,kz=0;
/*minj代表当前行中最小值的列下标；设置标志量kz*/
readmtr(a,n);
prntmtr(a,n);
for(i=0;i<n;i++)
{t=a[i][0]; minj=1;
for(j=1;j<n;j++)
if(a[i][j]<t)
{t=a[i][j];minj=j;}
for(k=0;k<n;k++)
if(a[k][minj]>a[i][minj]) break;
if(k<n) continue;
print(“the result is a[“,i ,“][”,minj,“]=”，a[i][minj]);
kz=1;
break;
}
if