《算法分析與設(shè)計(jì)》實(shí)驗(yàn)指導(dǎo)書

1、算法分析與設(shè)計(jì)實(shí)驗(yàn)指導(dǎo)書重慶郵電大學(xué)應(yīng)用技術(shù)學(xué)院二八年四月算法分析與設(shè)計(jì)實(shí)驗(yàn)?zāi)康呐c要求一、實(shí)驗(yàn)?zāi)康乃惴ǚ治雠c設(shè)計(jì)是信息與計(jì)算科學(xué)專業(yè)中一門重要的專業(yè)課程。當(dāng)用計(jì)算機(jī)來解決實(shí)際問題時(shí)，就要涉及到對實(shí)際問題進(jìn)行抽象模擬，也就是數(shù)學(xué)建模的過程，然后再設(shè)計(jì)相應(yīng)的解決算法來解決實(shí)際問題，還要驗(yàn)證所設(shè)計(jì)的算法能夠在可忍受或可達(dá)到的時(shí)間和空間內(nèi)完成任務(wù)，因此算法的分析與設(shè)計(jì)就成了非常重要的環(huán)節(jié)。通過理論課的學(xué)習(xí)，我們知道要想設(shè)計(jì)一個(gè)算法必須從算法設(shè)計(jì)-算法確認(rèn)-算法分析-編碼-檢查-調(diào)試-計(jì)時(shí)，七大步驟嚴(yán)格執(zhí)行，所以讀者可嚴(yán)格按照以上步驟進(jìn)行，為以后進(jìn)行算法研究的工作打下堅(jiān)實(shí)的基礎(chǔ)。二、實(shí)驗(yàn)要求1準(zhǔn)備好上機(jī)

2、所需要的程序，并經(jīng)人工檢查后才能上機(jī)，以提高上機(jī)效率。對程序中自己有疑問的地方應(yīng)作記號，以便在上機(jī)時(shí)給予注意。不得抄別人所編的程序。 2上機(jī)輸入并調(diào)試所編的程序。 3上機(jī)結(jié)束后，提交實(shí)驗(yàn)報(bào)告，實(shí)驗(yàn)報(bào)告應(yīng)包括以下內(nèi)容：（1）題目；（2）算法的基本思想描述；（3）算法分析；（4）主要數(shù)據(jù)結(jié)構(gòu)描述；（5）程序流程圖； （6）程序清單；（7）運(yùn)行的結(jié)果；（8）對運(yùn)行情況所作的分析以及本次調(diào)試程序所取的經(jīng)驗(yàn)。如果程序未通過，應(yīng)分析其原因。三、實(shí)驗(yàn)步驟1問題分析和任務(wù)的定義明確問題要求做什么，限制做什么（本步強(qiáng)調(diào)做什么，而不是怎么做）。對問題的描述應(yīng)避開算法和所涉及的數(shù)據(jù)類型，而是所完成的任務(wù)做出明確的回

3、答。如輸入數(shù)據(jù)的類型、值的范圍以及輸入的形式；輸出數(shù)據(jù)的類型、值得范圍及輸出的形式；這異步還應(yīng)該為調(diào)試程序準(zhǔn)備好測試數(shù)據(jù)，包括合法的輸入數(shù)據(jù)和非法形式的輸入數(shù)據(jù)。2 數(shù)據(jù)類型和系統(tǒng)設(shè)計(jì)在設(shè)計(jì)這一步驟中分為邏輯設(shè)計(jì)和詳細(xì)設(shè)計(jì)兩步實(shí)現(xiàn)。邏輯設(shè)計(jì)指的是，為問題的描述中涉及的操作對象定義相應(yīng)的數(shù)據(jù)類型，并按照以數(shù)據(jù)結(jié)構(gòu)為中心的原則劃分模塊，定義主模塊和各抽象數(shù)據(jù)類型；詳細(xì)設(shè)計(jì)則為定義相應(yīng)的存儲結(jié)構(gòu)并寫出各函數(shù)的偽碼算法。在這個(gè)過程中，要綜合考慮系統(tǒng)的功能，使得系統(tǒng)結(jié)構(gòu)清晰、合理、簡單和易于調(diào)試，抽象數(shù)據(jù)類型的實(shí)現(xiàn)盡可能做到數(shù)據(jù)的封裝，基本操作的規(guī)格說明盡可能的明確和具體。作為邏輯設(shè)計(jì)的結(jié)果。應(yīng)寫出每個(gè)

4、抽象數(shù)據(jù)類型的定義（包括數(shù)據(jù)結(jié)構(gòu)的描述和每個(gè)基本操作的規(guī)格說明），各個(gè)主要模塊的算法，并畫出模塊之間的調(diào)用關(guān)系圖。詳細(xì)設(shè)計(jì)的結(jié)果是對數(shù)據(jù)結(jié)構(gòu)和基本操作的規(guī)格說明做出進(jìn)一步的求精，寫出數(shù)據(jù)存儲結(jié)構(gòu)的類型定義，按照算法書寫規(guī)范用類c語言寫出函數(shù)形式的算法框架。3 編碼實(shí)現(xiàn)和靜態(tài)檢查4 上機(jī)準(zhǔn)備和上機(jī)調(diào)試5 總結(jié)和整理實(shí)習(xí)報(bào)告四、實(shí)驗(yàn)總結(jié)對實(shí)驗(yàn)中發(fā)現(xiàn)的問題，調(diào)試中的問題分析、解決方法，對算法的改進(jìn)意見、建議、收獲、體會等。實(shí)驗(yàn)報(bào)告參考規(guī)范：實(shí)驗(yàn)題目班級 姓名 學(xué)號 日期一、 需求分析1 程序的功能；2 輸入輸出的要求；3 測試數(shù)據(jù)。二、 概要設(shè)計(jì)1 本程序所用的抽象數(shù)據(jù)類型的定義；2 主程序的流程及

5、各程序模塊之間的層次關(guān)系。三、 詳細(xì)設(shè)計(jì)1 采用c語言定義相關(guān)的數(shù)據(jù)類型；2 寫出各模塊的偽碼算法；3 畫出函數(shù)的調(diào)用關(guān)系圖。四、 調(diào)試分析1 調(diào)試中遇到的問題及對問題的解決方法；（編譯錯(cuò)誤與運(yùn)行錯(cuò)誤）2 算法的時(shí)間復(fù)雜度和空間復(fù)雜度。五、 運(yùn)行結(jié)果1、 程序的使用說明2、 運(yùn)行結(jié)果六、 實(shí)驗(yàn)完成后的思考1、 通過實(shí)驗(yàn)學(xué)到了什么、理解了什么2、 程序還有哪些不足或還有哪些需要完善的地方七、 源程序（帶注釋）實(shí)驗(yàn)一斐波那契數(shù)列實(shí)驗(yàn)?zāi)康? 掌握遞歸算法及其編程方法；實(shí)驗(yàn)課時(shí)總課時(shí)：2學(xué)時(shí)/1次實(shí)驗(yàn)內(nèi)容1 利用遞歸方法或非遞歸方法實(shí)現(xiàn)求斐波那契數(shù)列第n項(xiàng)的值斐波那契數(shù)列描述如下：f(n)=f(n-1

6、)+f(n-2)f(1)=1f(2)=12 根據(jù)算法編制代碼（c/c+語言編寫，環(huán)境可選tc2或vc6）3 調(diào)試代碼直至得出正確結(jié)果實(shí)驗(yàn)要求一、 輸入一個(gè)值n，能夠得出第n項(xiàng)的斐波那契數(shù)列值，當(dāng)n值不是一個(gè)合法值時(shí)，給出提示（越詳細(xì)越好）二、 程序能夠循環(huán)輸入值n三、 程序有退出鍵四、 下課前提交word文檔，內(nèi)容包括程序代碼、運(yùn)行結(jié)果截圖（正確的和錯(cuò)誤的n值）實(shí)驗(yàn)二實(shí)驗(yàn)?zāi)康?、 掌握基礎(chǔ)算法分析和編程方法；實(shí)驗(yàn)課時(shí)總課時(shí)：2學(xué)時(shí)/1次實(shí)驗(yàn)內(nèi)容1完成下列程序* *.*. *.*.*. *.*.*.*. *.*.*.*.*. *.*.*.*.*.*. *.*.*.*.*.*.*. *.*.*.*

7、.*.*.*.*.實(shí)驗(yàn)要求一、 下課前提交word文檔，內(nèi)容包括程序代碼、運(yùn)行結(jié)果截圖實(shí)驗(yàn)三排序?qū)嶒?yàn)?zāi)康?.、掌握排序算法分析和編程方法；實(shí)驗(yàn)課時(shí)總課時(shí)：2學(xué)時(shí)/1次實(shí)驗(yàn)內(nèi)容1完成下列程序，實(shí)現(xiàn)對數(shù)組的降序排序 #include void sort( ); int main() int array=45，56，76，234，1，34，23，2，3； /數(shù)字任意給出 sort( ); return 0; void sort( ) 實(shí)驗(yàn)要求一、方法不限，下課前提交word文檔，內(nèi)容包括程序代碼、運(yùn)行結(jié)果截圖實(shí)驗(yàn)四螺旋數(shù)列實(shí)驗(yàn)?zāi)康?.、掌握算法分析和編程方法；實(shí)驗(yàn)課時(shí)總課時(shí)：2學(xué)時(shí)/1次實(shí)驗(yàn)內(nèi)容如圖

8、： 7 8 9 10 6 1 2 11 5 4 3 12 16 15 14 13 設(shè)“1”的坐標(biāo)為（0，0） “7”的坐標(biāo)為（1，1） 編寫一個(gè)小程序，使程序做到輸入坐標(biāo)（x,y）之后顯示出相應(yīng)的數(shù)字。 實(shí)驗(yàn)要求一、方法不限，下課前提交word文檔，內(nèi)容包括程序代碼、運(yùn)行結(jié)果截圖實(shí)驗(yàn)五六七八實(shí)驗(yàn)?zāi)康?.、掌握算法分析和編程方法；實(shí)驗(yàn)課時(shí)總課時(shí)：2學(xué)時(shí)/1次，共8學(xué)時(shí)實(shí)驗(yàn)內(nèi)容在下面的題目中任選40分的題作為實(shí)驗(yàn)五六七八的實(shí)驗(yàn)內(nèi)容。1、（15分）要求：隨機(jī)產(chǎn)生一個(gè)字符串，每次產(chǎn)生的字符串內(nèi)容，長度都不同2、（15分）將整數(shù)轉(zhuǎn)換成字符串：char* itoa(int); 例如itoa(-123)則返

9、回“-123”;3、（15分）設(shè)計(jì)函數(shù) int atoi(char *s)。atoi()會掃描參數(shù)s字符串，跳過前面的空格字符，直到遇上數(shù)字或正負(fù)符號才開始做轉(zhuǎn)換，而再 遇到非數(shù)字或字符串結(jié)束時(shí)()才結(jié)束轉(zhuǎn)換，并將結(jié)果返回。返回值 返回轉(zhuǎn)換后的整型數(shù)。4、（15分）并編寫一個(gè)函數(shù)實(shí)現(xiàn)一個(gè)整數(shù)到二進(jìn)制數(shù)的轉(zhuǎn)換，如輸入6，輸出110。5、（15分）寫函數(shù)將一個(gè)字符串反轉(zhuǎn). 函數(shù)原型如下:char *reverse(char *str);6、（15分）寫一個(gè)函數(shù)將一個(gè)鏈表逆序. 比如一個(gè)鏈表是這樣的: 1-2-3-4-5 通過反轉(zhuǎn)后成為5-4-3-2-17、（25分）題目描述：一個(gè)正整數(shù)有可能可以被

10、表示為 n 個(gè)連續(xù)正整數(shù)之和，如： 15=1+2+3+4+5 15=4+5+6 15=7+8 請編寫程序，根據(jù)輸入的任何一個(gè)正整數(shù)，找出符合這種要求的所有連續(xù)正整數(shù)序列。 輸入數(shù)據(jù)：一個(gè)正整數(shù)，以命令行參數(shù)的形式提供給程序。 輸出數(shù)據(jù)：在標(biāo)準(zhǔn)輸出上打印出符合題目描述的全部正整數(shù)序列，每行一個(gè)序列，每個(gè)序列都從該序列的最小正整數(shù)開始、以從小到大的順序打印。如果結(jié)果有多個(gè)序列，按各序列的最小正整數(shù)的大小從小到大打印各序列。此外，序列不允許重復(fù)，序列內(nèi)的整數(shù)用一個(gè)空格分隔。如果沒有符合要求的序列，輸出 “none” 。 例如，對于 15 ，其輸出結(jié)果是： 1 2 3 4 5 4 5 6 7 8 對于

11、 16 ，其輸出結(jié)果是： none 8、（25分）題目描述 為了在緊張的上班時(shí)間讓員工們輕松些，百度休息室里放置著按摩椅、 cd 、高爾夫套裝和 wii 游戲機(jī)等休閑用品。其中最受歡迎的當(dāng)然是游戲機(jī)。 wii 游戲機(jī)每個(gè)手柄需要使用兩節(jié)電池（這兩個(gè)電池可以是不同的品牌）。工程師們在玩游戲時(shí)。如果手柄沒有電，他們都是將其中沒電的電池拿走，并換上一個(gè)全新的電池，有電的必須繼續(xù)使用。 例如，已知三種電池的使用時(shí)間分別為 3 小時(shí)、 5 小時(shí)和 8 小時(shí)。一開始，工程師使用 3 小時(shí)和 5 小時(shí)的電池。 3 小時(shí)后，換上一個(gè) 8 小時(shí)的，再過 2 小時(shí)后，手柄再次沒電時(shí)，已經(jīng)沒有電池可用了。但如果一開

12、始就使用那個(gè) 8 小時(shí)電量的電池，可以玩滿 8 個(gè)小時(shí)。 告訴你每個(gè)品牌電池的使用時(shí)間以及該品牌電池的個(gè)數(shù)，請計(jì)算工程師們玩游戲時(shí)間的最小值和最大值。輸入格式輸入第一行為一個(gè)正整數(shù) n ，表示電池的種數(shù)。接下來 n 行，每行兩個(gè)整數(shù) l 和 f ，表示使用時(shí)間為 l 的電池有 f 個(gè)。輸出格式輸出僅一行，包含兩個(gè)整數(shù)，分別表示工程師們的最短游戲時(shí)間和最長游戲時(shí)間（短的時(shí)間在前）。兩個(gè)整數(shù)之間以空格隔開。 輸入樣例 3 3 2 5 2 8 2 輸出樣例 5 8 9、（25分）題目描述 “ 叉燒雞翅膀，我呀最愛吃！ ” 百度 spider 組的 “ 黑龍?zhí)吨?” 在烤著雞翅，唱著星爺?shù)慕?jīng)典時(shí)達(dá)到

13、高潮。大家在篝火旁圍成一圈，開始玩 “ 數(shù) 7 ” 加強(qiáng)版游戲，規(guī)則如下： 規(guī)則 1 ： 遇 7 的倍數(shù)或含 7 的數(shù)時(shí) pass 。 規(guī)則 2 ： 遇有包含相同數(shù)字的數(shù)時(shí) pass 。注意相同數(shù)字不必相鄰。例如 121 。 數(shù)錯(cuò)的懲罰很殘酷 吞食烤全羊。為避免懲罰，百度工程師們需要你 史上最強(qiáng)程序員的幫助。百度工程師想知道： req1 x ：符合規(guī)則 1 的第 x 個(gè)數(shù)是什么？ req2 y ：符合規(guī)則 2 的第 y 個(gè)數(shù)是什么？ req12 z ：同時(shí)符合規(guī)則 1 、 2 的第 z 個(gè)數(shù)是什么？ query n ：數(shù) n 是規(guī)則 1 中的第幾個(gè)數(shù)，是規(guī)則 2 中的第幾個(gè)數(shù)？ 輸入格式 輸入

14、的每一行為一個(gè)查詢，由一個(gè)查詢詞和一個(gè)無符號整型數(shù)組成。共有四種查詢，查詢詞分別為 req1 、 req2 、 req12 、 query （區(qū)分大小寫）。 輸出格式 前三種查詢輸出一個(gè)無符號整型的解。對于 “ query n ” 的查詢，若 n 是規(guī)則中的數(shù)則輸出相應(yīng)的解，否則輸出 -1 。 輸入樣例 req1 10 req2 10 req12 10 query 14 輸出樣例 11 10 12 -1 13 補(bǔ)充說明 輸入數(shù)據(jù)共分五組，前四組中： 1=x=10000000,1=y1000000,1=z250000, 1=n24000000. ；第五組中的 y 可能達(dá)到 5000000 10、

15、（40分）飯團(tuán)的煩惱“午餐飯團(tuán)“是百度內(nèi)部參與人數(shù)最多的民間組織。 同一個(gè)部門的，同一間大學(xué)的，同一年出生的，用同一種型號電腦的，員工們總是以各種理由，各種借口組織各種長久的，臨時(shí)的飯團(tuán)。 參加飯團(tuán)，不僅可以以優(yōu)惠的價(jià)格嘗到更加豐富的菜式，還可以在吃飯的時(shí)候和同事們嘮嘮嗑，吹吹水，增進(jìn)感情。 但是，隨著百度的員工越來越多，各個(gè)飯團(tuán)的管理隨即變得煩雜。特別是為了照顧員工們越來越挑剔的胃口，飯團(tuán)的點(diǎn)菜負(fù)責(zé)人背負(fù)的責(zé)任越來越大。現(xiàn)在，這個(gè)重?fù)?dān)落在百度之星的肩上，因?yàn)?，你們將要為所有的百度飯團(tuán)設(shè)計(jì)一個(gè)自動點(diǎn)菜的算法。 飯團(tuán)點(diǎn)菜的需求如下： 1 經(jīng)濟(jì)是我們要考慮的一個(gè)因素，既要充分利用百度員工的午餐補(bǔ)助

16、，又不能鋪張浪費(fèi)。因此，我們希望最后的人均費(fèi)用越接近 12 元越好。 2 菜式豐富是我們要考慮的另一個(gè)因素。為簡單起見，我們將各種菜肴的屬性歸結(jié)為葷菜，素菜，辛辣，清淡，并且每個(gè)菜只能點(diǎn)一次。 3 請緊記，百度飯團(tuán)在各大餐館享受 8 折優(yōu)惠。 輸入數(shù)據(jù)描述如下： 第一行包含三個(gè)整數(shù) n ， m ， k （ 0n=16 ， 0m=n ， 0k=12 ），分別表示菜單上菜的數(shù)目，飯團(tuán)需要點(diǎn)的菜的數(shù)目，就餐的人數(shù)。 緊接著 n 行，每行的格式如下： 菜名（長度不超過 20 個(gè)字符） 價(jià)格（原價(jià)，整數(shù)） 是否葷菜（ 1 表示是， 0 表示否） 是否辛辣（ 1 表示是， 0 表示否） 例： 水煮魚 30

17、 1 1 緊接著是 a b c d 四個(gè)整數(shù)，分別表示需要點(diǎn)的葷菜，素菜，辛辣，清淡菜的數(shù)目。 輸出數(shù)據(jù)： 對于每一測試數(shù)據(jù)，輸出數(shù)據(jù)包含 m+1 行，前 m 行每行包含一個(gè)菜名（按菜名在原菜單的順序排序）。第 m+1 行是人均消費(fèi)，結(jié)果保留兩位小數(shù)。 說明： 1 結(jié)果菜單的數(shù)目應(yīng)該恰好為 m ，葷菜，素菜，辛辣，清淡菜的數(shù)目恰好為 a ， b ， c ， d 。在滿足這樣的前提下，選擇人均消費(fèi)最接近 12 元的點(diǎn)菜方案。題目數(shù)據(jù)保證有且僅有一個(gè)解。 2 每組測試數(shù)據(jù)的結(jié)果用一個(gè)空行隔開。末尾不要有多余的空行。 輸入樣例 3 2 2 水煮魚 30 1 1 口水雞 18 1 1 清燉豆腐 12

18、0 0 1 1 1 1 輸出樣例 口水雞 清燉豆腐 12.00 11、（40分）題目名稱：蟈蟈式的記分 內(nèi)容描述： 蟈蟈小朋友剛剛學(xué)會了 0-9 這十個(gè)數(shù)字 , 也跟爸爸媽媽來參加百度每周進(jìn)行的羽毛球活動。但是他還沒有球拍高，于是大人們叫他記錄分?jǐn)?shù)。聰明的蟈蟈發(fā)現(xiàn)只要記錄連續(xù)得分的情況就可以了，比如用“ 3 2 4 ” 可以表示一方在這一局中連得三分后，輸了兩分，接著又連得到四分。可是，后來大人們發(fā)現(xiàn)蟈蟈只會用 0-9 這十個(gè)數(shù)字，所以當(dāng)比賽選手得分超過 9 的時(shí)候，他會用一個(gè) x 來表示 10 完成記分。但問題是，當(dāng)記錄為“ x 3 5 ” 的時(shí)候，蟈蟈自己也記不起來是一方連續(xù)得到十三分后，

19、再輸五分；還是先贏十分輸三分再贏五分。 因?yàn)榘俣葍?nèi)部就要開始進(jìn)行羽毛球聯(lián)賽了，要先摸清大家的實(shí)力才好分組比賽呢于是，大人們想知道以前每局的比分是怎樣的，以及誰獲得了勝利。要是遇到了根據(jù)比賽記錄無法確認(rèn)比賽進(jìn)程的情況，也要輸出相應(yīng)的提示哦。 需要幫蟈蟈進(jìn)一步說明的是，比賽是五局三勝的，每局先獲得二十一分的為勝，但是勝方必須領(lǐng)先對手兩分或以上，否則必須繼續(xù)比賽直到一方超出對手兩分為止，比分多的一方獲勝。任何一方先獲得三局的勝利后就獲得勝利，比賽也相應(yīng)的結(jié)束。而且蟈蟈保證是完整的無多余信息的記錄了比賽。 輸入數(shù)據(jù)： 以 point.in 為輸入文件，文件中首行只有一個(gè)整數(shù) m ，表示蟈蟈記錄了多少場

20、比賽的分?jǐn)?shù)。每場比賽用兩行記錄，第一行是一個(gè)整數(shù) n(n=1000) 表示當(dāng)前這個(gè)記錄中有多少個(gè)字符，第二行就是具體的 n 個(gè)字符表示記錄的分?jǐn)?shù)。 輸出數(shù)據(jù)： 相應(yīng)的內(nèi)容將輸出到 point.out 文件中，對應(yīng)每一個(gè)分?jǐn)?shù)記錄，輸出相應(yīng)的每局分?jǐn)?shù)，每局分?jǐn)?shù)都使用兩個(gè)整數(shù)表示，表示兩個(gè)選手的得分，中間用 : 分隔開；每組分?jǐn)?shù)記錄間使用一個(gè)空行分隔開。如果相應(yīng)的比賽結(jié)果無法預(yù)測的時(shí)候，以” unknown “一個(gè)單詞獨(dú)占一行表示。 ?輸入和輸出結(jié)果數(shù)據(jù)樣例： sample input ： 3 23 9 7 3 6 2 4 7 8 3 2 7 9 x 2 2 1 2 1 x 1 x 1 1 25 9

21、 3 8 5 4 8 3 9 8 4 x x x x 2 x x x x 2 8 4 9 2 4 43 7 7 7 7 7 3 4 5 6 7 6 5 4 2 1 3 5 7 9 7 5 3 1 3 0 9 9 3 9 3 2 1 1 1 5 1 5 1 5 1 5 5 1 sample output ： 21:17 24:22 21:3 unknown 21:14 20:22 21:23 21:16 21:9 12、（40分）變態(tài)的比賽規(guī)則 為了促進(jìn)各部門員工的交流，百度 (baidu) 舉辦了一場全公司范圍內(nèi)的 拳皇友誼賽 ，負(fù)責(zé)組織這場比賽的是百度的超級 拳皇 迷 w.z. w.z 不想

22、用傳統(tǒng)的淘汰賽或者循環(huán)賽的方式，而是自己制定了一個(gè)比賽規(guī)則。 由于一些員工（比如同部門或者相臨部門員工）平時(shí)接觸的機(jī)會比較多，為了促進(jìn)不同部門之間的交流， w.z 希望員工自己組成不同組。不同組之間的每兩個(gè)人都會進(jìn)行一場友誼賽而同一組內(nèi)的人則之間不會打任何比賽。 比如 4 個(gè)人，編號為 1-4, 如果分為兩個(gè)組并且 1,2 一個(gè)組， 3 ， 4 一個(gè)組，那么一共需要打四場比賽： 1 vs 3,1 vs 4,2 vs 3,2 vs 4. 而如果是 1,2,3 一組， 4 單獨(dú)一組，那么一共需要打三場比賽 : 1 vs 4,2 vs 4,3 vs 4. 很快 w.z 意識到，這樣的比賽規(guī)則可能會讓

23、比賽的場數(shù)非常多。 w.z 想知道如果有 n 個(gè)人 , 通過上面這種比賽規(guī)則，總比賽場數(shù)有可能為 k 場嗎？比如 3 個(gè)人，如果只分到一組則不需要比賽，如果分到兩組則需要 2 場比賽 , 如果分為三組則需要 3 場比賽。但是無論怎么分都不可能只需要 1 場比賽。 相信作為編程高手的你一定知道該怎么回答這個(gè)問題了吧？ 那么現(xiàn)在請你幫助 w.z 吧。 輸入 每行為一組數(shù)據(jù)，包含兩個(gè)數(shù)字 n, k 。 (0n=0) 輸出 對輸入的 n,k 如果 n 個(gè)員工通過一定的分組方式可能會一共需要 k 場比賽，則輸出 yes, 否則輸出 no, 每組數(shù)據(jù)占一行。 所有的輸入輸出均為標(biāo)準(zhǔn)輸入輸出。 例子 輸入文

24、件 : 2 0 2 1 3 1 3 2 輸出 : yes yes no yes 13、（40分）剪刀石頭布 n 個(gè)小孩正在和你玩一種剪刀石頭布游戲。 n 個(gè)小孩中有一個(gè)是裁判，其余小孩分成三組（不排除某些組沒有任何成員的可能性），但是你不知道誰是裁判，也不知道小孩們的分組情況。然后，小孩們開始玩剪刀石頭布游戲，一共玩 m 次，每次任意選擇兩個(gè)小孩進(jìn)行一輪，你會被告知結(jié)果，即兩個(gè)小孩的勝負(fù)情況，然而你不會得知小孩具體出的是剪刀、石頭還是布。已知各組的小孩分別只會出一種手勢（因而同一組的兩個(gè)小孩總會是和局），而裁判則每次都會隨便選擇出一種手勢，因此沒有人會知道裁判到底會出什么。請你在 m 次剪刀石

25、頭布游戲結(jié)束后，猜猜誰是裁判。如果你能猜出誰是裁判，請說明最早在第幾次游戲結(jié)束后你就能夠確定誰是裁判。 輸入格式： 輸入文件包含多組測試數(shù)據(jù)。每組測試數(shù)據(jù)第一行為兩個(gè)整數(shù) n 和 m （ 1 n 500 ， 0 m 2000 ），分別為小孩的個(gè)數(shù)和剪刀石頭布游戲進(jìn)行的次數(shù)。接下來 m 行，每行兩個(gè)整數(shù)且中間以一個(gè)符號隔開。兩個(gè)整數(shù)分別為進(jìn)行游戲的兩個(gè)小孩各自的編號，為小于 n 的非負(fù)整數(shù)。符號的可能值為“ = ”、“ ”和“ ”，分別表示和局、第一個(gè)小孩勝和第二個(gè)小孩勝三種情況。 輸出格式： 每組測試數(shù)據(jù)輸出一行，若能猜出誰是裁判，則輸出身為裁判的小孩的編號，并輸出在第幾次游戲結(jié)束后就能夠確定

26、誰是裁判。如果無法確定誰是裁判，或者發(fā)現(xiàn)剪刀石頭布游戲的勝負(fù)情況不合理（即無論誰是裁判都會出現(xiàn)矛盾），則輸出相應(yīng)的信息。具體輸出格式請參考輸出樣例。 輸入樣例： 3 3 01 12 20 3 5 01 12 02 4 4 01 23 1 0 輸出樣例： can not determine player 1 can be determined to be the judge after 4 lines impossible player 0 can be determined to be the judge after 0 lines 說明： 共有 5 個(gè)測試數(shù)據(jù)集，每個(gè)測試數(shù)據(jù)集為一個(gè)輸入文件

27、，包含多組測試數(shù)據(jù)。每個(gè)測試數(shù)據(jù)集從易到難分別為 5 、 10 、 15 、 30 和 40 分，對每個(gè)測試數(shù)據(jù)集分別執(zhí)行一次程序，每次必須在運(yùn)行時(shí)限 3 秒內(nèi)結(jié)束程序并輸出正確的答案才能得分。 所有數(shù)據(jù)均從標(biāo)準(zhǔn)輸入設(shè)備（ stdin/cin ）讀入，并寫出到標(biāo)準(zhǔn)輸出設(shè)備 （ stdout/cout ）中。 五個(gè)測試數(shù)據(jù)集中輸入 n 分別不大于 20 、 50 、 100 、 200 和 500 ，各有 10 組測試數(shù)據(jù)。 14、（40分）座位調(diào)整 題目描述： 百度辦公區(qū)里到處擺放著各種各樣的零食。百度人力資源部的調(diào)研發(fā)現(xiàn)，員工如果可以在自己喜歡的美食旁邊工作，工作效率會大大提高。因此，百度決

28、定進(jìn)行一次員工座位的大調(diào)整。 調(diào)整的方法如下： 1 首先將辦公區(qū)按照各種零食的擺放分成 n 個(gè)不同的區(qū)域。（例如：可樂區(qū)，餅干區(qū)，牛奶區(qū)等等）。 2 每個(gè)員工對不同的零食區(qū)域有不同的喜好程度（喜好程度度的范圍為 1 100 的整數(shù)， 喜好程度越大表示該員工越希望被調(diào)整到相應(yīng)的零食區(qū)域）。 3 由于每個(gè)零食區(qū)域可以容納的員工數(shù)量有限，人力資源部希望找到一個(gè)最優(yōu)的調(diào)整方案令到總的喜好程度最大。 數(shù)據(jù)輸入： 第一行包含兩個(gè)整數(shù) n ， m ，（ 1=n ， m=300 ）。分別表示 n 個(gè)區(qū)域和 m 個(gè)員工。 第二行是 n 個(gè)整數(shù)構(gòu)成的數(shù)列 a ，其中 ai 表示第 i 個(gè)區(qū)域可以容納的員工數(shù)， (

29、1=ai=m ， a1+a2+.+an=m) 。 緊接著是一個(gè) m*n 的矩陣 p ， p （ i ， j ）表示第 i 個(gè)員工對第 j 個(gè)區(qū)域的喜好度。 答案輸出： 對于每個(gè)測試數(shù)據(jù)，輸出可以達(dá)到的最大的喜好程度。 輸入樣例： 3 3 1 1 1 100 50 25 100 50 25 100 50 25 輸出樣例： 175 數(shù)據(jù)解釋：此數(shù)據(jù)只存在一種安排方法，三個(gè)員工分別安置在三個(gè)區(qū)域。最終的喜好程度為 100+50+25=175 15、（40分）百度語言翻譯機(jī) 時(shí)限 1s 百度的工程師們是非常注重效率的，在長期的開發(fā)與測試過程中，他們逐漸創(chuàng)造了一套他們獨(dú)特的縮率語。他們在平時(shí)的交談，會議

30、，甚至在各中技術(shù)文檔中都會大量運(yùn)用。 為了讓新員工可以更快地適應(yīng)百度的文化，更好地閱讀公司的技術(shù)文檔，人力資源部決定開發(fā)一套專用的翻譯系統(tǒng)，把相關(guān)文檔中的縮率語和專有名詞翻譯成日常語言。 輸入數(shù)據(jù)： 輸入數(shù)據(jù)包含三部分 1. 第一行包含一個(gè)整數(shù) n （ n=10000 ），表示總共有多少個(gè)縮率語的詞條。 2. 緊接著有 n 行的輸入，每行包含兩個(gè)字符串，以空格隔開。第一個(gè)字符串為縮率語（僅包含大寫英文字符，長度不超過 10 ），第二個(gè)字符串為日常語言（不包含空格，長度不超過 255 ） . 3. 從第 n+2 開始到輸入結(jié)束為包含縮略語的相關(guān)文檔。（總長度不超過 1000000 個(gè)字符） 輸出

31、數(shù)據(jù)： 輸出將縮率語轉(zhuǎn)換成日常語言的文檔。（將縮率語轉(zhuǎn)換成日常語言，其他字符保留原樣） 輸入例子： 6 ps 門戶搜索部 nlp 自然語言處理 pm 產(chǎn)品市場部 hr 人力資源部 pmd 產(chǎn)品推廣部 md 市場發(fā)展部 百度的部門包括 ps ， pm ， hr ， pmd ， md 等等，其中 ps 還包括 nlp 小組。 輸出例子： 百度的部門包括門戶搜索部，產(chǎn)品市場部，人力資源部，產(chǎn)品推廣部，市場發(fā)展部等等，其中門戶搜索部還包括自然語言處理小組。 注意： 1 輸入數(shù)據(jù)中是中英文混合的，中文采用 gbk 編碼。 2 為保證答案的唯一性，縮率語的轉(zhuǎn)換采用正向最大匹配（從左到右為正方向）的原則。請

32、注意輸入例子中 pmd 的翻譯。 16、（40分）百度的高級搜索方法 題面描述： 你嘗試過在百度上使用 site inurl 語法查詢嗎 ? 如果還沒有的話可以試一下 :) 如輸入 site: inurl:news 則會搜出所有在 站點(diǎn)上的包含 news 子串的 url 。 現(xiàn)在我們有兩份數(shù)據(jù)，一份是 site_inurl.txt 一份是 url.txt site_inurl.txt 中每行是一個(gè) site inurl 語法組成的查詢串， url.txt 中保存的是 url 列表。 你能否在 url 列表中找出所有能被 site_inurl

33、.txt 中的查詢串檢索到的 url? 如 site_inurl.txt 內(nèi)容如下： site: inurl:/more site: inurl:/browse/ site: inurl:www20041223am url.txt 內(nèi)容如下： /more/ /guding/more.html /events/20060105/photomore.html /b

34、rowse/ /baidu/ /head/www20021123am.shtml /head/www20041223am.shtml 則你的程序運(yùn)行完輸出的結(jié)果應(yīng)該為： /more/ /guding/more.html /head/www20041223am.shtml 程序以命令行形式傳入這兩個(gè)文件名，第一個(gè)參數(shù)為 site_inurl 文件對應(yīng)的文件名，第

35、二個(gè)參數(shù)為 url 列表對應(yīng)的文件名，程序的輸出請輸出到標(biāo)準(zhǔn)輸出。17、（40分）實(shí)習(xí)生小胖的百度網(wǎng)頁過濾器 題目描述 百度網(wǎng)頁采集器 (baiduspider) 每天從互聯(lián)網(wǎng)收錄數(shù)億網(wǎng)頁，互聯(lián)網(wǎng)的網(wǎng)頁質(zhì)量參差不齊。百度的工程師們每天都在改進(jìn)方法來判斷一個(gè)網(wǎng)頁質(zhì)量的好壞，使質(zhì)量差的網(wǎng)頁出現(xiàn)在檢索結(jié)果中較后的位置?，F(xiàn)在實(shí)習(xí)生小胖想到一個(gè)很簡單的方法來判斷一個(gè)網(wǎng)頁內(nèi)容的好壞，方法如下： 1. 利用數(shù)據(jù)挖掘技術(shù)在互聯(lián)網(wǎng)語料庫中挖掘出一批有特點(diǎn)的詞匯，分為好詞和壞詞兩種，好詞標(biāo)上正的權(quán)重，壞詞標(biāo)上負(fù)的權(quán)重； 2. 通過好詞和壞詞詞典對每個(gè)網(wǎng)頁計(jì)算網(wǎng)頁總權(quán)重：從第一個(gè)字開始匹配，找到一個(gè)好詞則加上相應(yīng)的

36、權(quán)重，找到一個(gè)壞詞則減去相應(yīng)的權(quán)重，下一次匹配將從找到的詞末尾的下一個(gè)位置開始。 3. 壞詞采用正向最短匹配：從當(dāng)前匹配位置開始的若干連續(xù)漢字，如果形成多個(gè)壞詞，則只計(jì)算最短的那個(gè)壞詞的權(quán)重，下一次匹配將從這個(gè)最短壞詞末尾的下一個(gè)位置開始。 4. 好詞采取正向最長匹配：從當(dāng)前匹配位置開始的若干連續(xù)漢字，如果形成多個(gè) “ 有效 ” 好詞，則只計(jì)算最長 “ 有效 ” 好詞的權(quán)重，下一次匹配從這個(gè)最長 “ 有效 ” 好詞末尾的下一個(gè)位置開始。 5. “ 無效 ” 好詞的定義：好詞的一部分本身是一個(gè)壞詞；或者好詞的一部分與后續(xù)相鄰的若干字組成一個(gè)壞詞。 現(xiàn)在小胖已經(jīng)做好了第 1 步的工作，有一個(gè)好詞和

37、壞詞的列表（詞典），但是由于沒有對中文文本處理的程序經(jīng)驗(yàn)，他想請未來的百度之星們幫他完成這個(gè)程序。 輸入格式 輸入第一行為一個(gè)字符串（網(wǎng)頁正文）。從第二行開始為詞典，格式為 “ 詞 空格 詞的權(quán)重 ” 。權(quán)重為一個(gè)帶符號 32 位整數(shù)。如果權(quán)重為正，則為好詞，反之則為壞詞；不存在重復(fù)的詞，不存在權(quán)重為 0 的詞。 測試數(shù)據(jù)中的詞全部為 1-5 個(gè)字的中文，但作為 “ 網(wǎng)頁 ” 的字符串中同時(shí)包含中文和 ascii 字符，每個(gè)漢字占 2 個(gè)字節(jié)。并非 “ 網(wǎng)頁 ” 中的所有字都在詞典中。 樣例輸入 小胖之噴火龍騎士 ! 小胖 6 噴火 -1 噴火龍 -1 火龍 -1 龍 4 龍騎 3 龍騎士 2

38、 騎士 -2 士 3 輸出格式 輸出僅一行，為網(wǎng)頁總權(quán)重（答案保證不超過帶符號 32 位整數(shù)的范圍）。 樣例輸出 7 樣例解釋 從 “ 網(wǎng)頁 ” 中找到的好詞為 “ 小胖 ” 和 “ 龍 ” ，壞詞為 “ 噴火 ” 和 “ 騎士 ” 。特別要說明一下 “ 龍 ” 被識別為好詞的原因 “ 噴火 ” 和 “ 噴火龍 ” 均為壞詞，按正向最短匹配得到 “ 噴火 ” ，接著往下匹配到好詞 “ 龍 ” 、 “ 龍騎 ” 和 “ 龍騎士 ” ，但是由于 “ 騎士 ” 是壞詞，所以 “ 龍騎 ” 、 “ 龍騎士 ” 無效而 “ 龍 ” 是最長的有效好詞。注意題目描述中的匹配規(guī)則，好詞的 “ 有效 ” 和 “

39、 無效 ” 只考慮該好詞的一部分與后續(xù)字是否能夠組成壞詞，而不考慮和前面的字是否能夠組成壞詞 樣例中的 “ 龍 ” 雖然可以與前面的字組成壞詞 “ 噴火龍 ” 和 “ 火龍 ” ，但由于這兩個(gè)詞都是未能匹配成功的壞詞，因此對好詞 “ 龍 ” 的詞性沒有影響，可以累積 “ 龍 ” 的權(quán)重。18、（40分）百度時(shí)間（ 2007 年初賽） 題目描述 baidu 的服務(wù)器上使用的不是北京時(shí)間，而是 baidu 時(shí)間。 baidu 時(shí)間的時(shí)分秒與北京時(shí)間相同，但是日期與北京時(shí)間不同，是用一個(gè)正整數(shù)表示從 2000 年 1 月 1 日 起的第幾天。 現(xiàn)在就請大家設(shè)計(jì)一個(gè)程序?qū)⒈本r(shí)間轉(zhuǎn)換為百度時(shí)間。 輸入

40、格式 輸入數(shù)據(jù)的每一行為一個(gè)待轉(zhuǎn)化的北京時(shí)間，格式包括兩種： 一種為： yyyy-mm-dd ，（ yyyy 表示四位數(shù)年份， mm 為兩位月份， dd 為兩位日期）； 另一種為： mm/dd/yyyy ，（ yyyy 表示四位數(shù)年份， mm 為兩位月份， dd 為兩位日期）； 不符合任何一種格式的輸入視為非法輸入。 輸出格式 每個(gè)數(shù)據(jù)輸出一行。如果格式正確，輸出一個(gè)正整數(shù)，否則輸出 error 。 輸入樣例 2006-03-21 astar2007 04/22/2007 輸出樣例 2149 error 2463 19、（40分）繁忙的會議室預(yù)定問題題目描述 百度由最開始的 7 人團(tuán)隊(duì)迅速發(fā)展為幾千人的大團(tuán)隊(duì)，而工程師們經(jīng)常需要在一起進(jìn)行 “ 頭腦風(fēng)暴 ” ，這樣會議室就成了緊缺資源。為了有效利用資源，大家決定制定規(guī)則， 自動安排會議室的使用。 為了公平起見，應(yīng)按照申請