ACM培训课程算法设计课件.ppt

1、ACM培训课程算法设计主讲教师：校景中如何用计算机求解问题？1. 1. 问题分析问题分析 准确、完整地理解和描述问题是解决问题的准确、完整地理解和描述问题是解决问题的第一步。要做到这一点，必须注意以下一些问第一步。要做到这一点，必须注意以下一些问题：在未经加工的原始表达中，所用的术语是题：在未经加工的原始表达中，所用的术语是否都明白其准确定义？题目提供了哪些信息？否都明白其准确定义？题目提供了哪些信息？这些信息有什么用？题目要求得到什么结果？这些信息有什么用？题目要求得到什么结果？题目中作了哪些假定？是否有潜在的信息？判题目中作了哪些假定？是否有潜在的信息？判定求解结果所需要的中间结果有哪些？

2、定求解结果所需要的中间结果有哪些？如何用计算机求解问题？2 2、数学模型建立、数学模型建立 用计算机解决实际问题必须有合适的数学模型，因用计算机解决实际问题必须有合适的数学模型，因为在现实问题面前，计算机是无能为力。对一个实际为在现实问题面前，计算机是无能为力。对一个实际问题建立数学模型，可以考虑这样两个基本问题：最问题建立数学模型，可以考虑这样两个基本问题：最适合于此问题的数学模型是什么？是否有已经解决了适合于此问题的数学模型是什么？是否有已经解决了的类似问题可借鉴？的类似问题可借鉴？如何用计算机求解问题？3 3、算法设计与选择、算法设计与选择 算法设计是指设计求解某一特定类型问题的算法设计

3、是指设计求解某一特定类型问题的一系列步骤，并且这些步骤是可以通过计算机一系列步骤，并且这些步骤是可以通过计算机的基本操作来实现的。算法设计要同时结合数的基本操作来实现的。算法设计要同时结合数据结构的设计，简单说数据结构的设计就是选据结构的设计，简单说数据结构的设计就是选取存储方式。算法的设计与模型的选择更是密取存储方式。算法的设计与模型的选择更是密切相关的，但同一模型仍然可以有不同的算法，切相关的，但同一模型仍然可以有不同的算法，而且它们的有效性可能有相当大的差距。而且它们的有效性可能有相当大的差距。如何用计算机求解问题？在这些步骤中，算法设计是解决问题在这些步骤中，算法设计是解决问题的核心的

4、核心算法又是如何定义的呢？算法由操作、控制结构、数据结构三要素算法由操作、控制结构、数据结构三要素组成。组成。算法又是如何定义的呢？1 1）操作）操作 算术运算：加、减、乘、除算术运算：加、减、乘、除 关系比较：大于、小于、等于、不等于关系比较：大于、小于、等于、不等于 逻辑运算：与、或、非逻辑运算：与、或、非 数据传送：输入、输出数据传送：输入、输出, , 赋值赋值算法又是如何定义的呢？2 2）控制结构）控制结构 各操作之间的执行次序。各操作之间的执行次序。 顺序结构：各操作依次执行顺序结构：各操作依次执行 选择结构：由条件是否成立来选择选择结构：由条件是否成立来选择 执行执行 循环结构：有

5、些操作要重复执行，直到循环结构：有些操作要重复执行，直到 功能满足某个条件时结束。又称重复或功能满足某个条件时结束。又称重复或 迭代结构。迭代结构。算法又是如何定义的呢？3 3）数据结构）数据结构 算法操作的对象是数据，数据间的逻算法操作的对象是数据，数据间的逻辑关系、数据的存储方式及处理方式就辑关系、数据的存储方式及处理方式就是数据的数据结构。它与算法设计是紧是数据的数据结构。它与算法设计是紧密相关的。密相关的。如何设计循环？ 1 1设计中要注意算法的效率设计中要注意算法的效率 2 2“自顶向下自顶向下”的设计方法的设计方法 循环体的特点是：循环体的特点是：“以不变应万变以不变应万变”。 所

6、谓所谓“不变不变”是指循环体内运算的表现是指循环体内运算的表现形式是不变的，而每次具体的执行内容却是形式是不变的，而每次具体的执行内容却是不尽相同的。在循环体内用不变的运算表现不尽相同的。在循环体内用不变的运算表现形式去描述各种相似的重复运算。形式去描述各种相似的重复运算。1 1循环循环设计中设计中如何如何注意算法的效率注意算法的效率【例【例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)!分析：此问题中既有累加又有累乘，准确地说累分析：此问题中既有累加又有累乘，准确地说累加的对象是累乘的结

7、果。加的对象是累乘的结果。数学模型数学模型1 1：SnSn=Sn-1+=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如下：如下：算法如下：算法如下：main( ) int i,n,j,sign=1; float s,t=1;/s存储最终的结果，存储最终的结果，t存储存储(2k-1)的阶乘的阶

8、乘 input(n);/输入输入n s=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+1 for(j=1;j=i+1;j=j+1) sign = sign *(-1); s=s+ sign/t; print(“Snm=”,s);算法分析算法分析： 以上算法是二重循环来完成以上算法是二重循环来完成 ，但算，但算法的效率却太低是法的效率却太低是O（n2）。）。 其原因是，当前一次循环已求出其原因是，当前一次循环已求出7 7！，当这次要！，当这次要想求想求9 9！时，没必要再从！时，没

9、必要再从1 1去累乘到去累乘到9 9，只需要充分利，只需要充分利用前一次的结果，用用前一次的结果，用7 7！* *8 8* *9 9即可得到即可得到9 9！，模型为！，模型为A An n=A=An-1n-1* *1/(21/(2* *n-2)n-2)* *(2(2* *n-1)n-1)。另外运算。另外运算sign = sign sign = sign * *(-1);(-1);总共也要进行总共也要进行n n* *(n-1)/2(n-1)/2次乘法，这也是没有次乘法，这也是没有必要的。下面我们就进行改进。必要的。下面我们就进行改进。 数学模型数学模型2：Sn=Sn-1+（-1）n+1An； An

10、=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 2：构造循环不变式时，一定要注意循环变量的意义，如当构造循环不变式时，一定要注意循环变量的意义，如当i i不是项数序号时（右边

11、的循环中）有关不是项数序号时（右边的循环中）有关t t的的累乘累乘式与式与i i是项是项数序号时就不能相同。数序号时就不能相同。算法分析：按照数学模型算法分析：按照数学模型2 2，只需一重循环就能解决问题，只需一重循环就能解决问题算法的时间复杂性为算法的时间复杂性为O O（n n）。 2 2“自顶向下自顶向下”的设计方法的设计方法 自顶向下的方法是从全局走向局部、从自顶向下的方法是从全局走向局部、从概略概略走向走向详尽的详尽的设计设计方法。自上而下是系统分解和细化的过程。方法。自上而下是系统分解和细化的过程。 【例【例2 2】编算法找出】编算法找出10001000以内所有完数以内所有完数例如，

12、例如，2828的因子为的因子为1 1、2 2、4 4、7 7，1414，而，而28=1+2+4+7+1428=1+2+4+7+14。因此因此2828是是“完数完数”。编算法找出。编算法找出10001000之内的所有完之内的所有完数 ， 并 按 下 面 格 式 输 出 其 因 子 ：数 ， 并 按 下 面 格 式 输 出 其 因 子 ： 2 8 i t s 2 8 i t s factors are 1factors are 1，2 2，4 4，7 7，1414。1 1）这里不是要质因数，所以找到因数后也无需将其从）这里不是要质因数，所以找到因数后也无需将其从数据中数据中“除掉除掉”。2 2）每

13、个因数只记一次，如）每个因数只记一次，如8 8的因数为的因数为1 1，2 2，4 4而不是而不是1 1，2 2，2 2，2 2，4 4。（注：本题限定因数不包括这个数本。（注：本题限定因数不包括这个数本身）身）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 4）考虑输出格式）考虑输出

14、格式判断判断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） 按格式输出结果按格式输出结果 算法如下：算法如下：mai

15、n( )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); 递归算法是一个模块（函数、过程）除了可调用递归算法是一个模块（函数、过程）除了可调用其它模其它模 块（函数、过程）外，还可以直接或间接块（函数、过程）外，还可以直

16、接或间接地调用自身的算法地调用自身的算法。 递归是一种比迭代循环更强、更好用的循环结构递归是一种比迭代循环更强、更好用的循环结构。只需要找出递归关系和最小问题的解。只需要找出递归关系和最小问题的解。 递归的关键在于找出递归方程式和递归终止条件。递归的关键在于找出递归方程式和递归终止条件。递归定义：使问题向边界条件转化的规则。递归定义递归定义：使问题向边界条件转化的规则。递归定义必须能使问题越来越简单。必须能使问题越来越简单。递归边界条件：也就是所描述问题的最简单情况，它递归边界条件：也就是所描述问题的最简单情况，它本身不再使用递归的定义。本身不再使用递归的定义。递归算法解题通常有三个步骤：递归

17、算法解题通常有三个步骤：1 1）分析问题、寻找递归：找出大规模问题与小规模问）分析问题、寻找递归：找出大规模问题与小规模问题的关系，这样通过递归使问题的规模逐渐变小。题的关系，这样通过递归使问题的规模逐渐变小。2 2）设置边界、控制递归：找出停止条件，即算法可解）设置边界、控制递归：找出停止条件，即算法可解的最小规模问题。的最小规模问题。3 3）设计函数、确定参数：和其它算法模块一样设计函）设计函数、确定参数：和其它算法模块一样设计函数体中的操作及相关参数。数体中的操作及相关参数。 【例【例2 2】整数的分划问题】整数的分划问题 对于一个正整数对于一个正整数n n的分划就是把的分划就是把n n

18、写成一系列正整数之和的表达写成一系列正整数之和的表达式。例如，对于正整数式。例如，对于正整数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，第六行的数据不超过，第六行的数据

19、不超过1”1”。 因此，定义一个函数因此，定义一个函数Q(n,m)Q(n,m)，表示整数，表示整数n n的的“任何被加任何被加数都不超过数都不超过m”m”的分划的数目，的分划的数目，n n的所有分划的数目的所有分划的数目P(n)=Q(n,n)P(n)=Q(n,n)。模型建立：模型建立： 一般地一般地Q(n.m)Q(n.m)有以下递归关系：有以下递归关系： 1)1)Q(n,n)=1+Q(n,n-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)2)

20、Q(n,m)=Q(n,m-1)+Q(n-m,m) (mn)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)=1 2)Q(1,m

21、)=1，表示整数，表示整数n=1n=1只有一个分划，不管最大被加只有一个分划，不管最大被加数的上限数的上限m m是多大。是多大。 算法如下：算法如下：Divinteger(n, m) if （n 1 or m 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 ） return(1 + Divinteger(n, n-1) else return(Divinte

22、ger(n,m-1)+Divinteger(n-m,m); 算法与数据结构算法与数据结构数据的逻辑结构常分为四大类：数据的逻辑结构常分为四大类：（1 1）集合结构）集合结构 （2 2）线性结构）线性结构 （3 3）树形结构）树形结构（4 4）图结构（网结构）图结构（网结构） 存储结构可以分为：连续存储和链式存储。存储结构可以分为：连续存储和链式存储。连续存储又可以分为：静态存储和动态存储连续存储又可以分为：静态存储和动态存储 1 1、常用的几种数据结构、常用的几种数据结构 顺序存储的优点：顺序存储的优点： (1) 方法简单，各种高级语言中都提供数组结方法简单，各种高级语言中都提供数组结构，容易

23、实现。构，容易实现。 (2) 不用为表示结点间的逻辑关系而增加额外不用为表示结点间的逻辑关系而增加额外的存储开销。的存储开销。 (3) 顺序表具有按元素序号随机访问的特点。顺序表具有按元素序号随机访问的特点。2 2、连续存储和链式存储比较、连续存储和链式存储比较顺序存储的缺点：顺序存储的缺点： (1) 在顺序表中做插入删除操作时，平均移动在顺序表中做插入删除操作时，平均移动大约表中一半的元素，因此对大约表中一半的元素，因此对n较大的顺序表效较大的顺序表效率低。率低。 (2) 需要预先分配足够大的存储空间，估计过需要预先分配足够大的存储空间，估计过大，可能会导致顺序表后部大量闲置；预先分配大，可

24、能会导致顺序表后部大量闲置；预先分配过小，又会造成溢出。过小，又会造成溢出。温馨提示：温馨提示： 链表的优缺点恰好与顺序表相反。链表的优缺点恰好与顺序表相反。3 3、在选取存储结构时权衡因素有：、在选取存储结构时权衡因素有：）基于存储的考虑）基于存储的考虑 顺序表的存储空间是静态分配的，在程顺序表的存储空间是静态分配的，在程序执行之前必须明确规定它的存储规模，也就序执行之前必须明确规定它的存储规模，也就是说事先对是说事先对“MAXSIZE”MAXSIZE”要有合适的设定，过要有合适的设定，过大造成浪费，过小造成溢出。可见对线性表的大造成浪费，过小造成溢出。可见对线性表的长度或存储规模难以估计时

25、，不宜采用顺序表；长度或存储规模难以估计时，不宜采用顺序表；链表不用事先估计存储规模，但链表的存储密链表不用事先估计存储规模，但链表的存储密度较低，度较低，）基于运算的考虑）基于运算的考虑 在顺序表中按序号访问在顺序表中按序号访问a ai i的时间性能时的时间性能时O(1)O(1)，而链表中按序号访问的时间性能而链表中按序号访问的时间性能O(n)O(n)，所以如果，所以如果经常做的运算是按序号访问数据元素，显然顺序经常做的运算是按序号访问数据元素，显然顺序表优于链表；表优于链表；）基于环境的考虑）基于环境的考虑 顺序表容易实现，任何高级语言中都有数顺序表容易实现，任何高级语言中都有数组类型，链

26、表的操作是基于指针的，操作简单。组类型，链表的操作是基于指针的，操作简单。 科目及格学生学号语文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方法一方法一： 从语文及格名单中逐一抽出各及格学生学号，先在代数及格名单核对，若有从语文及格名单中逐一抽出各及格学生学号，先在代数及格名单核对，若有该学号（说明代数也及格了），再在外语及格名单中继续查找，看该学号是否也该学号（说明代数也及格了），再在

27、外语及格名单中继续查找，看该学号是否也在外语及格名单中。若仍在，说明该号属全及格学生的学号，否则就是至少有一在外语及格名单中。若仍在，说明该号属全及格学生的学号，否则就是至少有一科不及格的。若语文及格名单中就没有某生的号，显然该生根本不在比较之列，科不及格的。若语文及格名单中就没有某生的号，显然该生根本不在比较之列，自然不属全及格学生自然不属全及格学生 。该方法采用了枚举尝试的方法该方法采用了枚举尝试的方法A A，B B，C C三组分别存放语文、代数、外语及格名单，尝三组分别存放语文、代数、外语及格名单，尝试范围为三重循环：试范围为三重循环： I I循环，循环， 初值初值0 0， 终值终值6

28、6， 步长步长1 1 J J循环，循环， 初值初值0 0， 终值终值5 5， 步长步长1 1 K K循环，循环， 初值初值0 0， 终值终值7 7， 步长步长1 1 定解条件：定解条件： AI=BJ=CKAI=BJ=CK 共尝试共尝试7 7* *6 6* *8=3368=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)

29、 input(ci); 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 A的九个下标分量作为各号考生及格科目的计数器。将三科及格名单的九个下标分量作为各号考生及格科目的计数器。将三科及格名单共存一个数组，当扫描完毕总及格名单后，凡下标计数器的值为共存一个数组，当扫描完毕总及格名单后，凡下标计数器的值为3 3的就是全及格的就是全及格的，其余则至少有一科不及格的。的

30、，其余则至少有一科不及格的。 该方法同样也采用了枚举尝试的方法。该方法同样也采用了枚举尝试的方法。 算法步骤为：算法步骤为：1 1）用下标计数器累加各学号学生及格科数，）用下标计数器累加各学号学生及格科数，2 2）尝试、输出部分。）尝试、输出部分。累加部分为一重循环，初值累加部分为一重循环，初值1 1 ，终值为三科及格的总人，终值为三科及格的总人数，包括重复部分。计数，包括重复部分。计7+6+8=217+6+8=21，步长，步长1 1。尝试部分的尝试范围为一重循环，初值尝试部分的尝试范围为一重循环，初值1 1 ，终值，终值9 9，步，步长长1 1。定解条件：定解条件：A A（i i）=3 =3

31、 方法二算法如下：方法二算法如下：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 数组记录状态信息数组记录状态信息问题提出：问题提出： 有的问题会限定在现有数据中，每个数据只有的问题会限定在现有数据中，每个数据只能被使用一次，怎么样表示一个数据能被使用一次，怎么样表示一个数据“使用过使用过”还是没有还是没有“使用过使用过”？ 一个朴素的想法是：用数组存储已使用过一个朴素的想法是：用数组存

32、储已使用过的数据，然后每处理一个新数据就与前面的数的数据，然后每处理一个新数据就与前面的数据逐一比较看是否重复。这样做，当数据量大据逐一比较看是否重复。这样做，当数据量大时，判断工作的效率就会越来越低。时，判断工作的效率就会越来越低。返回3.2.3 例1 例2例例1 【例【例1 1】求】求X X，使，使X X2 2为一个各位数字互不相同的九位为一个各位数字互不相同的九位数。数。总体分析：总体分析：只能用枚举法尝试完成此题。由只能用枚举法尝试完成此题。由X X2 2为一为一个九位数，估算个九位数，估算X X应在应在10000100003200032000之间。之间。算法设计：算法设计： 1 1）

33、 用一个用一个10 10 个元素的状态数组个元素的状态数组p p，记录数字，记录数字0 09 9在在X X2 2中出现的情况。数组元素都赋初值为中出现的情况。数组元素都赋初值为1 1，表示数字，表示数字0 09 9没有被使用过。没有被使用过。 2 2） 对尝试的每一个数对尝试的每一个数x x，求，求x x* *x,x,并取其各个位数字，并取其各个位数字，数字作为数组的下标，若对应元素为数字作为数组的下标，若对应元素为1 1，则该数字第一，则该数字第一次出现，将对应的元素赋为次出现，将对应的元素赋为0 0，表示该数字已出现一次。，表示该数字已出现一次。否则，若对应元素为否则，若对应元素为0 0，

34、则说明有重复数字，结束这次，则说明有重复数字，结束这次尝试。尝试。 3 3） 容易理解当状态数组容易理解当状态数组p p中有中有9 9个元素为个元素为0 0时，就找时，就找到了问题的解。但这样判定有解，需要扫描一遍数组到了问题的解。但这样判定有解，需要扫描一遍数组p p。为避免这个步骤，设置一个计数器为避免这个步骤，设置一个计数器k k，在取，在取x x* *x x各个位数各个位数字的过程中记录不同的数字的个数，当字的过程中记录不同的数字的个数，当k=9k=9时就找到了时就找到了问题的解。问题的解。 main( )long x, y1, y2; int p10, 2, i, t, k, num

35、=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); 大整数的存储及运算大整数的存储及运算 计算机存储数据是按类型分配空间的。在微型机上为计算机存储数据是按类型分配空间的。在微型机上为整型提供整型提供2 2个字节个字节

36、1616位的存储空间，则整型数据的范围为位的存储空间，则整型数据的范围为- -32768327683276732767；为长整型提供；为长整型提供4 4个字节个字节3232位的存储空间，位的存储空间，则长整型数据的范围为则长整型数据的范围为-2147483648-214748364821474836472147483647；为；为实型也是提供实型也是提供4 4个字节个字节3232位的存储空间，但不是精确存储位的存储空间，但不是精确存储数据，只有六位精度，数据的范围数据，只有六位精度，数据的范围(3.4e-383.4e+38) ；为双精度型数据提供为双精度型数据提供8 8个字节个字节6464位的

37、存储空间，数据的范位的存储空间，数据的范围围(1.7e-3081.7e+308)，其精确位数是，其精确位数是1717位。位。返回3.2.4 在用数组存储高精度数据时，从计算的方便性考虑，在用数组存储高精度数据时，从计算的方便性考虑，决定将数据是由低到高还是由高到低存储到数组中；可以决定将数据是由低到高还是由高到低存储到数组中；可以每位占一个数组元素空间，也可几位占一个数组元素空间。每位占一个数组元素空间，也可几位占一个数组元素空间。 若需从键盘输入要处理的高精度数据，一般用字符数若需从键盘输入要处理的高精度数据，一般用字符数型组存储，这样无需对高精度数据进行分段输入。当然这型组存储，这样无需对

38、高精度数据进行分段输入。当然这样存储后，需要有类型转换的操作，不同语言转换的操作样存储后，需要有类型转换的操作，不同语言转换的操作差别虽然较大，但都是利用数字字符的差别虽然较大，但都是利用数字字符的ASCIIASCII码进行的。码进行的。其它的技巧和注意事项通过下面的例子来说明。本节只针其它的技巧和注意事项通过下面的例子来说明。本节只针对大对大 整数的计算进行讨论，对高精度实数的计算可以仿整数的计算进行讨论，对高精度实数的计算可以仿照进行。照进行。 【例】编程求当【例】编程求当N=100N=100时，时，N N！的准确值！的准确值问题分析：问题要求对输入的正整数问题分析：问题要求对输入的正整数

39、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 46

40、3976 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算法设计：算法设计：1 1）乘法的结果是按由低位到高位存储在数组）乘法的结果是按由低位到高位存储在数组abab中，中，由由于计算结果位数太多，若存储结果的数组，每个存储于计算结果位数太多，若存储结果的数组，

41、每个存储空间只存储一位数字，对每一位进行累乘次数太多。空间只存储一位数字，对每一位进行累乘次数太多。所以将数组定义为长整型，每个元素存储六位。所以将数组定义为长整型，每个元素存储六位。 2 2）对两个高精度数据的乘法运算，比较简单的方法）对两个高精度数据的乘法运算，比较简单的方法就是两个高精度数据的按元素交叉相乘，用二重循环就是两个高精度数据的按元素交叉相乘，用二重循环来实现。其中一个循环变量来实现。其中一个循环变量i i代表累乘的数据，代表累乘的数据，b b存储存储计算的中间结果，数组计算的中间结果，数组abab存储每次累乘的结果，每个存储每次累乘的结果，每个元素存储六位数据，元素存储六位数

42、据，d 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=m;i+)/结果清零结果清零 abi=0;d=0;/存储进位存储进位for( i=2; i=n;i+)/从从2乘到乘到n for (j=1;j=1;i-) if( abi=0) continue; els

43、e r=i; break;返回返回3.2.4 print(n,“!=”); print(abr); for(i=r-1;i=1;i-) if (abi99999) print(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.

44、4算法说明：算法说明： 1 1）算法中）算法中“m=log(n)m=log(n)* *n/6+2;”n/6+2;”是对是对N N！位数的粗！位数的粗略估计。略估计。 2 2）输出时，首先计算结果的准确位数）输出时，首先计算结果的准确位数r r，然后输出，然后输出最高位数据，在输出其它存储单元的数据时要特别注最高位数据，在输出其它存储单元的数据时要特别注意，如若计算结果是意，如若计算结果是123000001123000001，abab22中存储的是中存储的是123123，而，而abab11中存储的不是中存储的不是000001000001，而是，而是1 1。所以在。所以在输出时，通过多个条件语句保

45、证输出的正确性。输出时，通过多个条件语句保证输出的正确性。 返回3.2.4枚举法枚举法 枚举（枚举（ enumerate）法（穷举法）是）法（穷举法）是蛮力策略的一种表现形式蛮力策略的一种表现形式，也是一种使用非常普遍的思维方法。它是根据问题中的条件将可能也是一种使用非常普遍的思维方法。它是根据问题中的条件将可能的情况一一列举出来，逐一尝试从中找出满足问题条件的解。但有的情况一一列举出来，逐一尝试从中找出满足问题条件的解。但有时一一列举出的情况数目很大，如果超过了我们所能忍受的范围，时一一列举出的情况数目很大，如果超过了我们所能忍受的范围，则需要进一步考虑，排除一些明显不合理的情况，尽可能减少

46、问题则需要进一步考虑，排除一些明显不合理的情况，尽可能减少问题可能解的列举数目。可能解的列举数目。用枚举法解决问题，通常可以从两个方面进行算法设计：用枚举法解决问题，通常可以从两个方面进行算法设计： 1）找出枚举范围：分析问题所涉及的各种情况。找出枚举范围：分析问题所涉及的各种情况。 2 2）找出约束条件：分析问题的解需要满足的条件，并用逻辑）找出约束条件：分析问题的解需要满足的条件，并用逻辑表达式表示。表达式表示。【例【例1 1】百钱百鸡问题。中国古代数学家张丘建在他的百钱百鸡问题。中国古代数学家张丘建在他的算经算经中提出了著名的中提出了著名的“百钱百鸡问题百钱百鸡问题”：鸡翁一，值钱五；鸡

47、母一，：鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一；百钱买百鸡，翁、母、雏各几何值钱三；鸡雏三，值钱一；百钱买百鸡，翁、母、雏各几何? ?算法设计算法设计1：通过对问题的理解，读者可能会想到列出两个三元一次方程，通过对问题的理解，读者可能会想到列出两个三元一次方程，去解这个不定解方程，就能找出问题的解。这确实是一种办法，去解这个不定解方程，就能找出问题的解。这确实是一种办法，但这里我们要用但这里我们要用“懒惰懒惰”的枚举策略进行算法设计：的枚举策略进行算法设计： 设设x，y，z分别为公鸡、母鸡、小鸡的数量。分别为公鸡、母鸡、小鸡的数量。 尝试范围：由尝试范围：由题意给定共题意给定共100钱

48、要买百鸡，若全买公鸡最钱要买百鸡，若全买公鸡最多买多买100/5=100/5=20只，显然只，显然x的取值范围的取值范围120之间；同理，之间；同理，y的的取值范围在取值范围在133之间，之间，z z的取值范围的取值范围在在11001100之间之间。 约束条件：约束条件： x+y+z=100 x+y+z=100 且且 5 5* *x+3x+3* *y+z/3=100y+z/3=100 算法算法1如下：如下： main( )main( ) int int x,y,z; 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+

49、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 if(100=x+y+z and 100=5* *x+3x+3* *y+z/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 i

50、s z); 算法分析：以上算法需要枚举尝试算法分析：以上算法需要枚举尝试20*34*100=68000次。次。算法的效率显然太低算法的效率显然太低算法设计算法设计2：在在公鸡（公鸡（x x）、母鸡（）、母鸡（y y）的数量的数量确定后，小鸡确定后，小鸡的数量的数量z就固就固定为定为100-x-y，无需再进行枚举了，无需再进行枚举了此时此时约束条件只有一个：约束条件只有一个： 5*x+3*y+z/3=100算法算法2如下：如下： main( )main( ) int int x,y,z; x,y,z; for(x=1;x=20;x=x+1) for(x=1;x=20;x=x+1) for(y=1