《2019-2020年高中信息技術(shù) 全國青少年奧林匹克聯(lián)賽教案 貪心法.doc》由會員分享，可在線閱讀，更多相關《2019-2020年高中信息技術(shù) 全國青少年奧林匹克聯(lián)賽教案 貪心法.doc（3頁珍藏版）》請在裝配圖網(wǎng)上搜索。
2019-2020年高中信息技術(shù) 全國青少年奧林匹克聯(lián)賽教案 貪心法
在求最優(yōu)解問題的過程中，依據(jù)某種貪心標準，從問題的初始狀態(tài)出發(fā)，直接去求每一步的最優(yōu)解，通過若干次的貪心選擇，最終得出整個問題的最優(yōu)解，這種求解方法就是貪心算法。
從貪心算法的定義可以看出，貪心法并不是從整體上考慮問題，它所做出的選擇只是在某種意義上的局部最優(yōu)解，而由問題自身的特性決定了該題運用貪心算法可以得到最優(yōu)解。
我們看看下面的例子
貪心法應用
例1 均分紙牌（NOIPxxtg）
[問題描述] 有 N 堆紙牌，編號分別為 1，2，…, N。每堆上有若干張，但紙牌總數(shù)必為 N 的倍數(shù)?？梢栽谌我欢焉先∪舾蓮埣埮?，然后移動。移牌規(guī)則為：在編號為 1 堆上取的紙牌，只能移到編號為 2 的堆上；在編號為 N 的堆上取的紙牌，只能移到編號為 N-1 的堆上；其他堆上取的紙牌，可以移到相鄰左邊或右邊的堆上?，F(xiàn)在要求找出一種移動方法，用最少的移動次數(shù)使每堆上紙牌數(shù)都一樣多。例如 N=4，4 堆紙牌數(shù)分別為：
?、佟? ② 8?、邸?7?、堋?
移動3次可達到目的：
從 ③ 取 4 張牌放到 ④ （9 8 13 10） -> 從 ③ 取 3 張牌放到 ②（9 11 10 10）-> 從 ② 取 1 張牌放到①（10 10 10 10）。
[輸 入]：鍵盤輸入文件名。
文件格式：N（N 堆紙牌，1 <= N <= 100）
A1 A2 … An （N 堆紙牌，每堆紙牌初始數(shù)，l<= Ai <=10000）
[輸 出]：輸出至屏幕。格式為：所有堆均達到相等時的最少移動次數(shù)。
[輸入輸出樣例]
a.in：
4
9 8 17 6
屏慕顯示：3
算法分析：設a[i]為第i堆紙牌的張數(shù)（0<=i<=n），v為均分后每堆紙牌的張數(shù)，s為最小移到次數(shù)。
我們用貪心法，按照從左到右的順序移動紙牌。如第i堆(0
v，則將a[i]-v張紙牌從第I堆移動到第I+1堆；
（2） 若a[i]v then {貪心選擇}
begin
inc(s);{移牌步數(shù)計數(shù)}
a[i+1]:=a[i+1]+a[i]-v;{使第i堆牌數(shù)為v}
end;{then}
writeln(s);
end.
利用貪心算法解題，需要解決兩個問題：
一是問題是否適合用貪心法求解。我們看一個找?guī)诺睦?如果一個貨幣系統(tǒng)有3種幣值,面值分別為一角、五分和一分，求最小找?guī)艛?shù)時，可以用貪心法求解；如果將這三種幣值改為一角一分、五分和一分，就不能使用貪心法求解。用貪心法解題很方便，但它的適用范圍很小，判斷一個問題是否適合用貪心法求解，目前還沒有一個通用的方法，在信息學競賽中，需要憑個人的經(jīng)驗來判斷何時該使用貪心算法。
二是確定了可以用貪心算法之后，如何選擇一個貪心標準，才能保證得到問題的最優(yōu)解。在選擇貪心標準時，我們要對所選的貪心標準進行驗證才能使用，不要被表面上看似正確的貪心標準所迷惑，如下面的列子。
例2 （NOIPxxtg）設有n個正整數(shù)，將他們連接成一排，組成一個最大的多位整數(shù)。例如:n=3時，3個整數(shù)13,312,343,連成的最大整數(shù)為:34331213
又如:n=4時,4個整數(shù)7,13,4,246連接成的最大整數(shù)為7424613
輸入：N
N個數(shù)
輸出:連接成的多位數(shù)
算法分析：此題很容易想到使用貪心法，在考試時有很多同學把整數(shù)按從大到小的順序連接起來，測試題目的例子也都符合，但最后測試的結(jié)果卻不全對。按這種貪心標準，我們很容易找到反例：12，121 應該組成12121而非12112,那么是不是相互包含的時候就從小到大呢？也不一定，如：12，123 就是12312而非12112,這樣情況就有很多種了。是不是此題不能用貪心法呢？
其實此題是可以用貪心法來求解，只是剛才的貪心標準不對，正確的貪心標準是：先把整數(shù)化成字符串，然后再比較a+b和b+a，如果a+b>b+a，就把a排在b的前面，反之則把a排在b的后面。
源程序：
var
s:array[1..20] of string;
t:string;i,j,k,n:longint;
begin
readln(n);
for i:=1 to n do begin
read(k);
str(k,s[i]);
end;
for i:=1 to n-1 do
for j:=i+1 to n do
if s[i]+s[j]
下載提示(請認真閱讀)
- 1.請仔細閱讀文檔，確保文檔完整性，對于不預覽、不比對內(nèi)容而直接下載帶來的問題本站不予受理。
- 2.下載的文檔，不會出現(xiàn)我們的網(wǎng)址水印。
- 3、該文檔所得收入（下載+內(nèi)容+預覽）歸上傳者、原創(chuàng)作者；如果您是本文檔原作者，請點此認領！既往收益都歸您。
文檔包含非法信息？點此舉報后獲取現(xiàn)金獎勵！
下載文檔到電腦，查找使用更方便
9.9
積分
- 配套講稿：
如PPT文件的首頁顯示word圖標，表示該PPT已包含配套word講稿。雙擊word圖標可打開word文檔。
- 特殊限制：
部分文檔作品中含有的國旗、國徽等圖片，僅作為作品整體效果示例展示，禁止商用。設計者僅對作品中獨創(chuàng)性部分享有著作權(quán)。
- 關 鍵 詞：
-
2019-2020年高中信息技術(shù)
全國青少年奧林匹克聯(lián)賽教案
貪心法
2019
2020
年高
信息技術(shù)
全國青少年
奧林匹克
聯(lián)賽
教案
貪心
- 溫馨提示:
1: 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2: 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3.本站RAR壓縮包中若帶圖紙，網(wǎng)頁內(nèi)容里面會有圖紙預覽，若沒有圖紙預覽就沒有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 裝配圖網(wǎng)僅提供信息存儲空間，僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理，對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對任何下載內(nèi)容負責。
6. 下載文件中如有侵權(quán)或不適當內(nèi)容，請與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
裝配圖網(wǎng)所有資源均是用戶自行上傳分享，僅供網(wǎng)友學習交流，未經(jīng)上傳用戶書面授權(quán)，請勿作他用。
2019-2020年高中信息技術(shù) 全國青少年奧林匹克聯(lián)賽教案 貪心法.doc
鏈接地址：http://www.820124.com/p-2589955.html