期末復(fù)習(xí)網(wǎng)協(xié)串講窮舉篇

1、枚舉法- Dr. Meyerby 阿基里斯何為枚舉？枚舉是指從可能的集合中一一枚舉各個(gè)元素，用題目給定的約束條件判定哪些是無用的，哪些是有用的。能使命題成立者，即為問題的解。枚舉法的基本思路確定枚舉對(duì)象、枚舉范圍和判定條件。一一枚舉可能的解，驗(yàn)證是否是問題的解。例題：平方和的解求 的正整數(shù)解。問題分析ConceptGameTestExam 這道題顯然是一道枚舉題，因此我們可設(shè)定兩個(gè)變量X、Y，令它們進(jìn)行循環(huán)，當(dāng)它們平方和為2000時(shí)輸出結(jié)果即可。枚舉范圍如何定？ConceptGameTestExam 我們可以算出45*452000，因此我們可以得到X、Y的范圍都是145。再開二重循環(huán)即可。#i

2、ncludestdio.h#includestdlib.hint main( ) int X , Y ; for( X = 1 ; X 45 ; X + ) /X從1開始循環(huán) for( Y = 1 ; Y 2000 ) break ; system(pause) ; return 0 ;代碼實(shí)現(xiàn)：例題：整數(shù)分解例如：1998 =10000，是一個(gè)累加和等于N的連續(xù)的自然數(shù)段。輸出每個(gè)累加和等于N的連續(xù)的自然數(shù)段的第一個(gè)數(shù)和最后一個(gè)數(shù)，兩個(gè)數(shù)之間用符號(hào)隔開，每段一行，所有行按每行的第一個(gè)數(shù)從小到大升序排列。如果沒有符合條件的自然數(shù)段，輸出None。問題分析ConceptGameTestExam

3、采用枚舉法解決此題的時(shí)候，很容易想到的一種方法是：設(shè)兩個(gè)變量（枚舉對(duì)象），一個(gè)是數(shù)段的始端left，另一個(gè)數(shù)是數(shù)段的尾端right。進(jìn)行循環(huán)時(shí)，先將始端定下來，再讓尾端進(jìn)行移動(dòng)。當(dāng)數(shù)段之和為輸入的整數(shù)時(shí)，輸出當(dāng)前結(jié)果。枚舉范圍如何定？ConceptGameTestExam 因?yàn)槲覀兪褂玫氖莍nt型變量，當(dāng)N為偶數(shù)時(shí)，N/2+N/2+1=N+1；N為奇數(shù)時(shí)，N/2+N/2+ 1=N。left從1開始，最多不能超過N/2。right從left+1開始，最多不能超過N/2+1。#includestdio.h#includestdlib.hint main( ) int N ; int left ,

4、right , flag = 0 ; /left為數(shù)段始端的數(shù)，right為數(shù)段尾端的數(shù)，flag為是否有解的標(biāo)志 scanf(%d,&N) ; for( left = 1 ; left = N / 2 ; left + ) /left從1開始循環(huán) for( right = left + 1 ; right = ( N / 2 + 1 ) ; right + ) /right從left+1開始循環(huán) if( N = ( left + right ) * ( right - left + 1 ) / 2 ) /數(shù)列段之和為N flag = 1 ; printf(%d%dn,left,right)

5、; break ; if( flag = 0 ) printf(Nonen) ; system(pause) ; return 0 ;代碼實(shí)現(xiàn)：?jiǎn)栴}優(yōu)化在上面的代碼中，電腦進(jìn)行了很多次不必要的計(jì)算，例如：輸入10000，當(dāng)left=2000，right從2001開始循環(huán)，循環(huán)至2003時(shí)，數(shù)列段之和為2000 =8006,循環(huán)至2004時(shí)，數(shù)列之和為2000 =10010。此時(shí)right再往后的循環(huán)已經(jīng)沒必要計(jì)算了。因此我們可以在循壞內(nèi)加入一個(gè)判斷條件，當(dāng)數(shù)列段之和大于N時(shí)，跳出小循環(huán)，進(jìn)行下一次大循環(huán)。#includestdio.h#includestdlib.hint main( ) in

6、t N ; int left , right , flag = 0 ; /left為數(shù)段始端的數(shù)，right為數(shù)段尾端的數(shù)，flag為是否有解的標(biāo)志 scanf(%d,&N) ; for( left = 1 ; left = N / 2 ; left + ) /left從1開始循環(huán) for( right = left + 1 ; right = ( N / 2 + 1 ) ; right + ) /right從left+1開始循環(huán) if( N = ( left + right ) * ( right - left + 1 ) / 2 ) /數(shù)列段之和為n flag = 1 ; printf(%

7、d%dn,left,right) ; break ; if( N =N的最小整數(shù)解。解二元一次方程得： 因?yàn)長(zhǎng)ength為整數(shù)解，在此將它放縮為N/2+1，N等于3時(shí)兩者相等。 left的最小值為1，left后面的數(shù)一定大于left，因此left的最大值一定小于等于N/Length,N=3時(shí)兩者相等，可將它放縮為N/Length。#includestdio.h#includestdlib.hint main( ) int N ; int Length , left , flag = 0 ; /Length為數(shù)列段長(zhǎng)度，left為數(shù)段始端的數(shù)，flag為是否有解的標(biāo)志 scanf(%d,&N) ; for( Length = ( 1 +N / 2 ) ; Length = 2 ; Length - ) /Length從(1+N/2)開始循環(huán) for( left = 1 ; left = N / Length ; left + ) /left從1開始循環(huán) if( N = ( ( 2 * left + Length - 1 ) * Length / 2 ) /數(shù)列段之和為n flag = 1 ; printf(%d%dn