2013級(jí)計(jì)算機(jī)類專業(yè)各班課程設(shè)計(jì)材料

1、程序設(shè)計(jì)課程設(shè)計(jì)適應(yīng)對(duì)象：2013級(jí)計(jì)算機(jī)類各專業(yè)一、課程設(shè)計(jì)的基本步驟（1） 任務(wù)書由教師下達(dá)，學(xué)生必須仔細(xì)閱讀，明確任務(wù)要求，并與相關(guān)的商業(yè)軟件在使用、功能、界面等方面對(duì)比，獲得開發(fā)的啟示。（2） 系統(tǒng)分析在充分讀懂任務(wù)書后，必須做到： 理解問題，明確做什么，初步設(shè)想怎么做，也可查看有關(guān)資料后尋求入手的基本步驟。 結(jié)構(gòu)圖的設(shè)計(jì)。對(duì)于較復(fù)雜的系統(tǒng)，應(yīng)勾劃系統(tǒng)結(jié)構(gòu)圖，決定系統(tǒng)由哪幾個(gè)模塊組成，各個(gè)模塊又有哪些子模塊，樹狀層次應(yīng)分明直觀。對(duì)于較簡(jiǎn)單的系統(tǒng)，也應(yīng)勾劃系統(tǒng)結(jié)構(gòu)圖。（3） 系統(tǒng)設(shè)計(jì)針對(duì)各個(gè)模塊，在體系結(jié)構(gòu)明確的基礎(chǔ)上，注意設(shè)計(jì)好入口、出口參數(shù)數(shù)據(jù)，完成各個(gè)模塊（在C中也就是函數(shù)）設(shè)計(jì)，

2、預(yù)先應(yīng)做好數(shù)據(jù)流程與算法設(shè)計(jì)、用戶界面設(shè)計(jì)的全盤考慮。（4） 代碼設(shè)計(jì)（或編程）單個(gè)模塊或函數(shù)處理 將整個(gè)系統(tǒng)程序分解為各個(gè)單獨(dú)的模塊，即C的函數(shù)，各模塊可單獨(dú)編譯；整個(gè)程序的聯(lián)調(diào) 在各個(gè)模塊基本的單獨(dú)編譯通過后，用主函數(shù)將他們集成在一起，實(shí)現(xiàn)調(diào)用，并進(jìn)行輸出數(shù)據(jù)的可靠性、輸入數(shù)據(jù)及系統(tǒng)的容錯(cuò)性測(cè)試。（5） 程序說(shuō)明書撰寫程序說(shuō)明書文檔，說(shuō)明程序的功能、模塊的組成、數(shù)據(jù)及數(shù)據(jù)格式、使用方法、應(yīng)注意的事項(xiàng)。（6） 答辯(視學(xué)生情況選擇進(jìn)行) 演示軟件 講解軟件 提問二、課程設(shè)計(jì)的時(shí)間進(jìn)程安排（1）任務(wù)下達(dá) 在第11周下達(dá)任務(wù)，學(xué)生按班級(jí)分組選題，原則上，每道題目的選擇不得超過二次。學(xué)習(xí)委員負(fù)責(zé)學(xué)

3、生按班級(jí)分組選題，學(xué)生選題后即開始設(shè)計(jì)過程。（2）抽查 從第14周起，指導(dǎo)教師開始抽查，一般在下午。 （3）程序設(shè)計(jì)課程設(shè)計(jì)報(bào)告上交 第19周，各班學(xué)習(xí)委員收集程序設(shè)計(jì)課程設(shè)計(jì)報(bào)告（每人均要有紙質(zhì)檔和電子檔，合作完成的應(yīng)指明自己完成的部分），上交給指導(dǎo)教師。-C 語(yǔ) 言 課 程 設(shè) 計(jì) 任 務(wù) 書適應(yīng)對(duì)象：2013級(jí)計(jì)算機(jī)類各專業(yè)指導(dǎo)教師：桂超電 話:郵 箱：gui_ 下達(dá)時(shí)間：2014年11月10日 星期一每一位參加課程設(shè)計(jì)的學(xué)生，只能選擇一個(gè)題目，對(duì)于允許多個(gè)學(xué)生聯(lián)合完成的題目，在上交程序設(shè)計(jì)報(bào)告時(shí)（程序設(shè)計(jì)報(bào)告的書寫，可參考提供給學(xué)生的附件

4、），必須注明自己所做的部分。一、基礎(chǔ)程序設(shè)計(jì)課程設(shè)計(jì)題目A1：鏈表操作。本題各個(gè)小題，均要在主函數(shù)中通過調(diào)用相應(yīng)的用戶自定義函數(shù)檢驗(yàn)輸出。 1定義結(jié)點(diǎn)類型結(jié)構(gòu)如下：struct chainchar data;chain *next;jd;試建立如下具有8個(gè)結(jié)點(diǎn)的單鏈表，要求編寫函數(shù)crechain如下jd *crechain(char *ch,int n)，返回為首結(jié)點(diǎn)的首地址head，其中，n是結(jié)點(diǎn)的個(gè)數(shù)，數(shù)組ch存放各結(jié)點(diǎn)上的數(shù)據(jù)，首結(jié)點(diǎn)的數(shù)據(jù)為ch0，尾結(jié)點(diǎn)數(shù)據(jù)為chn-1，其它順推。A B C H head 2編寫函數(shù)circulachain，將上述單鏈表改為單循環(huán)鏈表，結(jié)點(diǎn)H的鏈域存

5、放首結(jié)點(diǎn)A的地址。 chain *circulachain(chain *head)，返回仍為首地址head。 3編寫函數(shù)addnode，在數(shù)據(jù)為x的結(jié)點(diǎn)之后插入數(shù)據(jù)為y的結(jié)點(diǎn)，仍構(gòu)成單循環(huán)鏈表。調(diào)用時(shí)，可在結(jié)點(diǎn)H的后面加入結(jié)點(diǎn) I。 void addnode(chain * head，char x，char y) 4編寫函數(shù)delenode，刪除單循環(huán)鏈表中數(shù)據(jù)為x，刪除后仍構(gòu)成單循環(huán)鏈表。 void delenode(chain * head，char x) 5利用前面的工作解決以下約瑟夫問題 有n個(gè)人，圍坐一圈，對(duì)他們從1開始編號(hào)，即1，2，3，.，n，如果從某一個(gè)人開始報(bào)數(shù)，他報(bào)數(shù)1，

6、按順時(shí)針進(jìn)行，緊挨的人報(bào)數(shù)2，再往下的人跟著報(bào)3， .，一直報(bào)到k，凡報(bào)到k的人出列，再往下，繼續(xù)從1 開始報(bào)數(shù)，2，3，.，一直報(bào)到k，凡報(bào)到k的人出列。試輸出該問題中順序出列的人的名字。 調(diào)用時(shí)，k=4,n=9, 編號(hào)為 1，2，3，.，9的人的名字分別為A、B、C.，I課程設(shè)計(jì)題目A2：（可二人合做） 學(xué)生成績(jī)管理系統(tǒng)?？捎芍笇?dǎo)教師提供設(shè)計(jì)目的、功能描述、總體設(shè)計(jì)、程序?qū)崿F(xiàn)，學(xué)生可通過模仿設(shè)計(jì)，深入掌握C的綜合編程能力，諸如文件系統(tǒng)、結(jié)構(gòu)、指針、鏈表技術(shù)等。 主要功能由學(xué)生根據(jù)實(shí)際自定，可參考如下：（1）輸入記錄模塊。能按學(xué)期、按班級(jí)完成對(duì)學(xué)生成績(jī)的錄入、修改（2）統(tǒng)計(jì)模塊。能按班級(jí)統(tǒng)計(jì)

7、學(xué)生的成績(jī)，求學(xué)生的總分及平均分，并能根據(jù)學(xué)生的平均成績(jī)進(jìn)行排序（3）查詢模塊。能查詢學(xué)生成績(jī)，不及格科目及學(xué)生名單（4）輸出模塊。能按班級(jí)輸出學(xué)生的成績(jī)單，也可排序輸出（5）記錄修改模塊。按學(xué)號(hào)或姓名班級(jí)完成對(duì)學(xué)生成績(jī)的修改（6）可考慮添加口令管理子模塊，程序運(yùn)行后首先執(zhí)行口令檢查，口令可修改維護(hù)等。 口令可放在一個(gè)文件中加密保存。 課程設(shè)計(jì)題目A3：（可二人合做） 迷宮問題的求解。問題描述：迷宮是實(shí)驗(yàn)心理學(xué)中一個(gè)古典問題。以一個(gè)8*8的長(zhǎng)方陣表示迷宮，0和1分別表示迷宮中的通路和障礙。入口在左上方（1，1）處，出口在右下方（8，8）處。要求：（1） 設(shè)計(jì)一個(gè)程序，對(duì)任意設(shè)定的迷宮，求出一條

8、從入口到出口的通路，或者得出沒有通路的結(jié)論。（2） 設(shè)計(jì)一個(gè)程序，對(duì)任意設(shè)定的迷宮，求出一條從入口到出口的通路的最短路徑。 下圖中，紅色的方格表示坐標(biāo)提示，入口、出口如圖示。01234567891入口2345678出口9課程設(shè)計(jì)題目A4： 漢諾塔問題的二種求解。 1、編寫遞歸方法求解的程序； 2、編寫非遞歸方法求解的程序；課程設(shè)計(jì)題目A5：（可二人合做） 分油問題?，F(xiàn)有3斤、7斤、10斤的油桶三個(gè)，前2個(gè)是空桶， 10斤的油桶裝滿了油，現(xiàn)要求借助這些桶分出二個(gè)5斤的油于油桶中，問：1、 應(yīng)如何倒法？2、 將油從一個(gè)桶倒入另一個(gè)桶稱為一次操作，如果限制倒油的總次數(shù)為N，程序怎么編寫？3、 能否找

9、出所需的最少次數(shù)？ 注意倒油的規(guī)則： 1、只能使用這些油桶； 2、倒油時(shí)，要么把自己倒空，要么把目標(biāo)桶倒?jié)M。課程設(shè)計(jì)題目A6：一元多項(xiàng)式計(jì)算能夠按照指數(shù)降序排列建立并輸出多項(xiàng)式；能夠完成兩個(gè)多項(xiàng)式的相加、相減和相乘，并將結(jié)果輸出。課程設(shè)計(jì)題目A7：矩陣的運(yùn)算采用十字鏈表表示稀疏矩陣，并實(shí)現(xiàn)矩陣的加法運(yùn)算, 要求：要檢查有關(guān)運(yùn)算的條件，并對(duì)錯(cuò)誤的條件產(chǎn)生報(bào)警。 二、綜合應(yīng)用型程序設(shè)計(jì)題：課程設(shè)計(jì)題目B1：（可二人合做） 俄羅斯方塊游戲。由指導(dǎo)教師提供設(shè)計(jì)目的、功能描述、總體設(shè)計(jì)、程序?qū)崿F(xiàn)，學(xué)生可通過模仿設(shè)計(jì)，深入掌握C的綜合編程能力和游戲開發(fā)技巧。課程設(shè)計(jì)題目B2：（可二人合做） 推箱子游戲。由

10、指導(dǎo)教師提供設(shè)計(jì)目的、功能描述、總體設(shè)計(jì)、程序?qū)崿F(xiàn)，學(xué)生可通過模仿設(shè)計(jì)，深入掌握C的綜合編程能力和游戲開發(fā)技巧。課程設(shè)計(jì)題目B3：（可二人合做） 五子棋游戲。由指導(dǎo)教師提供設(shè)計(jì)目的、功能描述、總體設(shè)計(jì)、程序?qū)崿F(xiàn)，學(xué)生可通過模仿設(shè)計(jì)，深入掌握C的綜合編程能力和游戲開發(fā)技巧。課程設(shè)計(jì)題目B4：（可二人合做） 網(wǎng)絡(luò)編程：Ping程序設(shè)計(jì)。由指導(dǎo)教師提供設(shè)計(jì)目的、功能描述、總體設(shè)計(jì)、程序?qū)崿F(xiàn)，學(xué)生可通過模仿設(shè)計(jì)，深入掌握C的網(wǎng)絡(luò)應(yīng)用編程能力課程設(shè)計(jì)題目B5：（可二人合做） 網(wǎng)絡(luò)編程：TCP程序設(shè)計(jì)。由指導(dǎo)教師提供設(shè)計(jì)目的、功能描述、總體設(shè)計(jì)、程序?qū)崿F(xiàn)，學(xué)生可通過模仿設(shè)計(jì)，深入掌握C的網(wǎng)絡(luò)應(yīng)用編程能力課

11、程設(shè)計(jì)題目B6：（可二人合做）訂票系統(tǒng)設(shè)計(jì)航班信息，訂票信息的存儲(chǔ)結(jié)構(gòu)，設(shè)計(jì)程序完成如下功能：錄入：可以錄入航班情況(數(shù)據(jù)可以存儲(chǔ)在一個(gè)數(shù)據(jù)文件中，數(shù)據(jù)結(jié)構(gòu)、具體數(shù)據(jù)自定)查詢：可以查詢某個(gè)航線的情況(如，輸入航班號(hào)，查詢起降時(shí)間，起飛抵達(dá)城市，航班票價(jià)，票價(jià)折扣，確定航班是否滿倉(cāng))；可以輸入起飛抵達(dá)城市，查詢飛機(jī)航班情況；訂票：(訂票情況可以存在一個(gè)數(shù)據(jù)文件中，結(jié)構(gòu)自己設(shè)定)可以訂票，如果該航班已經(jīng)無(wú)票，可以提供相關(guān)可選擇航班；退票： 可退票，退票后修改相關(guān)數(shù)據(jù)文件；客戶資料有姓名，證件號(hào)，訂票數(shù)量及航班情況，訂單要有編號(hào)。修改航班信息：當(dāng)航班信息改變可以修改航班數(shù)據(jù)文件課程設(shè)計(jì)題目B7：文

12、章編輯器 編寫一個(gè)簡(jiǎn)單的文本編輯軟件，能基本實(shí)現(xiàn)文本的輸入、修改、插入、刪除等功能。課程設(shè)計(jì)題目B8： 賓館訂房和退房系統(tǒng)假設(shè)一個(gè)賓館有n個(gè)標(biāo)準(zhǔn)的客房，每個(gè)標(biāo)準(zhǔn)客房有m個(gè)標(biāo)準(zhǔn)間，利用鏈表、?；蛘哧?duì)列等數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)出具有訂房和退房等功能的管理系統(tǒng)。課程設(shè)計(jì)題目B9：設(shè)計(jì)類似Windows界面的萬(wàn)年歷。 三、競(jìng)賽型基礎(chǔ)課程設(shè)計(jì)題 （注：選擇此類題目者，必須完成二道方達(dá)到本課程設(shè)計(jì)目標(biāo)）C1求素?cái)?shù)對(duì):中間只隔一個(gè)數(shù)字的兩個(gè)素?cái)?shù)被稱為素?cái)?shù)對(duì), 比如5和7, 17和19, 給出一個(gè)范圍a, b, 輸出其中所有素?cái)?shù)對(duì), 并驗(yàn)證所有素?cái)?shù)對(duì)之間的數(shù)字總能被6整除。例如: 10, 20內(nèi)共有2對(duì)素?cái)?shù)對(duì): 11-

13、13, 17-19, 故輸出結(jié)果為2。數(shù)據(jù)輸入:每一行都有2個(gè)整數(shù), 分別為a, b的值, 最后一行以兩個(gè)0作為結(jié)束標(biāo)志。結(jié)果輸出:針對(duì)每一行的兩個(gè)整數(shù)a和b, 輸出a, b內(nèi)所有的素?cái)?shù)對(duì)的數(shù)量。樣例輸入樣例輸出10 200 02C2 正整數(shù)序列:有些正整數(shù)可以表示成n (n 2) 個(gè)連續(xù)的正整數(shù)的和, 如:15 = 1 + 2 + 3 + 4 + 515 = 4 + 5 + 615 = 7 + 8共有3種表示方法。試編寫程序, 輸入正整數(shù)n, 求出這種表示方法的數(shù)量。w 輸入數(shù)據(jù)每行輸入一個(gè)正整數(shù)n, 最后以0作為結(jié)束標(biāo)記。w 輸出數(shù)據(jù)每行輸出一個(gè)整數(shù), 即這種表示方法的數(shù)量。w 測(cè)試樣例輸

14、入輸出78150103C3 因數(shù)分解:對(duì)于任意給定的自然數(shù)n(n108)和自然數(shù)k(kn), 求n可以分解成兩個(gè)均不小于k的因數(shù)之積的所有情況有多少種。例如: n = 30, k = 3時(shí), 顯然30可以被分解為130, 215, 310和56等4種形式, 其中只有310和56等2種情況下, 兩個(gè)因素都大于等于3, 故輸出結(jié)果為2。數(shù)據(jù)輸入:每一行都有2個(gè)整數(shù), 分別為n, k的值, 最后一行以兩個(gè)0作為結(jié)束標(biāo)志。結(jié)果輸出:針對(duì)每一行的兩個(gè)整數(shù)n和k, 計(jì)算并輸出所有情況的數(shù)量。樣例輸入樣例輸出6 230 380 40 0123C4 整數(shù)分解問題:一個(gè)自然數(shù)N可以分解成若干個(gè)比N小的不同的自然

15、數(shù)之和, 例如: 6 = 1 + 5 = 2 + 4 = 1 + 2 + 3, 即有三種分解方法。對(duì)于任意給定的自然數(shù)N(N200), 請(qǐng)編程序求出符合這種要求的分解方法有多少種?數(shù)據(jù)輸入:每一行一個(gè)整數(shù), 即N的取值, 最后一行以0作為結(jié)束標(biāo)志。結(jié)果輸出:對(duì)應(yīng)輸入整數(shù)所有可能的分解的總數(shù)。樣例輸入樣例輸出461280134013543C5 括號(hào)嵌套的深度:某個(gè)字符序列完全由圓括號(hào)“(”和“)”組成, 如果序列中的括號(hào)成對(duì)出現(xiàn), 則序列中的每一個(gè)“(”, 在它的右邊都能找到唯一的一個(gè)與之匹配的“)”, 同樣, 對(duì)于每一個(gè)“)”, 在它的左邊都能找到唯一的一個(gè)與之匹配的“(”, 也就是說(shuō)每一個(gè)括

16、號(hào)都只會(huì)與唯一的另外一個(gè)進(jìn)行配對(duì), 否則就稱之為不匹配。設(shè)n為序列中出現(xiàn)的括號(hào)對(duì)數(shù), k為序列中括號(hào)的嵌套深度(即括號(hào)的最大層數(shù)), 那么序列“()()()()()”的n為8, k為3。請(qǐng)編程計(jì)算圓括號(hào)序列的嵌套深度。樣例輸入樣例輸出4()()()()()()()()()()123Error數(shù)據(jù)輸入:第一行為一個(gè)正整數(shù)m, 表示測(cè)試樣本的個(gè)數(shù)。隨后就是m行由括號(hào)組成的字符串, 每個(gè)字符串的長(zhǎng)度都不超過1000, 都以回車作為結(jié)束符。結(jié)果輸出:針對(duì)每個(gè)樣本, 輸出該字符串括號(hào)嵌套的深度。如果該樣本中的括號(hào)不匹配, 則輸出“Error”。C6 括號(hào)配對(duì)的情況:繼續(xù)研究前面的題目, 如果已知括號(hào)對(duì)數(shù)

17、為n(n20), 請(qǐng)輸出所有可能配對(duì)的情況有多少種? 例如: 當(dāng)有2對(duì)括號(hào)時(shí), 可能的配對(duì)情況有: ()(), (), 故輸出結(jié)果為2。數(shù)據(jù)輸入:每一行數(shù)據(jù)表示括號(hào)對(duì)數(shù)n的值, 最后一行以0作為結(jié)束。結(jié)果輸出:輸出結(jié)果為對(duì)應(yīng)的配對(duì)情況的總數(shù)。樣例輸入樣例輸出23402514C7 指定數(shù)量和深度的括號(hào)配對(duì)情況:繼續(xù)深入研究前面的問題, 若指定括號(hào)對(duì)數(shù)為n, 括號(hào)嵌套深度為k, 且1 k n 20則所有可能的序列有多少種?例如: 當(dāng)n = 3, k = 2時(shí), 表示有3對(duì)括號(hào)時(shí), 所有配對(duì)情況包括: ()()(), ()(), ()(), ()(), (), 其中嵌套深度為2的只有3種, 故輸出結(jié)

18、果為3。樣例輸入樣例輸出2 23 24 25 315 30 013718497845數(shù)據(jù)輸入:每一行有兩個(gè)整數(shù), 分別表示n和k, 最后一行以兩個(gè)0結(jié)束。結(jié)果輸出:輸出結(jié)果為對(duì)應(yīng)的配對(duì)情況的總數(shù)。C8 廣義“水仙花數(shù)”:一個(gè)真正意義上的“水仙花數(shù)”實(shí)質(zhì)上是一個(gè)3位的正整數(shù), 它的值恰好等于組成該數(shù)的各位數(shù)字的3次方之和。受此啟發(fā), 我們定義了廣義的“水仙花數(shù)”: 任取一個(gè)n位的正整數(shù), 如果該正整數(shù)的值恰好等于組成它的各位數(shù)字的n次方之和, 則稱該數(shù)為廣義“水仙花數(shù)”。例如: 3 = 31, 407 = 43 + 03 + 73, 8208 = 84 + 24 + 04 + 84等?，F(xiàn)在的問題

19、是: 對(duì)于任意給定的2個(gè)正整數(shù)范圍內(nèi)(包含這兩個(gè)整數(shù)), 到底存在多少個(gè)這樣的廣義“水仙花數(shù)”?數(shù)據(jù)輸入:每一行有兩個(gè)正整數(shù), 表示問題要求的“水仙花數(shù)”范圍, 前一個(gè)數(shù)較小, 后一個(gè)較大, 而且較大的數(shù)不超過108, 最后一行以兩個(gè)-1作為結(jié)束。結(jié)果輸出:輸出給定范圍內(nèi)“水仙花”的個(gè)數(shù), 每一種輸出單獨(dú)占一行。樣例輸入樣例輸出1 510 1590000 100000-1 -1502C9 整數(shù)分組:輸入n(n為偶數(shù))個(gè)不重復(fù)的正整數(shù), 將其分成個(gè)數(shù)相等的兩組, 使兩組數(shù)的總和相差最小。例如: 輸入4個(gè)正整數(shù)3, 9, 1, 4。將其分組為: (3, 9)和(1, 4), 兩組的和分別為12和5

20、, 差額為7; 而分組為: (1, 9)和(3, 4)時(shí), 兩組的和分別為10和7, 差額為3, 相差最小。w 輸入數(shù)據(jù)每個(gè)輸入包括兩行, 第一行是整數(shù)n, 第二行是n個(gè)整數(shù)m1、m2、mn。當(dāng)n為0時(shí)結(jié)束。w 輸出數(shù)據(jù)每個(gè)輸出包括兩行, 分別是兩組整數(shù), 每組整數(shù)都按升序排序輸出, 且第一組的首數(shù)比第二組的首數(shù)小。w 測(cè)試樣例輸入輸出43 9 1 464 2 6 11 5 301 43 92 3 114 5 6C10 約瑟夫的迷惑:N(N1000)個(gè)人圍坐成一圈, 按順時(shí)針方向順序編號(hào)為1, 2, , N, 每人持有一個(gè)整數(shù)的數(shù)字密碼, 編號(hào)為i的人的密碼記為Mi(Mi10000)?，F(xiàn)在給定

21、一個(gè)初始值M(M10000), 從編號(hào)為1的人開始, 按順時(shí)針方向依次報(bào)數(shù), 從1到M, 報(bào)到M的人出圈不再參與后面的報(bào)數(shù), 并以他的密碼作為新的M, 從下一個(gè)人開始重新報(bào)數(shù), 從1到M, 報(bào)到M的人再出圈, 并再以他的密碼作為新的M, 如此類推, 直到圈中只剩下一個(gè)人為止。請(qǐng)編寫程序輸出此人的編號(hào)。數(shù)據(jù)輸入:每一個(gè)測(cè)試樣例包括兩行數(shù)據(jù): 第一行數(shù)據(jù)為兩個(gè)正整數(shù)N和M, 若兩個(gè)都為0, 則為結(jié)束標(biāo)記。第二行為N個(gè)人的數(shù)字密碼。若N和M都為0, 則為結(jié)束標(biāo)記。結(jié)果輸出:對(duì)于每一個(gè)測(cè)試樣例, 請(qǐng)單獨(dú)輸出一行結(jié)果。樣例輸入樣例輸出4 22 3 4 35 32 5 7 3 410 32 5 8 3 5

22、 2 6 16 11 70 0328C11 分牛:古印度有位老人, 臨終前把三個(gè)兒子叫到床前, 說(shuō): “我有19頭牛, 老大分1/2, 老二分1/4, 老三分1/5”, 說(shuō)完就去逝了。按照古印度的教規(guī)是不能宰牛的, 老人的三個(gè)兒子為此發(fā)愁。一天, 一位老農(nóng)民牽著1頭牛經(jīng)過這里, 幫助他們解決了難題: “我把自己的這頭牛借給你們, 湊成20頭。老大分10頭; 老二分5頭; 老三分4頭; 最后剩下1頭, 正好還給我?！奔僭O(shè)老人有n頭牛, 老大分1/a, 老二分1/b, 老三分1/c, 現(xiàn)在的問題是: 能不能按老人的遺囑分牛? 如果能, 需要借幾頭牛?特例: 總共有30頭牛, 老大分1/2, 老二分

23、1/3, 老三分1/6, 則不需要借牛, 老大分得15頭, 老二分得10頭, 老三分得5頭。再如: 總共有25頭牛, 老大分1/2, 老二分1/3, 老三分1/5, 則無(wú)法按遺囑分牛。w 輸入數(shù)據(jù)每行輸入四個(gè)整數(shù)n、a、b、c, 最后以四個(gè)0作為結(jié)束標(biāo)記。w 輸出數(shù)據(jù)每行輸出一個(gè)整數(shù)。如果能分牛, 則輸出需要借牛的數(shù)量; 否則輸出-1。w 測(cè)試樣例輸入輸出19 2 4 530 2 3 647 3 4 525 2 3 50 0 0 01013-1C12 乒乓球賽:某公司為了促進(jìn)各部門員工的交流, 舉辦了一場(chǎng)乒乓球賽, 并制定了特殊的比賽規(guī)則: 員工自由分組; 不同組的選手都要進(jìn)行一場(chǎng)比賽; 同組

24、的選手不進(jìn)行比賽。例如: 共有4名選手, 依次編號(hào)為1、2、3、4, 分組情況有以下4種:第1種情況: 4名選手都分在一組, 則不需要進(jìn)行比賽;第2種情況: 分兩個(gè)組, 每組2人, 比如1、2分在一組, 3、4分在另一組, 則一共要進(jìn)行4場(chǎng)比賽: 1-3, 1-4, 2-3, 2-4;第3種情況: 分兩個(gè)組, 一組3人, 一組1人, 比如1、2、3分在一組, 4單獨(dú)一組, 則一共要進(jìn)行3場(chǎng)比賽: 1-4, 2-4, 3-4;第4種情況: 分三個(gè)組, 一組2人, 另兩組各1人, 比如: 1、2分在一組, 3單獨(dú)一組, 4也單獨(dú)一組, 則一共要進(jìn)行5場(chǎng)比賽: 1-3, 1-4, 2-3, 2-4,

25、 3-4。第5種情況: 分四個(gè)組, 4名選手都單獨(dú)成組, 則一共要進(jìn)行6場(chǎng)比賽: 1-2, 1-3, 1-4, 2-3, 2-4, 3-4。如果有n (0 n 50) 名選手參賽, 則比賽的場(chǎng)數(shù)可沒有可能是某個(gè)給定的整數(shù)k (k 0) 呢? 比如: 4名選手參賽, 比賽場(chǎng)數(shù)有可能是0、3、4、5、6, 而不可能是1、2等。再如: 3名選手參賽, 如果都分到一組, 則不進(jìn)行比賽; 如果分為兩組, 一組1人, 一組2人, 則一共要進(jìn)行2場(chǎng)比賽; 如果分為三組, 每組1人, 則一共要進(jìn)行3場(chǎng)比賽。即3名選手參賽, 比賽場(chǎng)數(shù)有可能是0、2、3, 而不可能是1等。w 輸入數(shù)據(jù)每行輸入兩個(gè)整數(shù)n和k, 最

26、后以兩個(gè)0作為結(jié)束標(biāo)記。w 輸出數(shù)據(jù)每行輸出一串文字。如果n名選手可能進(jìn)行k場(chǎng)比賽, 則輸出“Yes”; 否則輸出“No”。w 測(cè)試樣例輸入輸出2 02 13 13 24 24 60 0YesYesNoYesNoYesC13 求解不定方程:不定方程ax1 + bx2 + cx3 + dx4 = e (其中, a、b、c、d、e是整數(shù), 且a、b、c、d 10000, e 1000000), 求該方程的全部正整數(shù)解的個(gè)數(shù)。例如: 不定方程x1 + x2 + x3 + x4 = 4, 有唯一正整數(shù)解: x1 = 1, x2 = 1, x3 = 1, x4 = 1。又如: 不定方程-x1 + x2

27、- 2x3 + x4 = 5, 有無(wú)窮多個(gè)正整數(shù)解, x1 = 1, x2 = 3, x3 = 1, x4 = 5是一個(gè)解, 而x1 = 1, x2 = 5, x3 = 1, x4 = 3是另一個(gè)解, 。再如: 不定方程x1 + x2 + 2x3 + 3x4 = 4, 沒有正整數(shù)解。w 輸入數(shù)據(jù)每行輸入包括五個(gè)整數(shù)a、b、c、d、e, 最后以五個(gè)0作為結(jié)束標(biāo)記。w 輸出數(shù)據(jù)每行輸出一個(gè)整數(shù), 即不定方程的正整數(shù)解的個(gè)數(shù)。若方程有無(wú)窮多個(gè)解, 則輸出-1。w 測(cè)試樣例輸入輸出1 1 1 1 4-1 1 -2 1 51 1 2 3 40 0 0 0 01-10C14 序關(guān)系計(jì)數(shù)問題:用關(guān)系“”和“

28、=”將3個(gè)數(shù)a、b、c依序排列時(shí), 共有13 種不同的序關(guān)系: a = b = ca = b ca b = ca b ca = c ba c bb a = cb a cb = c ab c ac a = bc a bc b a現(xiàn)在的問題是: n ( 1 n 50) 個(gè)數(shù)依序排列時(shí), 有多少種序關(guān)系? w 輸入數(shù)據(jù)每行輸入一個(gè)整數(shù), 即n的值, 以0作為結(jié)束標(biāo)記。w 輸出數(shù)據(jù)每行輸出一個(gè)整數(shù), 即序關(guān)系的數(shù)量。w 測(cè)試樣例輸入輸出3013C15 刪除重復(fù)數(shù)據(jù):從鍵盤輸入n個(gè)整數(shù)a1, a2, ., an, 刪去其中重復(fù)的數(shù)據(jù), 然后輸出。例如: 輸入10個(gè)整數(shù): 1, 5, 3, 2, 1, 3

29、, 8, 4, 1, 6, 輸出: 1, 5, 3, 2, 8, 4, 6。w 輸入數(shù)據(jù)每個(gè)輸入包括兩行, 第一行是整數(shù)n, 第二行是n個(gè)整數(shù)a1, a2, ., an。當(dāng)n為0時(shí)結(jié)束。w 輸出數(shù)據(jù)每個(gè)輸出包括一行, 即刪除重復(fù)數(shù)據(jù)后的若干整數(shù)。w 測(cè)試樣例輸入輸出31 2 151 2 1 2 1101 5 3 2 1 3 8 4 1 601 21 21 5 3 2 8 4 6C16 水滴入杯:有一只空水杯, 水滴不斷地滴入杯中, 假設(shè)水杯容量為120滴水。當(dāng)杯中水量達(dá)到或超過2/3后, 每滴入一滴水, 杯中就會(huì)有1/120的水被濺出。試問, 當(dāng)杯中水量累積到n(80 n 120)滴水時(shí), 需

30、要滴多少滴水?w 輸入數(shù)據(jù)每個(gè)輸入包括一行, 只一個(gè)整數(shù)n。當(dāng)n為0時(shí)結(jié)束。w 輸出數(shù)據(jù)每個(gè)輸出包括一行, 只一個(gè)整數(shù), 即滴入的水滴總數(shù)。w 測(cè)試樣例輸入輸出8090100110080116164247C17 分糖:將n(n60)顆糖分給k(1 k 20)個(gè)人, 每人分到的數(shù)量至少1顆、至多m (1 m 10)顆, 一共有多少種分法?例如: 當(dāng)n = 3, k = 2, m = 2時(shí), 只有1種分法: (1, 2)。其中(1, 2)和(2, 1)被認(rèn)為是同一種分法。再如: 當(dāng)n = 6, k = 3, m = 3時(shí), 有2種分法: (1, 2, 3), (2, 2, 2)。w 輸入數(shù)據(jù)每個(gè)輸

31、入包括兩行, 第一行是整數(shù)n, 第二行是整數(shù)k和m。當(dāng)n為0時(shí)結(jié)束。w 輸出數(shù)據(jù)每個(gè)輸出包括一行, 只一個(gè)整數(shù), 即分糖方法的種數(shù)。w 測(cè)試樣例輸入輸出32 263 3104 40127C18 數(shù)字三角形:在下圖所示的無(wú)限等邊三角形網(wǎng)格中, 從上至下、從左至右為所有的交叉點(diǎn)順序編碼。圖中一些點(diǎn)可以構(gòu)成三角形, 如: 1, 2, 3和7, 9, 18; 某些點(diǎn)不能構(gòu)成三角形, 如: 3, 6, 8和5, 13, 14。構(gòu)成三角形的條件是: 每條邊都和網(wǎng)格中的邊重合; 三條邊的長(zhǎng)度相等。124711161718192021121314151063589w 輸入數(shù)據(jù)每個(gè)輸入包括一行, 是三個(gè)點(diǎn)的編碼

32、。當(dāng)輸入為三個(gè)0時(shí)結(jié)束。w 輸出數(shù)據(jù)每個(gè)輸出包括一行, 若輸入的三個(gè)點(diǎn)構(gòu)點(diǎn)三角形時(shí), 輸出YES, 否則輸出NO。w 測(cè)試樣例輸入輸出1 2 34 13 623 38 4024 43 380 0 0YESYESYESNOC19 貨幣組合:假定某國(guó)共有n種面值的貨幣, 它們的金額從大到小分別為c1、c2、cn, 給定一個(gè)金額a, 它可以有多少種組合方法?假設(shè)共有3面值的貨幣, 分別是: 4, 2, 1, 對(duì)于金額7可以有以下6種組合方法: 4+2+1, 4+1+1+1, 2+2+2+1, 2+2+1+1+1, 2+1+1+1+1+1, 1+1+1+1+1+1+1注: 4+2+1、1+4+2和1+

33、2+4被認(rèn)為是相同的組合, 計(jì)為1種。w 輸入數(shù)據(jù)每個(gè)輸入包括三行, 第一行是整數(shù)n, 第二行是n個(gè)整數(shù)c1、c2、cn, 第三行是金額a。當(dāng)n為0時(shí)結(jié)束。w 輸出數(shù)據(jù)每個(gè)輸出包括一行, 只一個(gè)整數(shù), 即組合方法的數(shù)量。w 測(cè)試樣例輸入輸出23 1534 2 18029C20 平行四邊形:請(qǐng)編寫程序, 輸入寬度w和高度h, 其中w 1, h 1, 輸出對(duì)應(yīng)的空心平行四邊形。w 輸入數(shù)據(jù)寬度w和高度h, 例如:10 4w 輸出數(shù)據(jù)寬度為w和高度為h的空心平行四邊形, 例如: * * * * *C21 發(fā)薪:某企業(yè)有m個(gè)員工, 他們的薪水被保存在文本文件Salary.txt中。請(qǐng)編寫程序, 幫助出

34、納員計(jì)算發(fā)薪水時(shí)需要到銀行領(lǐng)取的各種面值的貨幣的數(shù)量, 并將計(jì)算結(jié)果寫入文本文件Pay.txt。要求: 所領(lǐng)取的貨幣的總數(shù)量最少。w 輸入數(shù)據(jù)Salary.txt: 每行包含一個(gè)員工的工資(精確到元), 員工的人數(shù)由文件的行數(shù)確定, 例如:273337161869w 輸出數(shù)據(jù)Pay.txt: 各種貨幣的總數(shù)量。例如:100: 82 50: 1 20: 1 10: 3 5: 2 2: 3 1: 2C22 文字排序:輸入n(n 1)行長(zhǎng)度均為m(m 1)的字符串進(jìn)行排序, 要求從第s(1 s m)個(gè)字符開始排序。w 輸入數(shù)據(jù)第一行為n和s的值, 隨后是n行字符串, 例如:4, 6std 308 a

35、05udf 201 3b8tab 412 qt7tst 112 p01w 輸出數(shù)據(jù)排序后的n行字符串, 例如:udf 201 3b8std 308 a05tst 112 p01tab 412 qt7C23 最佳路線:在一個(gè)n n的方陣中, 每一個(gè)點(diǎn)位置處有04個(gè)數(shù)量不等的珠寶, 現(xiàn)在從最左上角出發(fā), 去往右下角, 只能向下走或者向右走, 取走途中經(jīng)過的所有點(diǎn)的珠寶。請(qǐng)?jiān)O(shè)計(jì)算法找出一條路線, 獲得最多的珠寶。w 輸入數(shù)據(jù)第一行為整數(shù)n(n 100), 其后是n行n列的方陣, 元素取值為0到4之間的整數(shù), 例如:31 2 30 2 23 4 0w 輸出數(shù)據(jù)第一行為獲得的珠寶數(shù)量, 其后是n行n列的

36、0-1矩陣, 1表示最佳路線經(jīng)過的點(diǎn)。例如:91 1 00 1 00 1 1C24 愛情約會(huì):羅密歐與朱麗葉被困在一個(gè)m n大小方格構(gòu)成的迷宮中, 羅密歐在(p, q)點(diǎn)位置, 朱麗葉在(r, s)點(diǎn)位置, 其中有k個(gè)方格被堵死而不能進(jìn)入。現(xiàn)在羅密歐必須找到一條通往朱麗葉并且拐彎(每次改變走動(dòng)方向算一次拐彎)次數(shù)最少的路徑, 否則他將無(wú)法見到朱麗葉。羅密歐可以從他所在的方格移動(dòng)到周圍8個(gè)相鄰且沒有被堵死的方格中, 請(qǐng)?jiān)O(shè)計(jì)一個(gè)算法算出最少的拐彎次數(shù), 以及與之對(duì)應(yīng)的路徑。w 輸入數(shù)據(jù)第一行3個(gè)整數(shù), 分別為m, n和k; 其后k行數(shù)據(jù), 每行2個(gè)正整數(shù), 分別為k個(gè)被堵死方格的行列號(hào); 最后2行

37、數(shù)據(jù), 分別為羅密歐和朱麗葉的位置p, q , r, s, 例如:3 4 31 23 42 21 11 4w 輸出數(shù)據(jù)第一行為最少的拐彎次數(shù), 緊接著輸出一個(gè)m n大小的矩陣, -1表示被堵死的方格, 0表示沒有堵死的方格, 而數(shù)字1, 2, 3 . 表示羅密歐行走的路徑。例如:21 -1 0 6 2 -1 5 03 4 0 -1C25 螺旋方陣:請(qǐng)編寫程序, 輸入方陣的階數(shù)n ( n 1 ), 輸出n階螺旋方陣。w 輸入數(shù)據(jù)每行一個(gè)正整數(shù), 即階數(shù)n的值, 最后一行以0作為結(jié)束標(biāo)記。360w 輸出數(shù)據(jù)輸出對(duì)應(yīng)高度的螺旋方陣。1 2 38 9 47 6 5 1 2 3 4 5 620 21 2

38、2 23 24 719 32 33 34 25 818 31 36 35 26 917 30 29 28 27 1016 15 14 13 12 11C26 顛倒乘法:在下面的算式中, 拿一個(gè)1位的正整數(shù)n ( 2 n 9 ) 去乘以一個(gè)4位的正整數(shù)abcd ( 其中: 0 a、b、c、d 9, 且a、b、c、d各不相同), 有可能得到一個(gè)次序顛倒的4位正整數(shù)dcba。abcd ndcba顯然a、d 0。請(qǐng)編寫程序, 輸出滿足條件的全部答案。w 輸入數(shù)據(jù)每行輸入一個(gè)正整數(shù), 即n的值, 最后一行以0作為結(jié)束標(biāo)記。470w 輸出數(shù)據(jù)輸出對(duì)應(yīng)的滿足條件的全部4位正整數(shù), 即abcd。如果滿足條件的

39、答案多于一個(gè), 則都在一行內(nèi)輸出, 答案之間以空格隔開。如果沒有滿足條件的答案, 則輸出None。2178NoneC27 分玩具:幼兒園里有n ( 3 n 9 )個(gè)小朋友, 老師拿來(lái)n件玩具(用1、2、3、9來(lái)表示)分給小朋友。為使每位小朋友都滿意, 逐個(gè)詢問每位小朋友都喜歡哪些玩具。請(qǐng)編寫程序, 輸出使每一位小朋友都滿意的全部分配方案。w 輸入數(shù)據(jù)第一行是一個(gè)正整數(shù), 是小朋友和玩具的數(shù)量, 即n。如果n為0, 則表示結(jié)束。其后是n行n列的0-1矩陣, 每一行表示一個(gè)小朋友, 每一列表示一件玩具, 其中0表示不喜歡, 1表示喜歡。51 0 1 1 00 0 0 1 01 0 1 1 11 1

40、 0 0 10 1 0 0 041 0 1 01 0 1 11 0 0 10 0 1 00w 輸出數(shù)據(jù)第一行為分配方案種數(shù), 其后若干行為分配方案, 每行輸出一種分配方案, 依次輸出每位小朋友所分得的玩具的編號(hào)。若如果無(wú)法滿足每位小朋友的要求, 則輸出None。31 4 3 5 23 4 1 5 23 4 5 1 2None注: 分配方案“1 4 3 5 2”表示1號(hào)小朋友分得1號(hào)玩具, 2號(hào)小朋友分得4號(hào)玩具, 3號(hào)小朋友分得3號(hào)玩具, 4號(hào)小朋友分得5號(hào)玩具, 5號(hào)小朋友分得2號(hào)玩具。C28 開平方:請(qǐng)編寫程序, 求的第100位小數(shù)。C29 生詞表:在英文教材中, 通常前面是課文, 后面是

41、生詞表。所謂生詞就是沒有見過的新單詞。為簡(jiǎn)化問題, 這里只給出一篇課文, 它由若干段落組成, 段落之間以回車符分隔。請(qǐng)編寫程序, 輸入一篇課文, 然后按字母順序輸出該篇課文的生詞表。測(cè)試數(shù)據(jù)輸入(課文以空行結(jié)束)輸出 (按字母順序每行輸出一個(gè)英文單詞)This is a desk. That is a table. There is a little doll on the floor.The desk is clean. The table is clean, too.acleandeskdollfloorislittleontablethatthetherethistooC30 拔河分組:

42、某公司的聚會(huì)上將有m ( m 100 )人舉行拔河比賽，現(xiàn)在需將這些人盡可能分為實(shí)力相當(dāng)?shù)膬芍ш?duì)伍。每個(gè)人必須在其中一支隊(duì)伍里，兩隊(duì)的人數(shù)差不能超過一個(gè)，且兩隊(duì)的隊(duì)員總體重應(yīng)該盡可能接近。請(qǐng)編程輸入m個(gè)人的體重(1到300間的整數(shù)), 輸出一種最好的分組方案。測(cè)試數(shù)據(jù)輸入(人數(shù)m, 以及m個(gè)人的體重)輸出 (兩個(gè)整數(shù), 分別為兩支隊(duì)伍的體重總和)7100 90 200 220 130 120 110470500C31 冪函數(shù):編寫冪函數(shù)Power(x, n) = xn, (其中x為正實(shí)數(shù), n 為非負(fù)整數(shù)), 采用了下面的方法：2.57 = 2.51+2+4 = 2.51 2.52 2.542

43、.515 = 2.51+2+4+8 = 2.51 2.52 2.54 2.582.5100 = 2.54+32+64 = 2.54 2.532 2.564請(qǐng)按思路用循環(huán)方法高效編寫函數(shù), 使時(shí)間復(fù)雜度降到O(log2n), 空間復(fù)雜度降到O(1)。測(cè)試數(shù)據(jù)輸入(每行數(shù)據(jù)為實(shí)數(shù)和整數(shù)，以0 0結(jié)束)輸出(每行數(shù)據(jù)為對(duì)應(yīng)的干支年號(hào))2.5 23.5 51.000000001 10000000000 06.25525.2192.71828C32 干支紀(jì)年問題:我國(guó)古代紀(jì)年方法是干支紀(jì)年法。即以甲、乙、丙、丁、戊、己、庚、辛、壬、癸為天干, 子、丑、寅、卯、辰、巳、午、未、申、酉、戌、亥為地支, 按照順序組合起來(lái)紀(jì)年。例如：1984年是甲子年，1985年是乙丑年，1986年是丙寅年，2013年是癸巳年，2014年是甲午年。請(qǐng)編寫程序，輸入年份(大于0)，輸出干支年號(hào)。測(cè)試數(shù)據(jù)輸入(每行數(shù)據(jù)為年份值，以0結(jié)束)輸出(每行數(shù)據(jù)為對(duì)應(yīng)的干支年號(hào))1984198519862013201820000甲子乙丑丙寅癸巳戊戌庚辰四、應(yīng)用型經(jīng)典問題(回溯法的設(shè)計(jì)策