穷举及其优化.ppt

《穷举及其优化.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、穷举及其优化泰州二附中谢志锋例1、一个火星人用一个人类的手演示了如何用手指计数。如果把五根手指——拇指、食指、中指、无名指和小指分别编号为1，2，3，4和5，当它们按正常顺序排列时，形成了5位数12345，当你交换无名指和小指的位置时，会形成5位数12354，当你把五个手指的顺序完全颠倒时，会形成54321，在所有能够形成的120个5位数中，12345最小，它表示1；12354第二小，它表示2；54321最大，它表示120。下表展示了只有3根手指时能够形成的6个3位数和它们代表的数字：三进制数1231322132

2、31312321代表的数字123456现在你有幸成为了第一个和火星人交流的地球人。一个火星人会让你看他的手指，科学家会告诉你要加上去的很小的数。你的任务是，把火星人用手指表示的数与科学家告诉你的数相加，并根据相加的结果改变火星人手指的排列顺序。输入数据保证这个结果不会超出火星人手指能表示的范围。【样例输入】5312345【样例输出】12453【数据规模】对于30%的数据，N<=15；对于60%的数据，N<=50；对于全部的数据，N<=10000；问题分析直接穷举，因为数据较大显然不能达到目的，由于本题本质上是求全

3、排列，这里用生成法求全排列比较合适。read(n);read(m);fori:=1tondoread(a[i]);t:=0;a[0]:=0;whilea[0]=0dobeginj:=n;whilea[j]a[j-1])and(a[i]

4、-1dofory:=j+1tondoifa[x]>a[y]thenbegintemp:=a[x];a[x]:=a[y];a[y]:=temp;end;t:=t+1;ift=mthenbreak;end;例2、选数：已知n（1<=n<=20）个整数x1,x2,…,xn（1<=xi<=5000000），以及一个整数k（k

5、=38,3+12+19=34。现在，要求你计算出和为素数的组合共有多少种。如上例中，只有一种组合的和为素数：3+7+19=29。输入：n,kx1，x2，…，xn输出：一个整数(满足条件的组合个数)样例输入：43371219输出：1分析：本题可分解成以下两部分：从n个数中任取k个数的组合因为n<=20，所以可以用穷举实现。用数组a[1],a[2],…,a[k]记录每种组合中各数的下标，a[0]是循环开关，初始时a[0]=0，当a[0]=1时穷举结束。当选用前面的输入样例，n=4，k=3时，a[0]～a[3]的变化如

6、下表所示：a[0]a[1],a[2]a[3]生成的组合01233712012437190134312190234712191234循环结束②判断一个整数是否为素数判断一个整数P(P>1)是否为素数最简单的方法就是看是否存在一个素数a(a<=sqrt(P))是P的约数，如果不存在，该数就为素数。由于在此题中1<=xi<=5000000，n<=20，所以要判断的数P不会超过100000000，sqrt(p)<=10000，因此，为了加快速度，我们可以用筛选法先将2…10000之间的素数保存到一个数组里（共1229个）

7、，这样速度估计将提高许多。生成法求组合fori:=0tokdoa[i]:=i;{产生第一种组合}whilea[0]=0dobeginsum:=0;{sum是累加器，求当前组合的k个整数之和}fori:=1tokdosum:=sum+x[a[i]];iffit(sum)thentotal:=total+1;{验证当前组合的k个整数之和是否为素数}j:=k;whilea[j]=n-k+jdoj:=j-1;a[j]:=a[j]+1;{产生一种新的组合}fori:=j+1tokdoa[i]:=a[i-1]+1;end;例

8、3、除法运算（NOIP1995初中组复赛第一题）设有下列的除法算式：请根据上述算式中的信息求出被除数和除数。分析：设除数为x，被除数为y，由算式信息可知：10<=x<=99，1000<=y<=9999，且8*x<=99，9*x>=100。因此，我们可选择枚举除数，而被除数则可按公式y=809*x+1计算得出。varx,y:integer;beginforx:=10to99