窮舉及其優(yōu)化.ppt

《窮舉及其優(yōu)化.ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、窮舉及其優(yōu)化泰州二附中謝志鋒例1、一個(gè)火星人用一個(gè)人類的手演示了如何用手指計(jì)數(shù)。如果把五根手指——拇指、食指、中指、無(wú)名指和小指分別編號(hào)為1，2，3，4和5，當(dāng)它們按正常順序排列時(shí)，形成了5位數(shù)12345，當(dāng)你交換無(wú)名指和小指的位置時(shí)，會(huì)形成5位數(shù)12354，當(dāng)你把五個(gè)手指的順序完全顛倒時(shí)，會(huì)形成54321，在所有能夠形成的120個(gè)5位數(shù)中，12345最小，它表示1；12354第二小，它表示2；54321最大，它表示120。下表展示了只有3根手指時(shí)能夠形成的6個(gè)3位數(shù)和它們代表的數(shù)字：三進(jìn)制數(shù)1231322132

2、31312321代表的數(shù)字123456現(xiàn)在你有幸成為了第一個(gè)和火星人交流的地球人。一個(gè)火星人會(huì)讓你看他的手指，科學(xué)家會(huì)告訴你要加上去的很小的數(shù)。你的任務(wù)是，把火星人用手指表示的數(shù)與科學(xué)家告訴你的數(shù)相加，并根據(jù)相加的結(jié)果改變火星人手指的排列順序。輸入數(shù)據(jù)保證這個(gè)結(jié)果不會(huì)超出火星人手指能表示的范圍?！緲永斎搿?312345【樣例輸出】12453【數(shù)據(jù)規(guī)?！繉?duì)于30%的數(shù)據(jù)，N<=15；對(duì)于60%的數(shù)據(jù)，N<=50；對(duì)于全部的數(shù)據(jù)，N<=10000；問(wèn)題分析直接窮舉，因?yàn)閿?shù)據(jù)較大顯然不能達(dá)到目的，由于本題本質(zhì)上是求全

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、選數(shù)：已知n（1<=n<=20）個(gè)整數(shù)x1,x2,…,xn（1<=xi<=5000000），以及一個(gè)整數(shù)k（k

5、=38,3+12+19=34?，F(xiàn)在，要求你計(jì)算出和為素?cái)?shù)的組合共有多少種。如上例中，只有一種組合的和為素?cái)?shù)：3+7+19=29。輸入：n,kx1，x2，…，xn輸出：一個(gè)整數(shù)(滿足條件的組合個(gè)數(shù))樣例輸入：43371219輸出：1分析：本題可分解成以下兩部分：從n個(gè)數(shù)中任取k個(gè)數(shù)的組合因?yàn)閚<=20，所以可以用窮舉實(shí)現(xiàn)。用數(shù)組a[1],a[2],…,a[k]記錄每種組合中各數(shù)的下標(biāo)，a[0]是循環(huán)開(kāi)關(guān)，初始時(shí)a[0]=0，當(dāng)a[0]=1時(shí)窮舉結(jié)束。當(dāng)選用前面的輸入樣例，n=4，k=3時(shí)，a[0]～a[3]的變化如

6、下表所示：a[0]a[1],a[2]a[3]生成的組合01233712012437190134312190234712191234循環(huán)結(jié)束②判斷一個(gè)整數(shù)是否為素?cái)?shù)判斷一個(gè)整數(shù)P(P>1)是否為素?cái)?shù)最簡(jiǎn)單的方法就是看是否存在一個(gè)素?cái)?shù)a(a<=sqrt(P))是P的約數(shù)，如果不存在，該數(shù)就為素?cái)?shù)。由于在此題中1<=xi<=5000000，n<=20，所以要判斷的數(shù)P不會(huì)超過(guò)100000000，sqrt(p)<=10000，因此，為了加快速度，我們可以用篩選法先將2…10000之間的素?cái)?shù)保存到一個(gè)數(shù)組里（共1229個(gè)）

7、，這樣速度估計(jì)將提高許多。生成法求組合fori:=0tokdoa[i]:=i;{產(chǎn)生第一種組合}whilea[0]=0dobeginsum:=0;{sum是累加器，求當(dāng)前組合的k個(gè)整數(shù)之和}fori:=1tokdosum:=sum+x[a[i]];iffit(sum)thentotal:=total+1;{驗(yàn)證當(dāng)前組合的k個(gè)整數(shù)之和是否為素?cái)?shù)}j:=k;whilea[j]=n-k+jdoj:=j-1;a[j]:=a[j]+1;{產(chǎn)生一種新的組合}fori:=j+1tokdoa[i]:=a[i-1]+1;end;例

8、3、除法運(yùn)算（NOIP1995初中組復(fù)賽第一題）設(shè)有下列的除法算式：請(qǐng)根據(jù)上述算式中的信息求出被除數(shù)和除數(shù)。分析：設(shè)除數(shù)為x，被除數(shù)為y，由算式信息可知：10<=x<=99，1000<=y<=9999，且8*x<=99，9*x>=100。因此，我們可選擇枚舉除數(shù)，而被除數(shù)則可按公式y(tǒng)=809*x+1計(jì)算得出。varx,y:integer;beginforx:=10to99