星期天小明來到動物園游玩,園內(nèi)共有n個景點,每個景點序號為0,1,2,3……至n-1?,F(xiàn)在只知道每個景點有一條路連接下一個景點。小明想尋找能游玩景點個數(shù)最多的一種方案并且從其中一個景點出發(fā),最后能夠回到出發(fā)景點。如果游玩的景點個數(shù)一樣,則優(yōu)先考慮景點序號小的。例如,共有n=5個景點,每個景點連接的下個景點分別是1,3,4,4,1。
景點號 |
0 |
1 |
2 |
3 |
4 |
下一個景點號 |
1 |
3 |
4 |
4 |
1 |
方案一:從0號景點出發(fā),則游玩線路為:0號→1號→3號→4號→1號,由于此方案無法回到出發(fā)點,則不考慮。
方案二:從1號景點出發(fā),則游玩線路為:1號→3號→4號→1號,然后回到1號景點。最多可以玩3個景點。
現(xiàn)用Python程序模擬這個問題:
先輸入景點總數(shù):n;則對應(yīng)的景點為[0,1,2,3,4]
然后隨機產(chǎn)生各景點所連接的下一個景點的序號,如:[1,3,4,4,1];
接著產(chǎn)生一個列表,如上表的信息則產(chǎn)生的列表s為:[[0,1],[1,3],[2,4],[3,4],[4,1]],最后利用鏈表的方式來分析解決問題。
程序如下: