- 相關(guān)推薦
Java面試的面試題目與解題思路 2014
題目描述：
在A，B兩個(gè)城市之間設(shè)有N個(gè)路站(如下圖中的S1，且N<100)，城市與路站之間、路站和路站之間各有若干條路段(各路段數(shù)≤20，且每條路段上的距離均為一個(gè)整數(shù))。
A，B的一條通路是指：從A出發(fā)，可經(jīng)過(guò)任一路段到達(dá)S1，再?gòu)腟1出發(fā)經(jīng)過(guò)任一路段，…最后到達(dá)B。通路上路段距離之和稱(chēng)為通路距離(最大距離≤1000)。當(dāng)所有的路段距離給出之后，求出所有不同距離的通路個(gè)數(shù)(相同距離僅記一次)。
例如：下圖所示是當(dāng)N=1時(shí)的情況：
從A到B的通路條數(shù)為6，但因其中通路5+5=4+6，所以滿足條件的不同距離的通路條數(shù)為5。
數(shù)據(jù)結(jié)構(gòu)：
N記錄A，B間路站的個(gè)數(shù)
D[I][0]記錄第I-1到第I路站間路段的個(gè)數(shù)
D[I][1]，D[I][2]……記錄每個(gè)路段距離
G[X]標(biāo)記長(zhǎng)度為X的通路是否可能
B數(shù)組在窮舉過(guò)程中記錄當(dāng)前路
B[I]表示第I-1到第I路站之間選擇哪一條路段
--------------------------------------------------------------------------------
算法提示：
本題采用窮舉算法，窮舉所有可能的路徑，求出它們的長(zhǎng)度，并在一標(biāo)記數(shù)組中標(biāo)記該長(zhǎng)度為可能，最后計(jì)算所有的可能標(biāo)記個(gè)數(shù)。
窮舉時(shí)采用回溯法，最初從11……111這樣的路徑開(kāi)始，每次都從最后一個(gè)路站開(kāi)始往前尋找當(dāng)前路徑可修改的地方，直到當(dāng)前路徑變得無(wú)法修改為止。
【Java面試的面試題目與解題思路 】相關(guān)文章：
java面試的經(jīng)驗(yàn)11-20
java面試的測(cè)試11-20
2014選調(diào)生面試備考 編故事題解題思路11-20
電話面試 題目11-20
面試經(jīng)典考題回答思路11-07
海信面試英語(yǔ)題目06-15
JAVA面試筆試題11-15
小升初面試筆試及面試題目11-21