資源簡介

第三章 算法基礎(chǔ)
從A市到B市耗時最少的旅行路線方案設(shè)計報告
—— 以從廣州市到長春市為例
一、引言
隨著科學(xué)技術(shù)的快速發(fā)展，我國鐵路、航空、橋梁建設(shè)得到了快速發(fā) 展，這給我們的交通出行提供了多種選擇，如鐵路運(yùn)輸、航空運(yùn)輸、汽車 客運(yùn)等給我們的出行帶了許多的便利。
二、設(shè)計目的
(一)項(xiàng)目情景
小張是廣州市某中學(xué)高三的學(xué)生，國慶節(jié)到了，小張要去探訪在長春 市就讀的好友，為了節(jié)約成本而且更多地欣賞沿途風(fēng)光，并且能夠一睹北 京市容，小張決定以北京作為中轉(zhuǎn)站，乘高鐵前往長春。現(xiàn)請你幫他設(shè)計 一個以高鐵為交通工具、以北京為中轉(zhuǎn)站的從廣州市到長春市耗時最少的 旅行方案。
(二)設(shè)計目的
通過對“耗時最少的旅行方案”設(shè)計，體驗(yàn)計算機(jī)解決問題的過程， 理解和概述算法的概念與特征，學(xué)會運(yùn)用恰當(dāng)?shù)拿枋龇椒ê涂刂平Y(jié)構(gòu)表示 簡單算法，懂得描述程序設(shè)計語言產(chǎn)生與發(fā)展的過程，了解不同種類程序 設(shè)計語言的特點(diǎn)。
三、需求分析
要設(shè)計一個以高鐵為交通工具，以北京為中轉(zhuǎn)站的從廣州市到長春市 耗時最少的旅行方案，首先必須知道廣州市到北京市的高鐵有哪些班次、
· 1 ·
北京市到長春市的高鐵有哪些班次。
然后分析從廣州市到長春市高鐵的可行旅行方案有哪些？在可行的旅 行方案中，找出從廣州市到長春市耗時最少的旅行方案。
四、需要的工具與方法
在設(shè)計廣州市到長春市耗時最少的旅行方案時，可以編寫計算機(jī)程序 來解決問題。編寫計算機(jī)程序解決問題的基本過程是：分析問題、設(shè)計算 法、編寫程序、程序調(diào)試與運(yùn)行。
算法描述常用的方法有：自然語言描述法、流程圖描述法、偽代碼描 述法。
算法描述過程中用到的三種基本結(jié)構(gòu)是：順序結(jié)構(gòu)、分支結(jié)構(gòu)、循環(huán) 結(jié)構(gòu)。
本項(xiàng)目中，用到的工具有：Python程序設(shè)計語言、思維導(dǎo)圖等；用到的 方法有：自然語言描述法，用順序結(jié)構(gòu)、分支結(jié)構(gòu)、循環(huán)結(jié)構(gòu)三種基本結(jié) 構(gòu)描述算法的方法等。
五、設(shè)計方案
1．問題分析
本項(xiàng)目要求設(shè)計一個以高鐵為交通工具，以北京為中轉(zhuǎn)站的從廣州市 到長春市耗時最少的旅行方案。首先我們通過網(wǎng)絡(luò)獲取廣州市到北京市、 北京市到長春市的高鐵班次信息。(本章所展示的高鐵班次信息僅為項(xiàng)目 分析提供數(shù)據(jù)支持，查詢時間不同，高鐵班次信息或有差異，請以實(shí)際查 詢?yōu)闇?zhǔn)。)
(1)廣州市到北京市的高鐵班次信息如圖3-1所示。
·2 ·
圖 3-1 廣州市到北京市的高鐵班次信息
(2)北京市到長春市的高鐵班次信息如圖3-2所示。
圖 3-2 北京市到長春市的高鐵班次信息
·3 ·
然后，我們將獲取的信息經(jīng)過數(shù)據(jù)清洗后，形成結(jié)構(gòu)化的數(shù)據(jù)存儲為 Excel文件，廣州至北京高鐵班次查詢結(jié)果如圖3-3所示。
圖 3-3 廣州市至北京市高鐵班次查詢結(jié)果圖
北京市至長春市高鐵班次查詢結(jié)果如圖3-4所示。
圖 3-4 北京市至長春市高鐵班次查詢結(jié)果圖
2．設(shè)計算法
以北京市為中轉(zhuǎn)站從廣州市到長春市耗時最少的旅行方案問題，根據(jù) 獲取的廣州市到北京市、北京市到長春市的高鐵班次信息，采用以下的方 法找出耗時最少的聯(lián)運(yùn)班次方案，算法如下：
·4 ·
分別算出從廣州市至北京市各班次所用的時間。
分別算出從北京市到長春市各班次所用的時間。
(2)找到能夠從廣州市經(jīng)北京市到達(dá)長春市的聯(lián)運(yùn)班次，共 k 條
線路。
(3)從 k 條聯(lián)運(yùn)班次線路中找出耗時最少的為最佳旅行路線。
3．編寫程序
根據(jù)所設(shè)計的算法，編寫程序，程序的核心代碼如下。
(
#
導(dǎo)入xlrd 模塊
#
以下3行初始化列表
)import xlrd ms=[] ra=[] rb=[] data = xlrd.open_workbook("B1.xls") # Excel文件名 B1.xls table_1 = data.sheet_by_name("Sheet1") # 取出 Excel 文件中的數(shù)據(jù)表 Sheet1 table_2 = data.sheet_by_name("Sheet2") # 取出 Excel 文件中的數(shù)據(jù)表 Sheet2 (
#
讀
取數(shù)據(jù)表Sheet1 的每一行記錄數(shù)據(jù),記為rs1
#
讀
取數(shù)據(jù)表Sheet2 的每一行記錄數(shù)據(jù),記為rs2
#旅行
方
案耗時最小值初始化
#枚
舉
rs
1(即數(shù)據(jù)表
Sheet
1)中每一行記錄
)rs1 = table_1.nrows rs2 = table_2.nrows m= 99 for i in range(1,rs1): t14 = table_1.cell(i,4).value #讀取數(shù)據(jù)表第4列的數(shù)據(jù)(由廣州出發(fā)到達(dá)北京的時間) t15 = table_1.cell(i,5).value #讀取數(shù)據(jù)表第5列的數(shù)據(jù)(由廣州出發(fā)到達(dá)北京的時間) if t15=="第二天": t14=t14+24 t12 = t14-table_1.cell(i,2).value #計算由廣州出發(fā)到達(dá)北京所用的時間(到達(dá)時間-出發(fā)時間) for j in range(1,rs2):
·5 ·
#枚舉rs2(即數(shù)據(jù)表sheet2)中的每一行記錄 t22 = table_2.cell(j,2).value #讀取從北京出發(fā)的時間 if t22>t14 : #如果從北京出發(fā)的時間大于到達(dá)北京的時間 m1=t12+(t22-t14)+(table_2.cell(j,4).value-t22) #算出到達(dá)長春所用的時間 if m>m1: #如果當(dāng)前值比最小值還小 m=m1 # 則更新最小值 r1=i #記錄這時從廣州出發(fā)到達(dá)北京的數(shù)據(jù) r2=j #記錄從北京出發(fā)到達(dá)長春的數(shù)據(jù) ms.append(m) #將最小值添加到列表中 ra.append(r1) #將取得最小值時從A出發(fā)到達(dá)中間地的記錄添加到列表ra中 rb.append(r2) #將取得最小值時從中間地出發(fā)到達(dá)B市的記錄添加到列表rb中 ms0=min(ms) #取出列表ms中的取最小值 ms1=ms.index(ms0) #找出中間城市編號 print("從廣州出發(fā)經(jīng)北京到達(dá)長春，最少耗時為：",ms0*24,"小時。 具體行程請查看文件ZHXC.XLS。") #輸出結(jié)果 data = xlrd.open_workbook("B1"+".xls") #找出取最小值時中間城市對應(yīng)的數(shù)據(jù)文件 table_1 = data.sheet_by_name("Sheet1") #找數(shù)據(jù)文件的數(shù)據(jù)表Sheet1 table_2 = data.sheet_by_name("Sheet2") #找數(shù)據(jù)文件的數(shù)據(jù)表Sheet2
·6 ·
(
import
xlwt
wbk
=
xlwt.Workbook()
sheet
=
wbk.add_sheet("Sheet
1")
)#導(dǎo)入模塊 xlwt #創(chuàng)建一個工作簿文件 #創(chuàng)建數(shù)據(jù)表Sheet1 (
style
=
xlwt.XFStyle() #創(chuàng)建單元格格式對象
for
l
in
range
(5
): #枚舉要寫出結(jié)果的列 l(1--4)
sheet
.
write
(
0
,l, table_1.cell(0,l).value)
#將
數(shù)
據(jù)文件的數(shù)據(jù)表Sheet1的表頭第l列數(shù)據(jù)寫入數(shù)據(jù)表Sheet1
if
l in (2,4):
)#對于開始時間和到達(dá)時間，指定時間格式 style.num_format_str = "hh:mm" else: #其他單元格不設(shè)置格式 style.num_format_str = "" #寫入數(shù)據(jù)時指定格式(最后一個參數(shù)) sheet.write(1,l, table_1.cell(ra[ms1],l).value,style) #將最優(yōu)值時到達(dá)對應(yīng)經(jīng)過中間城市數(shù)據(jù)文件的數(shù)據(jù)表Sheet1的第 #l列數(shù)據(jù)寫入數(shù)據(jù)表Sheet1 sheet.write(2,l, table_2.cell(rb[ms1],l).value,style) #將最優(yōu)值時對應(yīng)從中間城市出發(fā)數(shù)據(jù)文件的數(shù)據(jù)表Sheet1的第l #列數(shù)據(jù)寫入數(shù)據(jù)表Sheet1 wbk.save("zjxc.xls") # 將結(jié)果保存到數(shù)據(jù)簿文件zjxc.xls
4．調(diào)試運(yùn)行程序
掃描封底的二維碼，打開配套資源中的“項(xiàng)目范例程序.py”，運(yùn)行程 序，輸入數(shù)據(jù)以圖3-3、圖3-4的數(shù)據(jù)為例，可以快速地找出從廣州市到長 春市耗時最少的高鐵旅行方案，如表3-1所示。
·7 ·
表 3-1 耗時最少的高鐵旅行方案
交通工具 出發(fā)地 出發(fā)時間 到達(dá)地 到達(dá)時間
高鐵 廣州 8:25 北京 16:27
高鐵 北京 16:37 長春 21:33
在本項(xiàng)目的算法描述中，用到了自然語言描述法，而在程序?qū)崿F(xiàn)過程 中，程序是由上而下執(zhí)行，屬于順序結(jié)構(gòu)，在枚舉rs1(即數(shù)據(jù)表Sheet1)中 每一行記錄、以及枚舉rs2(即數(shù)據(jù)表Sheet2)中的每一行記錄時用到了循 環(huán)結(jié)構(gòu)，在判斷從北京市出發(fā)的時間是否大于到達(dá)北京市的時間、以及判 斷當(dāng)前值是否比最小值還小時用到了分支結(jié)構(gòu)。
六、結(jié)語
通過參與并完成本項(xiàng)目，我們深刻體會到：
1．設(shè)計算法是用計算機(jī)解決問題的關(guān)鍵。
算法是指在有限步驟內(nèi)求解某一問題所使用的一組定義明確的規(guī)則。 通俗地說，算法就是用計算機(jī)求解某一問題的方法，是能被機(jī)械地執(zhí)行的 動作或指令的有窮集合。一個問題能否用計算機(jī)來解決，很大程度取決于 能否設(shè)計出解決問題的算法。
2．根據(jù)具體問題用恰當(dāng)?shù)拿枋龇椒枋鏊惴ā?br/>描述算法的常用方法有自然語言描述算法、流程圖描述算法和偽代碼 描述算法。每一種描述方法各有優(yōu)點(diǎn)與不足，要根據(jù)具體問題選用恰當(dāng)?shù)?描述方法描述算法。
3．計算機(jī)解決問題更高效。
通過本項(xiàng)目問題可以明顯體會到用計算機(jī)解決問題的優(yōu)勢，當(dāng)數(shù)據(jù)量 不多時，我們可以采用人工方法來處理；然而，當(dāng)數(shù)據(jù)量較多時，運(yùn)用計 算機(jī)解決問題可以更高效、更便捷。
在開展本項(xiàng)目的過程中，我們進(jìn)行了自主、協(xié)作、探究學(xué)習(xí)，體驗(yàn) 了計算機(jī)解決問題的過程，理解了算法的概念與特征，學(xué)會了運(yùn)用恰當(dāng) 的描述方法和控制結(jié)構(gòu)表示簡單算法，了解了程序設(shè)計語言產(chǎn)生與發(fā)展的 過程、不同種類程序設(shè)計語言的特點(diǎn)，促進(jìn)了信息技術(shù)學(xué)科核心素養(yǎng)的達(dá) 成，達(dá)成了項(xiàng)目學(xué)習(xí)的目的。
·8 ·

展開更多......

收起↑