Java面試的面試題目與解題思路 2014

　　題目描述：

　　在A，B兩個城市之間設(shè)有N個路站(如下圖中的S1，且N<100)，城市與路站之間、路站和路站之間各有若干條路段(各路段數(shù)≤20，且每條路段上的距離均為一個整數(shù))。

　　A，B的一條通路是指：從A出發(fā)，可經(jīng)過任一路段到達S1，再從S1出發(fā)經(jīng)過任一路段，…最后到達B。通路上路段距離之和稱為通路距離(最大距離≤1000)。當(dāng)所有的路段距離給出之后，求出所有不同距離的通路個數(shù)(相同距離僅記一次)。

　　例如：下圖所示是當(dāng)N=1時的情況：

　　從A到B的通路條數(shù)為6，但因其中通路5+5=4+6，所以滿足條件的不同距離的通路條數(shù)為5。

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

　　N記錄A，B間路站的個數(shù)

　　D[I][0]記錄第I-1到第I路站間路段的個數(shù)

　　D[I][1]，D[I][2]……記錄每個路段距離

　　G[X]標(biāo)記長度為X的通路是否可能

　　B數(shù)組在窮舉過程中記錄當(dāng)前路

　　B[I]表示第I-1到第I路站之間選擇哪一條路段

　　--------------------------------------------------------------------------------

　　算法提示：

　　本題采用窮舉算法，窮舉所有可能的路徑，求出它們的長度，并在一標(biāo)記數(shù)組中標(biāo)記該長度為可能，最后計算所有的可能標(biāo)記個數(shù)。

　　窮舉時采用回溯法，最初從11……111這樣的路徑開始，每次都從最后一個路站開始往前尋找當(dāng)前路徑可修改的地方，直到當(dāng)前路徑變得無法修改為止。

【Java面試的面試題目與解題思路 】相關(guān)文章：

java面試的經(jīng)驗11-20

java面試的測試11-20

廣西選調(diào)生面試備考：編故事題解題思路11-20

2014選調(diào)生面試備考 編故事題解題思路11-20

電話面試 題目11-20

面試經(jīng)典考題回答思路11-07

海信面試英語題目06-15

JAVA面試筆試題11-15

小升初面試筆試及面試題目11-21