《算法优化技巧》PPT课件.ppt

1,算法设计与分析,Design and Analysis to Algorithms,2,3.从算法到实现-算法基本技巧举例,a.算术运算的妙用例1.2 开灯问题b.巧用“标志量”例1.3 判定输入n个数据互不相等例1.4 冒泡排序c.信息数字化例1.5 警察抓小偷d.学会找规律例1.6 数组移位,3,a.算术运算的妙用-例1.2开灯问题,算术运算：加减乘除。,例1.2 开灯问题从前，有从1到n依次编号的n个同学和n 盏灯。1号同学将所有的灯都关掉；2号同学将编号为2的倍数的灯都打开；3号同学则将编号为3的倍数的灯作相反处理（该号灯如打开的，则关掉；如关闭的，则打开）；以后的同学都将自己编号的倍数的灯，作相反处理。问：经n个同学操作后，哪些灯是打开的？,4,问题分析：1）用数组表示某种状态，这里定义有n个元素的a数组，它的每个下标变量ai视为一灯，i表示其编号。ai=1表示灯处于打开状态，ai=0表示灯处于关闭状态。,此用法也称为“乒乓开关”。简化逻辑表达式、减少条件判断,2）实现将第i 灯作相反处理的操作：条件语句if表示：if ai=1 ai=0；if ai=0 ai=1；,通过算术运算更简练、逼真：ai=1-ai。,a.算术运算的妙用-例1.2问题分析/建模,5,a.算术运算的妙用-例1.2-算法设计,int a1000;,输入n的数值；,关闭所有灯，即a1an置为0；,第2个学生-第n个学生(学生i)进行操作：,操作对象：数组a，灯编号含因数i，即ai*k；,操作：ai*k=1-ai*k；,输出灯的开关状态。,6,建立一个充分大的数组int a1000;输入n的数值；关闭所有灯，即a1an置为0；第2-第n个学生(每个学生i)进行操作：操作对象：数组a，灯编号含因数i，即ai*k操作：ai*k=1-ai*k；输出灯的开关状态。,void main()int n,a1000,i,k;scanf(%d,翻译,a.算术运算的妙用-例1.2-算法设计/实现,7,b 巧用“标志量”-例1.3-问题分析,例2.2 判定输入n个数据互不相等。,问题分析/算法设计：完全比较一遍需要n-1+n-2+n-3+1=n*(n-1)/2次比较。双重循环；通过引入标志量记录数据是否有重复的情况，相当于整合每趟循环中的比较结果。,8,建立一个充分大的数组；,标志量flag=1；,输入n个数，保存在数组的前n个元素；,从第1个第n-1个(每个元素i)操作,与第i+1第n元素(每个元素j)比较，若相等则标志量置0，循环中断；,若flag=1，则无重复；反之，有重复。,b 巧用“标志量”-例1.3-算法设计,9,b 巧用“标志量”-例1.3 实现,void main()int a100,i,j,flag,n;scanf(%d,10,例1.4冒泡排序,排序过程,1、比较第一个记录与第二个 记录，若关键字为逆序则交换；然 后比较第二个记录与第三个记录；依次类推，直至第 n-1 个记录和第 n 个记录比较为止第一趟冒泡 排序，结果关键字最大的记录被安 置在最后一个记录上。,2、对前 n-1 个记录进行第二 趟冒泡排序，结果使关键字次大的 记录被安置在第 n-1 个记录位置。,3、重复上述过程，直到“在 一趟排序过程中没有进行过交换记 录的操作”为止。,第 一 趟 排 序,49,38,49,97,76,97,97,13,97,97,27,97,97,49,97,38 49 65 76 13 27 49 97,38 49 65 13 27 49 76,第 二 趟 排 序,38 49 13 27 49 65,第 三 趟 排 序,38 13 27 49 49,第 四 趟 排 序,13 27 3849,第 五 趟 排 序,13 27 38,第 六 趟 排 序,for(j=1;j n;j+)if(r j+1 r j)r j r j+1;,for(j=1;j n-1;j+)if(r j+1 r j)r j r j+1;,for(i=n;i 1;i-),i;,while(i 1),/while,i=n;,i=k;,Void BubbleSort(SqList&L),冒泡排序算法,k=j;/交换的位置,k=1;,11,c 信息数字化-例1.5 警察抓小偷,一些表面上看是非数值的问题，但经过进行数字化后，就可方便进行算法设计。,例1.5 警察抓小偷警察局抓了a，b，c，d四名偷窃嫌疑犯，其中只有一人是小偷。审问中 a说：“我不是小偷。”b说：“c是小偷。”c说：“小偷肯定是d。”d说：“c在冤枉人。”现在已经知道四个人中三人说的是真话，一人说的是假话，问到底谁是小偷？,12,c 信息数字化-例1.5-问题分析,问题分析：可通过循环，每次假设一名嫌疑犯为小偷，代入问题系统，检验是否只有一句假话。,这种让所有可能解都进行检验，以求得真解的方法称为“枚举尝试法”，也是“蛮力法”、“暴力法”。,为方便设计程序，将a,b,c,d将四个人进行编号，号码分别为1，2，3，4。,13,c 信息数字化-例1.5-算法设计,算法设计：用变量x存放小偷的编号，则x的取值范围从1取到4，就假设了他们中的某人是小偷的所有情况。四个人所说的话就可以分别写成：,a说的话：x1b说的话：x=3c说的话：x=4d说的话：x4或not(x=4),注意:在x的枚举过程中，当这四个逻辑式的值相加等于3时，即表示“四个人中三人说的是真话，一人说的是假话”。,if(x!=1)+(x=3)+(x=4)+(x!=4)=3),14,c 信息数字化-例1.5-实现,#include stdafx.hvoid main()int x;for(x=1;x=4;x=x+1)if(x!=1)+(x=3)+(x=4)+(x!=4)=3)printf(%c is a thief,char(64+x);,15,d 学会找规律-例1.6 数组移位,例1.6 数组中有n个数据，要将它们顺序循环向后移k位，即前面的元素向后移k位，后面的元素则循环向前移k位，例：0、1、2、3、4循环移3位后为：2、3、4、0、1。考虑到n会很大，不允许用2*n以上个空间来完成此题。,16,d 学会找规律-例1.6-问题分析(思路1),问题分析1：若题目中没有关于存储空间的限制，我们可以方便地开辟两个一维数组，一个存储原始数据，另一个存储移动后的数据。,开始部分的元素从前向后移，容易确定；但数组中后k个元素是从后向前移，如何确定？,17,d 学会找规律-例1.6-问题分析(思路1),void alg1()int a100,b100,i,n,k;scanf(%d,%d,for(i=0;in;i=i+1)b(k+i)%n=ai;for(i=0;in;i=i+1)printf(%d,bi);printf(n);,18,d 学会找规律-例1.6-问题分析(思路2),问题分析2：将最后一个存储空间的数据,存储在临时存储空间中；其余数据逐个向后移动一位。这样操作共k次就能完成问题的要求。,19,d 学会找规律-例1.6-算法设计/实现(思路2),有可能kn，这样移动会出现重复操作,可以在输入数据后，执行k=k mod n;以保证不出现重复移动的问题。这个算法的移动（赋值）次数为k*n。当n较大时不是一个好的算法。,void alg2()int a100,i,j,n,k,temp;scanf(%d,%d,20,d学会找规律-例1.6-问题分析(思路3),问题分析3：利用一个临时存储空间，把每一个数据一次移动到位。,1）一组循环移动的情况：通过计算我们可以确定某个元素移动后的具体位置，如n=5,k=3时：0、1、2、3、4循环移3位后为3、4、0、1、2。可通过计算得出0移到3的位置，3移到1的位置，1移到4的位置，4移到2的位置，2移到0的位置；一组移动（0-3-1-4-2-0）正好将全部数据按要求进行了移动。这样只需要一个辅助变量，每个数据只需一次移动就可完成整个移动过程。,如果算法就这样按一组移动去解决问题，就错了。因为还有其它情况。,21,2）多组循环移动的情况：算法不能只按一组移动去解决问题。看下一个例子，当n=6，k=3时，0、1、2、3、4、5经移动的结果是3、4、5、0、1、2.共要进行三组循环移动（0-3，1-4，2-5）才能将全部数据操作完毕。,循环移动的组数，与k、n是怎么样的关系呢？,我们再看一个例子，当N=6，K=2时，0、1、2、3、4、5经移动的结果是4、5、0、1、2、3。0移到2的位置，2移到4的位置，4移到0的位置，一组移动完成了3个数据的移动，接下来，还有一组1-3-5-1。共进行二组循环移动，就能将全部数据移动完毕。,d学会找规律-例1.6-问题分析(思路3),22,d学会找规律-例1.6-建模/算法设计(思路3),数学模型：循环移动的组数等于N与K的最大公约数。算法设计：1）编写函数，完成求n,k最大公约数m的功能。2）进行m组循环移动。3）每组移动，和算法2一样，通过计算可以确定某个元素移动后的具体位置。在移动之前，用临时变量存储需要被覆盖的数据。,23,d学会找规律-例1.6-实现(思路3),void alg3()int a100,b0,b1,i,j,n,k,m,tt;scanf(%d,for(j=0;jm;j=j+1)b0=aj;tt=j;for(i=0;in/m;i=i+1)tt=(tt+k)%n;b1=att;att=b0;b0=b1;for(i=0;in;i=i+1)printf(%d,ai);printf(n);,24,4 优化算法的数学模型,1、认识数学模型和数学建模 看一个很简单的例子：已知有五个数，求前四个数与第五个数分 别相乘后的最大得数。给出两个算法分别如下：,25,max1(int a,b,c,d,e)max2(int a,b,c,d,e)int x;int x a=a*e;if(ab)b=b*e;x=a;c=c*e;else d=d*e;x=b;if(ab)if(cx)x=a;x=c;else if(dx)x=b;x=d;if(cx)x=x*e;x=c;print(x);if(dx)x=d;print(x);,26,数学建模：就是把现实世界中的实际问题加以提炼，抽象为数学模型，求出模型的解，验证模型的合理性，并用该数学模型所提供的解答来解释现实问题，我们把数学知识的这一应用过程称为数学建模。,27,2数学建模的基本方法,归纳法从简单到复杂，由个别到一般的 一种研究方法。,28,公倍数的应用,【例】编程完成下面给“余”猜数的游戏：你心里先想好一个1100之间的整数x，将它分别除以3、5和7并得到三个余数。你把这三个余数告诉计算机，计算机能马上猜出你心中的这个数。问题分析：算法的关键是：找出余数与求解数之间的关系，也就是建立问题的数学模型。,29,数学模型：1）不难理解当s=u+3*v+3*w时，s除以3的 余数与u除以3的余数是一样的。2）对s=cu+3*v+3*w，当c除以3余数为1的 数时,s除以3的余数与u除以3的余数也是 一样的。,30,记a，b，c分别为所猜数据d除以3，5，7后的余数，则d=70*a+21*b+15*c为问题的数学模型，其中70称作a的系数，21称作b的系数,15称作c的系数。,31,算法设计：用以上模型求解的数d，可能比100大，这时只要减去3，5，7的最小公倍数就是问题的解了。main()int a,b,c,d;print(“please think of a number between 1 and 100.”);print(“your number divded by 3 has a remainker of”);input(a);print(“your number divded by 5 has a remainker of”);input(b);print(“your number divded by 7 has a remainker of”);input(c);print(“let me think a moment”);d=70*a+21*b+15*c;while(d105)d=d-105;print(“your number was”,d);,