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

才智咖 人氣:1.4W

題目描述:

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

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

A,B的一條通路是指:從A出發,可經過任一路段到達S1,再從S1出發經過任一路段,…最後到達B。通路上路段距離之和稱為通路距離(最大距離≤1000)。當所有的路段距離給出之後,求出所有不同距離的通路個數(相同距離僅記一次)。

例如:下圖所示是當N=1時的'情況:

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

資料結構:

N記錄A,B間路站的個數

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

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

G[X]標記長度為X的通路是否可能

B陣列在窮舉過程中記錄當前路

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

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

演算法提示:

本題採用窮舉演算法,窮舉所有可能的路徑,求出它們的長度,並在一標記陣列中標記該長度為可能,最後計算所有的可能標記個數。

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