目錄

什么是枚舉法？

枚舉法的應用

1.雞兔同籠

2.韓信點兵

3.年齡問題?

4.統(tǒng)計方形

全排列?

5.火星人

?6.帶分數(shù)

---

重點算法:(1)枚舉；(2)遞推遞歸；(3)動態(tài)規(guī)劃；(4)搜索；(5)回溯。

什么是枚舉法？

暴力破解，最常用的是枚舉法，也叫窮舉法。

枚舉法是在分析問題時，逐個列舉出所有可能情況，然后根據(jù)條件判斷此答案是否合適，合適就保留，不合適就丟棄，最后得出一般結(jié)論。主要利用計算機運算速度快、精確度高的特點，對要解決問題的所有可能情況，一個不漏地進行檢驗，從中找出符合要求的答案，因此枚舉法是通過犧牲時間來換取答案的全面性。

就是通過循環(huán)或者遞歸，把所有可能的情況過一遍，符合條件就留下，不符合繼續(xù)找。

方法步驟：

1.確定枚舉對象、枚舉范圍、判斷條件。

2.循環(huán)驗證每一個解。

枚舉法的應用

1.雞兔同籠

問題：有雞兔共50頭，共有腳120只。 問 ：雞兔分別的數(shù)量？

public class Main {public static void main(String[] args) {for(int i=0;i<=50;i++) {//設雞有i只 //最小是0，最大為50，在一個循環(huán)中一個一個的測試，看哪一個條件能夠滿足題目要求int j=50-i;//設兔有j只if(2*i + 4*j==120) {//雞有2條腿，兔有4條腿System.out.println("i="+i+" "+"j="+j);}}} }

【答案】i=40 j=10

2.韓信點兵

?問題：韓信知道部隊人數(shù)大約1000人左右，具體數(shù)字不詳，5人一組剩余1人，7個人一組還剩兩個人，8個人一組還剩3個人，問：這支部隊有多少人?

public class Main {public static void main(String[] args) {for(int i=0;i<2000;i++) {if(i%5==1 && i%7==2 && i%8==3) {System.out.println("i="+i);}}} }

【答案】i=51
i=331
i=611
i=891
i=1171
i=1451
i=1731

3.年齡問題?

美國數(shù)學家維納(N.Wiener)智力早熟，11 歲就上了大學。他曾在 1935~1936 年應邀來中國清華大學講學。一次，他參加某個重要會議，年輕的臉孔引人注目。于是有人詢問他的年齡，他回答說：“我年齡的立方是個 4 位數(shù)。我年齡的 4 次方是個6 位數(shù)。這 10 個數(shù)字正好包含了從 0 到 9 這 10 個數(shù)字，每個都恰好出現(xiàn) 1 次。”
請你推算一下，他當時到底有多年輕。

【解析】界限 “我年齡的立方是個 4 位數(shù)。我年齡的 4 次方是個6 位數(shù)” 所以在 18和25 之間?

public class Main {public static void main(String[] args) {String sum;for(int i=11;i<25;i++) {sum=i*i*i+""+i*i*i*i;int j=0;while(sum.lastIndexOf(sum.charAt(j))==j) {if(j==9) {System.out.println(i);return;}j++;}}} }

【答案】18

lastIndexOf()

返回指定元素在數(shù)組中的最后一個的索引，如果不存在則返回 -1 。

chatAt()

返回指定索引位置的char值。索引范圍為0~length()-1。

如: str.charAt(0)檢索str中的第一個字符,str.charAt(str.length()-1)檢索最后一個字符。

4.統(tǒng)計方形

有一個n*m方格的棋盤，求其方格包含多少正方形、長方形
【輸入格式】
n,m規(guī)定m小于等于5000，n小于等于5000
【輸出格式】
方格包含多少正方形、長方形
輸入輸出樣例
【輸入】
2 3
【輸出】
8 10

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc=new Scanner(System.in);int n=sc.nextInt();int m=sc.nextInt();int [][ ]map=new int[n][m];long zsum=0,csum=0;//zsum是正方形，csum是長方形long sum=0;//sum是所有矩形for(int i=0;i<map.length;i++) {for(int j=0;j<map[i].length;j++) {sum+=(i+1)*(j+1);zsum+=Math.min(i+1,j+1);}}csum=sum-zsum;System.out.println(zsum+" "+csum);} }

全排列?

5.火星人

人類終于登上了火星的土地并且見到了神秘的火星人。人類和火星人都無法理解對方的語言，但是我們的科學家發(fā)明了一種用數(shù)字交流的方法。這種交流方法是這樣的，首先，火星人把一個非常大的數(shù)字告訴人類科學家，科學家破解這個數(shù)字的含義后，再把一個很小的數(shù)字加到這個大數(shù)上面，把結(jié)果告訴火星人，作為人類的回答。

火星人用一種非常簡單的方式來表示數(shù)字――掰手指。火星人只有一只手，但這只手上有成千上萬的手指，這些手指排成一列，分別編號為1,2,3…。火星人的任意兩根手指都能隨意交換位置，他們就是通過這方法計數(shù)的。

一個火星人用一個人類的手演示了如何用手指計數(shù)。如果把五根手指――拇指、食指、中指、無名指和小指分別編號為1,2,3,4和5，當它們按正常順序排列時，形成了5位數(shù)12345，當你交換無名指和小指的位置時，會形成5位數(shù)12354，當你把五個手指的順序完全顛倒時，會形成54321，在所有能夠形成的120個5位數(shù)中，12345最小，它表示1；12354第二小，它表示2；54321最大，它表示120。下表展示了只有3根手指時能夠形成的6個3位數(shù)和它們代表的數(shù)字：

三進制數(shù)

123
132
213
231
312
321

代表的數(shù)字

1
2
3
4
5
6

現(xiàn)在你有幸成為了第一個和火星人交流的地球人。一個火星人會讓你看他的手指，科學家會告訴你要加上去的很小的數(shù)。你的任務是，把火星人用手指表示的數(shù)與科學家告訴你的數(shù)相加，并根據(jù)相加的結(jié)果改變火星人手指的排列順序。輸入數(shù)據(jù)保證這個結(jié)果不會超出火星人手指能表示的范圍。
【輸入格式】共三行。
第一行一個正整數(shù)N，表示火星人手指的數(shù)目（1≤N≤10000）。
第二行是一個正整數(shù)M，表示要加上去的小整數(shù)（1≤M≤100）。
下一行是1到N這N個整數(shù)的一個排列，用空格隔開，表示火星人手指的排列順序。
【輸出格式】N個整數(shù)，表示改變后的火星人手指的排列順序。每兩個相鄰的數(shù)中間用一個空格分開，不能有多余的空格。

一個經(jīng)典全排列的變形

首先要確定給出的火星人手指排列，在全排列的第幾層
然后，相加上那個小數(shù)
然后再找到對應的層數(shù)的全排列，輸出

import java.util.Scanner;public class Main {static int N;//火星人的手指個數(shù)static int M;//加上去的一個小數(shù)字static int[] ans = new int[10000];//存儲全排列的數(shù)組static int[] book =new int[100001];//標記數(shù)組static int[] num1 =new int[10000];//火星人原始的手指個數(shù)public static void main(String[] args) {Scanner sc = new Scanner(System.in);N = sc.nextInt();M = sc.nextInt();for(int i=0;i<N;i++)num1[i] = sc.nextInt();//火星人原始的手指個數(shù)dfs(0);}static int cnt = 1;//記錄每個全排列所表達的十進制數(shù)字private static void dfs(int step) {if(step == N) {check();cnt++;return;}for(int i=1;i<=N;i++) {if(book[i] == 0) {ans[step] = i;book[i] = 1;dfs(step+1);book[i] = 0;}}}static int num2;private static void check() {int i;if(num2 ==0) {for(i=0;i<N;i++)if(num1[i] != ans[i])break;if(i == N)num2 = cnt+M;}else if(num2 == cnt)for(int j=0;j<N;j++)if(j == N-1)System.out.println(ans[j]);elseSystem.out.print(ans[j]+" ");//改變后的火星人手指的排列順序} }

?6.帶分數(shù)

100 可以表示為帶分數(shù)的形式：100 = 3 + 69258 / 714

還可以表示為：100 = 82 + 3546 / 197

注意特征：帶分數(shù)中，數(shù)字1~9分別出現(xiàn)且只出現(xiàn)一次（不包含0）。

類似這樣的帶分數(shù)，100 有 11 種表示法。

題目要求：

從標準輸入讀入一個正整數(shù)N (N<1000*1000)

程序輸出該數(shù)字用數(shù)碼1~9不重復不遺漏地組成帶分數(shù)表示的全部種數(shù)。

注意：不要求輸出每個表示，只統(tǒng)計有多少表示法！

例如：

用戶輸入：

100

程序輸出：

11

再例如：

用戶輸入：

105

程序輸出：

6

資源約定：

峰值內(nèi)存消耗（含虛擬機） < 64M

CPU消耗 < 3000ms

請嚴格按要求輸出，不要畫蛇添足地打印類似：“請您輸入…” 的多余內(nèi)容。

所有代碼放在同一個源文件中，調(diào)試通過后，拷貝提交該源碼。

注意：不要使用package語句。不要使用jdk1.6及以上版本的特性。

注意：主類的名字必須是：Main，否則按無效代碼處理。

每當形成一個全排列時，我們還要根據(jù)題意來枚舉 第一個數(shù)的大小和“ / ” 的位置

import java.util.Scanner;public class Main {static int[] fp = new int[9];static int[] book = new int[10];static int ans;static int n;public static void main(String[] args) {Scanner sc = new Scanner(System.in);n = sc.nextInt();dfs(0);System.out.println(ans);}//進行全排列public static void dfs(int step) {if(step == 9) {if(check()) ans++;return;}for(int i =1;i<=9;i++) {if(book[i] == 0) { fp[step] = i;book[i] = 1;dfs(step+1);book[i] = 0;} }}public static boolean check() {int t = n;int numCnt = 0;while(t != 0) {numCnt++;t/=10;}for(int i = 0; i < numCnt ; i++) {int sum = 0 , sums = 1;int temp = i;while(temp>=0) {sum+=fp[temp]*sums;sums*=10;temp--;}// " / "的位置for(int j = i+4; j<9;j++) {//計算int fz=0,fm=0,fzs=1,fms=1;for(int k = 8; k > i;k--) {if(k <= j) {fz+=fp[k]*fzs;fzs*=10;}else {fm+=fp[k]*fms;fms*=10;}}//整數(shù)if(fz!=0 && fm!=0 && fz/fm == (float)fz/fm && fz/fm < n) {if(sum+fz/fm == n)return true;}}}return false;} }

總結(jié)

以上是生活随笔為你收集整理的蓝桥杯Java——枚举法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。