ACM培训课程算法设计课件

ACM培训课程算法设计主讲教师：校景中ACM培训课程算法设计主讲教师：校景中1如何用计算机求解问题？1.1.问题分析问题分析 准确、完整地理解和描述问题是解决问题的准确、完整地理解和描述问题是解决问题的第一步。要做到这一点，必须注意以下一些问第一步。要做到这一点，必须注意以下一些问题：在未经加工的原始表达中，所用的术语是题：在未经加工的原始表达中，所用的术语是否都明白其准确定义？题目提供了哪些信息？否都明白其准确定义？题目提供了哪些信息？这些信息有什么用？题目要求得到什么结果？这些信息有什么用？题目要求得到什么结果？题目中作了哪些假定？是否有潜在的信息？判题目中作了哪些假定？是否有潜在的信息？判定求解结果所需要的中间结果有哪些？定求解结果所需要的中间结果有哪些？如何用计算机求解问题？1.问题分析2如何用计算机求解问题？2 2、数学模型建立、数学模型建立 用计算机解决实际问题必须有合适的数学模型，因用计算机解决实际问题必须有合适的数学模型，因为在现实问题面前，计算机是无能为力。对一个实际为在现实问题面前，计算机是无能为力。对一个实际问题建立数学模型，可以考虑这样两个基本问题：最问题建立数学模型，可以考虑这样两个基本问题：最适合于此问题的数学模型是什么？是否有已经解决了适合于此问题的数学模型是什么？是否有已经解决了的类似问题可借鉴？的类似问题可借鉴？如何用计算机求解问题？2、数学模型建立3如何用计算机求解问题？3 3、算法设计与选择、算法设计与选择 算法设计是指设计求解某一特定类型问题的算法设计是指设计求解某一特定类型问题的一系列步骤，并且这些步骤是可以通过计算机一系列步骤，并且这些步骤是可以通过计算机的基本操作来实现的。算法设计要同时结合数的基本操作来实现的。算法设计要同时结合数据结构的设计，简单说数据结构的设计就是选据结构的设计，简单说数据结构的设计就是选取存储方式。算法的设计与模型的选择更是密取存储方式。算法的设计与模型的选择更是密切相关的，但同一模型仍然可以有不同的算法，切相关的，但同一模型仍然可以有不同的算法，而且它们的有效性可能有相当大的差距。而且它们的有效性可能有相当大的差距。如何用计算机求解问题？3、算法设计与选择4如何用计算机求解问题？在这些步骤中，算法设计是解决问题在这些步骤中，算法设计是解决问题的核心的核心如何用计算机求解问题？在这些步骤中，算法设计是解决问题的核心5算法又是如何定义的呢？算法由操作、控制结构、数据结构三要素算法由操作、控制结构、数据结构三要素组成。组成。算法又是如何定义的呢？算法由操作、控制结构、数据结构三要素组6算法又是如何定义的呢？1 1）操作）操作 算术运算：加、减、乘、除算术运算：加、减、乘、除 关系比较：大于、小于、等于、不等于关系比较：大于、小于、等于、不等于 逻辑运算：与、或、非逻辑运算：与、或、非 数据传送：输入、输出数据传送：输入、输出,赋值赋值算法又是如何定义的呢？1）操作7算法又是如何定义的呢？2 2）控制结构）控制结构 各操作之间的执行次序。各操作之间的执行次序。顺序结构：各操作依次执行顺序结构：各操作依次执行 选择结构：由条件是否成立来选择选择结构：由条件是否成立来选择 执行执行 循环结构：有些操作要重复执行，直到循环结构：有些操作要重复执行，直到 功能满足某个条件时结束。又称重复或功能满足某个条件时结束。又称重复或 迭代结构。迭代结构。算法又是如何定义的呢？2）控制结构各操作之间的执行次8算法又是如何定义的呢？3 3）数据结构）数据结构 算法操作的对象是数据，数据间的逻算法操作的对象是数据，数据间的逻辑关系、数据的存储方式及处理方式就辑关系、数据的存储方式及处理方式就是数据的数据结构。它与算法设计是紧是数据的数据结构。它与算法设计是紧密相关的。密相关的。算法又是如何定义的呢？3）数据结构9如何设计循环？循环设计要点循环设计要点循环设计要点循环设计要点1 1设计中要注意算法的效率中要注意算法的效率 2 2“自自顶向下向下”的的设计方法方法 如何设计循环？循环设计要点10 循环体的特点是：循环体的特点是：“以不变应万变以不变应万变”。所谓所谓“不变不变”是指循环体内运算的表现是指循环体内运算的表现形式是不变的，而每次具体的执行内容却是形式是不变的，而每次具体的执行内容却是不尽相同的。在循环体内用不变的运算表现不尽相同的。在循环体内用不变的运算表现形式去描述各种相似的重复运算。形式去描述各种相似的重复运算。1 1循环循环设计中中如何如何注意算法的效率注意算法的效率循环体的特点是：“以不变应万变”。1循环设11【例【例1 1】求】求1/1!-1/3!+1/5!-1/7!+1/1!-1/3!+1/5!-1/7!+（-1 1）n+1/(2n-1)!n+1/(2n-1)!分析：此问题中既有累加又有累乘，准确地说累加分析：此问题中既有累加又有累乘，准确地说累加的对象是累乘的结果。的对象是累乘的结果。数学模型数学模型1 1：Sn=Sn-1+Sn=Sn-1+（-1-1）n+1n+1/(2n-1)!/(2n-1)!算法设计算法设计1 1：多数初学者会直接利用题目中累加项：多数初学者会直接利用题目中累加项通式，构造出循环体不变式为：通式，构造出循环体不变式为：S=S+S=S+（-1-1）n+1n+1/(2n-1)!/(2n-1)!需要用二重循环来完成算法，算法需要用二重循环来完成算法，算法1 1如下：如下：【例1】求1/1!-1/3!+1/5!-1/7!+（-112算法如下：算法如下：main()inti,n,j,sign=1;floats,t=1;/s存储最终的结果，存储最终的结果，t存储存储(2k-1)的阶乘的阶乘input(n);/输入输入ns=1；for(i=2;i=n;i=i+1)t=1;求阶乘求阶乘for(j=1;j=2*i-1;j=j+1)t=t*j;sign=1;求（求（-1）n+1for(j=1;j=i+1;j=j+1)sign=sign*(-1);s=s+sign/t;print(“Snm=”,s);算法如下：main()13算法分析算法分析：以上算法是二重循环来完成以上算法是二重循环来完成 ，但算，但算法的效率却太低是法的效率却太低是O（n2）。）。其其原原因因是是，当当前前一一次次循循环环已已求求出出7 7！，当当这这次次要要想想求求9 9！时时，没没必必要要再再从从1 1去去累累乘乘到到9 9，只只需需要要充充分分利利用用前前一一次次的的结结果果，用用7 7！*8*9*8*9即即可可得得到到9 9！，模模型型为为A An n=A=An-1n-1*1/(2*n-2)*(2*n-1)*1/(2*n-2)*(2*n-1)。另另外外运运算算sign sign=sign sign*(-1);(-1);总总共共也也要要进进行行n*(n-1)/2n*(n-1)/2次次乘乘法法，这这也也是是没没有有必必要的。下面我们就进行改进。要的。下面我们就进行改进。算法分析：14数学模型数学模型2：Sn=Sn-1+（-1）n+1An；An=An-1*1/(2*n-2)*(2*n-1)main()inti,n,sign;floats,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：Sn=Sn-1+（-1）n+1An；15算法说明算法说明2 2：构造循构造循环不不变式式时，一定要注意循，一定要注意循环变量的意量的意义，如当，如当i i不是不是项数序号数序号时（右（右边的循的循环中）有关中）有关t t的的累乘累乘式与式与i i是是项数序号数序号时就不能相同。就不能相同。算法分析：按照数学模型算法分析：按照数学模型2 2，只需一重循环就能解决问题，只需一重循环就能解决问题算法的算法的时间复复杂性性为O O（n n）。算法说明2：构造循环不变式时，一定要注意循环变量的意义，如162 2“自自顶向下向下”的的设计方法方法 自自顶向下的方法是从全局走向局部、从向下的方法是从全局走向局部、从概略概略走向走向详尽的尽的设计设计方法。自上而下是系方法。自上而下是系统分解和分解和细化的化的过程。程。【例【例2 2】编算法找出】编算法找出10001000以内所有完数以内所有完数例例如如，2828的的因因子子为为1 1、2 2、4 4、7 7，1414，而而28=1+2+4+7+1428=1+2+4+7+14。因因此此2828是是“完完数数”。编编算算法法找找出出10001000之之内内的的所所有有完完数数，并并按按下下面面格格式式输输出出其其因因子子：28 28 its its factors are 1factors are 1，2 2，4 4，7 7，1414。2“自顶向下”的设计方法自顶向下的方法是从全局171 1）这这里里不不是是要要质质因因数数，所所以以找找到到因因数数后后也也无无需需将将其其从从数据中数据中“除掉除掉”。2 2）每每个个因因数数只只记记一一次次，如如8 8的的因因数数为为1 1，2 2，4 4而而不不是是1 1，2 2，2 2，2 2，4 4。（注注：本本题题限限定定因因数数不不包包括括这这个个数数本本身）身）1）这里不是要质因数，所以找到因数后也无需将其从数据中“除掉181）顶层算法 for(i=2;i=n;i+)判断i是否是“完数”；是完数则按格式输出；2）判断是否是”完数”的算法for(j=2;ji;j+)找i的因子，并累加；如果累加值等于i,i是完数1）顶层算法193）进一步细化判断i是否“完数”算法s=1for(j=2;ji;j=j+1)if(i mod j=0)(j是i的因素)s=s+j;if （s=i）i是“完数”;3）进一步细化判断i是否“完数”算法s=1204 4）考虑输出格式）考虑输出格式判断判断i i是否是否“完数完数”算法算法 考考虑虑到到要要按按格格式式输输出出结结果果，应应该该开开辟辟数数组组存存储储数数据据i i的所有因子，并记录其因子的个数，因此算法细化如下：的所有因子，并记录其因子的个数，因此算法细化如下：定义数组定义数组a，s=1;k=0;for(j=2;ji;j=j+1)j=2;ji;j=j+1)if(i mod j=0)(j if(i mod j=0)(j是是i i的因素的因素)s=s+j;ak=j;k=k+1;s=s+j;ak=j;k=k+1;if if （s=is=i）按格式输出结果按格式输出结果 4）考虑输出格式判断i是否“完数”算法定义数组a，s=121算法如下：算法如下：main()inti,k,j,s,a20;for(i=1;i=1000;i+)s=1;/*两个赋初值语句两个赋初值语句s=1,k=0k=0;一定要位于外部循环的内部一定要位于外部循环的内部*/for(j=2;ji;j+)if(imodj)=0)s=s+j;ak=j;k+;if(i=s)print(s,“itsfactorsare:”,1);for(j=0;ik;j+)print(“,”,ak);算法如下：main()22如何进行如何进行递归设计递归设计递归算法是一个模块（函数、过程）除了可调用其递归算法是一个模块（函数、过程）除了可调用其它模它模 块（函数、过程）外，还可以直接或间接地调块（函数、过程）外，还可以直接或间接地调用自身的算法用自身的算法。递归是一种比迭代循环更强、更好用的循环结构递归是一种比迭代循环更强、更好用的循环结构。只需要找出递归关系和最小问题的解。只需要找出递归关系和最小问题的解。如何进行递归设计递归算法是一个模块（函数、过程）除了可调用23递归的关键在于找出递归方程式和递归终止条件。递归的关键在于找出递归方程式和递归终止条件。递归定义：使问题向边界条件转化的规则。递归定义递归定义：使问题向边界条件转化的规则。递归定义必须能使问题越来越简单。必须能使问题越来越简单。递归边界条件：也就是所描述问题的最简单情况，它递归边界条件：也就是所描述问题的最简单情况，它本身不再使用递归的定义。本身不再使用递归的定义。递归的关键在于找出递归方程式和递归终止条件。递归定义：使问题24递归算法解题通常有三个步骤：递归算法解题通常有三个步骤：1 1）分析问题、寻找递归：找出大规模问题与小规模问题）分析问题、寻找递归：找出大规模问题与小规模问题的关系，这样通过递归使问题的规模逐渐变小。的关系，这样通过递归使问题的规模逐渐变小。2 2）设置边界、控制递归：找出停止条件，即算法可解的）设置边界、控制递归：找出停止条件，即算法可解的最小规模问题。最小规模问题。3 3）设计函数、确定参数：和其它算法模块一样设计函数）设计函数、确定参数：和其它算法模块一样设计函数体中的操作及相关参数。体中的操作及相关参数。递归算法解题通常有三个步骤：25【例【例2 2】整数的分划问题】整数的分划问题 对于一个正整数对于一个正整数n n的分划就是把的分划就是把n n写成一系列正整数之和的表达写成一系列正整数之和的表达式。例如，对于正整数式。例如，对于正整数n=6n=6，它可以分划为：，它可以分划为：6 6 5+1 5+1 4+2,4+1+1 4+2,4+1+1 3+3,3+2+1,3+1+1+1 3+3,3+2+1,3+1+1+1 2+2,2+2+1+1,2+1+1+1+1 2+2,2+2+1+1,2+1+1+1+1 1+1+1+1+1+11+1+1+1+1+1 根据例子发现根据例子发现“包括第一行以后的数据不超过包括第一行以后的数据不超过6 6，包括，包括第二行的数据不超过第二行的数据不超过5 5，第六行的数据不超过，第六行的数据不超过1”1”。因此，定义一个函数因此，定义一个函数Q(n,m)Q(n,m)，表示整数，表示整数n n的的“任何被加任何被加数都不超过数都不超过m”m”的分划的数目，的分划的数目，n n的所有分划的数目的所有分划的数目P(n)=Q(n,n)P(n)=Q(n,n)。【例2】整数的分划问题对于一个正整数n的分划就是把n写成一26模型建立：模型建立：一般地一般地Q(n.m)Q(n.m)有以下递归关系：有以下递归关系：1)Q(n,n)=1+Q(n,n-1)1)Q(n,n)=1+Q(n,n-1)（m=nm=n）Q(n,n-1)Q(n,n-1)表示表示n n的所有其他分划，即最大被加数的所有其他分划，即最大被加数m=n-1m=n-1的划分。的划分。2)Q(n,m)=Q(n,m-1)+Q(n-m,m)(mn)2)Q(n,m)=Q(n,m-1)+Q(n-m,m)(mn)Q(n,m-1)Q(n,m-1)表示被加数中不包含表示被加数中不包含m m的分划的数目；的分划的数目；Q(n-m,m)Q(n-m,m)表示被加数中包含表示被加数中包含(注意不是小于注意不是小于)m)m的分划的数目，的分划的数目，递归的停止条件：递归的停止条件：1)Q(n,1)=11)Q(n,1)=1，表示当最大的被加数是，表示当最大的被加数是1 1时，该整数时，该整数n n只有一只有一种分划，即种分划，即n n个个1 1相加；相加；2)Q(1,m)=12)Q(1,m)=1，表示整数，表示整数n=1n=1只有一个分划，不管最大被加只有一个分划，不管最大被加数的上限数的上限m m是多大。是多大。模型建立：一般地Q(n.m)有以下递归关系：递归的停止条27算法如下：算法如下：Divinteger(n,m)if（n1ormn）Error(“输入参数错误输入参数错误”)；/*nmQ(n,m)是无意义的是无意义的*/elseif（n=1orm=1）return（1）；）；elseif（nm）returnDivinteger(n,n)elseif（n=m）return(1+Divinteger(n,n-1)elsereturn(Divinteger(n,m-1)+Divinteger(n-m,m);算法如下：Divinteger(n,m)if28 算法与数据结构算法与数据结构算法与数据结构29数据的逻辑结构常分为四大类：数据的逻辑结构常分为四大类：（1 1）集合结构）集合结构 （2 2）线性结构）线性结构 （3 3）树形结构）树形结构（4 4）图结构（网结构）图结构（网结构）存储结构可以分为：连续存储和链式存储。存储结构可以分为：连续存储和链式存储。连续存储又可以分为：静态存储和动态存储连续存储又可以分为：静态存储和动态存储 1 1、常用的几种数据结构、常用的几种数据结构数据的逻辑结构常分为四大类：存储结构可以分为：连续存储和链式30顺序存储的优点：顺序存储的优点：(1)方法简单，各种高级语言中都提供数组结构，方法简单，各种高级语言中都提供数组结构，容易实现。容易实现。(2)不用为表示结点间的逻辑关系而增加额外的不用为表示结点间的逻辑关系而增加额外的存储开销。存储开销。(3)顺序表具有按元素序号随机访问的特点。顺序表具有按元素序号随机访问的特点。2 2、连续存储和链式存储比较、连续存储和链式存储比较顺序存储的优点：2、连续存储和链式存储比较31顺序存储的缺点：顺序存储的缺点：(1)在顺序表中做插入删除操作时，平均移动在顺序表中做插入删除操作时，平均移动大约表中一半的元素，因此对大约表中一半的元素，因此对n较大的顺序表效较大的顺序表效率低。率低。(2)需要预先分配足够大的存储空间，估计过需要预先分配足够大的存储空间，估计过大，可能会导致顺序表后部大量闲置；预先分配大，可能会导致顺序表后部大量闲置；预先分配过小，又会造成溢出。过小，又会造成溢出。温馨提示：温馨提示：链表的优缺点恰好与顺序表相反。链表的优缺点恰好与顺序表相反。顺序存储的缺点：温馨提示：323 3、在选取存储结构时权衡因素有：、在选取存储结构时权衡因素有：）基于存储的考虑）基于存储的考虑 顺序表的存储空间是静态分配的，在程顺序表的存储空间是静态分配的，在程序执行之前必须明确规定它的存储规模，也就序执行之前必须明确规定它的存储规模，也就是说事先对是说事先对“MAXSIZE”“MAXSIZE”要有合适的设定，过要有合适的设定，过大造成浪费，过小造成溢出。可见对线性表的大造成浪费，过小造成溢出。可见对线性表的长度或存储规模难以估计时，不宜采用顺序表；长度或存储规模难以估计时，不宜采用顺序表；链表不用事先估计存储规模，但链表的存储密链表不用事先估计存储规模，但链表的存储密度较低，度较低，3、在选取存储结构时权衡因素有：）基于存储的考虑33）基于运算的考虑）基于运算的考虑 在顺序表中按序号访问在顺序表中按序号访问a ai i的时间性能时的时间性能时O(1)O(1)，而链表中按序号访问的时间性能，而链表中按序号访问的时间性能O(n)O(n)，所以如果，所以如果经常做的运算是按序号访问数据元素，显然顺序表经常做的运算是按序号访问数据元素，显然顺序表优于链表；优于链表；）基于环境的考虑）基于环境的考虑 顺序表容易实现，任何高级语言中都有数顺序表容易实现，任何高级语言中都有数组类型，链表的操作是基于指针的，操作简单。组类型，链表的操作是基于指针的，操作简单。）基于运算的考虑34科目及格学生学号语文1，9，6，8，4，3，7代数5，2，9，1，3，7外语8，1，6，7，3，5，4，9【例3】一次考试共考了语文、代数和外语三科。某小组共有九人，考后各科及格名单如下表，请编写算法找出三科全及格的学生的名单（学号）。返回3.2.1 例1 例2 例3 例4科目及格学生学号语文1，9，6，8，4，3，7代数5，2，935 数组记录状态信息数组记录状态信息问题提出：问题提出：有有的的问问题题会会限限定定在在现现有有数数据据中中，每每个个数数据据只只能能被被使使用用一一次次，怎怎么么样样表表示示一一个个数数据据“使使用用过过”还是没有还是没有“使用过使用过”？一一个个朴朴素素的的想想法法是是：用用数数组组存存储储已已使使用用过过的的数数据据，然然后后每每处处理理一一个个新新数数据据就就与与前前面面的的数数据据逐逐一一比比较较看看是是否否重重复复。这这样样做做，当当数数据据量量大大时，判断工作的效率就会越来越低。时，判断工作的效率就会越来越低。返回3.2.3 例1 例2数组记录状态信息问题提出：返回3.2.340例例1【例【例1 1】求】求X X，使，使X X2 2为一个各位数字互不相同的九位为一个各位数字互不相同的九位数。数。总总体体分分析析：只只能能用用枚枚举举法法尝尝试试完完成成此此题题。由由X X2 2为为一一个九位数，估算个九位数，估算X X应在应在10000320001000032000之间。之间。例141 大整数的存储及运算大整数的存储及运算 计算机存储数据是按类型分配空间的。在微型机上为计算机存储数据是按类型分配空间的。在微型机上为整型提供整型提供2 2个字节个字节1616位的存储空间，则整型数据的范围为位的存储空间，则整型数据的范围为-32768327673276832767；为长整型提供；为长整型提供4 4个字节个字节3232位的存储空间，位的存储空间，则长整型数据的范围为则长整型数据的范围为-21474836482147483647-21474836482147483647；为；为实型也是提供实型也是提供4 4个字节个字节3232位的存储空间，但不是精确存储位的存储空间，但不是精确存储数据，只有六位精度，数据的范围数据，只有六位精度，数据的范围(3.4e-383.4e+38)；为双精度型数据提供；为双精度型数据提供8 8个字节个字节6464位的存储空间，数据的位的存储空间，数据的范围范围(1.7e-3081.7e+308)，其精确位数是，其精确位数是1717位。位。返回3.2.4大整数的存储及运算计算机存储数据是按类型分配44 在用数组存储高精度数据时，从计算的方便性考虑，在用数组存储高精度数据时，从计算的方便性考虑，决定将数据是由低到高还是由高到低存储到数组中；可以决定将数据是由低到高还是由高到低存储到数组中；可以每位占一个数组元素空间，也可几位占一个数组元素空间。每位占一个数组元素空间，也可几位占一个数组元素空间。若需从键盘输入要处理的高精度数据，一般用字符数若需从键盘输入要处理的高精度数据，一般用字符数型组存储，这样无需对高精度数据进行分段输入。当然这型组存储，这样无需对高精度数据进行分段输入。当然这样存储后，需要有类型转换的操作，不同语言转换的操作样存储后，需要有类型转换的操作，不同语言转换的操作差别虽然较大，但都是利用数字字符的差别虽然较大，但都是利用数字字符的ASCIIASCII码进行的。码进行的。其它的技巧和注意事项通过下面的例子来说明。本节只针其它的技巧和注意事项通过下面的例子来说明。本节只针对大对大 整数的计算进行讨论，对高精度实数的计算可以仿整数的计算进行讨论，对高精度实数的计算可以仿照进行。照进行。在用数组存储高精度数据时，从计算的方便性考虑，决定将45【例】编程求当【例】编程求当N=100N=100时，时，N N！的准确值！的准确值问问题题分分析析：问问题题要要求求对对输输入入的的正正整整数数N N，计计算算N N！的的准准确确值值，而而N N！的的增增长长速速度度仅仅次次于于指指数数增增长长的的速速度度，所所以以这是一个高精度计算问题。这是一个高精度计算问题。例如：例如：9 9！=362880=362880100100！=93 326215 443944 152681 699263 =93 326215 443944 152681 699263 856266 700490 715968 264381 621468 592963856266 700490 715968 264381 621468 592963895217 599993 229915 608914 463976 156578895217 599993 229915 608914 463976 156578286253 697920 827223 758251 185210 916864286253 697920 827223 758251 185210 916864000000 000000 000000 000000 000000 000000 000000 000000 返回3.2.4【例】编程求当N=100时，N！的准确值返回3.2.446枚举法枚举法枚枚举举（enumerate）法法（穷穷举举法法）是是蛮蛮力力策策略略的的一一种种表表现现形形式式，也也是是一一种种使使用用非非常常普普遍遍的的思思维维方方法法。它它是是根根据据问问题题中中的的条条件件将将可可能能的的情情况况一一一一列列举举出出来来，逐逐一一尝尝试试从从中中找找出出满满足足问问题题条条件件的的解解。但但有有时时一一一一列列举举出出的的情情况况数数目目很很大大，如如果果超超过过了了我我们们所所能能忍忍受受的的范范围围，则则需需要要进进一一步步考考虑虑，排排除除一一些些明明显显不不合合理理的的情情况况，尽尽可可能能减减少少问问题题可能解的列举数目。可能解的列举数目。用枚举法解决问题，通常可以从两个方面进行算法设计：用枚举法解决问题，通常可以从两个方面进行算法设计：1）找出枚举范围：分析问题所涉及的各种情况。找出枚举范围：分析问题所涉及的各种情况。2 2）找找出出约约束束条条件件：分分析析问问题题的的解解需需要要满满足足的的条条件件，并并用用逻逻辑辑表达式表示。表达式表示。枚举法枚举（enumerate）法（穷举法）是蛮力策略的51【例【例1 1】百百钱百百鸡问题。中国古代数学家。中国古代数学家张丘建在他的算丘建在他的算经中提出了著名的中提出了著名的“百百钱百百鸡问题”：鸡翁一，翁一，值钱五；五；鸡母一，母一，值钱三；三；鸡雏三，三，值钱一；百一；百钱买百百鸡，翁、母、，翁、母、雏各几何各几何?算法设计算法设计1：通过对问题的理解，读者可能会想到列出两个三元一次方程，通过对问题的理解，读者可能会想到列出两个三元一次方程，去解这个不定解方程，就能找出问题的解。这确实是一种办法，去解这个不定解方程，就能找出问题的解。这确实是一种办法，但这里我们要用但这里我们要用“懒惰懒惰”的枚举策略进行算法设计：的枚举策略进行算法设计：设设x，y，z分别为公鸡、母鸡、小鸡的数量。分别为公鸡、母鸡、小鸡的数量。尝尝试试范范围围：由由题题意意给给定定共共100钱钱要要买买百百鸡鸡，若若全全买买公公鸡鸡最最多多买买100/5=100/5=20只只，显显然然x的的取取值值范范围围120之之间间；同同理理，y的的取取值值范范围在围在133之间，之间，z z的取值范围的取值范围在在11001100之间之间。约束条件：约束条件：x+y+z=100 x+y+z=100 且且 5*x+3*y+z/3=100 5*x+3*y+z/3=100 【例1】百钱百鸡问题。中国古代数学家张丘建在他的算经中提52算法算法1如下：如下：main()main()int x,y,z;int x,y,z;for(x=1;x=20;x=x+1)for(x=1;x=20;x=x+1)for(y=1;y=34;y=y+1)for(y=1;y=34;y=y+1)for(z=1;z=100;z=z+1)for(z=1;z=100;z=z+1)if(100=x+y+z and 100=5*x+3*y+z/3)if(100=x+y+z and 100=5*x+3*y+z/3)print(the cock number is,x)print(the cock number is,x)；print(the hen number is,y)print(the hen number is,y)；print(the chick number is z);print(the chick number is z);算法1如下：53算算法法分分析析：以以上上算算法法需需要要枚枚举举尝尝试试20*34*100=68000次次。算法的效率显然太低算法的效率显然太低算法设计算法设计2：在在公公鸡鸡（x x）、母母鸡鸡（y y）的的数数量量确确定定后后，小小鸡鸡的的数数量量z就就固固定为定为100-x-y，无需再进行枚举了，无需再进行枚举了此时此时约约束条件只有一个：束条件只有一个：5*x+3*y+z/3=100算法算法2如下：如下：算法分析：以上算法需要枚举尝试20*34*100=6800054main()main()int x,y,z;int x,y,z;for(x=1;x=20;x=x+1)for(x=1;x=20;x=x+1)for(y=1;y=33;y=y+1)for(y=1;y=33;y=y+1)z=100-x-y;z=100-x-y;if(z mod 3=0 and if(z mod 3=0 and 5*x+3*y+z/3=100)5*x+3*y+z/3=100)print(the cock number is,x)print(the cock number is,x)；print(the hen number is,y)print(the hen number is,y)；print(the chick number is z);print(the chick number is z);算法分析：以上算法只需要枚举尝试算法分析：以上算法只需要枚举尝试20*33=660次。实现时约次。实现时约束条件又限定束条件又限定Z能被能被3整除时，才会判断整除时，才会判断“5*x+3*y+z/3=100”5*x+3*y+z/3=100”。这样省去了省去了z z不整除不整除3 3时的算的算术计算和条件算和条件判断，判断，进一步提高了算一步提高了算法的效率。法的效率。main()intx,y,z;fo55【例【例3 3】狱吏问题狱吏问题 某国王对囚犯进行大赦，让一狱吏某国王对囚犯进行大赦，让一狱吏n n次通过一排锁着的次通过一排锁着的n n间牢房，每通过一次，按所定规则转动间牢房，每通过一次，按所定规则转动n n间牢房中的某些门间牢房中的某些门锁锁,每转动一次每转动一次,原来锁着的被打开原来锁着的被打开,原来打开的被锁上；原来打开的被锁上；通过通过n n次后，门锁开着的，牢房中的犯人放出，否则犯人不次后，门锁开着的，牢房中的犯人放出，否则犯人不得获释。得获释。转动门锁的规则是这样的，第一次通过牢房，要转动每转动门锁的规则是这样的，第一次通过牢房，要转动每一把门锁，即把全部锁打开；第二次通过牢房时，从第二间一把门锁，即把全部锁打开；第二次通过牢房时，从第二间开始转动，每隔一间转动一次；第开始转动，每隔一间转动一次；第k k次通过牢房，从第次通过牢房，从第k k间开间开始转动，每隔始转动，每隔k-1 k-1 间转动一次；问通过间转动一次；问通过n n次后，那些牢房的次后，那些牢房的锁仍然是打开的？锁仍然是打开的？【例3】狱吏问题56算法设计算法设计1 1：1 1）用用n n个空间的一维数组个空间的一维数组an,an,每个元素每个元素记录一个锁的状记录一个锁的状态，态，1 1为为被锁上，被锁上，0 0为被打开。为被打开。2 2）用数学运算方便模拟开关锁的技巧，对）用数学运算方便模拟开关锁的技巧，对i i号锁的一次开号锁的一次开 关锁可以转化为算术运算：关锁可以转化为算术运算：ai=1-aiai=1-ai。3 3）第一次转动的是）第一次转动的是1 1，2 2，3 3，n n号牢房；号牢房；第二次转动的是第二次转动的是2 2，4 4，6 6，号牢房；号牢房；第三次转动的是第三次转动的是3 3，6 6，9 9，号牢房；号牢房；第第i i次次转转动动的的是是i i，2i2i，3i3i，4i4i，号号牢牢房房，是是起起点为点为i i，公差为，公差为i i的等差数列。的等差数列。4 4）不做其它的优化，用蛮力法通过循环模拟狱吏的开关）不做其它的优化，用蛮力法通过循环模拟狱吏的开关 锁过程，最后当第锁过程，最后当第i号牢房对应的数组元素号牢房对应的数组元素aiai为为0 0时，时，该牢房的囚犯得到大赦。算法该牢房的囚犯得到大赦。算法1如下：如下：算法设计1：57main1()main1()int*a,i,j,n;int*a,i,j,n;input(n);input(n);a=calloc(n+1,sizeof(int);a=calloc(n+1,sizeof(int);for(i=1;i=n;i+)for(i=1;i=n;i+)ai=1;ai=1;for(i=1;i=n;i+)for(i=1;i=n;i+)for(j=i;j=n;j=j+i)for(j=i;j=n;j=j+i)ai=1-ai;ai=1-ai;for(i=1;i=n;i+)for(i=1;i=n;i+)if(ai=0)print(i,”is free.”);if(ai=0)print(i,”is free.”);算算法法分分析析：以以一一次次开开关关锁锁计计算算，算算法法的的时时间间复复杂杂度度为为n(1+1/2+1/3+1/n)=O(nlogn)n(1+1/2+1/3+1/n)=O(nlogn)。main1()58问题分析：问题分析：转动门锁的规则可以有另一种理解，第一次转动转动门锁的规则可以有另一种理解，第一次转动的是编号为的是编号为1 1的倍数的牢房；第二次转动的是编号为的倍数的牢房；第二次转动的是编号为2 2的倍的倍数的牢房；第三次转动的是编号为数的牢房；第三次转动的是编号为3 3的倍数的牢房；的倍数的牢房；则则狱吏问题是一个关于因子个数的狱吏问题是一个关于因子个数的问题。令问题。令d(n)d(n)为自然数为自然数n n的因子个数，这里不计重复的因子，如的因子个数，这里不计重复的因子，如4 4的因子为的因子为1 1，2 2，4 4共三个因子，而非共三个因子，而非1 1，2 2，2 2，4 4。则。则d(n)d(n)有的为奇数，有有的为奇数，有的为偶数，见下表的为偶数，见下表:表表4-3 4-3 编号与因数个数的关系编号与因数个数的关系 n 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 n 1 2 3 4 5 6 7 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 d(n)1 2 2 3 2 4 2 4 3 4 2 6 2 4 4 5 数学模型数学模型1 1：上表中的上表中的d(n)d(n)有的为奇数，有的为偶数，有的为奇数，有的为偶数，由于由于牢房的门开始是关着的，这样编号为牢房的门开始是关着的，这样编号为i i的牢房，所含的牢房，所含11i i之间的不重复因子个数为奇数时，牢房最后是打开的，之间的不重复因子个数为奇数时，牢房最后是打开的，反之，牢房最后是关闭的。反之，牢房最后是关闭的。问题分析：转动门锁的规则可以有另一种理解，第一次转动的是编号59算法设计算法设计2:2:1 1）算算法法应应该该是是求求出出每每个个牢牢房房编编号号的的不不重重复复的的因因子子个个数数，当当它它为奇数时，这里边的囚犯得到大赦。为奇数时，这里边的囚犯得到大赦。2 2）一一个个数数的的因因子子是是没没有有规规律律的的，只只能能从从1n1n枚枚举举尝尝试试。算算法法2 2如下：如下：main2()main2()int s,i,j,n;int s,i,j,n;input(n);input(n);for(i=1;i=n;i+)for(i=1;i=n;i+)s=1;s=1;for(j=2;j=i;j=j+)for(j=2;j=i;j=j+)if if（i mod j=0i mod j=0）s=s+1;s=s+1;if if（s mod 2=1s mod 2=1）print(i,”is free.”);print(i,”is free.”);算法设计2:60算法分析：算法分析：狱吏开关锁的主要操作是狱吏开关锁的主要操作是ai=1-ai;ai=1-ai;共执行了共执行了n*(1+1/2+1/3+1/n)n*(1+1/2+1/3+1/n)次，时间近似为复杂度为次，时间近似为复杂度为O（nlogn）。使用了）。使用了n n个空间的一维数组。算法个空间的一维数组。算法2 2没有使用辅助没有使用辅助空间，但由于求一个编号的因子个数也很复杂，其空间，但由于求一个编号的因子个数也很复杂，其主要操主要操作是判断作是判断i mod ji mod j是否为是否为0 0，共执行了，共执行了n*(1+2+3+n)n*(1+2+3+n)次，时间复杂度为次，时间复杂度为O O（n n2 2）。）。数数学学模模型型2 2：仔仔细细观观察察表表4-34-3，发发现现当当且且仅仅当当n n为为完完全全平平方方数数时时,d(n),d(n)为为奇奇数数；这这是是因因为为n n的的因因子子是是成成对对出出现现的的,也也即即当当n=a*bn=a*b且且abab时时，必必有有两两个个因因子子a a，b;b;只只有有n n为为完完全全平平方方数数，也也即即当当n=an=a2 2时时,才才会会出出现现d(n)d(n)为奇数的情形。为奇数的情形。算算法法设设计计3 3：这这时时只只需需要要找找出出小小于于n n的的平平方方数数即即可可。算法算法3 3如下：如下：算法分析：61main3()main3()int s,i,j,n;int s,i,j,n;input(n);input(n);for(i=1;i=n;i+)for(i=1;i=n;i+)ifif（i*i=ni*i=n）print(i,”is free.print(i,”is free.”););else else break;break;由由此此算算法法我我们们应应当当注注意意：在在对对运运行行效效率率要要求求较较高高的的大大规规模模的的数数据据处处理理问问题题时时，必必须须多多动动脑脑筋筋找找出出效效率率较较高高的的数数学学模模型型及及其其对应的算法。对应的算法。main3()62