貪心法習題匯總.doc

《貪心法習題匯總.doc》由會員上傳分享，免費在線閱讀，更多相關內容在教育資源-天天文庫。

1、貪心法習題匯總排隊接水源程序名.???（,,）可執(zhí)行文件名輸入文件名輸出文件名【問題描述】有個人在一個水龍頭前排隊接水，假如每個人接水的時間為，請編程找出這個人排隊的一種順序，使得個人的平均等待時間最小?！据斎搿枯斎胛募矁尚?，第一行為；第二行分別表示第個人到第個人每人的接水時間，，…，，每個數(shù)據(jù)之間有個空格?！据敵觥枯敵鑫募袃尚?，第一行為一種排隊順序，即到的一種排列；第二行為這種排列方案下的平均等待時間(輸出結果精確到小數(shù)點后兩位)。【樣例】【算法分析】平均等待時間是每個人的等待時間之和再除以，因為是一個常數(shù)，所以等待時間之和最小，也就是平均等待時間最小

2、。假設是按照的自然順序排列的，則這個問題就是求以下公式的最小值：如果用窮舉的方法求解，就需要我們產生個人的所有不同排列，然后計算每種排列所需要等待的時間之和，再“打擂臺”得到最小值，但這種方法需要進行!次求和以及判斷，時間復雜度很差！其實，我們仔細研究一下上面的公式，發(fā)現(xiàn)可以改寫成如下形式：這個公式何時取最小值呢？對于任意一種排列,,,…,，當≤≤≤…≤時，取到最小值。如何證明呢？方法如下：因為假設<，而<，這是的和為，而把和互換位置，設新的和為，則：我們發(fā)現(xiàn)上述△恒大于，所以也說明了任何次序的改變，都會導致等待時間的增加。從而證明了我們的設想。既然如此，我

3、們就得到了一種最有貪心策略：把接水時間少的人盡可能排在前面。這樣一樣，問題的本質就變成：把個等待時間按非遞減順序排列，輸出這種排列，并求出這種排列下的平均等待時間。智力大沖浪源程序名.???（,,）可執(zhí)行文件名輸入文件名輸出文件名【問題描述】小偉報名參加中央電視臺的智力大沖浪節(jié)目。本次挑戰(zhàn)賽吸引了眾多參賽者，主持人為了表彰大家的勇氣，先獎勵每個參賽者元。先不要太高興！因為這些錢還不一定都是你的？！接下來主持人宣布了比賽規(guī)則：首先，比賽時間分為個時段(≤)，它又給出了很多小游戲，每個小游戲都必須在規(guī)定期限前完成(≤≤)。如果一個游戲沒能在規(guī)定期限前完成，則要從

4、獎勵費元中扣去一部分錢，為自然數(shù)，不同的游戲扣去的錢是不一樣的。當然，每個游戲本身都很簡單，保證每個參賽者都能在一個時段內完成，而且都必須從整時段開始。主持人只是想考考每個參賽者如何安排組織自己做游戲的順序。作為參賽者，小偉很想贏得冠軍，當然更想贏取最多的錢！注意：比賽絕對不會讓參賽者賠錢!【輸入】輸入文件，共行。第行為，表示一開始獎勵給每位參賽者的錢；第行為，表示有個小游戲；第行有個數(shù)，分別表示游戲到的規(guī)定完成期限；第行有個數(shù)，分別表示游戲到不能在規(guī)定期限前完成的扣款數(shù)?！据敵觥枯敵鑫募?，僅行。表示小偉能贏取最多的錢。【樣例】【算法分析】因為不同的小游戲不

5、能準時完成時具有不同的扣款權數(shù)，而且是最優(yōu)解問題，所以本題很容易就想到了貪心法。貪心的主要思想是要讓扣款數(shù)值大的盡量準時完成。這樣我們就先把這些任務按照扣款的數(shù)目進行排序，把大的排在前面，先進行放置。假如罰款最多的一個任務的完成期限是，我們應該把它安排在哪個時段完成呢?應該放在第個時段，因為放在～任意一個位置，效果都是一樣的。一旦出現(xiàn)一個不可能在規(guī)定時限前完成的任務，則把其扔到最大的一個空時間段，這樣必然是最優(yōu)的，因為不能完成的任務，在任意一個時間段中罰款數(shù)目都是一樣的，具體實現(xiàn)請看下面的參考程序。本題也可以有另外一種貪心算法，即先把所有的數(shù)據(jù)按照結束時間的

6、先后排序，然后從前向后掃描。當掃描到第個時段，發(fā)現(xiàn)里面所分配的任務的結束時間等于，那么就說明在前面這些任務中必須舍棄一個，于是再掃描第～這個時段，挑出一個最小的去掉并累加扣款值，然后再去調整排列順序，讓后面的元素填補前面的空缺，具體實現(xiàn)請看下面的參考程序。取火柴游戲源程序名.???（,,）可執(zhí)行文件名輸入文件名輸出文件名【問題描述】輸入及個整數(shù)，，…，，表示有堆火柴棒，第堆火柴棒的根數(shù)為；接著便是你和計算機取火柴棒的對弈游戲。取的規(guī)則如下：每次可以從一堆中取走若干根火柴，也可以一堆全部取走，但不允許跨堆取，也不允許不取。誰取走最后一根火柴為勝利者。例如：＝，

7、＝＝，代表你，代表計算機，若決定先?。海?)→(){從一堆中取一根}：()→(){從另一堆中取一根}：()→()：()→(){勝利}如果決定后?。海?)→()：()→){勝利}又如＝，，＝，＝，決定后?。海?)→()：()→()已將游戲歸結為()的情況，不管如何取都必勝。編一個程序，在給出初始狀態(tài)之后，判斷是先取必勝還是先取必敗，如果是先取必勝，請輸出第一次該如何取。如果是先取必敗，則輸出“”?！緲永縶表示第一次從第堆取個出來，必勝}{第一次取后的狀態(tài)}【樣例】{先取必敗}【算法分析】從問題的描述分析，可以將問題中的堆火柴棒抽象為個非負整數(shù)，而每取一次火柴

8、棒可抽象為使其中的一個自然數(shù)變小，當所有的數(shù)都變?yōu)闀r