解題策略 貪進法(greedy method)

Slides:



Advertisements
Similar presentations
颐高集团项目中心 海亮地产开发模式研究报告. 目 录 目 录 第四部分:海亮地产高周转模式执行 第二部分:海亮地产高周转模式原因 第三部分:海亮地产高周转模式内涵 第一部分:海亮地产企业背景 第五部分:海亮地产高周转支撑体系.
Advertisements

1 教師敘薪 Q & A 教師敘薪 Q & A 新竹縣立新湖國中 陳淑芬 新竹縣立自強國中 楊美娟
103 學年度縣內介聘申請說明會 南郭國小 教務主任張妙芬.  重要作業日程 : 1 、 5/1( 四 ) 前超額學校 ( 含移撥超額 ) 備文函報縣府教 育處輔導介聘教師名單 2 、 5/7( 三 ) 超額教師積分審查( 9 : : 00 、 13 : : 00 )。 3.
大學甄選申請入學 〃備審資料 〃面試. 確認你的追求對象 學校環境概況 系別特質 有無交換學生 未來出路 性質相似的科系要清楚之間的差別 ex: 社會福利學系,社會工作學系, 社會學系.
人文行動考察 羅東聖母醫院 老人醫療大樓 吳采凌 黃玨宸 劉映姍 陳嫚萱.
焦點 1 陸域生態系. 臺灣的陸域生態系 臺灣四面環海 黑潮通過  高溫, 雨量充沛 熱帶, 亞熱帶氣候.
資源問題與環境保育 第 6 章. 學完本章我能 ……  知道中國土地資源的問題與保育  了解中國水資源的問題與保育  知道中國森林資源的問題與保育  能分析自然環境和人文環境如何影響人類 的生活型態  說舉出全球面臨與關心的課題.
景美樣品房工程變更 / 追加請款 / 說明 102/08/09 樣品房停工 102/10/10 樣品房完工 102/09/26 向工務部提出 追加工程估價單 102/10/25 經工務部審核 轉送採發部門 102/09/03 工地會議 確認後續施工方式 102/11/ /11/ /12/09.
統計之迷思問題 保險 4B 張君翌. 迷思問題及教學者之對策 常見迷思概念教學者之對策 解題的過程重於答案 例 : 全班有 50 位同學,英文不及格的有 15 人,數學不及格的有 19 人,英文與 數學都及格的有 21 人。請問英文與數 學都不及格的有幾人? 老師常使用畫圖來解決這樣的問題,英文和.
看日历.
社團法人台南市癲癇之友協會 講師:王乃央老師
寓言 何謂寓言? 寓言中的主角選擇 以動物為主角,形象分析—以成語及諺語中來歸納動物形象 以人為主角,形象分析
第七章 外營力作用 第一節 風化 第二節 崩壞 第三節 侵蝕與堆積.
物理治療師之僱傭關係 九十二年四月十二日.
勿讓權利睡著- 談車禍之損害賠償與消滅時效.
二、開港前的經濟發展 (一)土地開墾和農業發展 1.漢人移民的遷徙與拓墾 (1)遷徙 A.居住區 a.泉州人最多:沿海
設計新銳能量輔導 實習期中感想 實習生:賴美廷 部落格:TO13004.
日本的〈地獄劇〉 與 中國的〈目連戲〉.
授課教師:羅雅柔 博士 學員:吳沛臻/邱美如/張維庭/黃茹巧
國小教師檢定經驗分享 分享者:胡瑋婷 現職:國語日報語文中心寫作班教師 閱讀寫作營教材編輯及任課講師 榮獲「教育部教育實習績優獎」全國第三名.
民主政治的運作
教育與學習科技學系 103學年度課程說明 103年9月2日.
國有不動產撥、借用法令與實務 財政部國有財產局 接收保管組撥用科 蔡芳宜.
公務人員 育嬰留職停薪權益.
大學教、職員之法義務規範與法律效果 台南地檢署林仲斌.
第三課 政府的組織、功能與權限 一、內閣制 壹、民主國家的政府體制 二、總統制 三、混合制 四、小結 一、前言 貳、我國的中央政府體制
明代開國謀臣 劉伯溫 組員:吳政儒 林天財 王鈴秀 陳冠呈 施典均 李孟儒.
系统简介 理财顾问 业务 是基于通信平台的技术优势,整合《理财周刊》、第一理财网、乾隆集团等合作伙伴提供的理财产品内容和权威的理财专家资源,以集中式呼叫中心为主的服务方式,让普通百姓可以享受到快捷、全面、专业、权威的资讯及投资理财的服务平台。
中央與地方教育權限 第八組 王湘婷 邱淑婷 全 彥 洪英博
中國宦官 鄭永富 鄭雅之 莊尉慈.
盧世欽 律師 鼎禾律師聯合事務所 民國 一○四 年 九 月 十八 日
簡報大綱 壹、親師溝通 貳、學生不當行為的處理 參、學生輔導 肆、個案研討分析.
宦官那些事儿 宦官那些事儿 主讲:小学部李永善 主讲:小学部李永善.
福山國小 100學年度 新生家長始業輔導.
貨物稅稅務法令介紹 竹東稽徵所.
請開喇叭 我的家鄉我的情 2年11班 黃筑筠.
电视教育课 【5】 小学生行为习惯养成教育.
九年一貫課程綱要微調 健康與體育領域召集人 「課綱微調轉化」研習
公私立大學特色介紹 (以第二類組為主) 報告人:吳婉綺.
危險情人的特徵 危險情人的特徵.
宁波爱地房产市场年报 郊五区
機關團體所得稅申報實務 中區國稅局苗栗縣分局第一課林天琴.
幼兒環境學習規畫 期末報告 指導老師:蔡其蓁 老師
雕塑你我他.
財政部臺灣省北區國稅局中壢稽徵所 各類所得扣繳暨免扣繳法令.
「103年寒假教育優先區中小學生營隊」 校外補助計畫申請說明會.
水土保持法中「連續處罰」及「限期改正」制度之法律研究
國有公用財產管理及被占用處理暨活化運用法規與實務(含座談) 104年度教育部暨部屬機關學校總務人員研習會-不動產管理班
Chap5 Graph.
Q101 在701 SDX Linux上的標準安裝與使用程序v2
提升國民小學教師健康教育專業能力三年計畫
Ch 3 Dynamic Programming (動態規劃).
Sān cūn yān jiǔ tái liù tíng.
馬公高中100學年101大學博覽會 專題演講 演講主題 如何選填適合自己的大學科系
性騷擾防治宣導.
小學四年級數學科 8.最大公因數.
創業環境分析與 風險評估 赫斯提亞負責人:謝馥仲先生 主講 演講時間 : 2008/05/01.
葉脈標本的創意製作.
穿出自我… 高一家政.
蕭志明 老師 Algorithm(演算法) Ext:6779
蕭志明 老師 Algorithm(演算法) /FB:
12797: Letters ★★★☆☆ 題組:Problem Set Archive with Online Judge
第一章 貨幣的時間價值.
10328: Coin Toss ★★★☆☆ 題組:Problem Set Archive with Online Judge
程式設計--Quick Sort 通訊一甲 B 楊穎穆.
10599: Robots(II) ★★★★☆ 題組:Problem Set Archive with Online Judge
財政四 徐瑜鴻 財政四 林博硯 財政四 陳玄恩 財政四 王張皓鈞 財政四 李定瑜
品格:熱 性格的培養6親熱就,48頁。 (一)什麼是熱.
Chapter 16 動態規劃.
Presentation transcript:

解題策略 貪進法(greedy method) 綜合目前的情況,並不特別考慮下一階段的狀況下, 以最小的成本(或最大的效益)為原則,找出目前可行 的解答(最後找到的可能不是最佳解答) 概念簡單、效率高,常被用來解決最佳化(最低成本、 最短路徑…)的問題,

解題策略-貪進法 興建哪幾條馬路以連接5個城市&總興建成本最低? B A C D E 馬路興建成本示意圖 一 1 路段編號 成本 四 6 三 2 C 二 7 五 3 七 4 六 5 D E 八 9 馬路興建成本示意圖

解題策略-貪進法 用貪進法找出最低成本的路段組合 選取路段 成本 徒增成本 路段組合 A B C D E B 一 1 否→選取 {一} 三 2 {一、三} 五 3 {一、三、五} 七 4 是→不選 六 5 {一、三、五、六} 四 6 二 7 八 9 一 A 四 三 五 二 C 七 六 D 八 E A B C D E

解題策略Top Down 關鍵字:分解、模組化 分治法(各個擊破法) divide & conquer 找出解決方法(共通的)將問題分解成數個子問題 重複操作(共通的解決方法)解決各個子問題 直到問題解決

Ex: 用各個擊破法,將一串數值由小到大排序 演算法(文字表示法) 1. 以第一個數值為標準值 20,2,52,48,13 用各個擊破法,將一串數值由小到大排序 演算法(文字表示法) 1. 以第一個數值為標準值 2. 將標準值右邊小於標準值的數依次移至標準值最左邊 3. 對標準值左邊的數值重複步驟1、2 4. 對標準值右邊的數值重複步驟1、2 5.重複步驟3~5直到完成排序 標準值左右兩邊即為2個子問題

解題策略-各個擊破法 分 解 擊 破     20 02 52 48 13     02 20   52 48 13  13 02 20  52 48      13 02 20 52 48    02 13 0  20 52 48   02 13 20 52 48    02 13 20 48 52 48 移到最左邊 1 2 左 48 52  52 48 右 02 13  標準值 13 02 4 3

有60個外型一樣的硬幣及一個沒有砝碼的天平 ,現在知道只有一個偽幣和其它的重量不同, 問怎樣稱才能最少次數內就找到那個重量不同 的偽硬。(注意此題並未說明那個硬幣的重量 是輕是重,所以需要仔細考慮) 如果知道偽幣比較輕時,你又會怎麼稱?

只考慮偽幣是輕的 分成三堆20:20:20(秤兩次,取出較輕的那堆 ) 在分成三堆7:7:6(只秤7:7,若相同偽幣在6 ,若不同取輕的7) 在分成三堆3:3 or 3:3:1(只秤3:3,若相 同取得偽幣,若不同取輕的3) 第五次 1:1:1