使用遞歸尋找數組中所有元素的組合

我知道有很多類似於這個問題的問題，並且我在過去的一個小時內回顧了他們，但是我無法弄清楚如何使用提供的答案。使用遞歸尋找數組中所有元素的組合

我的任務如下：

編寫提示用戶輸入城市，那裏每個城市都有一個名字和X和Y座標列表中的程序。輸入所有城市後，程序應使用遞歸算法來打印所有可能路線的長度，這些路線始於輸入的第一個城市，在輸入的最後一個城市結束，並訪問列表中的每個城市。對於每條路線，程序應打印每個訪問城市的名稱，然後打印路線的長度。

我打破了這個問題，我可以找出大部分代碼。什麼讓我卡住是找到所有可能的組合之間的第一和最後一個城市。我到底該怎麼辦？我想解決它與一個簡單的5整數數組和我的生活我無法弄清楚如何打印所有組合。

你能否幫助我克服這個可怕的問題？

謝謝。

來源

2017-05-27 Oz Pere

請發佈您的代碼的簡短版本（[mcve]）。最好是包含編碼測試數據以避免用戶輸入。 – c0der

而不是使用陣列我建議你使用圖形。

你可以閱讀更多關於旅行商問題這裏TSP或Brute-force for TSP

來源

2017-05-27 22:23:58

我對圖表不熟悉，但我會看看，謝謝你的朋友！ –

你不得不使用遞歸算法？

如果沒有，這裏是我的建議：

假設進入城市是A，C1，...，CN，B，其中A和B是第一和最後一個城市。第一個和最後一個城市不能改變，所以你應該計算n城市的所有組合。要計算所有組合，您可以計算從0到2^n-1。對於計數器的每個值，您都有一個從A到B的路徑。每個計數器值的每一位可能與一個城市（Ci）有關。現在的計數器的每個值可以打印路徑形式A到B（有一些詞）：

如果在計數器值一個城市的相關位爲0，因此相關的城市是不是在路徑
如果計數器值的城市的相關位是1，那麼相關的城市就是路徑中的被查看城市。

來源

2017-05-27 22:25:28

謝謝哈迪，不幸的是我被迫使用遞歸。 –

這是一個衆所周知的圖表方法。如果您有關於圖表的知識，只需看一看DFS (recursively)就很可能符合您的期望。

來源

2017-05-28 10:32:32 snr

我對圖表不熟悉，但我會看看，謝謝你的朋友！ –

使用遞歸尋找數組中所有元素的組合

回答

相關問題