經(jīng)典算法例題分析

1、在前面的章節(jié)中大家對C語言有了大概的了解，本章將重點講解幾個常用到的經(jīng)典例題，幫助大家加深對C語言的掌握?，F(xiàn)有88的棋盤，要求在其中放入8個皇后，可以使任意兩個皇后不能吃掉對方。如果兩個皇后在同一行、同一列或者同一對角線，則其中的一個皇后會吃掉另外一個皇后。試求出其所有可能的解，并輸出到屏幕?，F(xiàn)有八個皇后，它們不能放在同一行、同一列、同一對角線上。我們首先手工擺放，嘗試從中找到規(guī)律，如圖16.1所示，圖中使用圓形表示皇后。當一個皇后放置后，該皇后所在的行、列、對角線上的位置都標成灰色。這些位置都不能再擺放其他皇后。根據(jù)問題分析，可以推導出八皇后的算法設計流程圖，如圖所示。根據(jù)問題分析，可以推導

2、出八皇后的算法設計流程圖。從前在古代印度羅門圣廟的僧尚中，有一種名為漢洛塔的游戲。設有柱子A、B、C，其中柱子A上有著若干個大小不等的圓盤，要將柱子A上的圓盤完整地移動到C柱子上。要求每次只能移動最上面的圓盤，并且可以將柱子B作為媒介，但大的圓盤不能在小的圓盤之上。設A柱上有從小到大的3個盤子，因為大盤不能在小盤之上，因此將A柱中最大的盤子移動到C柱之前，C柱必須為空?？梢韵葘柱中的2個盤子先移動到B柱上，然后將第3個盤子移動到C柱上。當C柱上已放有最大的盤子時，A柱為空，B柱上有2個盤子。這時可將B柱上的1個盤子移動到A柱上，再將B柱上的剩下的1個盤子移動到C柱上，如此循環(huán)直到最后盤子的個

3、數(shù)為1為止，直接將盤子移動到C盤上，循環(huán)結(jié)束。根據(jù)題意，來看一下此問題的具體分析，如圖16.4所示。根據(jù)問題分析，可以推導出漢洛塔的算法設計流程圖。 現(xiàn)有17個猴子，這些猴子根據(jù)一個游戲選舉大王。其游戲規(guī)則為17個猴子站成一圈，然后從1到3開始計數(shù)，數(shù)到3的猴子淘汰退出游戲，下一個猴子繼續(xù)從1開始數(shù)，直到最后只剩一個猴子，即為大王。可以將每個猴子抽象成一個編號016。其中，0表示第一個猴子，以后依次類推，16表示最后一只猴子。然后將數(shù)到3的猴子淘汰，下一個猴子從1開始數(shù)，根據(jù)題意，來看一下此問題的具體分析，如圖16.5所示。根據(jù)問題分析，可以推導出猴子選王算法設計流程圖，如圖16.6所示。最小

4、公倍數(shù)（Least Common Multiple，縮寫L.C.M.），如果有一個自然數(shù)a能被自然數(shù)b整除，則稱a為b的倍數(shù)，b為a的約數(shù)，對于兩個整數(shù)來說，指該兩數(shù)共有倍數(shù)中最小的一個。求出的最小公倍數(shù)看是否能整除這三個數(shù)。若能整除這三個數(shù)，則輸出其中的最小的數(shù)，就是公倍數(shù)。根據(jù)題意，看一下此問題的具體分析，如圖16.8所示根據(jù)問題分析，可以推導出三個數(shù)的最小公倍數(shù)的流程圖，如圖16.9所示?，F(xiàn)有9件商品，從中選出3件使得其重量之和與600克之間差值最小，其中每件商品的重量由鍵盤輸入。假設9件商品的重量分別為88、90、40、100、60、50、55、99、66，我們對這些商品進行分析，如圖

5、16.11所示。我們可以選擇其中重量最重的三件商品，看一看重量是否超過600克，如果超過選擇次其中的商品。根據(jù)問題分析，可以推導出背包問題的流程圖，如圖6.12所示。循環(huán)賽是大家經(jīng)常見到的，現(xiàn)在設有n個選手要進行乒乓球選拔賽，編寫一個程序設計其比賽日程安排表，具有以下要求：（1）每名選手都必須與其他選手比賽一次。（2）每名選手一天之內(nèi)只能進行一次比賽。（3）所有選手的比賽在n-1天內(nèi)比完。在遇到循環(huán)賽問題時，我們可以將隊員的人數(shù)分成兩半，即8個選手的比賽日程由4個選手的比賽日程決定。用這種一分為二的方法對選手進行劃分直至只剩下兩個對手為止，單獨設置其比賽日程，然后將這些單獨的塊最后合并起來即為

6、最終的解。根據(jù)題意，看一下此題的分析圖。如圖所示。根據(jù)分析圖，可以推到出循環(huán)賽問題的流程分析圖，如圖所示?，F(xiàn)有nm個格子的棋盤，馬在棋盤上行走，只能走日字。編寫程序，求出馬從任意位置出發(fā)，將所有格子走完并且只能走過一次的所有路徑。棋盤總共有n行和m列，馬的位置是任意的，馬從某點走日字走完所有格子并且只能走的一次，根據(jù)題意，看一下此題的分析圖所示根據(jù)分析圖，可以推到出馬遍歷的流程圖所示。魔術方正又稱幻方陣、魔方陣，是一種已流傳千年的數(shù)字排列，不管是中西方對這奇妙的陣列都有所理解。所謂魔術方陣，就是將連續(xù)的整數(shù)1、2、3、n，按某種特別的順序排在方陣里，方陣中的每一行每一列或?qū)蔷€位置的數(shù)各自相加

7、的和均相等。用簡捷連續(xù)填數(shù)法創(chuàng)建魔術方正。下面以填充一個3階魔術方正為例，根據(jù)題意，看一下此題的分析圖，如圖16.20所示根據(jù)分析圖，可以推到出魔術方正的流程圖，如圖所示。假設有一條繩子，上面有紅、白、藍3中顏色的多面旗子，這些旗子的排列是沒有順序的，要求用最少的步驟將繩子上的旗子按藍、白、紅3種顏色排列。要求只能在繩子上進行旗子的移動，并且每次只能調(diào)換兩個旗子。假設從繩子的一端開始進行，遇到藍色的旗子向前移，遇到白色的旗子就留在中間，遇到紅色的旗子就往后移，根據(jù)題意，看一下此題的分析圖，如圖所示。根據(jù)分析圖，可以推到出三色旗的流程圖，如圖所示。人類建造迷宮已有5000年的歷史。在世界的不同文化發(fā)展時期，這些奇特的建筑物始終吸引人們沿著彎彎曲曲、困難重重的小路吃力地行走，尋找真相?，F(xiàn)在給定一迷宮，編寫一程序?qū)崿F(xiàn)從入口走出迷宮。假設迷宮是由許多格子組成的矩形，其中用1表示有墻，0表示有路。走迷宮即為沿上、下、左、右方向走，直到最后走出迷宮。根據(jù)題意，看一