資源簡介

從A市到B市耗時最少的旅行路線方案設(shè)計報告
一、引言
數(shù)據(jù)在信息社會中具有重要價值，掌握數(shù)據(jù)處理的基本方法與技能具有重要意義。隨著數(shù)據(jù)的快速增長，人工方式處理海量數(shù)據(jù)的效率正變得低下，因此掌握利用計算機和算法更高效地分析和解決問題的方法在計算機科學(xué)界的作用日益凸顯。
二、設(shè)計目的
中國橋、中國路、中國車、中國港、中國網(wǎng)，一個個奇跡般建造起來的工程，讓人民切切實實感受到生活的便捷、美好和幸福。截至2017年10月，中國高速公路里程13.1萬千米，位居世界第一，2020
年將達15萬千米；高鐵里程2.2萬千米，位居世界第一；城市軌道交通4153千米，位居世界第一；光纜線路3041萬千米，位居世界第一；世界前10的斜拉橋，中國占7座；世界前10的懸索橋，中國占6座；港口吞吐量世界前10名中國占7席。當(dāng)從A市到B市沒有直達的交通工具時，人們可以利用鐵路公司、汽車客運公司和航空公司公布的信息，設(shè)計出最佳的旅行路線。
體驗計算機解決問題的過程，理解和概述算法的概念與特征，學(xué)會運用恰當(dāng)?shù)拿枋龇椒ê涂刂平Y(jié)構(gòu)表示簡單算法，懂得描述程序設(shè)計語言產(chǎn)生與發(fā)展的過程，了解不同種類程序設(shè)計語言的特點。
三、需求分析和功能描述
1.需求分析
需求由以下三部分構(gòu)成：
（1）體驗人工與計算機解決問題的過程。
（2）探究計算機解決問題的算法。
?
（3）了解計算機解決問題的程序。
2.功能描述
（1）設(shè)計從A市到B市耗時最少旅行路線的問題分析。
（2）設(shè)計從A市到B市耗時最少旅行路線的算法。
（3）編寫求解從A市到B市耗時最少的旅行路線問題的程序。
四、設(shè)計工具和方法
利用思維導(dǎo)圖工具和“頭腦風(fēng)暴”的方法組建團隊、明確任務(wù)；采用搜索技術(shù)，實施探究。
五、設(shè)計步驟與過程
1.設(shè)計從A市到B市耗時最少旅行路線的問題分析
我們從鐵路公司、各航空公司和汽車客運公司網(wǎng)站得知，直達B市的交通工具只有火車和汽車兩種，出發(fā)地有B1，B2，…，Bk市（沒有A市），從A市出發(fā)到B1，B2，…，Bk市的交通工具有飛機、火車和汽車三種，這樣從A市經(jīng)B1，B2，…，Bk市到B市的交通情況如右圖所示。
由于從A市到B1，B2，…，Bk市有不同的交通工具，每一種交通工具又有不同的班次，因此從A市出發(fā)到中轉(zhuǎn)城市B1，B2，…，Bk市就有M1、M2，…，Mk種班次。同樣，從中轉(zhuǎn)城市B1，B2，…，Bk市到B市也有不同的交通工具，每一種交通工具有不同的班次，因此從中轉(zhuǎn)城市B1，B2，…，Bk市到B市就有N1，N2，…，Nk種班次。于是從A市經(jīng)B1，B2，…，Bk市到B市的交通班車（班機）數(shù)共有：
S=M1×N1+M2×N2+…+Mk×Nk
尋找從A市到B市耗時最少的旅行路線問題就轉(zhuǎn)化為在S種聯(lián)運班次中找到一種耗時最少的聯(lián)運班次。這樣就需要遍歷每一個班次進行比較，人工方式找到能夠中轉(zhuǎn)且等待時間和行駛時間最少的班次，工作量極其浩大！
假設(shè)從A市到B市的中轉(zhuǎn)城市只有B1，B2市，從A市經(jīng)B1，B2市到B市的交通情況如表3-2和表3-3所示。
于是，從A市經(jīng)B1市到B市的聯(lián)運班次有7×9=63班；從A市經(jīng)B2市到B市的聯(lián)運班次有12×9=108班，合計為S=63+108=171班。然后在171班次中找到能夠中轉(zhuǎn)且等待時間加上行駛時間最少的聯(lián)運班次，如下圖所示。
當(dāng)數(shù)據(jù)量很大，人工處理效率很低時，我們可以借助計算機，通過編寫計算機程序解決問題。在利用計算機解決問題之前，我們首先要分析問題的需求情況、已知條件和需要解決的問題。
在從A市到B市耗時最少的旅行路線問題中，在不知道有多少個中轉(zhuǎn)城市和每個城市有多少班車（或飛機）的情況下，我們可以利用大數(shù)據(jù)挖掘技術(shù)中的爬蟲程序（參見配套學(xué)習(xí)資源包“第三章\課本素材\程序3-1”）到鐵路網(wǎng)站、各航空公司和汽車客運公司網(wǎng)站獲取從A市經(jīng)中轉(zhuǎn)城市B1，B2，…，Bk市到達B市的交通班次信息，經(jīng)過數(shù)據(jù)清洗，形成結(jié)構(gòu)化的數(shù)據(jù)存儲為Excel文件。
2.設(shè)計從A市到B市耗時最少旅行路線的算法
從A市到B市耗時最少的旅行路線問題，根據(jù)獲取的從A市到B市的中轉(zhuǎn)城市B1，B2，…，Bk的班次，以及各城市各交通班次的發(fā)車時間和行駛時間等信息，采用以下的思想找出耗時最少的聯(lián)運班次問題，即算法如下：
（1）分別找出能夠中轉(zhuǎn)的從A市經(jīng)B1，B2，…，Bk市到達B市的聯(lián)運班次，并計算所用的時間。
（2）分別找到能夠中轉(zhuǎn)的從A市經(jīng)B1，B2，…，Bk市到達B市的聯(lián)運班次中耗時最少的聯(lián)運班次，共k條線路。
（3）取k條線路中耗時最少的聯(lián)運班次為最佳旅行路線。
3.編寫求解從A市到B市耗時最少的旅行路線問題的程序
Python語言編寫從A市到B市耗時最少的旅行路線問題的算法的程序可參見配套學(xué)習(xí)資源包“第三章\課本素材\程序3-1”。其中，找出能夠從A市經(jīng)Bi（i=1，2，…，k）市到達B市的中轉(zhuǎn)聯(lián)運班次，并計算所用的時間以及找到耗時最少的聯(lián)運路線的關(guān)鍵程序段如下。
六、設(shè)計成果
1.計算機解決問題更高效、更便捷
在現(xiàn)實生活中，我們經(jīng)常需要對數(shù)據(jù)進行統(tǒng)計、分析。當(dāng)數(shù)據(jù)量不多時，我們可以采用人工方法來處理；然而，當(dāng)數(shù)據(jù)量變多時，運用計算機解決問題將是一種更高效、更便捷的方法。
在從A市到B市耗時最少的旅行路線問題中，我們分析并設(shè)計了算法和編寫了程序之后，可以快速地找出從A市到B市耗時最少的旅行路線問題的結(jié)果，如下圖所示。
2.算法是計算機解決問題的核心
算法是指在有限步驟內(nèi)求解某一問題所使用的一組定義明確的規(guī)則。通俗地說，算法就是用計算機求解某一問題的方法，是能被機械地執(zhí)行的動作或指令的有窮集合。
描述算法的常用方法有自然語言描述算法、流程圖描述算法和偽代碼描述算法。
3.
計算機程序就是指計算機可以識別運行的指令集合
計算機程序是指為了得到某種結(jié)果而可以由計算機等具有信息處理能力的裝置執(zhí)行的代碼化指令序列，或者可被自動轉(zhuǎn)換成代碼化指令序列的符號化指令序列或者符號化語句序列。簡而言之，計算機程序就是指計算機可以識別運行的指令集合。
在用計算機解決問題時，用自然語言、流程圖或是偽代碼所描述的解決問題的算法都不能被計算機直接執(zhí)行，還必須將算法按照一定的規(guī)則編寫成計算機能夠識別和運行的程序。而人們編寫程序的時候需要遵循的規(guī)則就是計算機語言規(guī)則。計算機程序設(shè)計語言，是指一組用來定義計算機程序的語法規(guī)則，通常簡稱為“編程語言”。它是一種被標(biāo)準(zhǔn)化的交流技巧，用于向計算機發(fā)出指令。正確地使用計算機程序設(shè)計語言，能讓程序員準(zhǔn)確地定義計算機所需要使用的數(shù)據(jù)，并精確地定義在不同情況下所應(yīng)執(zhí)行的命令。
七、結(jié)語
本章通過“設(shè)計從A市到B市最佳的旅行路線方案”項目，進行自主、協(xié)作、探究學(xué)習(xí)，讓同學(xué)們體驗計算機解決問題的過程，理解和概述算法的概念與特征，學(xué)會運用恰當(dāng)?shù)拿枋龇椒ê涂刂平Y(jié)構(gòu)表示簡單算法，懂得描述程序設(shè)計語言產(chǎn)生與發(fā)展的過程，了解不同種類程序設(shè)計語言的特點，從而將知識建構(gòu)、技能培養(yǎng)與思維發(fā)展融入運用數(shù)字化工具解決問題和完成任務(wù)的過程中，促進信息技術(shù)學(xué)科核心素養(yǎng)達成，完成項目學(xué)習(xí)目標(biāo)。交通工具
出發(fā)地
出發(fā)時間
到達地
到達時間
飛機
A
9:00
B1
12:00
飛機
A
12:00
B1
14:30
飛機
A
16:00
B1
18:00
火車
A
8:00
B1
20:00
火車
A
10:00
B1
21:00
火車
A
12:00
B1
21:40
火車
A
13:00
B1
22:30
交通工具
出發(fā)地
出發(fā)時間
到達地
到達時間
火車
B1
9:00
B
10:30
火車
B1
11:00
B
12:20
火車
B1
15:00
B
16:00
火車
B1
18:00
B
20:00
汽車
B1
8:00
B
9:50
汽車
B1
9:00
B
11:00
汽車
B1
13:00
B
15:10
汽車
B1
15:00
B
17:40
汽車
B1
18:00
B
19:40交通工具
出發(fā)地
出發(fā)時間
到達地
到達時間
飛機
A
8:00
B2
11:00
飛機
A
10:00
B2
12:30
飛機
A
11:00
B2
14:20
飛機
A
14:00
B2
16:30
火車
A
7:30
B2
20:30
火車
A
9:20
B2
21:40
火車
A
11:00
B2
22:20
火車
A
13:00
B2
23:55
汽車
A
7:30
B2
21:30
汽車
A
8:20
B2
21:40
汽車
A
9:00
B2
22:50
汽車
A
10:00
B2
23:30
汽車
A
11:00
B2
23:55
交通工具
出發(fā)地
出發(fā)時間
到達地
到達時間
火車
B2
8:00
B
9:30
火車
B2
10:00
B
11:20
火車
B2
14:00
B
15:00
火車
B2
19:00
B
21:00
汽車
B2
8:20
B
9:50
汽車
B2
9:30
B
11:20
汽車
B2
13:40
B
14:20
汽車
B2
16:20
B
18:30
汽車
B2
20:10
B
22:00交通工具
出發(fā)地
出發(fā)時間
到達地
到達時間
飛機
A
9:00
B3
12:00
飛機
A
11:00
B3
13:30
飛機
A
15:00
B3
17:30
飛機
A
7:30
B3
20:00
火車
A
9:20
B3
21:20
火車
A
11:00
B3
22:10
火車
A
13:00
B3
23:55
汽車
A
7:30
B3
21:00
汽車
A
8:20
B3
21:30
汽車
A
9:00
B3
22:30
汽車
A
10:00
B3
23:30
汽車
A
11:00
B3
23:55
交通工具
出發(fā)地
出發(fā)時間
到達地
到達時間
火車
B3
8:00
B
9:30
火車
B3
10:00
B
11:20
火車
B3
14:00
B
15:00
火車
B3
19:00
B
21:00
汽車
B3
8:20
B
9:50
汽車
B3
9:30
B
11:20
汽車
B3
13:40
B
14:20
汽車
B3
16:20
B
18:30
汽車
B3
20:10
B
22:00&P
交通工具
出發(fā)地
出發(fā)時間
到達地
到達時間
飛機
A
11:00:00
上午
B3
1:30:00
下午
汽車
B3
1:40:00
下午
B
2:20:00
下午
&F

展開更多......

收起↑