C語(yǔ)言課程設(shè)計(jì)參考題目

1、C語(yǔ)言課程設(shè)計(jì)參考課題第1題 破譯密碼問(wèn)題：據(jù)說(shuō)最早的密碼來(lái)自于羅馬的凱撒大帝。消息加密的辦法是：對(duì)消息原文中的每個(gè)字母，分別用該字母之后的第5個(gè)字母替換（例如：消息原文中的每個(gè)字母A都分別替換成字母F）。而你要獲得消息原文，也就是要將這個(gè)過(guò)程反過(guò)來(lái)。 密碼字母：A B C D E F G H I J K L M N O P Q R S T U V W X Y Z M 原文字母：V W X Y Z A B C D E F G H I J K L M N O P Q R S T U （注意：只有字母會(huì)發(fā)生替換，其他非字母的字符不變，并且消息原文的所有字母都是大寫(xiě)的。）輸入：最多不超過(guò)100個(gè)數(shù)據(jù)

2、集組成，每個(gè)數(shù)據(jù)集之間不會(huì)有空行，每個(gè)數(shù)據(jù)集由3部分組成: 1. 起始行：START 2. 密碼消息：由1到200個(gè)字符組成一行，表示凱撒發(fā)出的一條消息. 3. 結(jié)束行：END 在最后一個(gè)數(shù)據(jù)集之后，是另一行：ENDOFINPUT。輸出：每個(gè)數(shù)據(jù)集對(duì)應(yīng)一行，是凱撒的原始消息。n Sample InputSTARTNS BFW, JAJSYX TK NRUTWYFSHJ FWJ YMJ WJXZQY TK YWNANFQ HFZXJXENDSTARTN BTZQI WFYMJW GJ KNWXY NS F QNYYQJ NGJWNFS ANQQFLJ YMFS XJHTSI NS WTRJEND

3、STARTIFSLJW PSTBX KZQQ BJQQ YMFY HFJXFW NX RTWJ IFSLJWTZX YMFS MJENDENDOFINPUTn Sample OutputIN WAR, EVENTS OF IMPORTANCE ARE THE RESULT OF TRIVIAL CAUSESI WOULD RATHER BE FIRST IN A LITTLE IBERIAN VILLAGE THAN SECOND IN ROMEDANGER KNOWS FULL WELL THAT CAESAR IS MORE DANGEROUS THAN HE解題思路凱撒編碼，判斷字符是否

4、是字母，并循環(huán)-5即可，記得要循環(huán)哦，非常簡(jiǎn)單的題目哦第2題 方陣填數(shù)9第3題 進(jìn)制轉(zhuǎn)換問(wèn)題1. 問(wèn)題描述實(shí)現(xiàn)將N進(jìn)制到M進(jìn)制數(shù)的轉(zhuǎn)換(1 < N,M <= 36)。對(duì)于11到36進(jìn)制數(shù)，其基數(shù)使用從A到Z的英文字母（全部為大寫(xiě)）代替。例如對(duì)于11進(jìn)制，其基數(shù)10（十進(jìn)制）使用"A"表示；對(duì)于36進(jìn)制，其基數(shù)35（十進(jìn)制）使用"Z"表示。被轉(zhuǎn)換的數(shù)全部為正數(shù)且小于2147483647（long型的最大值）。下表為十進(jìn)制數(shù)100對(duì)應(yīng)的各進(jìn)制數(shù)：進(jìn)制1011162735數(shù)值10091643J2U 2. 要求：(1).實(shí)現(xiàn)10進(jìn)制數(shù)到M進(jìn)制數(shù)的轉(zhuǎn)換

5、。(2).程序具有較強(qiáng)的容錯(cuò)能力（例如對(duì)錯(cuò)誤的輸入數(shù)字串的處理）。(3). N進(jìn)制到M進(jìn)制數(shù)(1 < N,M < 36)的轉(zhuǎn)換（擴(kuò)展要求，選做）。3. 輸入: 輸入文件名為convert.in，文件內(nèi)容格式為第一列為被轉(zhuǎn)換數(shù)的進(jìn)制數(shù)，第二列為被轉(zhuǎn)換數(shù)，第三列為轉(zhuǎn)換后的進(jìn)制。這三列內(nèi)容均為字符串形式。每列之間使用一個(gè)空格隔開(kāi)。4. 輸出： 輸出文件名為convert.out，文件內(nèi)容為轉(zhuǎn)換后的數(shù)。對(duì)于一切錯(cuò)誤，則輸出“error”字符串。5. 輸入輸出文件樣例： 樣例1convert.inconvert.out10 100 273J 樣例2convert.inconvert.out3

6、 140 27error 第4題 打魚(yú)還是曬網(wǎng) 中國(guó)有句俗語(yǔ)叫“三天打魚(yú)兩天曬網(wǎng)”。某人從1990年1月1日起開(kāi)始“三天打魚(yú)兩天曬網(wǎng)”，問(wèn)這個(gè)人在以后的某一天中是“打魚(yú)”還是“曬網(wǎng)”。*問(wèn)題分析與算法設(shè)計(jì) 根據(jù)題意可以將解題過(guò)程分為三步：1)計(jì)算從1990年1月1日開(kāi)始至指定日期共有多少天；2)由于“打魚(yú)”和“曬網(wǎng)”的周期為5天，所以將計(jì)算出的天數(shù)用5去除；3)根據(jù)余數(shù)判斷他是在“打魚(yú)”還是在“曬網(wǎng)”； 若 余數(shù)為1，2，3，則他是在“打魚(yú)” 否則 是在“曬網(wǎng)” 在這三步中，關(guān)鍵是第一步。求從1990年1月1日至指定日期有多少天，要判斷經(jīng)歷年份中是否有閏年，二月為29天，平年為28天。閏年的方

7、法可以用偽語(yǔ)句描述如下： 如果 (年能被4除盡 且 不能被100除盡)或 能被400除盡) 則 該年是閏年； 否則 不是閏年。 C語(yǔ)言中判斷能否整除可以使用求余運(yùn)算(即求模)第5題 素?cái)?shù)幻方 求四階的素?cái)?shù)幻方。即在一個(gè)4X4 的矩陣中，每一個(gè)格填 入一個(gè)數(shù)字，使每一行、每一列和兩條對(duì)角線上的4 個(gè)數(shù)字所組成的四位數(shù)，均為可逆素?cái)?shù)。*問(wèn)題分析與算法設(shè)計(jì) 有了前面的基礎(chǔ)，本題應(yīng)當(dāng)說(shuō)是不困難的。 最簡(jiǎn)單的算法是：采用窮舉法，設(shè)定4X4矩陣中每一個(gè)元素的值后，判斷每一行、每一列和兩條對(duì)角線上的4個(gè)數(shù)字組成的四位數(shù)是否都是可逆素?cái)?shù)，若是則求出了滿足題意的一個(gè)解。 這種算法在原理是對(duì)的，也一定可以求出滿足

8、題意的全部解。但是，按照這一思路編出的程序效率很低，在微機(jī)上幾個(gè)小時(shí)也不會(huì)運(yùn)行結(jié)束。這一算法致命的缺陷是：要窮舉和判斷的情況過(guò)多。 充分利用題目中的“每一個(gè)四位數(shù)都是可逆素?cái)?shù)”這一條件，可以放棄對(duì)矩陣中每個(gè)元素進(jìn)行的窮舉的算法，先求出全部的四位可逆素?cái)?shù)(204個(gè))，以矩陣的行為單位，在四位可逆素?cái)?shù)的范圍內(nèi)進(jìn)行窮舉，然后將窮舉的四位整數(shù)分解為數(shù)字后，再進(jìn)行列和對(duì)角線方向的條件判斷，改進(jìn)的算法與最初的算法相比，大大地減少了窮舉的次數(shù)。 考慮矩陣的第一行和最后一行數(shù)字，它們分別是列方向四位數(shù)的第一個(gè)數(shù)字和最后一個(gè)數(shù)字，由于這些四位數(shù)也必須是可逆素?cái)?shù)，所以矩陣的每一行和最后一行中的各個(gè)數(shù)字都不能為偶數(shù)

9、或5。這樣窮舉矩陣的第一行和最后一行時(shí)，它們的取值范圍是：所有位的數(shù)字均不是偶數(shù)或5的四位可逆數(shù)。由于符合這一條件的四位可逆素?cái)?shù)很少，所以這一范圍限制又一次減少了窮舉的次數(shù)。 對(duì)算法的進(jìn)一步研究會(huì)發(fā)現(xiàn)：當(dāng)設(shè)定了第一和第二行的值后，就已經(jīng)可以判斷出當(dāng)前的這種組合是否一定是錯(cuò)誤的(尚不能肯定該組合一定是正確的)。若按列方向上的四個(gè)兩位數(shù)與四位可逆數(shù)的前兩位矛盾(不是其中的一種組合)，則第一、二行的取值一定是錯(cuò)誤的。同理在設(shè)定了前三行數(shù)據(jù)后，可以立刻判斷出當(dāng)前的這種組合是否一定是錯(cuò)誤的，若判斷出矛盾情況，則可以立刻設(shè)置新的一組數(shù)據(jù)。這樣就可以避免將四個(gè)數(shù)據(jù)全部設(shè)定好以后再進(jìn)行判斷所造成的低效。 根據(jù)

10、以上分析，可以用偽語(yǔ)言描述以上改進(jìn)的算法： 開(kāi)始 找出全部四位的可逆素?cái)?shù)； 確定全部出現(xiàn)在第一和最后一行的四位可逆素?cái)?shù)； 在指定范圍 內(nèi)窮舉第一行 在指定范圍內(nèi)窮舉第二行 若第一、第二、三行已出現(xiàn)矛盾，則繼續(xù)窮舉下一個(gè)數(shù)； 在指定范圍內(nèi)窮舉第四行 判斷列和對(duì)角方向是否符合題意 若符合題意，則輸出矩陣； 否則繼續(xù)窮舉下一個(gè)數(shù)； 結(jié)束 在實(shí)際編程中，采用了很多程序設(shè)計(jì)技巧，假如設(shè)置若干輔助數(shù)組，其目的就是要最大限度的提高程序的執(zhí)行效率，縮短運(yùn)行時(shí)間。下面的程序運(yùn)行效率是比較高的。第6題 乘式還原（1） A代表數(shù)字0到9中的前五個(gè)數(shù)字，Z代表后五個(gè)數(shù)字，請(qǐng)還原下列乘式。 A Z A × A

11、 A Z - A A A A A A Z Z Z A A - Z A Z A A*問(wèn)題分析與算法設(shè)計(jì) 問(wèn)題本身并不復(fù)雜，可以對(duì)乘式中的每一位使用窮舉法，最終可以得到結(jié)果。本題的關(guān)鍵在于怎樣有效的判斷每個(gè)部分積的每一位是否滿足題意，這一問(wèn)題處理不好，編寫(xiě)的程序會(huì)很長(zhǎng)。程序?qū)崿F(xiàn)中可采用了一個(gè)判斷函數(shù)，通過(guò)傳入函數(shù)的標(biāo)志字符串對(duì)所有的數(shù)進(jìn)行統(tǒng)一的判斷處理。乘式還原(2) 有乘法算式如下： × - - 18個(gè)的位置上全部是素?cái)?shù)(1、3、5或7)，請(qǐng)還原此算式。*問(wèn)題分析與算法設(shè)計(jì) 問(wèn)題中雖然有18數(shù)位，但只要確定乘數(shù)和被乘數(shù)后經(jīng)過(guò)計(jì)算就可確定其它的數(shù)位。 乘數(shù)和被乘數(shù)共有5個(gè)數(shù)位，要求每個(gè)數(shù)

12、都是質(zhì)數(shù)。完全可以采用窮舉的方法對(duì)乘數(shù)和被乘數(shù)進(jìn)行窮舉，經(jīng)過(guò)判斷后找出答案。但是這種方法給人的感覺(jué)是“太笨了”，因?yàn)榻M成的數(shù)字只是質(zhì)數(shù)(4個(gè))，完全沒(méi)有必要在那么大的范圍內(nèi)進(jìn)行窮舉，只需要試探每一位數(shù)字為質(zhì)數(shù)時(shí)的情況即可。 采用五重循環(huán)的方法實(shí)現(xiàn)對(duì)于5個(gè)數(shù)字的窮舉，前面的許多例題中都已見(jiàn)過(guò)。循環(huán)實(shí)現(xiàn)簡(jiǎn)單易行，但嵌套的層次太多，需要窮舉的變量的數(shù)量直接影響到循環(huán)嵌套的層數(shù)，這種簡(jiǎn)單的實(shí)現(xiàn)方法缺少技巧性。本例的程序中給出了另外一種同樣功能的算法，該算法的實(shí)現(xiàn)思想請(qǐng)閱讀程序。 程序中并沒(méi)有直接對(duì)質(zhì)數(shù)進(jìn)行窮舉，而是將每個(gè)質(zhì)數(shù)與1到4順序一一對(duì)應(yīng)，在窮舉時(shí)為處理簡(jiǎn)單僅對(duì)1到4進(jìn)行窮舉處理，待要判斷產(chǎn)生的

13、乘積是否滿足條件時(shí)再利用一個(gè)數(shù)組完成向?qū)?yīng)質(zhì)數(shù)的轉(zhuǎn)換。請(qǐng)?bào)w會(huì)程序中的處理方法。程序中使用的算法實(shí)際上是回朔法。第7題 除式還原(1) 給定下列除式，其中包含5個(gè)7，其它打×的是任意數(shù)字，請(qǐng)加以還原。 × 7 × -商 - 除數(shù)-××| ×××××-被除數(shù) ×7 7 - × 7 × × 7 × - × × × × - *題目分析與算法設(shè)計(jì) 首先分析題目，由除式本身盡可能多地推出已知條件。由除式本身書(shū)已知： 1

14、、被除數(shù)的范圍是10000到99999，除數(shù)的范圍是10到99，且可以整除； 2、商為100到999之間，且十位數(shù)字為7； 3、商的第一位與除數(shù)的積為三位數(shù)，且后兩位為77； 4、被除數(shù)的第三位一定為4； 5、 7乘以除數(shù)的積為一個(gè)三位數(shù)，且第二位為7； 6、商的最后一位不能為0，且與除數(shù)的積為一個(gè)二位數(shù)。由已知條件就可以采用窮舉的方法找出結(jié)果。除式還原(2) 下列除式中僅在商中給定了一個(gè)7，其它打×的位置全部是任意數(shù)字，請(qǐng)還原。 ×7××× -商 - 除數(shù) -×××| ×××

15、5;×××× -被除數(shù) ×××× -1) - ××× -2) ××× -3) - ×××× -4) ××× -5) - ×××× -6) ×××× -7) - 0*題目分析與算法設(shè)計(jì) 這道題是不可能用單純的窮舉法求解的，一則計(jì)算時(shí)間太長(zhǎng)，二則難于求出除式中各部分的值。 對(duì)除式進(jìn)行分析，改可能多地推出限制條件：

16、 由3)可以看出，商的第二位7乘除數(shù)得一個(gè)三位數(shù)，所以除數(shù)<=142。 由除數(shù)乘商的第一位為一個(gè)四位數(shù)可知，商的第一位只能為8或9且除數(shù)>=112。同時(shí)商的第五位也為8或9數(shù)的前四位一定<=142*9+99且>=1000+10。 由4)、5)、6)可以看出，4)的前兩位一定為“10”；5)的第一位一定為“9”；6)的前兩位一定在10到99之間；商的第四位一定為為0。 由 5)的第一位一定是“9”和“112”<=除數(shù)<=142可知：商的第三位可能為7或8。 由除式本身可知：商的第四位為0。 由 1)可知：除數(shù)X商的第一位應(yīng)當(dāng)為一個(gè)四位數(shù)。 由 5)可知：除數(shù)X

17、商的第三位應(yīng)當(dāng)為一個(gè)三位數(shù)。 編程時(shí)為了方便，將被除數(shù)分解：前四位用a0表示，第五位用a1，第六位用a2，第七八兩位用a3;除數(shù)用變量b表示；分解商：第一位用c0，第五位用c2;其它的部分商分別表示為：2)的前兩位為d0，4)的前三位為d1，6)的前二位為d2。將上述分析用數(shù)學(xué)的方法綜合起來(lái)可以表示為： 被除數(shù)： 1010<=a0<=1377 0<=a1<=9 0<=a2<=9 0<=a3<=99 除數(shù)： 112<=b <=142 商： 8<=c0<=9 7<=c1<=8 8<=c2<=9 2)的前

18、兩位： 10<=d0<=99 4)的前三位： 100<=d1<b 6)的前兩位： 10<=d2<=99 1)式部分積： b*c0>1000 5)式部分積： 100<b*c1<1000第8題 約瑟夫問(wèn)題 這是17世紀(jì)的法國(guó)數(shù)學(xué)家加斯帕在數(shù)目的游戲問(wèn)題中講的一個(gè)故事：15個(gè)教徒和15 個(gè)非教徒在深海上遇險(xiǎn)，必須將一半的人投入海中，其余的人才能幸免于難，于是想了一個(gè)辦法：30個(gè)人圍成一圓圈，從第一個(gè)人開(kāi)始依次報(bào)數(shù)，每數(shù)到第九個(gè)人就將他扔入大海，如此循環(huán)進(jìn)行直到僅余15個(gè)人為止。問(wèn)怎樣排法，才能使每次投入大海的都是非教徒。*問(wèn)題分析與算法設(shè)計(jì) 約瑟

19、夫問(wèn)題并不難，但求解的方法很多；題目的變化形式也很多。這里給出一種實(shí)現(xiàn)方法。 題目中30個(gè)人圍成一圈，因而啟發(fā)我們用一個(gè)循環(huán)的鏈來(lái)表示?？梢允褂媒Y(jié)構(gòu)數(shù)組來(lái)構(gòu)成一個(gè)循環(huán)鏈。結(jié)構(gòu)中有兩個(gè)成員，其一為指向下一個(gè)人的指針，以構(gòu)成環(huán)形的鏈；其二為該 人是否被扔下海的標(biāo)記，為1表示還在船上。從第一個(gè)人開(kāi)始對(duì)還未扔下海的人進(jìn)行計(jì)數(shù)，每數(shù)到9時(shí)，將結(jié)構(gòu)中的標(biāo)記改為0，表示該人已被扔下海了。這樣循環(huán)計(jì)數(shù)直到有15個(gè)人被扔下海為止。第9題 卡布列克常數(shù) 驗(yàn)證卡布列克運(yùn)算。任意一個(gè)四位數(shù)，只要它們各個(gè)位上的數(shù)字是不全相同的，就有這樣的規(guī)律： 1)將組成該四位數(shù)的四個(gè)數(shù)字由大到小排列，形成由這四個(gè)數(shù)字構(gòu)成的最大的四位

20、數(shù)； 2)將組成該四位數(shù)的四個(gè)數(shù)字由小到大排列，形成由這四個(gè)數(shù)字構(gòu)成的最小的四位數(shù)(如果四個(gè)數(shù)中含有0，則得到的數(shù)不足四位)； 3)求兩個(gè)數(shù)的差，得到一個(gè)新的四位數(shù)(高位零保留)。 重復(fù)以上過(guò)程，最后得到的結(jié)果是6174，這個(gè)數(shù)被稱為卡布列克數(shù)。*問(wèn)題分析與算法設(shè)計(jì) 題目中給出的處理過(guò)程很清楚，算法不需要特殊設(shè)計(jì)，可按照題目的敘述直接進(jìn)行驗(yàn)證。第10題 自動(dòng)發(fā)牌 一副撲克有52張牌，打橋牌時(shí)應(yīng)將牌分給四個(gè)人。請(qǐng)?jiān)O(shè)計(jì)一個(gè)程序完成自動(dòng)發(fā)牌的工作。要求：黑桃用S(Spaces)表示；紅桃用H(Hearts)表示；方塊用D(Diamonds)表示；梅花用C(Clubs)表示。*問(wèn)題分析與算法設(shè)計(jì) 按照

21、打橋牌的規(guī)定，每人應(yīng)當(dāng)有13張牌。在人工發(fā)牌時(shí)，先進(jìn)行洗牌，然后將洗好的牌按一定的順序發(fā)給每一個(gè)人。為了便于計(jì)算機(jī)模擬，可將人工方式的發(fā)牌過(guò)程加以修改：先確定好發(fā)牌順序：1、2、3、4；將52張牌順序編號(hào)：黑桃2對(duì)應(yīng)數(shù)字0，紅桃2對(duì)應(yīng)數(shù)字1，方塊2對(duì)應(yīng)數(shù)字2，梅花2對(duì)應(yīng)數(shù)字3，黑桃3對(duì)應(yīng)數(shù)字4，紅桃3對(duì)應(yīng)數(shù)字5，.然后從52 張牌中隨機(jī)的為每個(gè)人抽牌。 這里采用C語(yǔ)言庫(kù)函數(shù)的隨機(jī)函數(shù)，生成0到51之間的共52個(gè)隨機(jī)數(shù)，以產(chǎn)生洗牌后發(fā)牌的效果。第11題 黑白子交換 有三個(gè)白子和三個(gè)黑子如下圖布置： . 游戲的目的是用最少的步數(shù)將上圖中白子和黑子的位置進(jìn)行交換： . 游戲的規(guī)則是：(1)一次只能移

22、動(dòng)一個(gè)棋子； (2)棋子可以向空格中移動(dòng)，也可以跳過(guò)一個(gè)對(duì)方的棋子進(jìn)入空格，但不能向后跳，也不能跳過(guò)兩個(gè)子。請(qǐng)用計(jì)算機(jī)實(shí)現(xiàn)上述游戲。*問(wèn)題分析與算法設(shè)計(jì) 計(jì)算機(jī)解決勝這類問(wèn)題的關(guān)鍵是要找出問(wèn)題的規(guī)律，或者說(shuō)是要制定一套計(jì)算機(jī)行動(dòng)的規(guī)則。分析本題，先用人來(lái)解決問(wèn)題，可總結(jié)出以下規(guī)則： (1) 黑子向左跳過(guò)白子落入空格，轉(zhuǎn)(5) (2) 白子向右跳過(guò)黑子落入空格，轉(zhuǎn)(5) (3) 黑子向左移動(dòng)一格落入空格(但不應(yīng)產(chǎn)生棋子阻塞現(xiàn)象)，轉(zhuǎn)(5) (4) 白子向右移動(dòng)一格落入空格(但不應(yīng)產(chǎn)生棋子阻塞現(xiàn)萌)，轉(zhuǎn)(5) (5) 判斷游戲是否結(jié)束，若沒(méi)有結(jié)束，則轉(zhuǎn)(1)繼續(xù)。 所謂的“阻塞”現(xiàn)象就是：在移動(dòng)棋

23、子的過(guò)程中，兩個(gè)尚未到位的同色棋子連接在一起，使棋盤中的其它棋子無(wú)法繼續(xù)移動(dòng)。例如按下列方法移動(dòng)棋子： 0 . 1 . 2 . 3 . 4 兩個(gè)連在一起產(chǎn)生阻塞 . 或4 兩個(gè)白連在一起產(chǎn)生阻塞 . 產(chǎn)生阻塞的現(xiàn)象的原因是在第2步(狀態(tài))時(shí)，棋子不能向右移動(dòng)，只能將向左移動(dòng)。 總結(jié)產(chǎn)生阻塞的原因，當(dāng)棋盤出現(xiàn)“黑、白、空、黑”或“白、空、黑、白”狀態(tài)時(shí)，不能向左或向右移動(dòng)中間的棋子，只移動(dòng)兩邊的棋子。 按照上述規(guī)則，可以保證在移動(dòng)棋子的過(guò)程中，不會(huì)出現(xiàn)棋子無(wú)法移動(dòng)的現(xiàn)象，且可以用最少的步數(shù)完成白子和黑子的位置交換。第12題 搶 30 這是中國(guó)民間的一個(gè)游戲。兩人從1開(kāi)始輪流報(bào)數(shù)，每人每次可報(bào)一個(gè)

24、數(shù)或兩個(gè)連續(xù)的數(shù)，誰(shuí)先報(bào)到30，誰(shuí)就為勝方。*問(wèn)題分析與算法設(shè)計(jì) 本題與上題類似，算法也類似，所不同的是，本誰(shuí)先走第一步是可選的。若計(jì)算機(jī)走第一步，那么計(jì)算機(jī)一定是贏家。若人先走一步，那么計(jì)算機(jī)只好等待人犯錯(cuò)誤，如果人先走第一步且不犯錯(cuò)誤，那么人就會(huì)取勝；否則計(jì)算機(jī)會(huì)抓住人的一次錯(cuò)誤使自己成為勝利者。第13題 搬山游戲 設(shè)有n座山，計(jì)算機(jī)與人為比賽的雙方，輪流搬山。規(guī)定每次搬山的數(shù)止不能超 過(guò)k座，誰(shuí)搬最后一座誰(shuí)輸。游戲開(kāi)始時(shí)。計(jì)算機(jī)請(qǐng)人輸入山的總數(shù)(n)和每次允許搬山的最大數(shù)止(k)。然后請(qǐng)人開(kāi)始，等人輸入了需要搬走的山的數(shù)目后，計(jì)算機(jī)馬上打印出它搬多少座山，并提示尚余多少座山。雙方輪流搬山

25、直到最后一座山搬完為止。計(jì)算機(jī)會(huì)顯示誰(shuí)是贏家，并問(wèn)人是否要繼續(xù)比賽。若人不想玩了，計(jì)算機(jī)便會(huì)統(tǒng)計(jì)出共玩了幾局，雙方勝負(fù)如何。*問(wèn)題分析與算法設(shè)計(jì) 計(jì)算機(jī)參加游戲時(shí)應(yīng)遵循下列原則： 1) 當(dāng)： 剩余山數(shù)目-1<=可移動(dòng)的最大數(shù)k 時(shí)計(jì)算機(jī)要移(剩余山數(shù)目-1)座，以便將最后一座山留給人。 2)對(duì)于任意正整數(shù)x,y，一定有： 0<=x%(y+1)<=y 在有n座山的情況下，計(jì)算機(jī)為了將最后一座山留給人，而且又要控制每次搬山的數(shù)目不超過(guò)最大數(shù)k，它應(yīng)搬山的數(shù)目要滿足下列關(guān)系： (n-1)%(k+1) 如果算出結(jié)果為0，即整除無(wú)余數(shù)，則規(guī)定只搬1座山，以防止冒進(jìn)后發(fā)生問(wèn)題。第14題

26、人機(jī)猜數(shù)游戲 由計(jì)算機(jī)“想”一個(gè)四位數(shù)，請(qǐng)人猜這個(gè)四位數(shù)是多少。人輸入四位數(shù)字后，計(jì)算機(jī)首先判斷這四位數(shù)字中有幾位是猜對(duì)了，并且在對(duì)的數(shù)字中又有幾位位置也是對(duì)的，將結(jié)果顯示出來(lái)，給人以提示，請(qǐng)人再猜，直到人猜出計(jì)算機(jī)所想的四位數(shù)是多少為止。 例如：計(jì)算機(jī)“想”了一個(gè)“1234”請(qǐng)人猜，可能的提示如下： 人猜的整數(shù) 計(jì)算機(jī)判斷有幾個(gè)數(shù)字正確 有幾個(gè)位置正確 1122 2 1 3344 2 1 3312 3 0 4123 4 0 1243 4 2 1234 4 4 游戲結(jié)束 請(qǐng)編程實(shí)現(xiàn)該游戲。游戲結(jié)束時(shí)，顯示人猜一個(gè)數(shù)用了幾次。*問(wèn)題分析與算法設(shè)計(jì) 問(wèn)題本身清楚明了。判斷相同位置上的數(shù)字是否相同不

27、需要特殊的算法。只要截取相同位置上的數(shù)字進(jìn)行比較即可。但在判斷幾位數(shù)字正確時(shí)，則應(yīng)當(dāng)注意：計(jì)算機(jī)所想的是“1123”，而人所猜的是“1576”，則正確的數(shù)字只有1位。 程序中截取計(jì)算機(jī)所想的數(shù)的每位數(shù)字與人所猜的數(shù)字按位比較。若有兩位數(shù)字相同，則要記信所猜中數(shù)字的位置，使該位數(shù)字只能與一位對(duì)應(yīng)的數(shù)字“相同”。當(dāng)截取下一位數(shù)字進(jìn)行比較時(shí)，就不應(yīng)再與上述位置上的數(shù)字進(jìn)行比較，以避免所猜的數(shù)中的一位與對(duì)應(yīng)數(shù)中多位數(shù)字“相同”的錯(cuò)誤情況。人機(jī)猜數(shù)游戲(2) 將以上游戲雙方倒一下，請(qǐng)人想一個(gè)四位的整數(shù)，計(jì)算機(jī)來(lái)猜，人給計(jì)算機(jī)提示信息，最終看計(jì)算機(jī)用幾次猜出一個(gè)人“想”的數(shù)。請(qǐng)編程實(shí)現(xiàn)。*問(wèn)題分析與算法設(shè)

28、計(jì) 解決這類問(wèn)題時(shí)，計(jì)算機(jī)的思考過(guò)程不可能象人一樣具完備的推理能力，關(guān)鍵在于要將推理和判斷的過(guò)程變成一種機(jī)械的過(guò)程，找出相應(yīng)的規(guī)則，否則計(jì)算機(jī)難以完成推理工作。 基于對(duì)問(wèn)題的分析和理解，將問(wèn)題進(jìn)行簡(jiǎn)化，求解分為兩個(gè)步聚來(lái)完成：首先確定四位數(shù)字的組成，然后再確定四位數(shù)字的排列順序?？梢粤谐鋈缦乱?guī)則： 1)分別顯示四個(gè)1，四個(gè)2，.，四個(gè)0，確定四位數(shù)字的組成。 2)依次產(chǎn)生四位數(shù)字的全部排列(依次兩兩交換全部數(shù)字的位置)。 3)根據(jù)人輸入的正確數(shù)字及正確位置的數(shù)目，進(jìn)行分別處理： (注意此時(shí)不出現(xiàn)輸入的情況，因?yàn)樵谒膫€(gè)數(shù)字已經(jīng)確定的情況下，若有3個(gè)位置正確，則第四個(gè)數(shù)字的位置必然也是正確的) 若

29、輸入4：游戲結(jié)束。 判斷本次輸入與上次輸入的差值 若差為2：說(shuō)明前一次輸入的一定為0，本次輸入的為2，本次交換的兩個(gè)數(shù)字的位置是正確的，只要交換另外兩個(gè)沒(méi)有交換過(guò)的數(shù)字即可結(jié)束游戲。 若差為-2：說(shuō)明前一次輸入的一定為2，本次的一定為0。說(shuō)明剛交換過(guò)的兩個(gè)數(shù)字的位置是錯(cuò)誤的，只要將交換的兩個(gè)數(shù)字位置還原，并交換另外兩個(gè)沒(méi)有交換過(guò)的數(shù)字即可結(jié)束游戲。 否則：若本次輸入的正確位置數(shù)<=上次的正確位置數(shù) 則恢復(fù)上次四位數(shù)字的排列，控制轉(zhuǎn)3) 否則：將本次輸入的正確位置數(shù)作為“上次輸入的正確位置數(shù)”，控制轉(zhuǎn)3)。第15題 選美比賽 在選美大獎(jiǎng)賽的半決勝賽現(xiàn)場(chǎng)，有一批選手參加比賽，比賽的規(guī)則是最后

30、得分越高，名次越低。當(dāng)半決決賽結(jié)束時(shí)，要在現(xiàn)場(chǎng)按照選手的出場(chǎng)順序宣布最后得分和最后名次，獲得相同分?jǐn)?shù)的選手具有相同的名次，名次連續(xù)編號(hào)，不用考慮同名次的選手人數(shù)。例如： 選手序號(hào)： 1，2，3，4，5，6，7 選手得分： 5，3，4，7，3，5，6 則輸出名次為： 3，1，2，5，1，3，4 請(qǐng)編程幫助大獎(jiǎng)賽組委會(huì)完成半決賽的評(píng)分和排名工作。*問(wèn)題分析與算法設(shè)計(jì) 問(wèn)題用程序設(shè)計(jì)語(yǔ)言加以表達(dá)的話，即為：將數(shù)組A中的整數(shù)從小到大進(jìn)行連續(xù)編號(hào)，要求不改變數(shù)組中元素的順序，且相同的整數(shù)要具有相同的編號(hào)。 普通的排序方法均要改變數(shù)組元素原來(lái)的順序，顯然不能滿足要求。為此，引入一個(gè)專門存放名次的數(shù)組，再采

31、用通常的算法：在尚未排出名次的元素中找出最小值，并對(duì)具有相同值的元素進(jìn)行處理，重復(fù)這一過(guò)程，直到全部元素排好為止。第16題 滿足特異條件的數(shù)列 輸入m和n(20>=m>=n>0)求出滿足以下方程的正整數(shù)數(shù)列 i1,i2,.,in，使得：i1+i1+.+in=m，且i1>=i2.>=in。例如： 當(dāng)n=4, m=8時(shí)，將得到如下5 個(gè)數(shù)列： 5 1 1 1 4 2 1 1 3 3 1 1 3 2 2 1 2 2 2 2*問(wèn)題分析與算法設(shè)計(jì) 可將原題抽象為：將M分解為N個(gè)整數(shù)，且N個(gè)整數(shù)的和為M，i1>=i2>=.>=in。分解整數(shù)的方法很低多，由于

32、題目中有"i1>=i2>=.>=in，提示我們可先確定最右邊in元素的值為1，然后按照條件使前一個(gè)元素的值一定大于等于當(dāng)前元素的值，不斷地向前推就可以解決問(wèn)題。下面的程序允許用戶選定M和N，輸出滿足條件的所有數(shù)列。第17題 八皇后問(wèn)題 在一個(gè)8×8國(guó)際象棋盤上，有8個(gè)皇后，每個(gè)皇后占一格；要求皇后間不會(huì)出現(xiàn)相互“攻擊”的現(xiàn)象，即不能有兩個(gè)皇后處在同一行、同一列或同一對(duì)角線上。問(wèn)共有多少種不同的方法。*問(wèn)題分析與算法設(shè)計(jì) 這是一個(gè)古老的具有代表性的問(wèn)題，用計(jì)算機(jī)求解時(shí)的算法也很多，這里僅介紹一種。 采用一維數(shù)組來(lái)進(jìn)行處理。數(shù)組的下標(biāo)i表示棋盤上的第i列，a的

33、值表示皇后在第i列所放的位置。如：a1=5，表示在棋盤的第一例的第五行放一個(gè)皇后。 程序中首先假定a1=1，表示第一個(gè)皇后放在棋盤的第一列的第一行的位置上，然后試探第二列中皇后可能的位置，找到合適的位置后，再處理后續(xù)的各列，這樣通過(guò)各列的反復(fù)試探，可以最終找出皇后的全部擺放方法。 程序采用回溯法，算法的細(xì)節(jié)參看程序。第18題 超長(zhǎng)正整數(shù)的加法 請(qǐng)?jiān)O(shè)計(jì)一個(gè)算法來(lái)完成兩個(gè)超長(zhǎng)正整數(shù)的加法。*問(wèn)題分析與算法設(shè)計(jì) 首先要設(shè)計(jì)一種數(shù)據(jù)結(jié)構(gòu)來(lái)表示一個(gè)超長(zhǎng)的正整數(shù)，然后才能夠設(shè)計(jì)算法。 首先我們采用一個(gè)帶有表頭結(jié)點(diǎn)的環(huán)形鏈來(lái)表示一個(gè)非負(fù)的超大整數(shù)，如果從低位開(kāi)始為每 個(gè)數(shù)字編號(hào)，則第一位到第四位、第五位到第

34、八位.的每四位組成的數(shù)字，依次放在鏈表的第一個(gè)、第二個(gè)、.結(jié)點(diǎn)中，不足4位的最高位存放在鏈表的最后一個(gè)結(jié)點(diǎn)中，表頭結(jié)點(diǎn)的值規(guī)定為-1。例如： 大整數(shù)“587890987654321”可用如下的帶表頭結(jié)點(diǎn)head的鏈表表示：按照此數(shù)據(jù)結(jié)構(gòu)，可以從兩個(gè)表頭結(jié)點(diǎn)開(kāi)始，順序依次對(duì)應(yīng)相加，求出所需要的進(jìn)位后代入下面的運(yùn)算。第19題 數(shù)字移動(dòng) 0-0-0 | | / | 0-0-0 | / | | 0-0-0 在圖中的九個(gè)點(diǎn)上,空出中間的點(diǎn),其余的點(diǎn)上任意填入數(shù)字1到8;1的位置固定不動(dòng),然后移動(dòng)其余的數(shù)字,使1到8順時(shí)針從小到大排列.移動(dòng)的規(guī)律是:只能將數(shù)字沿線移向空白的點(diǎn). 請(qǐng)編程顯示數(shù)字移動(dòng)過(guò)程。*

35、題目分析與算法設(shè)計(jì) 分析題目中的條件,要求利用中間的空白格將數(shù)字順時(shí)針?lè)较蚺帕?且排列過(guò)程中只能借空白的點(diǎn)來(lái)移動(dòng)數(shù)字.問(wèn)題的實(shí)質(zhì)就是將矩陣外面的8個(gè)格看成一個(gè)環(huán),8個(gè)數(shù)字在環(huán)內(nèi)進(jìn)行排序,同于受題目要求的限制"只能將數(shù)字沿線移向空白的點(diǎn)",所以要利用中間的空格進(jìn)行排序,這樣要求的排序算法與眾不同. 觀察中間的點(diǎn),它是唯一一個(gè)與其它8個(gè)點(diǎn)有連線的點(diǎn),即它是中心點(diǎn).中心點(diǎn)的活動(dòng)的空間最大,它可以向8個(gè)方向移動(dòng),充分利用中心點(diǎn)這個(gè)特性是算法設(shè)計(jì)成功與否的關(guān)鍵. 在找到1所在的位置后,其余各個(gè)數(shù)字的正確位置就是固定的.我們可以按照下列算法從數(shù)字2開(kāi)始,一個(gè)一個(gè)地來(lái)調(diào)整各個(gè)數(shù)字的位置. *確定數(shù)字i應(yīng)處的位置; *從數(shù)字i應(yīng)處的位置開(kāi)始,向后查找數(shù)字i現(xiàn)在的位置; *若數(shù)字i現(xiàn)在位置不正確,則將數(shù)字i從現(xiàn)在的位置(沿連線)移向中間的空格