算法基本工具(Part2).ppt

1,算法基本工具,主要内容,2.1 循环与递归2.2 算法与数据结构2.3 优化算法的数学模型,2,2.2 算法与数据结构,2.2.1 原始信息与处理结果的对应存储2.2.2 数组使信息有序化2.2.3 数组记录状态信息2.2.4大整数存储及运算,数据的逻辑结构常分为四大类：（1）集合结构（2）线性结构（3）树形结构（4）图结构（网结构）,存储结构可以分为：连续存储和链式存储。连续存储又可以分为：静态存储和动态存储,1、常用的几种数据结构,顺序存储的优点：(1)方法简单，各种高级语言中都提供数组结构，容易实现。(2)不用为表示结点间的逻辑关系而增加额外的存储开销。(3)顺序表具有按元素序号随机访问的特点。,2、连续存储和链式存储比较,顺序存储的缺点：(1)在顺序表中做插入删除操作时，平均移动大约表中一半的元素，因此对n较大的顺序表效率低。(2)需要预先分配足够大的存储空间，估计过大，可能会导致顺序表后部大量闲置；预先分配过小，又会造成溢出。,温馨提示：链表的优缺点恰好与顺序表相反。,3、在选取存储结构时权衡因素有：,）基于存储的考虑 顺序表的存储空间是静态分配的，在程序执行之前必须明确规定它的存储规模，也就是说事先对“MAXSIZE”要有合适的设定，过大造成浪费，过小造成溢出。可见对线性表的长度或存储规模难以估计时，不宜采用顺序表；链表不用事先估计存储规模，但链表的存储密度较低.,）基于运算的考虑 在顺序表中按序号访问ai的时间性能时O(1)，而链表中按序号访问的时间性能O(n)，所以如果经常做的运算是按序号访问数据元素，显然顺序表优于链表；）基于环境的考虑 顺序表容易实现，任何高级语言中都有数组类型，链表的操作是基于指针的，操作简单。,2.2.1 原始信息与处理结果对应存储,每一个问题中的信息往往是多方面的，在算法中一般有输入信息、输出信息和信息加工处理过程中的中间信息。那么哪些信息需要用数组进行存储，数组元素下标与信息怎么样对应等问题的确定，在很大程度上影响着算法的编写效率和运行效率。下面的例子恰当地选择了用数组存储的信息，并把题目中的有关信息作为下标使用，使算法的实现过程大大简化。【例1】统计选票【例2】统计身高【例3】统计及格学生的名单【例4】统计找数字对的出现频率,【例1】某次选举，要从五个候选人（编号分别为1、2、3、4、5）中选一名厂长。请编程完成统计选票的工作。,算法设计：1）虽然选票发放的数量一般是已知的，但收回的数量通常是无法预知的，所以算法采用随机循环，设计停止标志为“-1”。2）统计过程的一般方法为：先为五个候选人各自设置五个“计数器”S1，S2，S3，S4，S5，然后根据录入数据通过多分支语句或嵌套条件语句决定为某个“计数器”累加1,这样做效率太低。现在把五个“计数器”用数组代替，选票中候选人的编号xp正好做下标，执行A(xp)=A(xp)+1就可方便地将选票内容累加到相应的“计数器”中。也就是说数组结构是存储统计结果的，而其下标正是原始信息。3）考虑到算法的健壮性，要排除对15之外的数据进行统计。,10,算法描述：,11,vote()int i,xp,a6;print(“input data until input-1”);input(xp);while(xp!=-1)if(xp=1 and xp=5)axp=axp+1;else print(xp,input error!);input(xp);for(i=1;i=5;i+)print(i,number get,ai,votes);,【例2】编程统计身高（单位为厘米）。统计分150154；155159；160164；165169；170174；175179及低于是150、高于是179共八档次进行。,算法设计：输入的身高可能在50250之间，若用输入的身高数据直接作为数组下标进行统计，即使是用PASCAL语言可设置上、下标的下界，也要开辟200多个空间，而统计是分八个档次进行的，这样是完全没有必要的。由于多数统计区间的大小是都固定为5，这样用“身高/5-29”做下标，则只需开辟8个元素的数组，对应八个统计档次，即可完成统计工作。,12,算法如下：,13,main()int i,sg,a8;print(“input height data until input-1”);input(sg);while（sg-1）if(sg179)a7=a7+1；else if(sg150)a0=a0+1；else asg/5-29=asg/5-29+1；input(sg);for(i=0;i=7;i=i+1)print(i+1，“field the number of people：”，ai);,【例3】一次考试共考了语文、代数和外语三科。某小组共有九人，考后各科及格名单如下表，请编写算法找出三科全及格的学生的名单（学号）。,14,方法一：,从语文及格名单中逐一抽出各及格学生学号，先在代数及格名单核对，若有该学号（说明代数也及格了），再在外语及格名单中继续查找，看该学号是否也在外语及格名单中。若仍在，说明该号属全及格学生的学号，否则就是至少有一科不及格的。若语文及格名单中就没有某生的号，显然该生根本不在比较之列，自然不属全及格学生。方法采用了枚举尝试的方法A，B，C三组分别存放语文、代数、外语及格名单，尝试范围为三重循环：I循环，初值0，终值6，步长1 J循环，初值0，终值5，步长1 K循环，初值0，终值7，步长1 定解条件：AI=BJ=CK 共尝试7*6*8=336次。,15,16,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);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;,方法二：,用数组A的九个下标分量作为各号考生及格科目的计数器。将三科及格名单共存一个数组，当扫描完毕总及格名单后，凡下标计数器的值为3的就是全及格的，其余则至少有一科不及格的。该方法同样也采用了枚举尝试的方法。,17,18,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);,【例4】统计找数字对的出现频率,19,算法说明：输入N（2N100）个数字（在0与9之间），然后统计出这组数中相邻两数字组成的链环数字对出现的次数。例如：输入：N=20 表示要输入数的数目 0 1 5 9 8 7 2 2 2 3 2 7 8 7 8 7 9 6 5 9 输出：（7，8）=2（8，7）=3 指（7，8）、（8，7）数字对出现次数分别为2次、3次（7，2）=1（2，7）=1（2，2）=2（2，3）=1（3，2）=1,算法设计：,其实并不是只有一维数组这样的数据结构可以在算法设计中有多采的应用，根据数据信息的特点，二维数组的使用同样可以使算法易于实现，此题就正是如此。用10*10的二维数组（行、列下标均为0-9），存储统计结果，i行j列存储数字对（i，j）出现的次数，无需存储原始数据，用其做下标，在数据输入的同时就能统计出问题的结果。,20,21,main()int a1010,m,i,j,k1,k0;print(“How many is numbers?”);input(n);print(“Please input these numbers:”);input(k0);for(i=2;i0 and aji0);print(“(”,i,j,”)=“,aij,”,(”,j,i,”)=”,aji),2.2.2数组使信息有序化,当题目中的数据缺乏规律时，很难把重复的工作抽象成循环不变式来完成，但先用数组结构存储这些地信息后，问题就迎刃而解。,22,【例1】编程将编号“翻译”成英文。例35706“翻译”成three-five-seven-zero-six。,算法设计1：1）编号一般位数较多，可按长整型输入和存储。2）将英文的“zeronine”存储在数组中，对应下标为09。这样无数值规律可循的单词，通过下标就可以方便存取、访问了。3）通过求余、取整运算，可以取到编号的各个位数字。用这个数字作下标，正好能找到对应的英文数字。4）考虑输出翻译结果是从高位到低位进行的，而取各位数字，比较简单的方法是从低位开始通过求余和整除运算逐步完成的。所以还要开辟一个数组来存储从低位到高位翻译好的结果，并记录编号的位数，最后倒着从高位到低位输出结果。,23,24,main()int i,a10,ind;long num1,num2;char eng106=“zero”,”one”,”two”,”three”,”four”,”five”,”six”,”seven”,“eight”,”nine”;print(“Input a num”);input(num1);num2=num1;ind=0;while(num20)aind=num2 mod 10;ind=ind+1;num2=num2/10;print(num1,“English_exp:”,engaind-1);for(i=ind-2;i=0;i=i-1)print(“-”，engai);,【例2】一个顾客买了价值x元的商品，并将y元的钱交给售货员。售货员希望用张数最少的钱币找给顾客。,问题分析：无论买商品的价值x是多大，找给他的钱最多需要以下六种币值：50，20，10，5，2，1。算法设计：1）为了能达到找给顾客钱的张数最少，先尽量多地取大面额的币种，由大面额到小面额币种逐渐进行。2）六种面额不是等到差数列，为了能构造出循环不变式，将六种币值存储在数组B。这样，六种币值就可表示为Bi，i=1，2，3，4，5，6。为了能达到先尽量多地找大面额的币种，六种币值应该由大到小存储。3）另外还要为统计六种面额的数量，同样为了能构造出循环不变式，设置一个有六个元素的累加器数组S，这样操作就可以通过循环顺利完成了。,25,算法如下：,26,main()int i,j,x,y,z,a,b7=0,50,20,10,5,2,1,s7;input(x,y);z=y-x;for(i=1;i0)print(bi,“-”,si);,算法说明：,1）每求出一种面额所需的张数后，一定要把这部分金额减去：“y=y-A*Bj;”，否则将会重复计算。2）算法无论要找的钱z是多大，我们都从50元开始统计，所以在输出时要注意合理性，不要输出无用的张数为0 的信息。,27,2.2.3数组记录状态信息,问题提出：有的问题会限定在现有数据中，每个数据只能被使用一次，怎么样表示一个数据“使用过”还是没有“使用过”？一个朴素的想法是：用数组存储已使用过的数据，然后每处理一个新数据就与前面的数据逐一比较看是否重复。这样做，当数据量大时，判断工作的效率就会越来越低。,28,【例1】求X，使X2为一个各位数字互不相同的九位数。,算法分析：只能用枚举法尝试完成此题。由X2为一个九位数，估算X应在1000032000之间。算法设计：1）用一个10 个元素的状态数组p，记录数字09在X2中出现的情况。数组元素都赋初值为1，表示数字09没有被使用过。2）对尝试的每一个数x，求x*x,并取其各个位数字，数字作为数组的下标，若对应元素为1，则该数字第一次出现，将对应的元素赋为0，表示该数字已出现一次。否则，若对应元素为0，则说明有重复数字，结束这次尝试。3）容易理解当状态数组p中有9个元素为0时，就找到了问题的解。但这样判定有解，需要扫描一遍数组p。为避免这个步骤，设置一个计数器k，在取x*x各个位数字的过程中记录不同的数字的个数，当k=9时就找到了问题的解。,29,30,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);,【例2】游戏问题：12个小朋友手拉手站成一个圆圈，从某一个小朋友开始报数，报到7的那个小朋友退到圈外，然后他的下一位重新报“1”。这样继续下去，直到最后只剩下一个小朋友，求解这个小朋友原来站在什么位置上呢？,31,算法设计：,这个问题初看起来很复杂，又是手拉手，又是站成圈，报数到7时退出圈似乎很难入手。细细分析起来，首先是如何表示状态的问题。开辟12个元素的数组，记录12个小朋友的状态，开始时将12个元素的数组值均赋为1，表示大家都在圈内。这样小朋友报数就用累加数组元素的值来模拟，累加到7时，该元素所代表的小朋友退到圈外，将相应元素的值改赋为0，这样再累加到该元素时和不会改变，又模拟了已出圈外的状态。为了算法的通用性，算法允许对游戏的总人数、报数的起点、退出圈外的报数点任意输入。其中n表示做游戏的总人数，k表示开始及状态数组的下标变量，m表示退出圈外的报数点，即报m的人出队，p表示已退出圈外的人数。,算法如下：,32,main()int a100,i,k,p,m;print(“input numbers of game:”);input(n);print(“input serial number of game start:”);input(k);print(“input number of out_ring:”);input(m);for(i=1;i=n;i+)ai=1;p=0;,while(pn)k=1;x=x+ak;print(k);ak=0;p=p+1;for(i=1;i=n;i+)if(ai=1)print(“i=”,i);,算法说明：,1）算法中当变量k n时，赋k=1，表示n号报完数就该1号报数。模拟了将n个人连成了一个“圈”的情况。2）x为“报”出的数，x=m时输出退出圈外人的下标k，将ak赋值为0；3）p=n-1时游戏结束；4）最后检测还在圈上ai=1的人，输出其下标值即编号（原来位置）。思考：可选择顺时针或反时针方向报数。,33b,3.3.4大整数的存储及运算,34,1 编程求当N=100时，N！的准确值。问题分析：例如：9！=362880100！=93 326215 443944 152681 699263 856266 700490 715968 264381 621468 592963895217 599993 229915 608914 463976 156578286253 697920 827223 758251 185210 916864000000 000000 000000 000000,35,问题分析:,计算机存储数据是按类型分配空间的。在PC上：整型：2个字节16位，则整型数据的范围为-3276832767；长整型：4个字节32位，则长整型数据的范围为-21474836482147483647；实型：4个字节32位，但非精确存储数据，只有六位精度，数据的范围(3.4e-383.4e+38)；双精度型：8个字节64位的存储空间，数据的范围(1.7e-3081.7e+308)，其精确位数是17位。,这些类型无法存储100！这样的“大整数”。,需要使用更复杂、更有针对性的数据结构。,36,算法设计,每一位数，都是一个10以内数字。多个，相同属性的，,数组是有头有尾的：a1an。高位、低位谁头谁尾？,低位固定，而高位不定。最低位为a1，且在高端要为问题最大存储数据留够空位。,基于存储的考虑,int an,37,算法设计,100！=1*2*3*99*100。按此方法计算，最困难的操作是：大整数*乘数，其中乘数=100。,基于功能的考虑,原来一个元素存一位，现在是否要改变？改变是否有用？,问题出在哪里？,当低位元素计算后的值超过9时，需向高位元素进位。,如何进位？,38,算法设计,int an中的数组元素可以存放更大的数。如，每个存3位。,基于性能的考虑,进位4次。,进位几次？,进位需要特殊的处理；减少进位的处理，可以提高效率。,每个元素处理的位数越多，进位次数越少。,在前面提到的四种数据类型的基础上，粗略估计一下，本问题中，每个元素最多可以存储几位数据？,39,算法实现,main()long ab256,b,d;int m,n,i,j,r;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+)for(j=1;j=m;j+)b=abj*i+d;abj=b%1000000;d=b/1000000;,for(i=m;i=1;i-)if(abi=0)continue;else r=i;break;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,算法说明：,1）算法中“m=log(n)*n/6+2;”是对N！位数的粗略估计。2）输出时，首先计算结果的准确位数r，然后输出最高位数据，在输出其它存储单元的数据时要特别注意，如若计算结果是123000001，ab2中存储的是123，而ab1中存储的不是000001，而是1。所以在输出时，通过多个条件语句保证输出的正确性。,