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) 板書(shū)示意: 1) 模擬的引入(例31) 2) 模擬的應(yīng)用(例32) 授課過(guò)程: 有些問(wèn)題很難建立枚舉、遞歸等算法,甚至建立不了數(shù)學(xué)模型,但可以根據(jù)問(wèn)題的描述,用程序模擬某種現(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ī)值來(lái)模擬事件的進(jìn)程,在隨機(jī)模擬過(guò)程中,通過(guò)修改變問(wèn)題的各種參數(shù),進(jìn)而觀察變更這些參數(shù)所引起的狀態(tài)變化。一般情況是,題目給出某一概率,設(shè)計(jì)者利用隨機(jī)函數(shù)去設(shè)定在某一范圍的隨機(jī)值,將符合概率的隨機(jī)值作為參數(shù)。然后根據(jù)這一模擬模型展開(kāi)算法設(shè)計(jì)。隨機(jī)模擬的關(guān)鍵是在概率已知的條件下,如何確定隨機(jī)值產(chǎn)生的范圍。這個(gè)隨機(jī)值設(shè)計(jì)得好,模擬效果就好。本節(jié)僅討論決定性模擬問(wèn)題。有關(guān)隨機(jī)模擬的問(wèn)題,大家可以參考一些相關(guān)書(shū)籍。 例31:約瑟夫問(wèn)題 N個(gè)人排成一個(gè)圓圈,然后把這N個(gè)人按逆時(shí)針?lè)较蚍謩e編號(hào)為1、2、……、N。從編號(hào)為1的人開(kāi)始按逆時(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 {模擬出圈過(guò)程} 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ò)開(kāi)發(fā)小組設(shè)計(jì)了一種稱為SERNET的網(wǎng)絡(luò),并希望開(kāi)發(fā)一個(gè)模擬軟件來(lái)模擬該網(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ò)傳輸過(guò)程中將各種傳輸數(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ā)過(guò)與該數(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è)程序來(lái)模擬SERNET網(wǎng)絡(luò)中的數(shù)據(jù)包傳輸情況。 輸入數(shù)據(jù): 輸入文件的第一行為一個(gè)正整數(shù)N(N<100),表示SERNET中服務(wù)器的數(shù)目。第二行有N個(gè)互不相等的不超過(guò)100的正整數(shù),表示每個(gè)服務(wù)器的地址。 第三行有一個(gè)正整數(shù)M,表示SERNET中傳輸線路的數(shù)目。接下來(lái)的M行每行用三個(gè)正整數(shù)表示一條傳輸線路連接的兩臺(tái)服務(wù)器的地址以及該傳輸線路的傳輸時(shí)間。線路傳輸時(shí)間為不超過(guò)100的正整數(shù)。 接下來(lái)的一行為一個(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è)空格隔開(kāi)。 輸出數(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ú)向圖。網(wǎng)上的服務(wù)器作為頂點(diǎn),服務(wù)器之間的傳輸線路作為無(wú)向邊,傳輸線路的傳輸時(shí)間作為邊上的權(quán)。這里要注意兩點(diǎn): ① 試題中服務(wù)器數(shù)N的上限是給定的(N<100),可以按慣例采用二維數(shù)組存儲(chǔ)圖的信息。但問(wèn)題是,服務(wù)器用服務(wù)器的地址予以標(biāo)識(shí),而這些地址是無(wú)序的。如果采用服務(wù)器地址作為數(shù)組下表,即會(huì)帶來(lái)計(jì)算的不便,造成內(nèi)存的無(wú)端浪費(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 見(jiàn)圖2-17 由于試題約定“每一條傳輸線路上在同一時(shí)刻能傳輸任意多個(gè)數(shù)據(jù)包”,因此數(shù)據(jù)包的傳輸互不影響。我們可以一個(gè)一個(gè)的模擬數(shù)據(jù)包的傳輸過(guò)程,從中統(tǒng)計(jì)出T時(shí)刻后仍在網(wǎng)絡(luò)中傳輸?shù)臄?shù)據(jù)包數(shù)。 現(xiàn)在的問(wè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ù)包的開(kāi)始時(shí)刻。由于服務(wù)器處理數(shù)據(jù)的時(shí)間忽略不計(jì),因此收到數(shù)據(jù)包的時(shí)刻即為轉(zhuǎn)發(fā)時(shí)刻。Recevie[I] = $FFFF時(shí)說(shuō)明當(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。 開(kāi)始時(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ù)如下過(guò)程: 在可接受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í)刻后才能接受來(lái)自服務(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。 這一過(guò)程一直進(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的開(kāi)始發(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后開(kāi)始接受下一個(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]前收到來(lái)自服務(wù)器I發(fā)來(lái)的數(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ā)過(guò)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ā)明者),問(wèn)他要什么。達(dá)依爾回答:“殿下只要在棋盤上第一個(gè)格子放一粒麥粒,在第二個(gè)格子放兩粒,在第三個(gè)格子放四粒,以后的格子都是前一格的兩倍。如此放滿64格,我就心滿意足了?!眹?guó)王想,這不難辦到。但一袋麥子很快就用完了,一倉(cāng)庫(kù)也用完了,全印度的麥子也遠(yuǎn)遠(yuǎn)不夠。請(qǐng)編程計(jì)算所需的麥子總數(shù)。 2.邏輯判斷題 來(lái)自不同國(guó)家的四位留學(xué)生A,B,C,D在一起交談,他們只會(huì)中、英、法、日四種語(yǔ)言中的2種,情況是, 沒(méi)有人既會(huì)日語(yǔ)又會(huì)法語(yǔ);A會(huì)日語(yǔ),但D不會(huì),A和D能互相交談,B不會(huì)英語(yǔ),但A和C交談時(shí)卻要B當(dāng)翻譯,B,C,D三個(gè)想互相交談,但找不到共同的語(yǔ)言,只有一種語(yǔ)言3人都會(huì),編程確定A,B,C,D四位留學(xué)生各會(huì)哪兩種語(yǔ)言。 3.枚舉排列數(shù) 任意輸入由小寫字母組成的字符串(長(zhǎng)度不超過(guò)15),求從中取出K個(gè)小寫字母的排列和排列總數(shù)。 4.貨郎擔(dān)問(wèn)題。 某售貨員要到若干個(gè)村莊售貨,各個(gè)村莊的路程是已知的,為了提高效率,售貨員決定從商店出發(fā)到每個(gè)村莊售一次貨然后返回商店,問(wèn)他應(yīng)選擇一條什么樣的路徑,才能使走的總路程最短。 輸入:從文本文件讀入N(第一行),表示一個(gè)商店和N-1個(gè)村莊。 其下N行為一個(gè)N*N的矩陣,每個(gè)矩陣元素(i,j)的值表示從i村莊(或商店)到j(luò)村莊(或商店)的距離。i=1或j=1表示商店。數(shù)值均為整數(shù),數(shù)值之間用空格隔開(kāi)。 輸出:在屏幕上輸出從商店出發(fā)經(jīng)過(guò)每一個(gè)村莊一次,最后返回商店的路線(第一行)輸出最短路線長(zhǎng)度(第二行)。 5.汽油花費(fèi) 一些旅行車從城市A到城市B運(yùn)送包裹。在沿途由很多價(jià)格不同的加油站。第一個(gè)加油站的位置在路程的開(kāi)始。旅行車的油箱容積可能不同,車在沿途需要及時(shí)給油箱加油,我們假設(shè),每個(gè)油站有足夠的油。 輸入:在文本文件中的第一行為一個(gè)整數(shù)p表示油箱的容量, 1 < p <= 1000000. 在第二行有一個(gè)整數(shù)n表是沿途加油站的數(shù)目。1 < n <= 1000000。接下來(lái)的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之和) 不超過(guò)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)度不超過(guò)255。輸入不要判錯(cuò)。 所有變量為單個(gè)小寫字母。只是要求去掉所有多余括號(hào),不要求對(duì)表達(dá)式化簡(jiǎn)- 1.請(qǐng)仔細(xì)閱讀文檔,確保文檔完整性,對(duì)于不預(yù)覽、不比對(duì)內(nèi)容而直接下載帶來(lái)的問(wèn)題本站不予受理。
- 2.下載的文檔,不會(huì)出現(xiàn)我們的網(wǎng)址水印。
- 3、該文檔所得收入(下載+內(nèi)容+預(yù)覽)歸上傳者、原創(chuàng)作者;如果您是本文檔原作者,請(qǐng)點(diǎn)此認(rèn)領(lǐng)!既往收益都?xì)w您。
下載文檔到電腦,查找使用更方便
9.9 積分
下載 |
- 配套講稿:
如PPT文件的首頁(yè)顯示word圖標(biāo),表示該P(yáng)PT已包含配套word講稿。雙擊word圖標(biāo)可打開(kāi)word文檔。
- 特殊限制:
部分文檔作品中含有的國(guó)旗、國(guó)徽等圖片,僅作為作品整體效果示例展示,禁止商用。設(shè)計(jì)者僅對(duì)作品中獨(dú)創(chuàng)性部分享有著作權(quán)。
- 關(guān) 鍵 詞:
- 2019-2020年高中信息技術(shù) 全國(guó)青少年奧林匹克聯(lián)賽教案 模擬法二 2019 2020 年高 信息技術(shù) 全國(guó)青少年 奧林匹克 聯(lián)賽 教案 模擬
鏈接地址:http://m.italysoccerbets.com/p-2618486.html