2019-2020年高中信息技術(shù) 全國青少年奧林匹克聯(lián)賽教案 貪心法.doc
《2019-2020年高中信息技術(shù) 全國青少年奧林匹克聯(lián)賽教案 貪心法.doc》由會員分享，可在線閱讀，更多相關(guān)《2019-2020年高中信息技術(shù) 全國青少年奧林匹克聯(lián)賽教案 貪心法.doc（3頁珍藏版）》請在裝配圖網(wǎng)上搜索。
2019-2020年高中信息技術(shù) 全國青少年奧林匹克聯(lián)賽教案 貪心法 在求最優(yōu)解問題的過程中，依據(jù)某種貪心標(biāo)準(zhǔn)，從問題的初始狀態(tài)出發(fā)，直接去求每一步的最優(yōu)解，通過若干次的貪心選擇，最終得出整個問題的最優(yōu)解，這種求解方法就是貪心算法。 從貪心算法的定義可以看出，貪心法并不是從整體上考慮問題，它所做出的選擇只是在某種意義上的局部最優(yōu)解，而由問題自身的特性決定了該題運(yùn)用貪心算法可以得到最優(yōu)解。 我們看看下面的例子 貪心法應(yīng)用 例1 均分紙牌（NOIPxxtg） [問題描述] 有 N 堆紙牌，編號分別為 1，2，…, N。每堆上有若干張，但紙牌總數(shù)必為 N 的倍數(shù)?？梢栽谌我欢焉先∪舾蓮埣埮疲缓笠苿?。移牌規(guī)則為：在編號為 1 堆上取的紙牌，只能移到編號為 2 的堆上；在編號為 N 的堆上取的紙牌，只能移到編號為 N-1 的堆上；其他堆上取的紙牌，可以移到相鄰左邊或右邊的堆上?，F(xiàn)在要求找出一種移動方法，用最少的移動次數(shù)使每堆上紙牌數(shù)都一樣多。例如 N=4，4 堆紙牌數(shù)分別為： ?、佟??、凇? ③ 17?、堋? 移動3次可達(dá)到目的： 從 ③ 取 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） [輸 出]：輸出至屏幕。格式為：所有堆均達(dá)到相等時的最少移動次數(shù)。 [輸入輸出樣例] a.in： 4 9 8 17 6 屏慕顯示：3 算法分析：設(shè)a[i]為第i堆紙牌的張數(shù)（0<=i<=n），v為均分后每堆紙牌的張數(shù)，s為最小移到次數(shù)。 我們用貪心法，按照從左到右的順序移動紙牌。如第i堆(0下載提示(請認(rèn)真閱讀)
- 1.請仔細(xì)閱讀文檔，確保文檔完整性，對于不預(yù)覽、不比對內(nèi)容而直接下載帶來的問題本站不予受理。
- 2.下載的文檔，不會出現(xiàn)我們的網(wǎng)址水印。
- 3、該文檔所得收入（下載+內(nèi)容+預(yù)覽）歸上傳者、原創(chuàng)作者；如果您是本文檔原作者，請點此認(rèn)領(lǐng)！既往收益都?xì)w您。
文檔包含非法信息？點此舉報后獲取現(xiàn)金獎勵！
下載文檔到電腦，查找使用更方便
9.9 積分
| 下載 |
還剩頁未讀，繼續(xù)閱讀
- 配套講稿：
如PPT文件的首頁顯示word圖標(biāo)，表示該P(yáng)PT已包含配套word講稿。雙擊word圖標(biāo)可打開word文檔。
- 特殊限制：
部分文檔作品中含有的國旗、國徽等圖片，僅作為作品整體效果示例展示，禁止商用。設(shè)計者僅對作品中獨(dú)創(chuàng)性部分享有著作權(quán)。
- 關(guān) 鍵 詞：
- 2019-2020年高中信息技術(shù) 全國青少年奧林匹克聯(lián)賽教案 貪心法 2019 2020 年高 信息技術(shù) 全國青少年 奧林匹克 聯(lián)賽 教案 貪心
裝配圖網(wǎng)所有資源均是用戶自行上傳分享，僅供網(wǎng)友學(xué)習(xí)交流，未經(jīng)上傳用戶書面授權(quán)，請勿作他用。
鏈接地址：http://www.820124.com/p-2589955.html