算法与程序实践习题解答7(枚举)

《算法与程序实践》习题解答7—一枚举枚举是基于已有的知识进行答案猜测的一种问题求解策略。在求解一个问题时，通常先建立一个数学模型，包括一组变量，以及这些变量需要满足的条件。问题求解的目标就是确定这些变量的值。根据问题的描述和相关的知识，能为这些变量分别确定一个大概的取值范围。在这个范围内对变量依次取值，判断所取的值是否满足数学模型中的条件，直到找到（全部）符合条件的值为止。这种解决问题的方法称作“枚举”。例如“求小于N的最大素数”。其数学模型是：一个整型变量n，满足：（1） n不能够被［2,n）中的任意一个素数整除；（2） n与N之间没有素数。利用已有的知识，能确定n的大概取值范围｛2｝｛2*i+1l1<=i,2*i+1<N｝。在这个范围内从小到大依次取值，如果n不能够被［2,n）中的任意一个素数整除，则满足条件（1）。在这个范围内找到的最后一个素数也一定满足条件（2），即为问题的解。枚举是用计算机求解问题最常用的方法之一，常用来解决那些通过公式推导、规则演绎的方法不能解决的问题。而且，枚举也是现代科学研究和工程计算的重要手段，因为科学研究是在发现问题的规律之前解决问题，然后再寻找不同问题之间的共同规律。在采用枚举的方法进行问题求解时，要注意3个方面的问题。建立简洁的数学模型。数学模型中变量的数量要尽量少，它们之间相互独立。这样问题解的搜索空间的维度就小。反应到程序代码中，循环嵌套的层次少。模型中的每个条件要反应问题的本质特征。“求小于N的最大素数”中的条件（1）是“n不能够被［2，n）中的任意一个素数整除”，而不是“n不能够被［2,n）中的任意一个整数整除”。这个条件极大的降低了判断n是否是素数的计算开销。减小搜索的空间。利用已有的知识缩小数学模型中各个变量的取值范围，避免不必要的计算。反应到程序代码中，循环体被执行的次数就少。除2之外的其它素数都是奇数，因此“小于N的最大素数”一定在集合｛2,2*i+1l1<=i，2*i+1<N｝中。用这个集合代替［2,N），搜索空间减小了一半。采用合适的搜索顺序。对搜索空间的遍历顺序要与数学模型中的条件表达式一致。例如在“求小于N的最大素数”中，在判断n是否是素数时，需要用到比n小的全部素数。因此，在程序代码中，应该对搜索空间｛2，2*i+1l1<=i，2*i+1<N｝采取从小到大的遍历顺序。CS71:生理周期（简单枚举）（来源：2977，程序设计导引及在线实践（李文新）例8.2P176）问题描述：人生来就有三个生理周期，分别为体力、感情和智力周期，它们的周期长度为23天、28天和33天。每一个周期中有一天是高峰。在高峰这天，人会在相应的方面表现出色。例如，智力周期的高峰，人会思维敏捷，精力容易高度集中。因为三个周期的周长不同，所以通常三个周期的高峰不会落在同一天。对于每个人，我们想知道何时三个高峰落在同一天。对于每个周期，我们会给出从当前年份的第一天开始，到出现高峰的天数（不一定是第一次高峰出现的时间）。你的任务是给定一个从当年第一天开始数的天数，输出从给定时间开始（不包括给定时间）下一次三个高峰落在同一天的时间（距给定时间的天数）。例如：给定时间为10，下次出现三个高峰同天的时间是12,则输出2（注意这里不是3）。输入：输入四个整数：p,e,i和d。p,e,i分别表示体力、情感和智力高峰出现的时间（时间从当年的第一天开始计算）。d是给定的时间，可能小于p,e,或i。所有给定时间是非负的并且小于365,所求的时间小于21252。输出：从给定时间起，下一次三个高峰同天的时间（距离给定时间的天数）。样例输入：00000001005203432545672831022332020330120340-1-1-1-1样例输出：Case1:thenexttriplepeakoccursin21252days.Case2:thenexttriplepeakoccursin21152days.Case3:thenexttriplepeakoccursin19575days.Case4:thenexttriplepeakoccursin16994days.Case5:thenexttriplepeakoccursin8910days.Case6:thenexttriplepeakoccursin10789days.解题思路：假设从当年的第一天开始数，第x天时三个高峰同时出现。符合问题要求的x必须大于d、小于等于21252，并满足下列三个条件：1） （x-p）%23=02） （x-e）%28=03） （x-i）%33=0在搜索空间［d+1，21252］中，对每个猜测的答案都进行三个条件的判断，开销很大，也没有必要。首先从搜索空间［d+1，21252］中找到符合条件1）的全部时间，然后从这些时间中寻找符合条件2）、3）的时间，可以将对条件2）、3）的判定次数减少为原来的1/23。用同样的办法，可以继续减少对条件3）的判定次数。对每一组数据，分别执行下列算法：1） 读入？，e,i,d2） 从d+1循环到21252,找到第一个满足条件1）的时间a、并跳出循环3） 从a循环到21252，找到第一个满足条件2）的时间b、并跳出循环4） 从b循环到21252，找到第一个满足条件3）的时间x、并跳出循环5） 输出x-d参考程序：#include<stdio.h>intmain（）{intp,e,i,d,j,no=1;scanf("%d%d%d%d”,&p,&e,&i,&d);while(p!=-1&&e!=-1&&i!=-1&&d!=-1){for(j=d+1;j<21252;j++){if((j-p)%23==0)break;}for(;j<21252;j=j+23)if((j-e)%28==0)break;for(;j<21252;j=j+23*28)if((j-i)%33==0)break;printf("Case%d",no);printf(":thenexttriplepeakoccursin%ddays.\n",j-d);scanf("%d%d%d%d”,&p,&e,&i,&d);no++;}return0;}实现技巧：在问题的数学模型中，有多个条件需要满足时，可以采用逐步减小搜索空间的方法提高计算的效率。依次按照条件一、条件二、……、进行搜索。在最初的搜索空间上，按条件一进行判定。除最后一次外，每次搜索都找到符合当前条件的全部答案，将它们作为下一个条件判定的搜索空间。CS72:完美立方(搜索解空间中解不唯一)(来源：2810，程序设计导引及在线实践(李文新)例8.4P181)问题描述：3CC O . c c c3 3 3 3 3 3 3a=b+c+d为完美立方等式。例如12=6+8+10。编与一个程序，对任给的正整数N(NW100)，寻找所有的四元组(a,b,c,d)，使得a3=b3+c3+d3，其中1<a,b,c,dWN。输入：正整数N(NW100)。输出：每行输出一个完美立方，按照a的值，从小到大依次输出。当两个完美立方等式中a的值相同，则依次按照b、c、d进行非降升序排列输出，即b值小的先输出、然后c值小的先输出、然后d值小的先输出。样例输入：24样例输出:Cube=6,Triple=(3,4,5)Cube=12,Triple=(6,8,10)Cube=18,Triple=(2,12,16)Cube=18,Triple=(9,12,15)Cube=19,Triple=(3,10,18)Cube=20,Triple=(7,14,17)Cube=24,Triple=(12,16,20)解题思路：此题的思路非常简单：给定4个整数的四元组(a、b、c、d)，判断它们是否满足完美立方等式a3=b3+c3+d3。对全部的四元组进行排序，依次进行判断。如果一个四元组满足完美立方等式，则按照要求输出。先判晚值小的四元组；两个四元组血值相同，则先判断b值小的；两个四元组血值和b值分别相同，则先判断c值小的。关键是解决两个方面的问题：确定全部需要判断的四元组，并对它们进行排序。稍作分析不难发现，在这个序列中，任意一个四元组(a、b、c、d)：(1)aN6，因为a最小必须是5,才能使得4c、d分别是3个大于1的不同整数，但(5、2、3、4)不满足完美立方等式的要求；(2)1<b<c<d，否则该四元组在序列中的位置就要向前移；(3)如果(a、b、c、d)满足完美立方等式，则b、c、d都要比a小。避免对一个整数的立方的重复计算。[2,N]中的每个整数i，在整个需要判断的四元组序列中都反复出现。每出现一次，就要计算一次它的立方。在开始完美立方等式的判断之前，先用一个数组保存[2,N]中的每个整数的立方值。在判断四元组(a、b、c、d)是否满足完美立方等式的要求时，直接使用存储在数组中的立方值。参考程序：#include<stdio.h>#include<math.h>intmain(){intn,a,b,c,d;longintcube[101];inti;scanf("%d”,&n);for(i=1;i<=n;i++){cube[i]=i*i*i;}for(a=6;a<=n;a++)for(b=2;b<a-1;b++){if(cube[a]<cube[b]+cube[b+1]+cube[b+2])break;for(c=b+1;c<a;c++)if(cube[a]<cube[b]+cube[c]+cube[c+1])break;for(d=c+1;d<a;d++)if(cube[a]==cube[b]+cube[c]+cube[d])printf("Cube=%d,Triple=(%d,%d,%d)\n",a,b,c,d);}}return0;}实现技巧：用一个数组来保存广N的立方，这样在判断四元组(a,b,c,d)是否是完美立方时，不3 3 3 3需要重复计算a、b、c、d。在对b循环时，如果a3<b3+(b+1)3+(b+2)3则没有必要继续搜索c和d。在对c循环时，如果a3<b3+c3+(c+1)3则没有必要继续搜索d。请思考：在最内层循环中，使用条件a3<b3+c3+d3判断是否要终止循环，能否带来性能上的提高？CS73:数字方格(来源：2747,程序设计导引及在线实践(李文新)练习2P195)问题描述：ala2密如上图，有3个方格，每个方格里面都有一个整数a1，a2,a3。已知0<=a1,a2,a3<=n，而且a1+a2是2的倍数，a2+a3是3的倍数，a1+a2+a3是5的倍数。你的任务是找到一组a1，a2，a3，使得a1+a2+a3最大。输入：输入的第一行是一个数t，表示测试数据的数目。接下来的t行，每行给出一个n(0<=n<=100)的值。输出：对于每一个n的值，输出a1+a2+a3的最大值。样例输入：203样例输出：0参考程序：#include<stdio.h>intmain(){intt,n;inta,b,c,max;scanf("%d”,&t);while(t—){scanf("%d”,&n);max=0;for(a=0;a<=n;a++){for(b=0;b<=n;b++){if((a+b)%2!=0)continue;for(c=0;c<=n;c++){if((b+c)%3!=0)continue;if((a+b+c)%5!=0)continue;if(a+b+c>max)max=a+b+c;}}}printf("%d\n”,max);}return0;}CS74:切换状态(Switch)(来源：ZOJ1622,程序设计方法及在线实践指导(王衍等)P146)问题描述：有N盏灯，排成一排。给定每盏灯的初始状态(开或关)，你的任务是计算至少要切换多少盏灯的状态(将开着的灯关掉，或将关着的灯开起来)，才能使得这N盏灯开和关交替出现。输入：输入文件中包含多个测试数据，每个测试数据占一行。首先是一个整数N，1<=N<=10000，然后是N个整数，表示这N盏灯的初始状态，1表示开着，0表示关着。测试数据一直到文件尾。输出：对每个测试数据，输出占一行，表示至少需要切换状态的灯的数目。样例输入：91001110103101样例输出：30解题分析：本题可以采取不同的枚举思路求解。N盏灯，每盏灯都有两种状态：1和0，则N盏灯共有2n种状态，从00…0到11…1，可以枚举这2n种状态，每种状态都判断一下是否是开和关交替出现，如果是，则还要统计从初始状态转换到该状态需要切换的灯的数目。但这种枚举策略势必要花费很多时间，因为N最大可以取到10000，而210000的数量级是103010。要使得N盏灯开和关交替出现，实际上只有两种可能：奇数位置上的灯是开着的，或者偶数位置上的灯是开着的。只要分别计算从N盏灯的初始状态出发，切换到这两种状态所需要切换灯的数目，取较小者即可。例如，样例输入中的第1个测试数据对应的初始状态为：100111010奇数位置上的灯开着：101010101偶数位置上的灯开着:010101010。如果将这9盏灯切换到奇数位置上的灯是开着的，需要切换6盏灯；若要切换到偶数位置上的灯是开着的，需要切换3盏灯。因此，至少需要切换3盏灯。注意到上述分析中3+6=9,9就是灯的数目N。稍加分析就可以得到以下结论：如果将N盏灯调整成奇数位置上的灯是开着的，需要调整灯的数目为numo,则将N盏灯调整为偶数位置上的灯是开着的，需要调整灯的数目nume=N-numo。因此只需要判断numo是否小于N/2,如果是，则取numo；否则取N-numo。这种思路只要枚举一种状态即可。参考程序：#include<stdio.h>intmain(){intN,i;intnumo;intlights[10001];while(scanf("%d”,&N)!=EOF){numo=0;for(i=1;i<=N;i++)scanf("%d”,&lights[i]);f