?? no3.htm
字號:
<html xmlns:o="urn:schemas-microsoft-com:office:office"xmlns:w="urn:schemas-microsoft-com:office:word"xmlns="http://www.w3.org/TR/REC-html40"><head><meta http-equiv=Content-Type content="text/html; charset=GB2312"><meta name=ProgId content=Word.Document><meta name=Generator content="Microsoft Word 9"><meta name=Originator content="Microsoft Word 9"><link rel=File-List href="./no3.files/filelist.xml"><title> NOI'96-97 天津隊組隊選拔賽試題及分析</title><!--[if gte mso 9]><xml> <o:DocumentProperties> <o:Author>lixuewu</o:Author> <o:LastAuthor>a</o:LastAuthor> <o:Revision>2</o:Revision> <o:TotalTime>2</o:TotalTime> <o:Created>1996-12-31T17:58:00Z</o:Created> <o:LastSaved>1996-12-31T17:58:00Z</o:LastSaved> <o:Pages>15</o:Pages> <o:Words>3255</o:Words> <o:Characters>18557</o:Characters> <o:Company>aaa</o:Company> <o:Lines>154</o:Lines> <o:Paragraphs>37</o:Paragraphs> <o:CharactersWithSpaces>22789</o:CharactersWithSpaces> <o:Version>9.2812</o:Version> </o:DocumentProperties></xml><![endif]--><!--[if gte mso 9]><xml> <w:WordDocument> <w:PunctuationKerning/> <w:DrawingGridHorizontalSpacing>5.25 磅</w:DrawingGridHorizontalSpacing> <w:DrawingGridVerticalSpacing>7.15 磅</w:DrawingGridVerticalSpacing> <w:DisplayHorizontalDrawingGridEvery>0</w:DisplayHorizontalDrawingGridEvery> <w:DisplayVerticalDrawingGridEvery>2</w:DisplayVerticalDrawingGridEvery> <w:Compatibility> <w:SpaceForUL/> <w:BalanceSingleByteDoubleByteWidth/> <w:DoNotLeaveBackslashAlone/> <w:ULTrailSpace/> <w:DoNotExpandShiftReturn/> <w:AdjustLineHeightInTable/> <w:UseFELayout/> </w:Compatibility> </w:WordDocument></xml><![endif]--><style><!-- /* Font Definitions */@font-face {font-family:宋體; panose-1:2 1 6 0 3 1 1 1 1 1; mso-font-alt:SimSun; mso-font-charset:134; mso-generic-font-family:auto; mso-font-pitch:variable; mso-font-signature:3 135135232 16 0 262145 0;}@font-face {font-family:"\@宋體"; panose-1:2 1 6 0 3 1 1 1 1 1; mso-font-charset:134; mso-generic-font-family:auto; mso-font-pitch:variable; mso-font-signature:1 135135232 16 0 262144 0;} /* Style Definitions */p.MsoNormal, li.MsoNormal, div.MsoNormal {mso-style-parent:""; margin:0cm; margin-bottom:.0001pt; text-align:justify; text-justify:inter-ideograph; mso-pagination:none; font-size:10.5pt; mso-bidi-font-size:12.0pt; font-family:"Times New Roman"; mso-fareast-font-family:宋體; mso-font-kerning:1.0pt;}p.MsoPlainText, li.MsoPlainText, div.MsoPlainText {margin:0cm; margin-bottom:.0001pt; text-align:justify; text-justify:inter-ideograph; mso-pagination:none; font-size:10.5pt; font-family:宋體; mso-hansi-font-family:"Courier New"; mso-bidi-font-family:"Courier New"; mso-font-kerning:1.0pt;} /* Page Definitions */@page {mso-page-border-surround-header:no; mso-page-border-surround-footer:no; mso-gutter-position:top;}@page Section1 {size:21.0cm 842.0pt; margin:79.4pt 87.7pt 70.9pt 87.65pt; mso-header-margin:42.55pt; mso-footer-margin:49.6pt; mso-paper-source:0;}div.Section1 {page:Section1;}--></style></head><body lang=ZH-CN style='tab-interval:21.0pt;text-justify-trim:punctuation' bgcolor="#e8ffe8"><div class=Section1><p class=MsoPlainText><span lang=EN-US><![if !supportEmptyParas]> <![endif]><o:p></o:p></span></p><p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:yes"> </span>NOI'96-97 天津隊組隊選拔賽試題及分析</span></p><p class=MsoPlainText style='text-indent:42.0pt;mso-char-indent-count:4.0;mso-char-indent-size:10.5pt'><span lang=EN-US>(原載：信息學奧林匹克，1999，1)</span></p><p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:yes"> </span>天津師范大學計算機科學系<span style="mso-spacerun: yes"> </span>李學武</span></p><p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:yes"> </span></span></p><p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:yes"> </span>為了組建參加 NOI'96 及 NOI'97 比賽的天津代表隊,天津市曾于1996年5月和12月</span></p><p class=MsoPlainText>組織了兩屆選拔賽<span lang=EN-US>,比賽收到了令人滿意的效果,水平較高的兩三位選手的成績明顯高于其他</span></p><p class=MsoPlainText>選手<span lang=EN-US>,組隊人選無可爭議.下面給出的試題,分析及參考程序都是筆者完成的.限于筆者的水平</span></p><p class=MsoPlainText>和精力<span lang=EN-US>,幾乎每一個程序及算法都有進一步優(yōu)化的余地.讀者不妨嘗試一下,或許從中會有所</span></p><p class=MsoPlainText>收益<span lang=EN-US>.</span></p><p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:yes"> </span></span></p><p class=MsoPlainText>一<span lang=EN-US>. 工作安排問題 (第一屆選拔賽第一題)</span></p><p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:yes"> </span>【試題】 現(xiàn)有 N (N≤8) 件工作, 分別由 N 個人完成, 每人都完成一件,且只完成一 件, </span></p><p class=MsoPlainText>每人完成不同工作的時間不同<span lang=EN-US>. 試設計一種分配工作方案, 使完成 N 件工作所需的總時間</span></p><p class=MsoPlainText>最少<span lang=EN-US>.</span></p><p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:yes"> </span>原始數(shù)據(jù)由文本文件 EXAM1.TXT 給出, 其格式如下:</span></p><p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:yes"> </span>第 1 行:<spanstyle="mso-spacerun: yes"> </span>工作任務數(shù)(N)</span></p><p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:yes"> </span>第 2 -- N+1 行:第 i+1 行為第 i 個人完成各件工作所需的時間. 以</span></p><p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:yes"> </span>上各數(shù)均為不超過 1000 的正整數(shù).</span></p><p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:yes"> </span>計算結果可直接在屏幕上輸出: 第一行為工作分配方案, 共 N組, 每組數(shù)</span></p><p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:yes"> </span>據(jù)的形式為 a-b, 其中 a 為工作人員編號, b 為他應完成的工作序號.</span></p><p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:yes"> </span>例: 設 EXAM1.TXT 的數(shù)據(jù)為:</span></p><p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:yes"> </span>4</span></p><p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:yes"> </span>2<spanstyle="mso-spacerun: yes"> </span>15<span style="mso-spacerun:yes"> </span>13<span style="mso-spacerun: yes"> </span>4</span></p><p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:yes"> </span>10<spanstyle="mso-spacerun: yes"> </span>4<span style="mso-spacerun: yes"> </span>14<span style="mso-spacerun: yes"> </span>15</span></p><p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:yes"> </span>9<spanstyle="mso-spacerun: yes"> </span>14<span style="mso-spacerun:yes"> </span>16<span style="mso-spacerun: yes"> </span>13</span></p><p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:yes"> </span>7<spanstyle="mso-spacerun: yes"> </span>8<span style="mso-spacerun: yes"> </span>11<span style="mso-spacerun: yes"> </span>9</span></p><p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:yes"> </span>對此, 一個正確的輸出可以是</span></p><p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:yes"> </span>1-4, 2-2, 3-1, 4-3</span></p><p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:yes"> </span>TOTAL=28</span></p><p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun: yes"> </span>【分析】 此題為常規(guī)題,以避免選手分數(shù)太低,分析及程序部分從略.</span></p><p class=MsoPlainText><span lang=EN-US><![if !supportEmptyParas]> <![endif]><o:p></o:p></span></p><p class=MsoPlainText>二<span lang=EN-US>. 圓盤問題 (第一屆選拔賽第二題)</span></p><p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:yes"> </span>【試題】從左向右依次安放 4 根細柱 A,B,C,D. 在 A 上套有N (N≤20) 個直</span></p><p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:yes"> </span>徑相同的圓盤, 從下到上依次用連續(xù)的小寫字母 a,b,c,...編號, 將這些圓盤經(jīng)過</span></p><p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:yes"> </span>B, C 單向地移入 D (即不允許從右向左移動). 圓盤可在 B,C 中暫存. 從鍵</span></p><p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:yes"> </span>盤輸入 N, 及前 N 個小寫字母的一個排列, 它表示最后在 D 盤上形成的一個</span></p><p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:yes"> </span>從下到上的圓盤序列. 請用文本文件 ANS2.TXT 輸出形成這一排列的操作過程.</span></p><p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:yes"> </span>該文件的每一行為一個形如 "k M L" 的字母序列, 其中 k 為圓盤編號, M 為</span></p><p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:yes"> </span>k 盤原先的柱號, L 為新柱號. 或者直接在屏幕上輸出"No", 表示不能生成這</span></p><p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:yes"> </span>種排列.</span></p><p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:yes"> </span></span></p><p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:yes"> </span>例:<span style="mso-spacerun:yes"> </span><span style="mso-spacerun: yes"> </span>┃<span style="mso-spacerun:yes"> </span>┃<span style="mso-spacerun:yes"> </span>┃<span style="mso-spacerun:yes"> </span>┃</span></p><p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:yes"> </span>鍵盤輸入:<span style="mso-spacerun:yes"> </span>┃<span style="mso-spacerun: yes"> </span>┃<spanstyle="mso-spacerun: yes"> </span>┃<spanstyle="mso-spacerun: yes"> </span>┃</span></p><p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:yes"> </span>3<spanstyle="mso-spacerun:yes"> </span>d<span style="mso-spacerun: yes"> </span>━╋━<spanstyle="mso-spacerun: yes"> </span>┃<span style="mso-spacerun:yes"> </span>┃<span style="mso-spacerun:yes"> </span>┃</span></p><p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:yes"> </span>acb<spanstyle="mso-spacerun:yes"> </span>c<span style="mso-spacerun: yes"> </span>━╋━<spanstyle="mso-spacerun: yes"> </span>┃<span style="mso-spacerun:yes"> </span>┃<span style="mso-spacerun:yes"> </span>┃</span></p><p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:yes"> </span>則一個正確的輸出文件<span style="mso-spacerun:yes"> </span>b<spanstyle="mso-spacerun: yes"> </span>━╋━<span style="mso-spacerun:yes"> </span>┃<span style="mso-spacerun:yes"> </span>┃<span style="mso-spacerun:yes"> </span>┃</span></p><p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun: yes"> </span>可以是:<span style="mso-spacerun:yes"> </span>a<span style="mso-spacerun: yes"> </span>━╋━<spanstyle="mso-spacerun: yes"> </span>┃<span style="mso-spacerun:yes"> </span>┃<span style="mso-spacerun:yes"> </span>┃</span></p><p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:yes"> </span>c<span style="mso-spacerun:yes"> </span>A<span style="mso-spacerun: yes"> </span>B<spanstyle="mso-spacerun:yes"> </span>━━┻━━━┻━━━┻━━━┻━?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -