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