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

　　題目描述：

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

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

　　例如：下圖所示是當N=1時(shí)的情況：

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

　　數據結構：

　　N記錄A，B間路站的個(gè)數

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

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

　　G[X]標記長(cháng)度為X的通路是否可能

　　B數組在窮舉過(guò)程中記錄當前路

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

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

　　算法提示：

　　本題采用窮舉算法，窮舉所有可能的路徑，求出它們的長(cháng)度，并在一標記數組中標記該長(cháng)度為可能，最后計算所有的可能標記個(gè)數。

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

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

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

java面試的測試11-20

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

2014選調生面試備考 編故事題解題思路11-20

電話(huà)面試 題目11-20

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

海信面試英語(yǔ)題目06-15

JAVA面試筆試題11-15

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