《ACM培训课程算法设计课件.ppt》由会员分享，可在线阅读，更多相关《ACM培训课程算法设计课件.ppt（62页珍藏版）》请在三一办公上搜索。
1、ACM培训课程算法设计,主讲教师：校景中,如何用计算机求解问题？,1.问题分析 准确、完整地理解和描述问题是解决问题的第一步。要做到这一点，必须注意以下一些问题：在未经加工的原始表达中，所用的术语是否都明白其准确定义？题目提供了哪些信息？这些信息有什么用？题目要求得到什么结果？题目中作了哪些假定？是否有潜在的信息？判定求解结果所需要的中间结果有哪些？,如何用计算机求解问题？,2、数学模型建立 用计算机解决实际问题必须有合适的数学模型，因为在现实问题面前，计算机是无能为力。对一个实际问题建立数学模型，可以考虑这样两个基本问题：最适合于此问题的数学模型是什么？是否有已经解决了的类似问题可借鉴？,如
2、何用计算机求解问题？,3、算法设计与选择 算法设计是指设计求解某一特定类型问题的一系列步骤，并且这些步骤是可以通过计算机的基本操作来实现的。算法设计要同时结合数据结构的设计，简单说数据结构的设计就是选取存储方式。算法的设计与模型的选择更是密切相关的，但同一模型仍然可以有不同的算法，而且它们的有效性可能有相当大的差距。,如何用计算机求解问题？,在这些步骤中，算法设计是解决问题的核心,算法又是如何定义的呢？,算法由操作、控制结构、数据结构三要素组成。,算法又是如何定义的呢？,1）操作 算术运算：加、减、乘、除 关系比较：大于、小于、等于、不等于 逻辑运算：与、或、非 数据传送：输入、输出,赋值,算
3、法又是如何定义的呢？,2）控制结构 各操作之间的执行次序。顺序结构：各操作依次执行 选择结构：由条件是否成立来选择 执行 循环结构：有些操作要重复执行，直到 功能满足某个条件时结束。又称重复或 迭代结构。,算法又是如何定义的呢？,3）数据结构 算法操作的对象是数据，数据间的逻辑关系、数据的存储方式及处理方式就是数据的数据结构。它与算法设计是紧密相关的。,如何设计循环？,循环设计要点 1设计中要注意算法的效率 2“自顶向下”的设计方法,循环体的特点是：“以不变应万变”。所谓“不变”是指循环体内运算的表现形式是不变的，而每次具体的执行内容却是不尽相同的。在循环体内用不变的运算表现形式去描述各种相似
4、的重复运算。,1循环设计中如何注意算法的效率,【例1】求1/1!-1/3!+1/5!-1/7!+（-1）n+1/(2n-1)!分析：此问题中既有累加又有累乘，准确地说累加的对象是累乘的结果。数学模型1：Sn=Sn-1+（-1）n+1/(2n-1)!算法设计1：多数初学者会直接利用题目中累加项通式，构造出循环体不变式为：S=S+（-1）n+1/(2n-1)!需要用二重循环来完成算法，算法1如下：,算法如下：,main()int i,n,j,sign=1;float s,t=1;/s存储最终的结果，t存储(2k-1)的阶乘 input(n);/输入n s=1；for(i=2;i=n;i=i+1)t
5、=1;求阶乘 for(j=1;j=2*i-1;j=j+1)t=t*j;sign=1;求（-1）n+1 for(j=1;j=i+1;j=j+1)sign=sign*(-1);s=s+sign/t;print(“Snm=”,s);,算法分析：以上算法是二重循环来完成，但算法的效率却太低是O（n2）。其原因是，当前一次循环已求出7！，当这次要想求9！时，没必要再从1去累乘到9，只需要充分利用前一次的结果，用7！*8*9即可得到9！，模型为An=An-1*1/(2*n-2)*(2*n-1)。另外运算sign=sign*(-1);总共也要进行n*(n-1)/2次乘法，这也是没有必要的。下面我们就进行改进
6、。,数学模型2：Sn=Sn-1+（-1）n+1An；An=An-1*1/(2*n-2)*(2*n-1),main()int i,n,sign;float s,t=1;input(n);s=1；sign=1;for(i=2;i=n;i=i+1)或 for(i=1;i=n-1;i=i+1)sign=-sign;sign=-sign;t=t*(2*i-2)*(2*i-1);t=t*2*i*(2*i+1);s=s+sign/t;s=s+sign/t;print(“Sum=”,s);,算法说明2：构造循环不变式时，一定要注意循环变量的意义，如当i不是项数序号时（右边的循环中）有关t的累乘式与i是项数序号
7、时就不能相同。算法分析：按照数学模型2，只需一重循环就能解决问题算法的时间复杂性为O（n）。,2“自顶向下”的设计方法 自顶向下的方法是从全局走向局部、从概略走向详尽的设计方法。自上而下是系统分解和细化的过程。,【例2】编算法找出1000以内所有完数例如，28的因子为1、2、4、7，14，而28=1+2+4+7+14。因此28是“完数”。编算法找出1000之内的所有完数，并按下面格式输出其因子：28 its factors are 1，2，4，7，14。,1）这里不是要质因数，所以找到因数后也无需将其从数据中“除掉”。2）每个因数只记一次，如8的因数为1，2，4而不是1，2，2，2，4。（注：
8、本题限定因数不包括这个数本身）,1）顶层算法 for(i=2;i=n;i+)判断i是否是“完数”；是完数则按格式输出；,2）判断是否是”完数”的算法for(j=2;ji;j+)找i的因子，并累加；如果累加值等于i,i是完数,3）进一步细化判断i是否“完数”算法,s=1for(j=2;ji;j=j+1)if(i mod j=0)(j是i的因素)s=s+j;if（s=i）i是“完数”;,4）考虑输出格式判断i是否“完数”算法 考虑到要按格式输出结果，应该开辟数组存储数据i的所有因子，并记录其因子的个数，因此算法细化如下：,定义数组a，s=1;k=0;for(j=2;ji;j=j+1)if(i mo
9、d j=0)(j是i的因素)s=s+j;ak=j;k=k+1;if（s=i）按格式输出结果,算法如下：,main()int i,k,j,s,a20;for(i=1;i=1000;i+)s=1;/*两个赋初值语句s=1,k=0 k=0;一定要位于外部循环的内部*/for(j=2;ji;j+)if(i mod j)=0)s=s+j;ak=j;k+;if(i=s)print(s,“its factors are:”,1);for(j=0;ik;j+)print(“,”,ak);,如何进行递归设计,递归算法是一个模块（函数、过程）除了可调用其它模 块（函数、过程）外，还可以直接或间接地调用自身的算法。
10、,递归是一种比迭代循环更强、更好用的循环结构。,只需要找出递归关系和最小问题的解。,递归的关键在于找出递归方程式和递归终止条件。,递归定义：使问题向边界条件转化的规则。递归定义必须能使问题越来越简单。递归边界条件：也就是所描述问题的最简单情况，它本身不再使用递归的定义。,递归算法解题通常有三个步骤：1）分析问题、寻找递归：找出大规模问题与小规模问题的关系，这样通过递归使问题的规模逐渐变小。2）设置边界、控制递归：找出停止条件，即算法可解的最小规模问题。3）设计函数、确定参数：和其它算法模块一样设计函数体中的操作及相关参数。,【例2】整数的分划问题,对于一个正整数n的分划就是把n写成一系列正整数
11、之和的表达式。例如，对于正整数n=6，它可以分划为：6 5+1 4+2,4+1+1 3+3,3+2+1,3+1+1+1 2+2,2+2+1+1,2+1+1+1+1 1+1+1+1+1+1,根据例子发现“包括第一行以后的数据不超过6，包括第二行的数据不超过5，第六行的数据不超过1”。因此，定义一个函数Q(n,m)，表示整数n的“任何被加数都不超过m”的分划的数目，n的所有分划的数目P(n)=Q(n,n)。,模型建立：,一般地Q(n.m)有以下递归关系：1)Q(n,n)=1+Q(n,n-1)（m=n）Q(n,n-1)表示n的所有其他分划，即最大被加数m=n-1的划分。2)Q(n,m)=Q(n,m-
12、1)+Q(n-m,m)(mn)Q(n,m-1)表示被加数中不包含m的分划的数目；Q(n-m,m)表示被加数中包含(注意不是小于)m的分划的数目，,递归的停止条件：1)Q(n,1)=1，表示当最大的被加数是1时，该整数n只有一种分划，即n个1相加；2)Q(1,m)=1，表示整数n=1只有一个分划，不管最大被加数的上限m是多大。,算法如下：,Divinteger(n,m)if（n n）Error(“输入参数错误”)；/*nm Q(n,m)是无意义的*/else if（n=1 or m=1）return（1）；else if（n m）return Divinteger(n,n)else if（n=m
13、）return(1+Divinteger(n,n-1)else return(Divinteger(n,m-1)+Divinteger(n-m,m);,算法与数据结构,数据的逻辑结构常分为四大类：（1）集合结构（2）线性结构（3）树形结构（4）图结构（网结构）,存储结构可以分为：连续存储和链式存储。连续存储又可以分为：静态存储和动态存储,1、常用的几种数据结构,顺序存储的优点：(1)方法简单，各种高级语言中都提供数组结构，容易实现。(2)不用为表示结点间的逻辑关系而增加额外的存储开销。(3)顺序表具有按元素序号随机访问的特点。,2、连续存储和链式存储比较,顺序存储的缺点：(1)在顺序表中做插入
14、删除操作时，平均移动大约表中一半的元素，因此对n较大的顺序表效率低。(2)需要预先分配足够大的存储空间，估计过大，可能会导致顺序表后部大量闲置；预先分配过小，又会造成溢出。,温馨提示：链表的优缺点恰好与顺序表相反。,3、在选取存储结构时权衡因素有：,）基于存储的考虑 顺序表的存储空间是静态分配的，在程序执行之前必须明确规定它的存储规模，也就是说事先对“MAXSIZE”要有合适的设定，过大造成浪费，过小造成溢出。可见对线性表的长度或存储规模难以估计时，不宜采用顺序表；链表不用事先估计存储规模，但链表的存储密度较低，,）基于运算的考虑 在顺序表中按序号访问ai的时间性能时O(1)，而链表中按序号访
15、问的时间性能O(n)，所以如果经常做的运算是按序号访问数据元素，显然顺序表优于链表；）基于环境的考虑 顺序表容易实现，任何高级语言中都有数组类型，链表的操作是基于指针的，操作简单。,【例3】一次考试共考了语文、代数和外语三科。某小组共有九人，考后各科及格名单如下表，请编写算法找出三科全及格的学生的名单（学号）。,返回3.2.1 例1 例2 例3 例4,方法一：,从语文及格名单中逐一抽出各及格学生学号，先在代数及格名单核对，若有该学号（说明代数也及格了），再在外语及格名单中继续查找，看该学号是否也在外语及格名单中。若仍在，说明该号属全及格学生的学号，否则就是至少有一科不及格的。若语文及格名单中就
16、没有某生的号，显然该生根本不在比较之列，自然不属全及格学生。,该方法采用了枚举尝试的方法A，B，C三组分别存放语文、代数、外语及格名单，尝试范围为三重循环：I循环，初值0，终值6，步长1 J循环，初值0，终值5，步长1 K循环，初值0，终值7，步长1 定解条件：AI=BJ=CK 共尝试7*6*8=336次。,返回3.2.1 例1 例2 例3 例4,方法一算法如下：,main()int a7,b6,c8,i,j,k,v,flag;for(i=0;i=6;i=i+1)input(ai);for(i=0;i=5;i=i+1)input(bi);for(i=0;i=7;i=i+1)input(ci);
17、for(i=0;i=6;i=i+1)v=ai;for(j=0;j=5;j=j+1)if(bj=v)for(k=0;k=7;k=k+1)if(ck=v)print(v);break;,返回3.2.1 例1 例2 例3 例4,方法二：,用数组A的九个下标分量作为各号考生及格科目的计数器。将三科及格名单共存一个数组，当扫描完毕总及格名单后，凡下标计数器的值为3的就是全及格的，其余则至少有一科不及格的。该方法同样也采用了枚举尝试的方法。,算法步骤为：1）用下标计数器累加各学号学生及格科数，2）尝试、输出部分。累加部分为一重循环，初值1，终值为三科及格的总人数，包括重复部分。计7+6+8=21，步长1。
18、尝试部分的尝试范围为一重循环，初值1，终值9，步长1。定解条件：A（i）=3,方法二算法如下：,main()int a10,i,xh;for(i=1;i=21;i=i+1)input(xh);axh=axh+1;for(xh=1;xh=9;xh=xh+1)if(axh=3)print(xh);,返回3.2.1 例1 例2 例3 例4,数组记录状态信息,问题提出：有的问题会限定在现有数据中，每个数据只能被使用一次，怎么样表示一个数据“使用过”还是没有“使用过”？一个朴素的想法是：用数组存储已使用过的数据，然后每处理一个新数据就与前面的数据逐一比较看是否重复。这样做，当数据量大时，判断工作的效率就
19、会越来越低。,返回3.2.3 例1 例2,例1,【例1】求X，使X2为一个各位数字互不相同的九位数。总体分析：只能用枚举法尝试完成此题。由X2为一个九位数，估算X应在1000032000之间。,算法设计：1）用一个10 个元素的状态数组p，记录数字09在X2中出现的情况。数组元素都赋初值为1，表示数字09没有被使用过。2）对尝试的每一个数x，求x*x,并取其各个位数字，数字作为数组的下标，若对应元素为1，则该数字第一次出现，将对应的元素赋为0，表示该数字已出现一次。否则，若对应元素为0，则说明有重复数字，结束这次尝试。3）容易理解当状态数组p中有9个元素为0时，就找到了问题的解。但这样判定有解
20、，需要扫描一遍数组p。为避免这个步骤，设置一个计数器k，在取x*x各个位数字的过程中记录不同的数字的个数，当k=9时就找到了问题的解。,main()long x,y1,y2;int p10,2,i,t,k,num=0;for(x=10000;x32000;x=x+1)for(i=0;i=9;i=i+1)pi=1;y1=x*x;y2=y1;k=0;for(i=1;i=9.i=i+1)t=y2 mod 10;y2=y2/10;if(pt=1)k=k+1;pt=0;else break;if(k=9)num=num+1;print(“No.”,num,“：n=”,x,“n2=”,y1);,大整数的存
21、储及运算,计算机存储数据是按类型分配空间的。在微型机上为整型提供2个字节16位的存储空间，则整型数据的范围为-3276832767；为长整型提供4个字节32位的存储空间，则长整型数据的范围为-21474836482147483647；为实型也是提供4个字节32位的存储空间，但不是精确存储数据，只有六位精度，数据的范围(3.4e-383.4e+38)；为双精度型数据提供8个字节64位的存储空间，数据的范围(1.7e-3081.7e+308)，其精确位数是17位。,返回3.2.4,在用数组存储高精度数据时，从计算的方便性考虑，决定将数据是由低到高还是由高到低存储到数组中；可以每位占一个数组元素空间
22、，也可几位占一个数组元素空间。若需从键盘输入要处理的高精度数据，一般用字符数型组存储，这样无需对高精度数据进行分段输入。当然这样存储后，需要有类型转换的操作，不同语言转换的操作差别虽然较大，但都是利用数字字符的ASCII码进行的。其它的技巧和注意事项通过下面的例子来说明。本节只针对大 整数的计算进行讨论，对高精度实数的计算可以仿照进行。,【例】编程求当N=100时，N！的准确值问题分析：问题要求对输入的正整数N，计算N！的准确值，而N！的增长速度仅次于指数增长的速度，所以这是一个高精度计算问题。例如：9！=362880100！=93 326215 443944 152681 699263 85
23、6266 700490 715968 264381 621468 592963895217 599993 229915 608914 463976 156578286253 697920 827223 758251 185210 916864000000 000000 000000 000000,返回3.2.4,算法设计：,1）乘法的结果是按由低位到高位存储在数组ab中，由于计算结果位数太多，若存储结果的数组，每个存储空间只存储一位数字，对每一位进行累乘次数太多。所以将数组定义为长整型，每个元素存储六位。2）对两个高精度数据的乘法运算，比较简单的方法就是两个高精度数据的按元素交叉相乘，用二重循
24、环来实现。其中一个循环变量i代表累乘的数据，b存储计算的中间结果，数组ab存储每次累乘的结果，每个元素存储六位数据，d存储超过六位数后的进位。,算法如下：,main()long ab256,b,d;/ab存储每次累乘的结果；b存储中间结果 int m,n,i,j,r;/I代表每次累乘的数据input(n);m=log(n)*n/6+2;/粗略估计结果的位数ab1=1;for(i=2;i=1;i-)if(abi=0)continue;else r=i;break;,返回3.2.4,print(n,“!=”);print(abr);for(i=r-1;i=1;i-)if(abi99999)prin
25、t(abi);continue;if(abi9999)print(“0”,abi);continue;if(abi 999)print(“00”,abi);continue;if(abi99)print(“000”,abi);continue;if(abi9)print(“0000”,abi);continue;print(“00000”,abi);/for,返回3.2.4,算法说明：,1）算法中“m=log(n)*n/6+2;”是对N！位数的粗略估计。2）输出时，首先计算结果的准确位数r，然后输出最高位数据，在输出其它存储单元的数据时要特别注意，如若计算结果是123000001，ab2中存储
26、的是123，而ab1中存储的不是000001，而是1。所以在输出时，通过多个条件语句保证输出的正确性。,返回3.2.4,枚举法,枚举（enumerate）法（穷举法）是蛮力策略的一种表现形式，也是一种使用非常普遍的思维方法。它是根据问题中的条件将可能的情况一一列举出来，逐一尝试从中找出满足问题条件的解。但有时一一列举出的情况数目很大，如果超过了我们所能忍受的范围，则需要进一步考虑，排除一些明显不合理的情况，尽可能减少问题可能解的列举数目。用枚举法解决问题，通常可以从两个方面进行算法设计：1）找出枚举范围：分析问题所涉及的各种情况。2）找出约束条件：分析问题的解需要满足的条件，并用逻辑表达式表示
27、。,【例1】百钱百鸡问题。中国古代数学家张丘建在他的算经中提出了著名的“百钱百鸡问题”：鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一；百钱买百鸡，翁、母、雏各几何?算法设计1：通过对问题的理解，读者可能会想到列出两个三元一次方程，去解这个不定解方程，就能找出问题的解。这确实是一种办法，但这里我们要用“懒惰”的枚举策略进行算法设计：设x，y，z分别为公鸡、母鸡、小鸡的数量。尝试范围：由题意给定共100钱要买百鸡，若全买公鸡最多买100/5=20只，显然x的取值范围120之间；同理，y的取值范围在133之间，z的取值范围在1100之间。约束条件：x+y+z=100 且 5*x+3*y+z/3=1
28、00,算法1如下：main()int x,y,z;for(x=1;x=20;x=x+1)for(y=1;y=34;y=y+1)for(z=1;z=100;z=z+1)if(100=x+y+z and 100=5*x+3*y+z/3)print(the cock number is,x)；print(the hen number is,y)；print(the chick number is z);,算法分析：以上算法需要枚举尝试20*34*100=68000次。算法的效率显然太低算法设计2：在公鸡（x）、母鸡（y）的数量确定后，小鸡的数量z就固定为100-x-y，无需再进行枚举了此时约束条件只
29、有一个：5*x+3*y+z/3=100算法2如下：,main()int x,y,z;for(x=1;x=20;x=x+1)for(y=1;y=33;y=y+1)z=100-x-y;if(z mod 3=0 and 5*x+3*y+z/3=100)print(the cock number is,x)；print(the hen number is,y)；print(the chick number is z);算法分析：以上算法只需要枚举尝试20*33=660次。实现时约束条件又限定Z能被3整除时，才会判断“5*x+3*y+z/3=100”。这样省去了z不整除3时的算术计算和条件判断，进一步提
30、高了算法的效率。,【例3】狱吏问题 某国王对囚犯进行大赦，让一狱吏n次通过一排锁着的n间牢房，每通过一次，按所定规则转动n间牢房中的某些门锁,每转动一次,原来锁着的被打开,原来打开的被锁上；通过n次后，门锁开着的，牢房中的犯人放出，否则犯人不得获释。转动门锁的规则是这样的，第一次通过牢房，要转动每一把门锁，即把全部锁打开；第二次通过牢房时，从第二间开始转动，每隔一间转动一次；第k次通过牢房，从第k间开始转动，每隔k-1 间转动一次；问通过n次后，那些牢房的锁仍然是打开的？,算法设计1：1）用n个空间的一维数组an,每个元素记录一个锁的状 态，1为被锁上，0为被打开。2）用数学运算方便模拟开关锁
31、的技巧，对i号锁的一次开 关锁可以转化为算术运算：ai=1-ai。3）第一次转动的是1，2，3，n号牢房；第二次转动的是2，4，6，号牢房；第三次转动的是3，6，9，号牢房；第i次转动的是i，2i，3i，4i，号牢房，是起点为i，公差为i的等差数列。4）不做其它的优化，用蛮力法通过循环模拟狱吏的开关 锁过程，最后当第i号牢房对应的数组元素ai为0时，该牢房的囚犯得到大赦。算法1如下：,main1()int*a,i,j,n;input(n);a=calloc(n+1,sizeof(int);for(i=1;i=n;i+)ai=1;for(i=1;i=n;i+)for(j=i;j=n;j=j+i)
32、ai=1-ai;for(i=1;i=n;i+)if(ai=0)print(i,”is free.”);算法分析：以一次开关锁计算，算法的时间复杂度为n(1+1/2+1/3+1/n)=O(nlogn)。,问题分析：转动门锁的规则可以有另一种理解，第一次转动的是编号为1的倍数的牢房；第二次转动的是编号为2的倍数的牢房；第三次转动的是编号为3的倍数的牢房；则狱吏问题是一个关于因子个数的问题。令d(n)为自然数n的因子个数，这里不计重复的因子，如4的因子为1，2，4共三个因子，而非1，2，2，4。则d(n)有的为奇数，有的为偶数，见下表:表4-3 编号与因数个数的关系 n 1 2 3 4 5 6 7
33、8 9 10 11 12 13 14 15 16 d(n)1 2 2 3 2 4 2 4 3 4 2 6 2 4 4 5 数学模型1：上表中的d(n)有的为奇数，有的为偶数，由于牢房的门开始是关着的，这样编号为i的牢房，所含1i之间的不重复因子个数为奇数时，牢房最后是打开的，反之，牢房最后是关闭的。,算法设计2:1）算法应该是求出每个牢房编号的不重复的因子个数，当它为奇数时，这里边的囚犯得到大赦。2）一个数的因子是没有规律的，只能从1n枚举尝试。算法2如下：main2()int s,i,j,n;input(n);for(i=1;i=n;i+)s=1;for(j=2;j=i;j=j+)if（i
34、mod j=0）s=s+1;if（s mod 2=1）print(i,”is free.”);,算法分析：狱吏开关锁的主要操作是ai=1-ai;共执行了n*(1+1/2+1/3+1/n)次，时间近似为复杂度为O（n log n）。使用了n个空间的一维数组。算法2没有使用辅助空间，但由于求一个编号的因子个数也很复杂，其主要操作是判断i mod j是否为0，共执行了n*(1+2+3+n)次，时间复杂度为O（n2）。数学模型2：仔细观察表4-3，发现当且仅当n为完全平方数时,d(n)为奇数；这是因为n的因子是成对出现的,也即当n=a*b且ab时，必有两个因子a，b;只有n为完全平方数，也即当n=a2时,才会出现d(n)为奇数的情形。算法设计3：这时只需要找出小于n的平方数即可。算法3如下：,main3()int s,i,j,n;input(n);for(i=1;i=n;i+)if（i*i=n）print(i,”is free.”);else break;由此算法我们应当注意：在对运行效率要求较高的大规模的数据处理问题时，必须多动脑筋找出效率较高的数学模型及其对应的算法。,
