ACM入門學什么

初學者建議購買，《算法競賽入門經(jīng)典》 劉汝佳作，十分好，在深入可以是他的另外一本，黑書，《算法藝術(shù)與信息學競賽》。

創(chuàng)新互聯(lián)公司一直通過網(wǎng)站建設(shè)和網(wǎng)站營銷幫助企業(yè)獲得更多客戶資源。 以"深度挖掘，量身打造，注重實效"的一站式服務，以成都網(wǎng)站建設(shè)、成都網(wǎng)站設(shè)計、移動互聯(lián)產(chǎn)品、成都營銷網(wǎng)站建設(shè)服務為核心業(yè)務。十余年網(wǎng)站制作的經(jīng)驗，使用新網(wǎng)站建設(shè)技術(shù)，全新開發(fā)出的標準網(wǎng)站，不但價格便宜而且實用、靈活，特別適合中小公司網(wǎng)站制作。網(wǎng)站管理系統(tǒng)簡單易用，維護方便，您可以完全操作網(wǎng)站資料，是中小公司快速網(wǎng)站建設(shè)的選擇。

計劃：

ACM的算法（覺得很好，有層次感）POJ上的一些水題(可用來練手和增加自信)

(poj3299,poj2159,poj2739,poj1083,poj2262,poj1503,poj3006,poj2255,poj3094)

初期:

一.基本算法:

(1)枚舉. (poj1753,poj2965)

(2)貪心(poj1328,poj2109,poj2586)

(3)遞歸和分治法.

(4)遞推.

(5)構(gòu)造法.(poj3295)

(6)模擬法.(poj1068,poj2632,poj1573,poj2993,poj2996)

二.圖算法:

(1)圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷.

(2)最短路徑算法(dijkstra,bellman-ford,floyd,heap+dijkstra)

(poj1860,poj3259,poj1062,poj2253,poj1125,poj2240)

(3)最小生成樹算法(prim,kruskal)

(poj1789,poj2485,poj1258,poj3026)

(4)拓撲排序 (poj1094)

(5)二分圖的最大匹配 (匈牙利算法) (poj3041,poj3020)

(6)最大流的增廣路算法(KM算法). (poj1459,poj3436)

三.數(shù)據(jù)結(jié)構(gòu).

(1)串 (poj1035,poj3080,poj1936)

(2)排序(快排、歸并排(與逆序數(shù)有關(guān))、堆排) (poj2388,poj2299)

(3)簡單并查集的應用.

(4)哈希表和二分查找等高效查找法(數(shù)的Hash,串的Hash)

(poj3349,poj3274,POJ2151,poj1840,poj2002,poj2503)

(5)哈夫曼樹(poj3253)

(6)堆

(7)trie樹(靜態(tài)建樹、動態(tài)建樹) (poj2513)

四.簡單搜索

(1)深度優(yōu)先搜索 (poj2488,poj3083,poj3009,poj1321,poj2251)

(2)廣度優(yōu)先搜索(poj3278,poj1426,poj3126,poj3087.poj3414)

(3)簡單搜索技巧和剪枝(poj2531,poj1416,poj2676,1129)

五.動態(tài)規(guī)劃

(1)背包問題. (poj1837,poj1276)

(2)型如下表的簡單DP(可參考lrj的書 page149):

1.E[j]=opt{D[i]+w(i,j)} (poj3267,poj1836,poj1260,poj2533)

2.E[i,j]=opt{D[i-1,j]+xi,D[i,j-1]+yj,D[i-1][j-1]+zij} (最長公共子序列)

(poj3176,poj1080,poj1159)

3.C[i,j]=w[i,j]+opt{C[i,k-1]+C[k,j]}.(最優(yōu)二分檢索樹問題)

六.數(shù)學

(1)組合數(shù)學:

1.加法原理和乘法原理.

2.排列組合.

3.遞推關(guān)系.

(POJ3252,poj1850,poj1019,poj1942)

(2)數(shù)論.

1.素數(shù)與整除問題

2.進制位.

3.同余模運算.

(poj2635, poj3292,poj1845,poj2115)

(3)計算方法.

1.二分法求解單調(diào)函數(shù)相關(guān)知識.(poj3273,poj3258,poj1905,poj3122)

七.計算幾何學.

(1)幾何公式.

(2)叉積和點積的運用(如線段相交的判定,點到線段的距離等). (poj2031,poj1039)

(3)多邊型的簡單算法(求面積)和相關(guān)判定(點在多邊型內(nèi),多邊型是否相交)

(poj1408,poj1584)

(4)凸包. (poj2187,poj1113)

中級:

一.基本算法:

(1)C++的標準模版庫的應用. (poj3096,poj3007)

(2)較為復雜的模擬題的訓練(poj3393,poj1472,poj3371,poj1027,poj2706)

二.圖算法:

(1)差分約束系統(tǒng)的建立和求解. (poj1201,poj2983)

(2)最小費用最大流(poj2516,poj2516,poj2195)

(3)雙連通分量(poj2942)

(4)強連通分支及其縮點.(poj2186)

(5)圖的割邊和割點(poj3352)

(6)最小割模型、網(wǎng)絡(luò)流規(guī)約(poj3308, )

三.數(shù)據(jù)結(jié)構(gòu).

(1)線段樹. (poj2528,poj2828,poj2777,poj2886,poj2750)

(2)靜態(tài)二叉檢索樹. (poj2482,poj2352)

(3)樹狀樹組(poj1195,poj3321)

(4)RMQ. (poj3264,poj3368)

(5)并查集的高級應用. (poj1703,2492)

(6)KMP算法. (poj1961,poj2406)

四.搜索

(1)最優(yōu)化剪枝和可行性剪枝

(2)搜索的技巧和優(yōu)化 (poj3411,poj1724)

(3)記憶化搜索(poj3373,poj1691)

五.動態(tài)規(guī)劃

(1)較為復雜的動態(tài)規(guī)劃(如動態(tài)規(guī)劃解特別的施行商問題等)

(poj1191,poj1054,poj3280,poj2029,poj2948,poj1925,poj3034)

(2)記錄狀態(tài)的動態(tài)規(guī)劃. (POJ3254,poj2411,poj1185)

(3)樹型動態(tài)規(guī)劃(poj2057,poj1947,poj2486,poj3140)

六.數(shù)學

(1)組合數(shù)學:

1.容斥原理.

2.抽屜原理.

3.置換群與Polya定理(poj1286,poj2409,poj3270,poj1026).

4.遞推關(guān)系和母函數(shù).

(2)數(shù)學.

1.高斯消元法(poj2947,poj1487, poj2065,poj1166,poj1222)

2.概率問題. (poj3071,poj3440)

3.GCD、擴展的歐幾里德(中國剩余定理) (poj3101)

(3)計算方法.

1.0/1分數(shù)規(guī)劃. (poj2976)

2.三分法求解單峰(單谷)的極值.

3.矩陣法(poj3150,poj3422,poj3070)

4.迭代逼近(poj3301)

(4)隨機化算法(poj3318,poj2454)

(5)雜題.

(poj1870,poj3296,poj3286,poj1095)

七.計算幾何學.

(1)坐標離散化.

(2)掃描線算法(例如求矩形的面積和周長并,常和線段樹或堆一起使用).

(poj1765,poj1177,poj1151,poj3277,poj2280,poj3004)

(3)多邊形的內(nèi)核(半平面交)(poj3130,poj3335)

(4)幾何工具的綜合應用.(poj1819,poj1066,poj2043,poj3227,poj2165,poj3429)

高級:

一.基本算法要求:

(1)代碼快速寫成,精簡但不失風格

(poj2525,poj1684,poj1421,poj1048,poj2050,poj3306)

(2)保證正確性和高效性. poj3434

二.圖算法:

(1)度限制最小生成樹和第K最短路. (poj1639)

(2)最短路,最小生成樹,二分圖,最大流問題的相關(guān)理論(主要是模型建立和求解)

(poj3155, poj2112,poj1966,poj3281,poj1087,poj2289,poj3216,poj2446

(3)最優(yōu)比率生成樹. (poj2728)

(4)最小樹形圖(poj3164)

(5)次小生成樹.

(6)無向圖、有向圖的最小環(huán)

三.數(shù)據(jù)結(jié)構(gòu).

(1)trie圖的建立和應用. (poj2778)

(2)LCA和RMQ問題(LCA(最近公共祖先問題) 有離線算法(并查集+dfs) 和 在線算法

(RMQ+dfs)).(poj1330)

(3)雙端隊列和它的應用(維護一個單調(diào)的隊列,常常在動態(tài)規(guī)劃中起到優(yōu)化狀態(tài)轉(zhuǎn)移的

目的). (poj2823)

(4)左偏樹(可合并堆).

(5)后綴樹(非常有用的數(shù)據(jù)結(jié)構(gòu),也是賽區(qū)考題的熱點).

(poj3415,poj3294)

四.搜索

(1)較麻煩的搜索題目訓練(poj1069,poj3322,poj1475,poj1924,poj2049,poj3426)

(2)廣搜的狀態(tài)優(yōu)化:利用M進制數(shù)存儲狀態(tài)、轉(zhuǎn)化為串用hash表判重、按位壓縮存儲狀態(tài)、雙向廣搜、A*算法. (poj1768,poj1184,poj1872,poj1324,poj2046,poj1482)

(3)深搜的優(yōu)化:盡量用位運算、一定要加剪枝、函數(shù)參數(shù)盡可能少、層數(shù)不易過大、可以考慮雙向搜索或者是輪換搜索、IDA*算法. (poj3131,poj2870,poj2286)

五.動態(tài)規(guī)劃

(1)需要用數(shù)據(jù)結(jié)構(gòu)優(yōu)化的動態(tài)規(guī)劃.

(poj2754,poj3378,poj3017)

(2)四邊形不等式理論.

(3)較難的狀態(tài)DP(poj3133)

六.數(shù)學

(1)組合數(shù)學.

1.MoBius反演(poj2888,poj2154)

2.偏序關(guān)系理論.

(2)博奕論.

1.極大極小過程(poj3317,poj1085)

2.Nim問題.

七.計算幾何學.

(1)半平面求交(poj3384,poj2540)

(2)可視圖的建立(poj2966)

(3)點集最小圓覆蓋.

(4)對踵點(poj2079)

八.綜合題.

(poj3109,poj1478,poj1462,poj2729,poj2048,poj3336,poj3315,poj2148,poj1263)gsyagsy 2007-11-29 00:22

以及補充 Dp狀態(tài)設(shè)計與方程總結(jié)

1.不完全狀態(tài)記錄

1青蛙過河問題

2利用區(qū)間dp

2.背包類問題

1 0-1背包，經(jīng)典問題

2無限背包，經(jīng)典問題

3判定性背包問題

4帶附屬關(guān)系的背包問題

5 + -1背包問題

6雙背包求最優(yōu)值

7構(gòu)造三角形問題

8帶上下界限制的背包問題(012背包)

3.線性的動態(tài)規(guī)劃問題

1積木游戲問題

2決斗（判定性問題）

3圓的最大多邊形問題

4統(tǒng)計單詞個數(shù)問題

5棋盤分割

6日程安排問題

7最小逼近問題(求出兩數(shù)之比最接近某數(shù)/兩數(shù)之和等于某數(shù)等等)

8方塊消除游戲(某區(qū)間可以連續(xù)消去求最大效益)

9資源分配問題

10數(shù)字三角形問題

11漂亮的打印

12郵局問題與構(gòu)造答案

13最高積木問題

14兩段連續(xù)和最大

152次冪和問題

16N個數(shù)的最大M段子段和

17交叉最大數(shù)問題

4.判定性問題的dp(如判定整除、判定可達性等)

1模K問題的dp

2特殊的模K問題，求最大(最小)模K的數(shù)

3變換數(shù)問題

5.單調(diào)性優(yōu)化的動態(tài)規(guī)劃

11-SUM問題

22-SUM問題

3序列劃分問題(單調(diào)隊列優(yōu)化)

6.剖分問題(多邊形剖分/石子合并/圓的剖分/乘積最大)

1凸多邊形的三角剖分問題

2乘積最大問題

3多邊形游戲(多邊形邊上是操作符,頂點有權(quán)值)

4石子合并(N^3/N^2/NLogN各種優(yōu)化)

7.貪心的動態(tài)規(guī)劃

1最優(yōu)裝載問題

2部分背包問題

3乘船問題

4貪心策略

5雙機調(diào)度問題Johnson算法

8.狀態(tài)dp

1牛仔射擊問題(博弈類)

2哈密頓路徑的狀態(tài)dp

3兩支點天平平衡問題

4一個有向圖的最接近二部圖

9.樹型dp

1完美服務器問題(每個節(jié)點有3種狀態(tài))

2小胖守皇宮問題

3網(wǎng)絡(luò)收費問題

4樹中漫游問題

5樹上的博弈

6樹的最大獨立集問題

7樹的最大平衡值問題

8構(gòu)造樹的最小環(huán)

參加ACM大賽應該準備哪些課程？

課程：

（1）基本算法: 二分,分治，貪心

（2） 離散數(shù)學離散數(shù)學動態(tài)規(guī)劃

（3） 搜索算法：深度優(yōu)先 搜索，廣度優(yōu)先搜?A*算法 ，阿爾法貝塔剪枝

（4）數(shù)據(jù)結(jié)構(gòu):??線段樹, 樹狀數(shù)組，并查集,Trie圖

（5）圖論問題：最小生成樹 最短路 強連通分量、橋和割點

（6）網(wǎng)絡(luò)流算法：基本的網(wǎng)絡(luò)流算法，Dinic算法，帶上下界的網(wǎng)絡(luò)流，最小費用流

（7）計算幾何：線與線求交，線與面求交，求凸包，半平面求交等

（8） 離散數(shù)學，高等數(shù)學，線性代數(shù)，初等數(shù)論，計算幾何

（9）計算機專業(yè)英語

（10）C++；基礎(chǔ)的遞歸、枚舉算法

擴展資料：

1.參賽隊伍最多由三名參賽隊員組成。

2.競賽中命題10題左右，試題描述為英文，比賽時間為5個小時，前四個小時可以實時看到排名，最后一小時封榜，無法看到排名。

3.競賽可以使用的語言：Java, C, C++, Kotlin 和 Python。

4.重點考察選手的算法和程序設(shè)計能力，不考察實際工程中常用的系統(tǒng)編程，多線程編程等等；

5.選手可攜帶任何非電子類資料，包括書籍和打印出來的程序等，部分賽區(qū)會對選手攜帶的紙質(zhì)資料做限制。

6.評委負責將結(jié)果（正確或出錯的類型）通過網(wǎng)絡(luò)盡快返回給選手，除此之外不提供任何額外幫助；

7.每個題目對應一種顏色的氣球，通過該題目的隊伍會得到對應顏色氣球。每道題目第一支解決掉它的隊還會額外獲得一個“FIRST PROBLEM SOLVED”的氣球。

參考資料：北京大學暑期課：ACM/ICPC競賽訓練

百度百科-ACM國際大學生程序設(shè)計競賽

java軟件開發(fā)的代碼規(guī)范

1、組織與風格

(1).關(guān)鍵詞和操作符之間加適當?shù)目崭瘛?/p>

(2).相對獨立的程序塊與塊之間加空行

(3).較長的語句、表達式等要分成多行書寫。

(4).劃分出的新行要進行適應的縮進，使排版整齊，語句可讀。

(5).長表達式要在低優(yōu)先級操作符處劃分新行，操作符放在新行之首。

(6).循環(huán)、判斷等語句中若有較長的表達式或語句，則要進行適應的劃分。

(7).若函數(shù)或過程中的參數(shù)較長，則要進行適當?shù)膭澐帧?/p>

(8).不允許把多個短語句寫在一行中，即一行只寫一條語句。

(9).函數(shù)或過程的開始、結(jié)構(gòu)的定義及循環(huán)、判斷等語句中的代碼都要采用縮進風格。

注：如果大家有興趣可以到安安DIY創(chuàng)作室博客，有相關(guān)說明性的文章和解釋。

2、注解

Java 的語法與 C++ 及為相似，那么，你知道 Java 的注釋有幾種嗎？是兩種？

// 注釋一行

/* ...... */ 注釋若干行

不完全對，除了以上兩種之外，還有第三種，文檔注釋：

/** ...... */ 注釋若干行，并寫入 javadoc 文檔

注釋要簡單明了。

String userName = null; //用戶名

邊寫代碼邊注釋，修改代碼同時修改相應的注釋，以保證注釋與代碼的一致性。

在必要的地方注釋，注釋量要適中。注釋的內(nèi)容要清楚、明了，含義準確，防止注釋二義性。

保持注釋與其描述的代碼相鄰，即注釋的就近原則。

對代碼的注釋應放在其上方相鄰位置，不可放在下面。對數(shù)據(jù)結(jié)構(gòu)的注釋應放在其上方相鄰位置，不可放在下面；對結(jié)構(gòu)中的每個域的注釋應放在此域的右方；

同一結(jié)構(gòu)中不同域的注釋要對齊。

變量、常量的注釋應放在其上方相鄰位置或右方。

全局變量要有較詳細的注釋，包括對其功能、取值范圍、哪些函數(shù)或過程存取它以及存取時注意事項等的說明。

在每個源文件的頭部要有必要的注釋信息，包括：文件名；版本號；作者；生成日期；模塊功能描述（如功能、主要算法、內(nèi)部各部分之間的關(guān)系、該文件與其它文件關(guān)系等）；主要函數(shù)或過程清單及本文件歷史修改記錄等。

/**

* Copy Right Information : Neusoft IIT

* Project : eTrain

* JDK version used : jdk1.3.1

* Comments : config path

* Version : 1.01

* Modification history :2003.5.1

* Sr Date Modified By Why What is modified

* 1. 2003.5.2 Kevin Gao new

**/

在每個函數(shù)或過程的前面要有必要的注釋信息，包括：函數(shù)或過程名稱；功能描述；輸入、輸出及返回值說明；調(diào)用關(guān)系及被調(diào)用關(guān)系說明等

/**

* Description :checkout 提款

* @param Hashtable cart info

* @param OrderBean order info

* @return String

*/

public String checkout(Hashtable htCart,

OrderBean orderBean)

throws Exception{

}

javadoc注釋標簽語法

@author 對類的說明 標明開發(fā)該類模塊的作者

@version 對類的說明 標明該類模塊的版本

@see 對類、屬性、方法的說明 參考轉(zhuǎn)向，也就是相關(guān)主題

@param 對方法的說明 對方法中某參數(shù)的說明

@return 對方法的說明 對方法返回值的說明

@exception 對方法的說明 對方法可能拋出的異常進行說明

3、命名規(guī)范

定義這個規(guī)范的目的是讓項目中所有的文檔都看起來像一個人寫的，增加可讀性，減少項目組中因為換人而帶來的損失。（這些規(guī)范并不是一定要絕對遵守，但是一定要讓程序有良好的可讀性）較短的單詞可通過去掉元音形成縮寫；要不然最后自己寫的代碼自己都看不懂了，那可不行。

較長的單詞可取單詞的頭幾發(fā)符的優(yōu)先級，并用括號明確表達式的操作順序，避免使用默認優(yōu)先級。

使用匈牙利表示法

Package 的命名

Package 的名字應該都是由一個小寫單詞組成。

package com.neu.util

Class 的命名

Class 的名字必須由大寫字母開頭而其他字母都小寫的單詞組成,對于所有標識符，其中包含的所有單詞都應緊靠在一起，而且大寫中間單詞的首字母。

public class ThisAClassName{}

Class 變量的命名

變量的名字必須用一個小寫字母開頭。后面的單詞用大寫字母開頭

userName , thisAClassMethod

Static Final 變量的命名

static Final 變量的名字應該都大寫，并且指出完整含義。

/**

*DBConfig PATH

**/

public static final String

DB_CONFIG_FILE_PATH =com.neu.etrain.dbconfig;

參數(shù)的命名

參數(shù)的名字必須和變量的命名規(guī)范一致。

數(shù)組的命名

數(shù)組應該總是用下面的方式來命名：

byte[] buffer;

而不是：

byte buffer[];

方法的參數(shù)

使用有意義的參數(shù)命名，如果可能的話，使用和要賦值的字段一樣的名字：

SetCounter(int size){

this.size = size;

}

4、文件樣式

所有的 Java(*.java) 文件都必須遵守如下的樣式規(guī)則：

版權(quán)信息

版權(quán)信息必須在 java 文件的開頭，比如：

/*

* Copyright ? 2000 Shanghai XXX Co. Ltd.

* All right reserved.

*/

其他不需要出現(xiàn)在 javadoc 的信息也可以包含在這里。

Package/Imports

package 行要在 import 行之前，import 中標準的包名要在本地的包名之前，而且按照字母

順序排列。如果 import 行中包含了同一個包中的不同子目錄，則應該用 * 來處理。

package hotlava.net.stats;

import java io.*;

import java.util.Observable;

import hotlava.util.Application;

這里 java。io.* 使用來代替InputStream and OutputStream 的。

Class

接下來的是類的注釋，一般是用來解釋類的。

/**

* A class representing a set of packet and byte counters

* It is observable to allow it to be watched, but only

* reports changes when the current set is complete

*/

接下來是類定義，包含了在不同的行的 extends 和 implements

public class CounterSet

extends Observable

implements Cloneable

Class Fields

接下來是類的成員變量：

/**

* Packet counters

*/

protected int[] packets;

public 的成員變量必須生成文檔（JavaDoc）。proceted、private和 package 定義的成

員變量如果名字含義明確的話，可以沒有注釋。

存取方法

接下來是類變量的存取的方法。它只是簡單的用來將類的變量賦值獲取值的話，可以簡單的

寫在一行上。

/**

* Get the counters

* @return an array containing the statistical data. This array has been

* freshly allocated and can be modified by the caller.

*/

public int[] getPackets() { return copyArray(packets, offset); }

public int[] getBytes() { return copyArray(bytes, offset); }

public int[] getPackets() { return packets; }

public void setPackets(int[] packets) { this.packets = packets; }

其它的方法不要寫在一行上

構(gòu)造函數(shù)

接下來是構(gòu)造函數(shù)，它應該用遞增的方式寫（比如：參數(shù)多的寫在后面）。

訪問類型 (public, private 等.) 和 任何 static, final 或 synchronized 應該在一行

中，并且方法和參數(shù)另寫一行，這樣可以使方法和參數(shù)更易讀。

public

CounterSet(int size){

this.size = size;

}

克隆方法

如果這個類是可以被克隆的，那么下一步就是 clone 方法：

public

Object clone() {

try {

CounterSet obj = (CounterSet)super.clone();

obj.packets = (int[])packets.clone();

obj.size = size;

return obj;

}catch(CloneNotSupportedException e) {

throw new InternalError(Unexpected CloneNotSUpportedException: +

e.getMessage());

}

}

類方法

下面開始寫類的方法：

/**

* Set the packet counters

* (such as when restoring from a database)

*/

protected final

void setArray(int[] r1, int[] r2, int[] r3, int[] r4)

throws IllegalArgumentException

{

//

// Ensure the arrays are of equal size

//

if (r1.length != r2.length || r1.length != r3.length || r1.length != r4.length)

throw new IllegalArgumentException(Arrays must be of the same size);

System.arraycopy(r1, 0, r3, 0, r1.length);

System.arraycopy(r2, 0, r4, 0, r1.length);

}

toString 方法

無論如何，每一個類都應該定義 toString 方法：

public

String toString() {

String retval = CounterSet: ;

for (int i = 0; i data.length(); i++) {

retval += data.bytes.toString();

retval += data.packets.toString();

}

return retval;

}

}

main 方法

如果main(String[]) 方法已經(jīng)定義了, 那么它應該寫在類的底部.

5、代碼可讀性

避免使用不易理解的數(shù)字，用有意義的標識來替代。

不要使用難懂的技巧性很高的語句。

源程序中關(guān)系較為緊密的代碼應盡可能相鄰。

6、代碼性能

在寫代碼的時候，從頭至尾都應該考慮性能問題。這不是說時間都應該浪費在優(yōu)化代碼上，而是我們時刻應該提醒自己要注意代碼的效率。比如：如果沒有時間來實現(xiàn)一個高效的算法，那么我們應該在文檔中記錄下來，以便在以后有空的時候再來實現(xiàn)她。

不是所有的人都同意在寫代碼的時候應該優(yōu)化性能這個觀點的，他們認為性能優(yōu)化的問題應該在項目的后期再去考慮，也就是在程序的輪廓已經(jīng)實現(xiàn)了以后。

不必要的對象構(gòu)造

不要在循環(huán)中構(gòu)造和釋放對象

使用 StringBuffer 對象

在處理 String 的時候要盡量使用 StringBuffer 類，StringBuffer 類是構(gòu)成 String 類的基礎(chǔ)。

String 類將 StringBuffer 類封裝了起來，（以花費更多時間為代價）為開發(fā)人員提供了一個安全的接口。當我們在構(gòu)造字符串的時候，我們應該用 StringBuffer 來實現(xiàn)大部分的工作，當工作完成后將 StringBuffer 對象再轉(zhuǎn)換為需要的 String 對象。比如：如果有一個字符串必須不斷地在其后添加許多字符來完成構(gòu)造，那么我們應該使用StringBuffer 對象和她的 append() 方法。如果我們用 String 對象代替StringBuffer 對象的話，會花費許多不必要的創(chuàng)建和釋放對象的 CPU 時間。大家可以來安安DIY創(chuàng)作室一起討論。

避免太多的使用 synchronized 關(guān)鍵字避免不必要的使用關(guān)鍵字 synchronized，應該在必要的時候再使用她，這是一個避免死鎖的好方法。

7、編程技巧

byte 數(shù)組轉(zhuǎn)換到 characters

為了將 byte 數(shù)組轉(zhuǎn)換到 characters，你可以這么做：

Hello world!.getBytes();

Utility 類

Utility 類（僅僅提供方法的類）應該被申明為抽象的來防止被繼承或被初始化。

初始化

下面的代碼是一種很好的初始化數(shù)組的方法：

objectArguments = new Object[] { arguments };

枚舉類型

JAVA 對枚舉的支持不好，但是下面的代碼是一種很有用的模板：

class Colour {

public static final Colour BLACK = new Colour(0, 0, 0);

public static final Colour RED = new Colour(0xFF, 0, 0);

public static final Colour GREEN = new Colour(0, 0xFF, 0);

public static final Colour BLUE = new Colour(0, 0, 0xFF);

public static final Colour WHITE = new Colour(0xFF, 0xFF, 0xFF);

}

這種技術(shù)實現(xiàn)了RED, GREEN, BLUE 等可以象其他語言的枚舉類型一樣使用的常量。

他們可以用 '==' 操作符來比較。

但是這樣使用有一個缺陷：如果一個用戶用這樣的方法來創(chuàng)建顏色 BLACK new Colour(0,0,0)

那么這就是另外一個對象，'=='操作符就會產(chǎn)生錯誤。她的 equal() 方法仍然有效。由于這個原因，這個技術(shù)的缺陷最好注明在文檔中，或者只在自己的包中使用。

8、編寫格式

代碼樣式

代碼應該用 unix 的格式，而不是 windows 的（比如：回車變成回車+換行）

文檔化

必須用 javadoc 來為類生成文檔。不僅因為它是標準，這也是被各種 java 編譯器都認可的方法。使用 @author 標記是不被推薦的，因為代碼不應該是被個人擁有的。

縮進

縮進應該是每行2個空格. 不要在源文件中保存Tab字符. 在使用不同的源代碼管理工具時Tab字符將因為用戶設(shè)置的不同而擴展為不同的寬度.如果你使用 UltrEdit 作為你的 Java 源代碼編輯器的話，你可以通過如下操作來禁止保存Tab字符, 方法是通過 UltrEdit中先設(shè)定 Tab 使用的長度室2個空格，然后用 Format|Tabs to Spaces 菜單將 Tab 轉(zhuǎn)換為空格。

頁寬

頁寬應該設(shè)置為80字符. 源代碼一般不會超過這個寬度, 并導致無法完整顯示, 但這一設(shè)置也可以靈活調(diào)整. 在任何情況下, 超長的語句應該在一個逗號或者一個操作符后折行. 一條語句折行后, 應該比原來的語句再縮進2個字符.

{} 對

{} 中的語句應該單獨作為一行. 例如, 下面的第1行是錯誤的, 第2行是正確的:

if (i0) { i ++ }; // 錯誤, { 和 } 在同一行

if (i0) {

i ++

}; // 正確, { 單獨作為一行

} 語句永遠單獨作為一行.如果 } 語句應該縮進到與其相對應的 { 那一行相對齊的位置。

括號

左括號和后一個字符之間不應該出現(xiàn)空格, 同樣, 右括號和前一個字符之間也不應該出現(xiàn)空格. 下面的例子說明括號和空格的錯誤及正確使用:

CallProc( AParameter ); // 錯誤

CallProc(AParameter); // 正確

不要在語句中使用無意義的括號. 括號只應該為達到某種目的而出現(xiàn)在源代碼中。下面的例子說明錯誤和正確的用法:

if ((I) = 42) { // 錯誤 - 括號毫無意義

if (I == 42) or (J == 42) then // 正確 - 的確需要括號

9、代碼編譯

1.編寫代碼時要注意隨時保存，并定期備份，防止由于斷電、硬盤損壞等原因造成代碼丟失。

2.同一項目組內(nèi)，最好使用相同的編輯器，并使用相同的設(shè)置選項。

3.合理地設(shè)計軟件系統(tǒng)目錄，方便開發(fā)人員使用。

4.打開編譯器的所有告警開關(guān)對程序進行編譯。

5.在同一項目組或產(chǎn)品組中，要統(tǒng)一編譯開關(guān)選項。

6.使用工具軟件（如Visual SourceSafe）對代碼版本進行維護。如果大家有不明白的可以到安安DIY創(chuàng)作室留言。

10、可移植性

Borland Jbulider 不喜歡 synchronized 這個關(guān)鍵字，如果你的斷點設(shè)在這些關(guān)鍵字的作用域內(nèi)的話，調(diào)試的時候你會發(fā)現(xiàn)的斷點會到處亂跳，讓你不知所措。除非必須，盡量不要使用。

換行

如果需要換行的話，盡量用 println 來代替在字符串中使用\n。

你不要這樣：

System.out.print(Hello,world!\n);

要這樣：

System.out.println(Hello,world!);

或者你構(gòu)造一個帶換行符的字符串，至少要象這樣：

String newline = System.getProperty(line.separator);

System.out.println(Hello world + newline);

PrintStream

PrintStream 已經(jīng)被不贊成（deprecated）使用，用 PrintWrite 來代替它。

匈牙利算法 java

#includestdio.h

#includestring.h

bool g[201][201];

int n,m,ans;

bool b[201];

int link[201];

bool init()

{

int _x,_y;

memset(g,0,sizeof(g));

memset(link,0,sizeof(link));

ans=0;

if(scanf("%d%d",n,m)==EOF)return false;

for(int i=1;i=n;i++)

{

scanf("%d",_x);

for(int j=0;j_x;j++)

{

scanf("%d",_y);

g[ i ][_y]=true;

}

}

return true;

}

bool find(int a)

{

for(int i=1;i=m;i++)

{

if(g[a][ i ]==1!b[ i ])

{

b[ i ]=true;

if(link[ i ]==0||find(link[ i ]))

{

link[ i ]=a;

return true;

}

}

}

return false;

}

int main()

{

while(init())

{

for(int i=1;i=n;i++)

{

memset(b,0,sizeof(b));

if(find(i))ans++;

}

printf("%d\n",ans);

}

}

Pascal:

Program matching;

Const

max = 1000;

Var

map : array [1..max, 1..max] of boolean; {鄰接矩陣}

match: array [1..max] of integer; {記錄當前連接方式}

chk : array [1..max] of boolean; {記錄是否遍歷過，防止死循環(huán)}

m, n, i, t1, t2, ans,k: integer;

Function dfs(p: integer): boolean;

var

i, t: integer;

begin

for i:=1 to k do

if map[p, i] and not chk[ i ] then

begin

chk[ i ] := true;

if (match[ i ] = 0) or dfs(match[ i ]) then {沒有被連過 或 尋找到增廣路}

begin

match[ i ] := p;

exit(true);

end;{if}

end;{for}

exit(false);

end;{function}

begin{main}

readln(n, m); {N 為二分圖左側(cè)點數(shù) M為可連接的邊總數(shù)}

fillchar(map, sizeof(map), 0);

k:=0;

for i:=1 to m do{initalize}

begin

readln(t1, t2);

map[t1, t2] := true;

if kt2 then k:=t2;

end;{for}

fillchar(match, sizeof(match), 0);

ans := 0;

for i:=1 to n do

begin

fillchar(chk, sizeof(chk), 0);

if dfs(i) then inc(ans);

end;

writeln(ans);

for i:=1 to 1000 do

if match[ i ] 0 then

writeln(match[ i ], '--', i);

end.

誰幫忙給個運籌學任務指派問題的JAVA算法阿！不需要C或者C++語言,也不要和我說看著C++就能改,我不會改!!!!!

public class AssignWorkProblem {

public static void main(String[] args) {

/*

*測試

**/

int[][] cost=new int[][]{{2,15,13,4},{10,4,14,15},{9,14,16,13},{7,8,11,9}};

System.out.println(Arrays.toString(awpProcedure(cost, 4, 4)));

cost=new int[][]{{12,7,9,7,9},{8,9,6,6,6},{7,17,12,14,12},{15,14,6,6,10},{4,10,7,10,6}};

System.out.println(Arrays.toString(awpProcedure(cost, 5, 5)));

}

/*

* 費用矩陣costMatrix,由于要改變costMatrix的值，clone方法只能對基本類型;

* pnum即為幾個人，也是costMatrix的行數(shù)，wnum是幾個任務，也是costMatrix的列數(shù)

* 返回值：沒兩個數(shù)字為一組，表示i,j。如返回[1,1,2,0]表示costMatrix[1][1]、costMatrix[2][0]費用最低

*/

public static int[] awpProcedure(int[][] costMatrix,int pnum,int wnum){

if(pnum1||pnumwnum)

return null; //test n=m

int[][] costC=new int[pnum][]; //clone 一份costMatrix

for(int i=0;ipnum;i++){

costC[i]=costMatrix[i].clone();

}

//每行減去最小的元素

int[] lzeroa=new int[pnum+1]; //記錄每行0的個數(shù),lzero[pnum]記錄0最少的行標

lzeroa[pnum]=-1;

int i,j;

for(i=0;ipnum;i++){

int lmin=costC[i][0]; //記錄每行最小的

for(j=1;jwnum;j++)

lmin=lmincostC[i][j]?costC[i][j]:lmin;

for(j=0;jwnum;j++){

costC[i][j]-=lmin;

lzeroa[i]+=costC[i][j]==0?1:0;

}

}

for(j=0;jwnum;j++){

int cmin=costC[0][j]; //記錄每列最小的

for(i=1;ipnum;i++)

cmin=cmincostC[i][j]?costC[i][j]:cmin;

if(cmin==0)continue;

for(i=0;ipnum;i++){

costC[i][j]-=cmin;

lzeroa[i]+=costC[i][j]==0?1:0;

}

}

int[] rzerop;

int whilenum=0;

while(true){

boolean[] lzerob=new boolean[pnum]; //記錄某行是否查找過

rzerop=new int[pnum*2]; //記錄0元素所在的行列

Arrays.fill(rzerop, -1);

if(awpIsSolution(costC,pnum,wnum,lzeroa.clone(),lzerob,rzerop))

break;

//下面調(diào)整矩陣

int[] coverLC=new int[pnum+wnum]; //要被標記的行列，0-pnum-1為行，pnum以后為列

Arrays.fill(coverLC, -1);

//沒有找到合適0元素的行做標記

for(i=0;ipnum;i++)

if(lzerob[i]==false)coverLC[i]=i;

//對已經(jīng)標記的行上的0元素所在的列做標記

for(i=0;ipnum;i++)

if(coverLC[i]!=-1){

for(j=0;jwnum;j++){

if(costC[coverLC[i]][j]==0)

coverLC[pnum+j]=j;

}

}

//對已經(jīng)標記的列上的已經(jīng)選中的0元素所在的行做標記

for(j=0;jwnum;j++){

if(coverLC[pnum+j]!=-1){

for(i=0;irzerop.lengthrzerop[i]!=-1;i+=2){

if(rzerop[i+1]==j)

coverLC[rzerop[i]]=rzerop[i];

}

}

}

//確定能找出新最小值的區(qū)域，直線覆蓋掉沒有打勾的行，打勾的列,最終coverLC[x]!=-1就是能選擇的數(shù)

for(i=0;iwnum;i++){

if(coverLC[pnum+i]!=-1)coverLC[pnum+i]=-1;

else coverLC[pnum+i]=i;

}

//從區(qū)域中找出最小元素

int nmin=-1;

for(i=0;ipnum;i++){

if(coverLC[i]==-1)continue;

for(j=0;jwnum;j++){

if(coverLC[pnum+j]==-1)continue;

if(nmin==-1)nmin=costC[i][j];

else nmin=nmincostC[i][j]?costC[i][j]:nmin;

}

}

//打勾的列加上nmin,打勾的行減去nmin,記錄0個數(shù)的數(shù)組作相應變化

for(j=0;jwnum;j++){

if(coverLC[pnum+j]==-1){

for(i=0;ipnum;i++){

if(costC[i][j]==0)lzeroa[i]-=1;

costC[i][j]+=nmin;

}

}

}

for(i=0;ipnum;i++){

if(coverLC[i]!=-1){

for(j=0;jwnum;j++){

costC[i][j]-=nmin;

if(costC[i][j]==0)lzeroa[i]+=1;

}

}

}

whilenum++;

if(whilenum==100){

System.out.println("100次之內(nèi)矩陣調(diào)整沒有找到");

return null;

}

}

return rzerop;

}

/*

* 測試矩陣costC是否有解，已經(jīng)通過變換或者調(diào)整得到的矩陣

*/

public static boolean awpIsSolution(int[][] costC,int pnum,int wnum,int[] lzeroa,boolean[] lzerob,int[] rzerop){

int i,j,rzeropi=0;

for(int p=0;ppnum;p++){ //開始按照匈牙利法劃去0所在的行列

//查找0元素個數(shù)最少的行

for(i=0;ipnum;i++){

if(lzerob[i]||lzeroa[i]1)continue; //如果某行已經(jīng)查找過或者沒有0元素，可能被劃去了

if(lzeroa[pnum]!=-1lzeroa[i]lzeroa[lzeroa[pnum]])lzeroa[pnum]=i;

else if(lzeroa[pnum]==-1) lzeroa[pnum]=i;

}

//沒有找到足夠的不在同一行同一列的0元素，需要對矩陣進行調(diào)整，如果lzeroa[pnum]有值，則說明該行一定能找到

if(lzeroa[pnum]==-1){

return false;

}

//劃去找到的行中沒有被覆蓋的0元素所在的行列

for(j=0;jwnum;j++){

if(costC[lzeroa[pnum]][j]!=0)continue;

//第一次找0元素最少的行

if(rzeropi==0){

rzerop[rzeropi++]=lzeroa[pnum];

rzerop[rzeropi++]=j;

lzerob[lzeroa[pnum]]=true; //找到第lzeroa[pnum]行，第j列0元素

//劃去所在的行列時 lzeroa做相應的變化

for(i=0;ipnum;i++){

if(i!=lzeroa[pnum]costC[i][j]==0)

lzeroa[i]-=1;

}

lzeroa[pnum]=-1;

break;

}

//找到的0元素是否被劃去

for(i=0;irzeropi(lzeroa[pnum]!=rzerop[i]j!=rzerop[i+1]);i+=2);

//如果被劃去則找該行下一個0元素

if(irzeropi)continue;

rzerop[rzeropi++]=lzeroa[pnum];

rzerop[rzeropi++]=j;

lzerob[lzeroa[pnum]]=true;

for(i=0;ipnum;i++){

if(i!=lzeroa[pnum]costC[i][j]==0)

lzeroa[i]-=1;

}

lzeroa[pnum]=-1;

break;

}

}

return true;

}

}

網(wǎng)頁標題：匈牙利算法java代碼 匈牙利算法java代碼大全
標題路徑：http://www.yijiale78.com/article44/dooiche.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供企業(yè)建站、全網(wǎng)營銷推廣、面包屑導航、移動網(wǎng)站建設(shè)、軟件開發(fā)、網(wǎng)頁設(shè)計公司

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)