第一節(jié).地鐵線路問題.2017.03

1、算法競賽入門課程目的參加算法競賽提高編程能力和算法設計能力，為后續(xù)課程的學習打下良好基礎公司招聘的技術(shù)考試試題我們所學課程與體育運動的對比操作系統(tǒng)計算機組成原理數(shù)字邏輯計算機網(wǎng)絡web程序設計.籃球乒乓球羽毛球速滑拉丁舞.與算法課對應的體育項目？跳的更高，跑的更遠，反應更快ACM算法競賽簡介ACM國際大學生程序設計競賽（英文全稱：ACM International Collegiate Programming Contest（簡稱ACM-ICPC或ICPC）是由美國計算機協(xié)會（ACM）主辦的，一項旨在展示大學生創(chuàng)新能力、團隊精神和在壓力下編寫程序、分析和解決問題能力的年度競賽。經(jīng)過近40年的發(fā)

2、展，ACM國際大學生程序設計競賽已經(jīng)發(fā)展成為全球最具影響力的大學生程序設計競賽。ACM競賽簡要規(guī)則參賽隊伍最多由三名參賽隊員組成，三名女生可組成女隊競賽中命題10題左右，試題描述為英文，比賽時間為5個小時，前四個小時可以實時看到排名，最后一小時封榜，無法看到排名競賽可以使用的語言：C+、C、Java、Pascal選手可攜帶任何非電子類資料，包括書籍和打印出來的程序等，部分賽區(qū)會對選手攜帶的紙質(zhì)資料做限制評委負責將結(jié)果（正確或出錯的類型）通過網(wǎng)絡盡快返回給選手，除此之外不提供任何額外幫助每個題目對應一種顏色的氣球，通過該題目的隊伍會得到對應顏色氣球只排名，不打分。根據(jù)答對題目數(shù)量進行排名，答對數(shù)

3、量一樣的，根據(jù)用時長短排名競賽場景OJ簡介OJ即Online Judge,是免費的公益性網(wǎng)上程序設計題庫，題目大部分來自ACM國際大學生程序設計競賽和各種自行舉辦比賽的題目，很多題目就反映工作和生活中的實際問題。用戶可以針對某個題目編寫程序并提交，讓OJ自動判定程序的對錯，幾秒之內(nèi)即可知道對還是錯。一般兼容Pascal、C、C+、Java、Fortran等多種語言。北大OJ：/，哈爾濱理工大學OJ：http:/ Set菜單下的Problems，選擇一個題目，或者根據(jù)題目id號直接進入題目的網(wǎng)頁，例如第1003號題目的網(wǎng)址為/problem?i

4、d=1003閱讀分析題目，寫程序代碼，點網(wǎng)頁下方的Submit提交程序代碼。等待幾分鐘，然后點/網(wǎng)頁Problem Set菜單下的Online Status，查看運行結(jié)果。和本課程相關的幾門課C程序設計面向?qū)ο蟪绦蛟O計(C+)數(shù)據(jù)結(jié)構(gòu)算法設計與分析數(shù)據(jù)結(jié)構(gòu)課程設計(大二短學期)考核方式平時成績：20%平時考核：30%實驗考試：50%(最后一次實驗課) 在計算機上編程序 計算機斷網(wǎng)，手機關機 簡單題目和有難度題目相結(jié)合 有語法錯誤，編譯沒通過的也能得到部分分數(shù) 程序?qū)懲暌院罂降嚼蠋煹腢盤課程的公共郵箱 dqpi_實驗1：地鐵線路問題請在此輸入您的副標題假設有兩條地鐵線路

5、，1號線為直線線路，2號線為環(huán)線線路，假設1號線的各個站點名稱分別為A10, A11, A12, A13, A14, A15, A16, A17,2號線的各個站點名稱分別為B1, B2, B3, A15, B4, B5, B6, A12,另外，假設地鐵都是雙向運行的。現(xiàn)給出兩個地鐵站名分別作為起點和終點，請給出從起點到終點至少需要多少站。解題思路直線線路(1號線路)上的起止車站的距離 數(shù)組下標差值的絕對值環(huán)線線路(2號線路)上的起止車站的距離 按環(huán)形隊列計算兩個繞行方向的距離，并取最小值情況1如果兩個站點恰好為兩個交叉點， dis1=兩個點之間的環(huán)線線路距離; dis2=兩個點之間的直線線路距

6、離; 兩個點之間的距離=min(dis1,dis2); 情況2如果兩個車站都在1號線上 dis1=兩個點之間的直線線路距離; dis2=起點到第一個交叉點的距離+兩個交叉點 之間的距離+第二個交叉點到終點的距離; dis3=起點到第二個交叉點的距離+兩個交叉點 之間的距離+第一個交叉點到終點的距離; 兩個點之間的距離=min(dis1,dis2,dis3);情況3如果兩個車站都在2號線上 dis1=兩個點之間的環(huán)線順時針前進距離; dis2=兩個點之間的環(huán)線逆時針前進距離; dis3=兩個點先走2號線，再走1號線，再走2號線; 兩個點之間的距離=min(dis1,dis2,dis3); 情況4如果起點在1號線上，終點在2號線上 dis1=起點與交叉點A12的距離+ 交叉點A12與終點的距離； dis2=起點與交叉點A15的距離+ 交叉點A15與終點的距離； 兩個點之間的距離=min(dis1,dis2); 情況5如果起點在2號線上，終點在1號線上 dis1=起點與交叉點A12的距離+ 交叉點A12與終點的距離； dis2=起點與交叉