第三章算法优化.ppt

3．3 算法优化基本技巧 3．3．1 算术运算的妙用 3．3．2 标志量的妙用 3．3．3 信息数字化 3.3.1 算术运算的妙用 有关算术运算的妙用，在前面的许多例题中已有体现。如：上一节3．2．1“原始信息与处理结果的巧妙对应”中的例2，通过算术运算把数据信息归类后与下标对应。 总之，通过恰当的算术运算可以很好地提高编程效率，以及相关算法的运行效率。值得认真总结学习。 【例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： ?*?=? 其中？表示：找到的满足条件的数和乘积。 3.3.2 标志量的妙用 【例1】冒泡排序算法的改进 【例2】编程判定从键盘输入n个数据互不相等。 问题分析： 这里要判定n个数互不相等，是无任何限定的数据。若用逻辑表达式表示需要： n-1 + n-2 + n-3 +……+1=n*(n-1)/2 个关系表达式。显然书写和运行效率都很低。 算法设计： 下面，通过引入标志量记录数据是否有重复的情况，避免了复杂的逻辑表达式。 【例3】输入三个数值，判断以它们为边长是否能构成的三角形，属于那种特殊三角形：等边、等腰、直角。 问题分析：这个题目表面看起来非常简单，但要做到合理输出却并不容易。这里我们先讨论一下可能的输出情况： 1）不构成三角形、2）构成等边三角形、3）构成等腰三角形、4）构成直角三角形5）构成一般三角形。 分析以上情况，输出情况5）与2）、3）、4）不应该同时出现，而输出情况3）4）有可能同时出现；只用嵌套或并列的if很容易出现不合理的输出，如会出现既输出“是一个三角形”又输出了“是等边三角形”等不合理的结果。 输出情况1）与其它情况是“否则”关系，容易分支。输出情况5）是在三角形不属于2）3）4）三种情况时的输出。特别地，情况4）与情况3）不是简单的否则关系，因为3）4）两种情况可能同时输出。 算法设计： 算法中我们需要避免情况5）与情况2）3）4）之一同时输出。设置一标志变量flag，当数据能构成三角形时就置flag=0表示情况5），一但测试出数据属于情况2）3）4）中的一种情况时，就置flag=1表示构成了特殊三角形，最后就不必输出“构成一般三角形”了；若flag最后仍保持0，则输出“构成一般三角形”。 算法如下： main( ) { int a,b,c,flag; print(“Input 3 number:”); input(a,b,c); if(a=b+c or b=a+c or c=a+b) print(“don’t form a triangle”); else {flag=0; if (a*a=b*b+c*c or b*b=a*a+c*c or c*c=a*a+b*b) {print(“form a right-angle triangle”); fl