- 相關推薦
Java面試的面試題目與解題思路 2014
題目描述:
在A,B兩個城市之間設有N個路站(如下圖中的S1,且N<100),城市與路站之間、路站和路站之間各有若干條路段(各路段數(shù)≤20,且每條路段上的距離均為一個整數(shù))。
A,B的一條通路是指:從A出發(fā),可經(jīng)過任一路段到達S1,再從S1出發(fā)經(jīng)過任一路段,…最后到達B。通路上路段距離之和稱為通路距離(最大距離≤1000)。當所有的路段距離給出之后,求出所有不同距離的通路個數(shù)(相同距離僅記一次)。
例如:下圖所示是當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]標記長度為X的通路是否可能
B數(shù)組在窮舉過程中記錄當前路
B[I]表示第I-1到第I路站之間選擇哪一條路段
--------------------------------------------------------------------------------
算法提示:
本題采用窮舉算法,窮舉所有可能的路徑,求出它們的長度,并在一標記數(shù)組中標記該長度為可能,最后計算所有的可能標記個數(shù)。
窮舉時采用回溯法,最初從11……111這樣的路徑開始,每次都從最后一個路站開始往前尋找當前路徑可修改的地方,直到當前路徑變得無法修改為止。
【Java面試的面試題目與解題思路 】相關文章:
java面試的經(jīng)驗11-20
java面試的測試11-20
2014選調(diào)生面試備考 編故事題解題思路11-20
電話面試 題目11-20
面試經(jīng)典考題回答思路11-07
海信面試英語題目06-15
JAVA面試筆試題11-15
小升初面試筆試及面試題目11-21