算术运算的妙用有关算术运算的妙用-Read.ppt

第三章
算法设计
算法优化基本技巧
算术运算的妙用
标志量的妙用
信息数字化
算术运算的妙用
有关算术运算的妙用,在前面的许多例题中已有体现。如:“原始信息与处理结果的巧妙对应”中的例2,通过算术运算把数据信息归类后与下标对应。“构造趣味矩阵”中例2的算法2 ,通过算术运算构造循环不变式。
总之,通过恰当的算术运算可以很好地提高编程效率,以及相关算法的运行效率。值得认真总结学****br/>【例1】一次考试,共考了五门课。统计五十个学生中至
少有三门课成绩高于90分的人数。
问题分析:若一个学生五门课的成绩分别记为:a1,a2,a3,a4,a5,则要表示有三门课成绩高于90分,有C35=10组关系逻辑表达式,每组三个关系表达式。无论书写还是运行效率都极低。但通过算法运算就能很简便地解决这类问题。
算法设计:
1)对每个同学,先计算其成绩高于90分的课程数目,若超过3,则累加满足条件的人数中。
2)用二重循环实现以上过程,外层循环模拟50个同学,内层循环模拟五门课程。
main( )
{int a[5],i,j,s,num=0;
for ( i=1;i<=50;i=i+1)
{s=0;
for( j=0;j<=4;j=j+1)
{input(a[j]);
if(a[j]>=90)
s=s+1; }
if(s>=3)
num=num+1;
}
print(“The number is”,num);
}
算法如下:
算法说明:对于计算其成绩高于90分的课程数目,还可以简单地这样实现:
s=0;
for( j=0;j<=4;j++)
{input(“a[j]);
s=s+(a[i]>=90);
}
【例2】开灯问题:有从1到n依次编号的n个同学和n 盏灯。1号同学将所有的灯都关掉;2号同学将编号为2的倍数的灯都打开;3号同学则将编号为3的倍数的灯作相反处理(该号灯如打开的,则关掉;如关闭的,则打开);以后的同学都将自己编号的倍数的灯,作相反处理。问经n个同学操作后,哪些灯是打开的?
问题分析:
1)用数组表示某种状态,这里定义有n个元素的a数组,它
的每个下标变量a[i]视为一灯,i表示其编号。a[i]=1
表示灯处于打开状态,a[i]=0表示灯处于关闭状态。
2)实现将第i 灯作相反处理的操作,可以用条件语句if表
示:当a[i]为1时,a[i]被重新赋为0;当a[i]为0时,
a[i]被重新赋为1。但通过以下算术运算: a[i]=1-a[i]
就很好地模拟“开关”灯的操作。
main( )
{ int n,a[1000],i,k;
print(“input a number”);
input(“%d”,&n);
for( i=1;i<=n;i++)
a[i]=0;
for( i=2;i<=n;i++)
{ k=1;
while ( i*k<=n)
{ a[i*k]=1-a[i*k];
k=k+1;}
}
for( i=1;i<=n;i++)
print( a[i]);
}
算法说明:算法中第二
个for循环i枚举的不是
灯的编号,而是编号为I
的同学,其内层循环中,
就将包含i因素的灯的编
号为“i*k”的灯,改变其
状态。
【例3】右图中所示的圆圈中,我们把相隔一个数据的两个数(如1和10,3和5,3和6)称作是“一对数”,试编程求出乘积最大的一对数和乘积最小的一对数。输出格式如下:
max: ?*?=?
min: ?*?=?
其中?表示:找到的满足条件的数和乘积。
1)题目中的数据有前后“位置”关系,因此必须用数组来
存储。设数组定义为a[num],则有a[0]—a[num-1]共
num个元素。
2)用i代表下标,题目就是顺序将a(i-1)与a(i+1)相
乘,求出乘积的最大值和最小值即可。
3)关键问题是使i=num-1时,保证i+1的“值”是0;当i=0
时,保证i-1的“值”是num-1,把数组当成圆圈操作通
过求余运算很容易实现将线性的数组当成圆圈操作:
i=num-1时,(i+1)%num等于0;
当i=0时(num+i-1)%num等于num-1,且这样的表达式当
i为其它值时也是同样适用的。
通过求余运算,“避免了”判别数组起点与终点的操作。
4)用变量Max记录当前最大的乘积,m、n为对应的两个乘
数;变量min记录当前最小的乘积,s、t为对应的两个
乘数。
算法设计: