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

時(shí)間：2024-07-22 02:46:39 綜合指導(dǎo) 我要投稿

相關(guān)推薦

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

　　題目描述：

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

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

　　A，B的一條通路是指：從A出發(fā)，可經(jīng)過任一路段到達(dá)S1，再從S1出發(fā)經(jīng)過任一路段，…最后到達(dá)B。通路上路段距離之和稱為通路距離(最大距離≤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ù)組在窮舉過程中記錄當(dāng)前路

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

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

　　算法提示：

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