2019-2020年高中信息技術(shù) 全國(guó)青少年奧林匹克聯(lián)賽教案 模擬法二.doc

《2019-2020年高中信息技術(shù) 全國(guó)青少年奧林匹克聯(lián)賽教案 模擬法二.doc》由會(huì)員分享，可在線閱讀，更多相關(guān)《2019-2020年高中信息技術(shù) 全國(guó)青少年奧林匹克聯(lián)賽教案 模擬法二.doc（10頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

2019-2020年高中信息技術(shù) 全國(guó)青少年奧林匹克聯(lián)賽教案 模擬法二 課題：模擬法 目標(biāo)： 知識(shí)目標(biāo)：模擬的的實(shí)現(xiàn) 能力目標(biāo)：模擬的實(shí)現(xiàn) 重點(diǎn)：模擬的實(shí)現(xiàn) 難點(diǎn)：模擬的實(shí)現(xiàn) 板書示意： 1） 模擬的引入（例31） 2） 模擬的應(yīng)用（例32） 授課過程： 有些問題很難建立枚舉、遞歸等算法，甚至建立不了數(shù)學(xué)模型，但可以根據(jù)問題的描述，用程序模擬某種現(xiàn)象或規(guī)律，從而跟蹤出結(jié)果。 根據(jù)模擬對(duì)象的不同特點(diǎn)，可以把計(jì)算機(jī)模擬分為決定型模擬和隨機(jī)行模擬兩大類。 決定型模擬是對(duì)決定性現(xiàn)象進(jìn)行的模擬，其所模擬的事件按照固有則規(guī)律發(fā)生發(fā)展，并且最終有明確的結(jié)果。在這種題目中，由于數(shù)學(xué)模型中各種參數(shù)的變化多半是有規(guī)律的，所以算法設(shè)計(jì)一般不是很困難。 隨機(jī)模擬是模擬隨機(jī)現(xiàn)象，由于隨機(jī)現(xiàn)象中至少有一個(gè)不確定的因素，因此在模擬中，必須建立一個(gè)用隨機(jī)值來模擬事件的進(jìn)程，在隨機(jī)模擬過程中，通過修改變問題的各種參數(shù)，進(jìn)而觀察變更這些參數(shù)所引起的狀態(tài)變化。一般情況是，題目給出某一概率，設(shè)計(jì)者利用隨機(jī)函數(shù)去設(shè)定在某一范圍的隨機(jī)值，將符合概率的隨機(jī)值作為參數(shù)。然后根據(jù)這一模擬模型展開算法設(shè)計(jì)。隨機(jī)模擬的關(guān)鍵是在概率已知的條件下，如何確定隨機(jī)值產(chǎn)生的范圍。這個(gè)隨機(jī)值設(shè)計(jì)得好，模擬效果就好。本節(jié)僅討論決定性模擬問題。有關(guān)隨機(jī)模擬的問題，大家可以參考一些相關(guān)書籍。 例31：約瑟夫問題 N個(gè)人排成一個(gè)圓圈，然后把這N個(gè)人按逆時(shí)針方向分別編號(hào)為1、2、……、N。從編號(hào)為1的人開始按逆時(shí)針計(jì)數(shù)，當(dāng)某人計(jì)數(shù)為M的倍數(shù)是，該人出圈；如此循環(huán)下去，直到圈中只有一個(gè)人留下。 分析：這道題似乎用不上什么算法，只需建立一個(gè)循環(huán)鏈表，然后按照題目中要求的模擬即可。 算法描述如下： for I := 1 to N DO P[I] := I + 1; {建立循環(huán)鏈表} P[N] := 1; Now := N; repeat {模擬出圈過程} Now := N; for I := 1 to M - 1 do Now := P[Now]; {模擬報(bào)數(shù)} P[Now] := P[Now[Now]]; {編號(hào)為P[Now]的人出圈} until P[Now] = Now; {直到圈中只剩下一個(gè)人} Writeln(The last man is , Now); 例32：SERNET模擬（NOI98-5） 計(jì)算機(jī)網(wǎng)絡(luò)是現(xiàn)代科技發(fā)展的熱點(diǎn)，傳播性能是計(jì)算機(jī)網(wǎng)絡(luò)的主要性能指標(biāo)。SERNET網(wǎng)絡(luò)開發(fā)小組設(shè)計(jì)了一種稱為SERNET的網(wǎng)絡(luò)，并希望開發(fā)一個(gè)模擬軟件來模擬該網(wǎng)絡(luò)的數(shù)據(jù)傳輸情況，進(jìn)而計(jì)算出網(wǎng)絡(luò)的傳輸性能。 SERNET網(wǎng)絡(luò)由服務(wù)器及連接它們的網(wǎng)絡(luò)傳輸線路組成，服務(wù)器用服務(wù)器地址予以標(biāo)識(shí)，網(wǎng)絡(luò)傳輸線路為雙向傳輸線路。網(wǎng)絡(luò)傳輸過程中將各種傳輸數(shù)據(jù)分隔為若干個(gè)大小相同的數(shù)據(jù)包，以數(shù)據(jù)包為單位進(jìn)行傳輸。數(shù)據(jù)包在傳輸線路上傳輸時(shí)需要一定的傳輸時(shí)間，不同的傳輸線路的傳輸時(shí)間不同。服務(wù)器處理數(shù)據(jù)的時(shí)間較之于傳輸時(shí)間很小，可忽略不計(jì)。每一個(gè)數(shù)據(jù)包中除了包括具體的數(shù)據(jù)信息外，還含有如下標(biāo)識(shí)信息： ① 數(shù)舉包編號(hào)； ② 數(shù)據(jù)包源服務(wù)器地址； ③ 數(shù)據(jù)包目的服務(wù)器地址。 網(wǎng)絡(luò)傳輸?shù)墓δ芫褪菍⒁粋€(gè)個(gè)數(shù)據(jù)包從源服務(wù)器傳輸?shù)侥康姆?wù)器。對(duì)于每一個(gè)數(shù)據(jù)包，具體的網(wǎng)絡(luò)傳輸方案為： ① 源服務(wù)器將待發(fā)送的數(shù)據(jù)包一律復(fù)制若干份并向與之相連的所有賦予其發(fā)送該數(shù)據(jù)包。 ② 服務(wù)器接收到一個(gè)數(shù)據(jù)包后，如果該數(shù)據(jù)包符合下面任何一個(gè)條件： l 數(shù)據(jù)包的源服務(wù)器地址與本服務(wù)器地址相同 l 數(shù)據(jù)包的目的服務(wù)器地址與本服務(wù)器地址相同 l 本服務(wù)器已轉(zhuǎn)發(fā)過與該數(shù)據(jù)包編號(hào)相同的數(shù)據(jù)包 則接收該數(shù)據(jù)包；否則，服務(wù)器將其復(fù)制若干份并向它相連的所有服務(wù)器轉(zhuǎn)發(fā)該數(shù)據(jù)包。 這里，兩臺(tái)服務(wù)器“相連”的含義是它們之間有網(wǎng)絡(luò)傳輸線路直接相連。 現(xiàn)在需要你編一個(gè)程序來模擬SERNET網(wǎng)絡(luò)中的數(shù)據(jù)包傳輸情況。 輸入數(shù)據(jù)： 輸入文件的第一行為一個(gè)正整數(shù)N（N<100），表示SERNET中服務(wù)器的數(shù)目。第二行有N個(gè)互不相等的不超過100的正整數(shù)，表示每個(gè)服務(wù)器的地址。 第三行有一個(gè)正整數(shù)M，表示SERNET中傳輸線路的數(shù)目。接下來的M行每行用三個(gè)正整數(shù)表示一條傳輸線路連接的兩臺(tái)服務(wù)器的地址以及該傳輸線路的傳輸時(shí)間。線路傳輸時(shí)間為不超過100的正整數(shù)。 接下來的一行為一個(gè)正整數(shù)K（K<10000），表示SERNET中數(shù)據(jù)包的數(shù)目。以下的K行每行表示一個(gè)數(shù)據(jù)包的信息，格式為： 數(shù)據(jù)包編號(hào) 起始發(fā)送時(shí)間 源服務(wù)器地址 目的服務(wù)器地址 其中數(shù)據(jù)包的編號(hào)為互不相同的小于100000的正整數(shù)，輸入文件的最后一行為一個(gè)正整數(shù)T（T<10000），T為輸出時(shí)刻，輸入文件中同一行相鄰兩項(xiàng)之間用一個(gè)或多個(gè)空格隔開。 輸出數(shù)據(jù)： 輸出文件僅含義個(gè)整數(shù)P，表示T時(shí)刻后還在網(wǎng)絡(luò)中傳輸?shù)臄?shù)據(jù)包數(shù)目（編號(hào)相同的數(shù)據(jù)包為同一數(shù)據(jù)包）。 約定： ① 本題中所有時(shí)間量的單位均相同； ② 每一條傳輸線路上在同一時(shí)刻能傳輸任意多個(gè)數(shù)據(jù)包。 輸入輸出示例： SERNET.IN SERNET.OUT 4 57 42 10 93 4 57 42 6 42 93 5 42 10 2 10 93 10 2 433 10 57 10 5678 11 42 93 23 1 分析： 很顯然，本題是對(duì)日常生活中的網(wǎng)絡(luò)文件傳輸進(jìn)行模擬。對(duì)于模擬的事物，首先是將其抽象成數(shù)學(xué)模型。于是我們將輸入文件給出的網(wǎng)絡(luò)信息轉(zhuǎn)換成一張帶權(quán)無向圖。網(wǎng)上的服務(wù)器作為頂點(diǎn)，服務(wù)器之間的傳輸線路作為無向邊，傳輸線路的傳輸時(shí)間作為邊上的權(quán)。這里要注意兩點(diǎn)： ① 試題中服務(wù)器數(shù)N的上限是給定的（N<100），可以按慣例采用二維數(shù)組存儲(chǔ)圖的信息。但問題是，服務(wù)器用服務(wù)器的地址予以標(biāo)識(shí)，而這些地址是無序的。如果采用服務(wù)器地址作為數(shù)組下表，即會(huì)帶來計(jì)算的不便，造成內(nèi)存的無端浪費(fèi)。因此我們改變服務(wù)器的標(biāo)識(shí)方式，用服務(wù)器地址的輸入順序標(biāo)識(shí)服務(wù)器并將這些序號(hào)作為數(shù)組下標(biāo)。例如： 服務(wù)器地址 57 42 10 93 服務(wù)器標(biāo)識(shí)（ID） 1 2 3 4 ② 一條傳輸線路上的信息可能會(huì)因?yàn)橛卸喾N傳輸時(shí)間而重復(fù)輸入多次。我們?nèi)∑渲凶钚鬏敃r(shí)間和最大傳輸時(shí)間作為線路的傳輸時(shí)間范圍。若一條傳輸線路的信息僅輸入一次，則線路的最小傳輸時(shí)間的最大傳輸時(shí)間設(shè)為輸入的傳輸時(shí)間。設(shè)： type Tlink = record {傳輸線路的時(shí)間類型} Short， {最短傳輸時(shí)間} Long: Byte; {最長(zhǎng)傳輸時(shí)間} End; var Links: array [1 .. N, 1 .. N] of Tlink; {網(wǎng)絡(luò)} 下表列出了樣例中的網(wǎng)絡(luò)信息： 服務(wù)器I地址（ID） 服務(wù)器J地址（ID） 傳輸時(shí)間 57（1） 42（2） 1 57（1） 42（2） 3 57（1） 42（2） 6 42（2） 93（4） 5 42（2） 10（3） 2 10（3） 93（4） 10 Links[1, 2].Short = Links[2, 1].Short = 1 Links[1,2].Long = Links[2, 1].Long = 6 Links[2, 4].Short = Links[4, 2].Short = 5 Links[2,4].Long = Links[4, 2].Long = 5 Links[2, 3].Short = Links[3, 2].Short = 2 Links[2,3].Long = Links[3, 2].Long = 2 Links[3, 4].Short = Links[4, 3].Short = 10 圖27 網(wǎng)絡(luò)傳輸示例圖 Links[3,4].Long = Links[4, 3].Long = 10 見圖2-17 由于試題約定“每一條傳輸線路上在同一時(shí)刻能傳輸任意多個(gè)數(shù)據(jù)包”，因此數(shù)據(jù)包的傳輸互不影響。我們可以一個(gè)一個(gè)的模擬數(shù)據(jù)包的傳輸過程，從中統(tǒng)計(jì)出T時(shí)刻后仍在網(wǎng)絡(luò)中傳輸?shù)臄?shù)據(jù)包數(shù)。 現(xiàn)在的問題是如何判別T時(shí)刻后當(dāng)前一個(gè)數(shù)據(jù)包是否還在網(wǎng)絡(luò)中傳輸 模擬一個(gè)數(shù)據(jù)包在網(wǎng)絡(luò)中的傳輸情況是算法的基礎(chǔ)。 設(shè)： it——當(dāng)前數(shù)據(jù)包序號(hào)； accepted[I]——服務(wù)器I接受it數(shù)據(jù)包的標(biāo)志（1≦I≦N） recevie[I]是服務(wù)器I向與它相連的所有服務(wù)器轉(zhuǎn)發(fā)數(shù)據(jù)包的開始時(shí)刻。由于服務(wù)器處理數(shù)據(jù)的時(shí)間忽略不計(jì)，因此收到數(shù)據(jù)包的時(shí)刻即為轉(zhuǎn)發(fā)時(shí)刻。Recevie[I] = $FFFF時(shí)說明當(dāng)前未確定服務(wù)器I轉(zhuǎn)發(fā)數(shù)據(jù)包的時(shí)刻或者服務(wù)器I已接受了it。顯然，如果receive[I] <> $FFFF且accepted[I] = false，則服務(wù)器I可能即將收到it。如果按照網(wǎng)絡(luò)的傳輸方案確定服務(wù)器I已接受了it，則accepted[I] = true。 開始時(shí)，it的源服務(wù)器首先將it復(fù)制若干份并同與之相連的所有服務(wù)器發(fā)送，即receive[it的源服務(wù)器]=it的源服務(wù)器的起始發(fā)送時(shí)間，其余服務(wù)器的receive值為$FFFF。此時(shí)，除可確定it的目標(biāo)服務(wù)器（但不能與it的服務(wù)器同址）為接受服務(wù)器外，其余服務(wù)器為收到it，即 if it的源服務(wù)器<>it的目標(biāo)服務(wù)器 then begin accepted[it的目標(biāo)服務(wù)器]:=true； 其余服務(wù)器的accepted值設(shè)為false； end； 然后重復(fù)如下過程： 在可接受it的服務(wù)器集合中尋找一個(gè)最早收到數(shù)據(jù)包的滿足下屬條件的服務(wù)器I： min{receive[I] |（receive[I] <> $FFFF）and（accepted[I] = false）} 服務(wù)器I試圖向與之相連的所有服務(wù)器J（Links[I, J].Short <> 0 | 1 ≦ J ≦ N）發(fā)送數(shù)據(jù)包。 如果服務(wù)器J可收到it（receive[I] + Links[I, J].Short < receive[J]），則將服務(wù)器J的receive值修正為receive[I] + Links[I, J].Short，讓其在該時(shí)刻收到和轉(zhuǎn)發(fā)it； 如果其中一個(gè)服務(wù)器J在T時(shí)刻后才能接受來自服務(wù)器I的it（receive[I] + Links[I,J].Long > T），則判定T時(shí)刻后仍有一個(gè)數(shù)據(jù)包在網(wǎng)絡(luò)中傳輸，算法結(jié)束； 如果在T時(shí)刻前與服務(wù)器I相連的所有線路完成傳輸it的任務(wù)，則按照網(wǎng)絡(luò)的傳輸方案確定服務(wù)器I接受了it，accepted[I]True，receive[I]$FFFF。 這一過程一直進(jìn)行到所有服務(wù)器都不再轉(zhuǎn)發(fā)數(shù)據(jù)包為止，即所有服務(wù)器的receive值為$FFFF。 上述算法由一個(gè)布爾函數(shù)Alive（it）描述。若數(shù)據(jù)包it在T時(shí)刻后還在網(wǎng)絡(luò)中傳播，則該函數(shù)返回True；否則返回False。 算法描述如下： function Alive(it): Boolean; Begin Alive := True; 初始化receive的值為$FFFF; Receive[it的源服務(wù)器] = it的開始發(fā)送時(shí)間 初始化Accepted的值為False; Accepted[it的目標(biāo)服務(wù)器] = true repeat 尋找一個(gè)receive值最小的服務(wù)器I; if Receive[I] = $FFFF then Break ; if Accepted[I] = False then for J := 1 to N do begin if 服務(wù)器I與服務(wù)器J有傳輸線路 then 修正receive[J]值; if 服務(wù)器J在T時(shí)刻后才能接收it then exit; end; Accepted[I] := True; Receive[I] := $FFFF; until False; Alive := False; end; 對(duì)每一個(gè)數(shù)據(jù)包都求一次Alive，Alive函數(shù)值為True的次數(shù)P就是T時(shí)刻后仍在網(wǎng)絡(luò)中傳輸?shù)臄?shù)據(jù)包數(shù)。如下： P := 0; for I := 1 to 數(shù)據(jù)包數(shù)K do if Alive(I) then P := P + 1； Writeln(P) 程序如下： {$R-,S-,Q-} program NOI98_5; const Inp = sernet.in; {輸入文件名串} Outp = sernet.out; {輸出文件名串} MaxN = 99; {服務(wù)器數(shù)的上限} MaxK = 9999; {數(shù)據(jù)包數(shù)的上限} type TPackage = record {數(shù)據(jù)包類型} Send: Word; {發(fā)出時(shí)刻} Source: Byte; {源服務(wù)器} Target: Byte; {目的服務(wù)器} end; TLink = record {傳輸線的時(shí)間類型} Short: Byte; {最短傳輸時(shí)間} Long: Byte; {最長(zhǎng)傳輸時(shí)間} end; var N: Byte; {服務(wù)器數(shù)} K: Word; {數(shù)據(jù)包數(shù)} T: Word; {輸出時(shí)刻} P: Word; {輸出時(shí)刻后還在網(wǎng)絡(luò)中傳輸?shù)臄?shù)據(jù)包數(shù)} Index: array [1 .. MaxN] of Byte; {Index[I]——地址為I的服務(wù)器序號(hào)} Links: array [1 .. MaxN, 1.. MaxN] of TLink; {Links[I, J]——服務(wù)器I的服務(wù)器J的傳輸時(shí)間} Packages: array [1 .. MaxPackage] of TPackage; {數(shù)據(jù)包序列} procedure Init; {輸入數(shù)據(jù)} var I, J: Word; M: Word; {傳輸線路數(shù)} S1, S2: Byte; {當(dāng)前傳輸線相連的兩個(gè)服務(wù)器序號(hào)} Time: Word; {當(dāng)前傳輸線路的傳輸時(shí)間} PackageID: Longint; {數(shù)據(jù)包編號(hào)} Begin Assign(Input, Inp); Reset(Input); Readln(N); {讀服務(wù)器數(shù)} for I := 1 to N do begin {度入每個(gè)服務(wù)器地址，計(jì)算Index表} Read(J); Index[J] := I; end; Readln(M); {讀傳輸線路輸} FillChar(Links, Sizeof(Links), 0); {Links表初始化} for I := 1 to M do begin {輸入每條線路的信息} Readln(S1, S2, Time); {讀相連的兩臺(tái)服務(wù)器地址和傳輸時(shí)間} S1 := Index[S1]; {計(jì)算這兩臺(tái)服務(wù)器的序號(hào)} S2 := Index[S2]; if (Links[S1,S2].Short=0)or(Links[S1,S2].Short>Time) then {計(jì)算該線路的最短傳輸時(shí)間和最長(zhǎng)傳輸時(shí)間} Links[S1, S2].Short := Time; if Links[S1, S2].Long < Time then Links[S1, S2].Long := Time; Links[S2, S1] := Links[S1, S2]; end; Readln(K); {讀數(shù)據(jù)包數(shù)} for I := 1 to K do {讀每一個(gè)數(shù)據(jù)包的信息} with Packages[I] do Readln(PackageID, Send, Source, Target); {讀第I個(gè)數(shù)據(jù)包的編號(hào)，起始發(fā)送時(shí)間，源服務(wù)器地址，目的服務(wù)器地址} Readln(T); {讀入輸出時(shí)刻} Close(Input); end; function Alive(It: TPackage): Boolean; {模擬數(shù)據(jù)包It在T時(shí)刻還在網(wǎng)絡(luò)中傳輸，則返回True；否則返回False} var I, J: Byte; Time: Word; Receive: array [1 .. MaxN] of Word; {Receive[I]：服務(wù)器I收到下一個(gè)數(shù)據(jù)的時(shí)刻} Accepted: array [1..MaxN] of Boolean; {Accepted[I]：為服務(wù)器I接收It的標(biāo)志} begin Alive := True; FillChar(Receive, Sizeof(Receive), $FF); {初始時(shí)，所有服務(wù)器未收到任何數(shù)據(jù)包} FillChar(Accepted, Sizeof(Accepted), False); Receive[Index[It.Source]] := It.Send; {源服務(wù)器在發(fā)送了It后開始接受下一個(gè)數(shù)據(jù)包} if It.Source <> It.Target then Accepted[Index[It.Target]] := True; {若源服務(wù)器與目的服務(wù)器不同，則確定目的服務(wù)器收到數(shù)據(jù)包It} repeat I := 1; {計(jì)算最早收到下一個(gè)數(shù)據(jù)包的服務(wù)器I} for J := 2 to N do if Receive[J] < Receive[I] then I := J; if Receive[I] = $FFFF then Break; {若所有服務(wù)器收到It，則返回false} if not Accepted[I] then begin {若服務(wù)器未接收數(shù)據(jù)包It，則搜索與服務(wù)器I相連的服務(wù)器} for J := 1 to N do if Links[I, J].Short <> 0 then begin Time := Receive[I] + Links[I, J].Short; if Time < Receive[J] then Receive[J] := Time; {若服務(wù)器J能在Receive[J]前收到來自服務(wù)器I發(fā)來的數(shù)據(jù)包} if Receive[I] + Links[I, J].Long > T then Exit; {若在該線路上傳輸It將超是，則返回True} end; Accepted[I] := True; {設(shè)定服務(wù)器I收到It標(biāo)志} end; Receive[I] := $FFFF; {設(shè)服務(wù)器I轉(zhuǎn)發(fā)過It標(biāo)志} until False; Alive := False; {It在TimeLine時(shí)刻前結(jié)束傳輸} end; procedure Main; {統(tǒng)計(jì)T時(shí)刻后還在網(wǎng)絡(luò)中傳輸?shù)臄?shù)據(jù)包數(shù)} var Y: Word; begin P := 0; for Y := 1 to K do if Alive(Packages[Y]) then Inc(P); end; procedure Out; {輸出} begin Assign(Output, Outp); Rewrite(Output); Writeln(P); Close(Output); end; begin Init; Main; Out; end. 習(xí) 題 1．多精度值處理 古印度國(guó)王要褒獎(jiǎng)他的聰明能干的宰相達(dá)依爾（國(guó)際象棋的發(fā)明者），問他要什么。達(dá)依爾回答：“殿下只要在棋盤上第一個(gè)格子放一粒麥粒，在第二個(gè)格子放兩粒，在第三個(gè)格子放四粒，以后的格子都是前一格的兩倍。如此放滿64格，我就心滿意足了?！眹?guó)王想，這不難辦到。但一袋麥子很快就用完了，一倉(cāng)庫(kù)也用完了，全印度的麥子也遠(yuǎn)遠(yuǎn)不夠。請(qǐng)編程計(jì)算所需的麥子總數(shù)。 2．邏輯判斷題 來自不同國(guó)家的四位留學(xué)生A,B,C,D在一起交談,他們只會(huì)中、英、法、日四種語言中的2種,情況是, 沒有人既會(huì)日語又會(huì)法語;A會(huì)日語,但D不會(huì),A和D能互相交談,B不會(huì)英語,但A和C交談時(shí)卻要B當(dāng)翻譯,B,C,D三個(gè)想互相交談,但找不到共同的語言,只有一種語言3人都會(huì),編程確定A,B,C,D四位留學(xué)生各會(huì)哪兩種語言。 3．枚舉排列數(shù) 任意輸入由小寫字母組成的字符串（長(zhǎng)度不超過15），求從中取出K個(gè)小寫字母的排列和排列總數(shù)。 4．貨郎擔(dān)問題。 某售貨員要到若干個(gè)村莊售貨，各個(gè)村莊的路程是已知的，為了提高效率，售貨員決定從商店出發(fā)到每個(gè)村莊售一次貨然后返回商店，問他應(yīng)選擇一條什么樣的路徑，才能使走的總路程最短。 輸入:從文本文件讀入N(第一行)，表示一個(gè)商店和N-1個(gè)村莊。 其下N行為一個(gè)N*N的矩陣，每個(gè)矩陣元素(i，j)的值表示從i村莊(或商店)到j(luò)村莊(或商店)的距離。i=1或j=1表示商店。數(shù)值均為整數(shù)，數(shù)值之間用空格隔開。 輸出:在屏幕上輸出從商店出發(fā)經(jīng)過每一個(gè)村莊一次，最后返回商店的路線(第一行)輸出最短路線長(zhǎng)度(第二行)。 5．汽油花費(fèi) 一些旅行車從城市A到城市B運(yùn)送包裹。在沿途由很多價(jià)格不同的加油站。第一個(gè)加油站的位置在路程的開始。旅行車的油箱容積可能不同，車在沿途需要及時(shí)給油箱加油，我們假設(shè)，每個(gè)油站有足夠的油。 輸入：在文本文件中的第一行為一個(gè)整數(shù)p表示油箱的容量, 1 < p <= 1000000. 在第二行有一個(gè)整數(shù)n表是沿途加油站的數(shù)目。1 < n <= 1000000。接下來的n行每行有兩個(gè)用單個(gè)正整數(shù)分隔的整數(shù)ci, di, 其中ci表示第I油站的價(jià)格。di 表示I和第(i+1)個(gè)油站的距離- (dn 就是最后一個(gè)油站到結(jié)束點(diǎn)的距離)。1 <= ci <= 1000, 1 <= di <= 1000000。AB的路線長(zhǎng)度(所有di之和) 不超過1000000 輸出：路線AB中加油的最少花費(fèi). 6．剔除多余括號(hào) 鍵盤輸入一個(gè)含有括號(hào)的四則運(yùn)算表式，可能含有多余的括號(hào)，編程整理該表達(dá)式，去掉所有多余的括號(hào)，原表達(dá)式中所有變量和運(yùn)算符相對(duì)位置保持不變，并保持與原表達(dá)式等價(jià)。 　　例：輸入表達(dá)式　　　　　　　應(yīng)輸出表達(dá)式 　　　　a+(b+c) a+b+c (a*b)+c/d a*b+c/d a+b/(c-d) a+b/(c-d) 　注意輸入a+b時(shí)不能輸出b+a。 　　表達(dá)式以字符串輸入，長(zhǎng)度不超過255。輸入不要判錯(cuò)。 所有變量為單個(gè)小寫字母。只是要求去掉所有多余括號(hào)，不要求對(duì)表達(dá)式化簡(jiǎn)