8-1 最大數及最小數找法 8-2 排序 8-3 二元搜尋法 8-4 動態規劃技巧 8-5 計算難題

Slides:



Advertisements
Similar presentations
高三英语有效复习策略 程国学. 一、高考备考的方向把握 1. 认真研究普通高中《英语课程标准》和《福建 省考试说明》关注高考命题原则和发展方向,定 准复习教学起点 1. 认真研究普通高中《英语课程标准》和《福建 省考试说明》关注高考命题原则和发展方向,定 准复习教学起点 一是明确高考英语可能考什么,我们应该怎样准.
Advertisements

考纲研读 语言知识要求 语言运用能力 附录 1: 语音项目表 附录 2: 语法项目表 附录 3: 功能意念项目表 附录 4: 话题项目表 附录 5: 词汇表 听力 阅读 写作 口语.
STR 五环性功能康复术. 技术名称: STR 五环性功能康复术 技术概述: “STR 五环性功能康复术 ” 是目前临床治疗男性功能障碍先进、有效、快 速的疗法。 “STR 五环性功能康复术 ” 是一种先进的治疗体系,集药物治疗、行为治疗、 物理治疗、心理治疗、手术治疗于一体,精确诊断找准病因后,根据患者个体化差异,
100 學年度 勞委會就業學程 國際企業管理學系-物業管理學程介紹. 何謂物業管理? 以台灣物業管理學會 所述,物業管理區分為 「物」、「業」、「人」三區塊。台灣物業管理學會 「物」係指傳統的建物設備、設施 「業」為不動產經營的資產管理 「人」則以生活服務、商業服務為主,並以人為 本位連結物與業,形成今日物業管理三足鼎立新.
變數與函數 大綱 : 對應關係 函數 函數值 顧震宇 台灣數位學習科技股份有限公司. 對應關係 蛋餅飯糰土司漢堡咖啡奶茶 25 元 30 元 25 元 35 元 25 元 20 元 顧震宇 老師 台灣數位學習科技股份有限公司 變數與函數 下表是早餐店價格表的一部分: 蛋餅 飯糰 土司 漢堡 咖啡 奶茶.
图书馆管理实务.
行政命令.
共产党领导的多党合作和政治协商制度: 中国特色的政党制度.
主讲:材料工程学院党总支宣传委员、党务秘书 教工党支部书记 王国志 2015年12月7日
普通高中新课程实验 若干问题 广东省教育厅教研室 吴惟粤 2004年4月29日 广州.
前言 採購程序每一環節所涉及人員,無論是訂定招標文件、招標、審標、決標、訂約、履約管理、驗收及爭議處理,如缺乏品德操守,有可能降低採購效率與品質,影響採購目標之達成,甚有違法圖利情事發生,致阻礙政府政策之推動並損害公共利益。因此,較之一般公務人員,採購人員更需遵循較高標準之道德規範。 主講人:林中財.
欢迎新同学.
2015年新课标高考历史试题分析 暨考试方向研判 李树全 西安市第八十九中学.
课题四 以天池、博斯腾湖 为重点的风景旅游区
“健康的基督徒” 入门.
南台科技大學電子工程系 指導老師:楊榮林 老師 學生姓名:蔡博涵 巨物索餌感測裝置(第II版)
2015年汕头一模质量分析会 34(1)题分析 濠江区河浦中学 詹金锋 34(2)题分析 汕头市实验学校 董友军
士師逐個捉(II) 石建華牧師 24/07/2016.
宣讲数学课程标准 增强课程改革意识.
高考地理全国卷和安徽卷 的对比分析及备考策略
快乐生活,快乐学习 《中国古代诗歌散文欣赏》.
班級經營之再思 香港班級經營學會 黃鳳意
佛法原典研習 五陰誦 (II) 2007/5/13 整理此報告的方式 : 主要節錄 果煜法師說法之重點.
2014年度合肥市中小学生学业质量 绿色指标测试相关情况说明及考务工作要求
普通高中课改方案介绍.
曾一 陈策 重庆大学计算机学院基础科学系 重庆
高三物理后期复习策略 秦皇岛市实验中学 刘苏祥.
理想与现实 有一所大学叫做“社会”,它教会人们奉承比自己强的,挤兑和自己差不多的,欺凌比自己弱的。
101學年度第二學期 呼吸治療學系 師生座談會 102年5月15日.
遞迴關係-爬樓梯.
第七章 机械加工工艺规程的制定.
家庭教育與服務學習.
压缩语段 II.
普通高中课程改革的方案与推进策略 安徽省教育厅 李明阳.
高校人才培养与学科建设的一些探索 徐哲峰 西北大学数学学院 2015年6月30日.
新课程背景下 高中教务主任工作的思考 南京市教学研究室 陆静.
精彩纷呈的 桂剧和彩调 ——桂林地方戏曲赏析.
網路填報系統學生異動轉銜操作及科技化評量6月 成長測驗施測說明
機械工程學系課程地圖 先進材料與精密製造組 設計分析組 校訂共同必修課程 機械系訂 必修課程 組訂 必修課程 畢業專題 工學院訂必修課程
生命轉化 (II) 天父的心 石建華牧師 13/09/2015.
全国高考语文试卷解析 与备考建议 张彬福.
8-1 最大數及最小數找法 8-2 排序 8-3 二元搜尋法 8-4 動態規劃技巧 8-5 計算難題
課程名稱:資料結構 授課老師:_____________
4B冊 認識公倍數和最小公倍數 公倍數和最小公倍數的關係.
Chapter 2 – Chapter 4 Chang Chi-Chung
動態規劃 Dynamic Programming.
Chap3 Linked List 鏈結串列.
Ch 3 Dynamic Programming (動態規劃).
北一女中 資訊選手培訓營.
French Open 2014 A note given in BCC class on June 11, 2014
8-1 最大數及最小數找法 8-2 排序 8-3 二元搜尋法 8-4 動態規劃技巧 8-5 計算難題
第8章 資料排序 資料結構設計與C++程式應用
10949 : Kids in a Grid ★★★★☆ 題組:Problem Set Archive with Online Judge
挑戰C++程式語言 ──第8章 進一步談字元與字串
蕭志明 老師 Algorithm(演算法) Ext:6779
蕭志明 老師 Algorithm(演算法) /FB:
Teacher: 郭育倫 Mail: 演算法 Teacher: 郭育倫 Mail:
程式設計-- Binary Search 通訊一甲 B 楊穎穆.
國民年金 np97006.
陣列與結構.
12797: Letters ★★★☆☆ 題組:Problem Set Archive with Online Judge
資料表示方法 資料儲存單位.
程式設計--Quick Sort 通訊一甲 B 楊穎穆.
本教學投影片係屬教科書著作之延伸,亦受著作權法之保護。
10599: Robots(II) ★★★★☆ 題組:Problem Set Archive with Online Judge
資料結構 老師:李崇明 助教:楊斯竣.
資料結構 老師:李崇明 助教:楊斯竣.
10107: What is the Median? ★★☆☆☆
11621 : Small Factors ★★☆☆☆ 題組:Problem Set Archive with Online Judge
Chapter 16 動態規劃.
Presentation transcript:

8-1 最大數及最小數找法 8-2 排序 8-3 二元搜尋法 8-4 動態規劃技巧 8-5 計算難題 第8章 演算法 8-1 最大數及最小數找法 8-2 排序 8-3 二元搜尋法 8-4 動態規劃技巧 8-5 計算難題

演算法 演算法就是計算機方法,是設計適合計算機執行的方法 演算法常需要好的設計與分析,有時也需要腦筋急轉彎,才能找到好解答 先來個腦筋急轉彎吧 128金幣問題 地獄與天堂問題 十個聰明的囚犯問題

8-1 最大數及最小數找法 請找出16、77、25、85、12、8、36及52裡的最大數 請找出16、77、25、85、12、8、36及52裡的最大數及最小數 請找出16、77、25、85、12、8、36及52裡的最大數及第二大數 前三大數如何做呢?

8-2 排序 排序問題:給定n個數,請將它們由小排到大 排序是電腦經常用到的演算法,資料一旦排序之後,後續尋找便能快速進行 排序的演算法效率差別很大,當資料量變大時,演算法的好壞將影響執行所需時間甚鉅 本章介紹幾個排序法 選擇排序法(selection sort) 插入排序法(insertion sort) 泡沫排序法(bubble sort) 快速排序法(quick sort)

選擇排序法

選擇排序法

插入排序法

插入排序法

泡沫排序法

泡沫排序法

快速排序法

8-3 二元搜尋法 (binary search)

二元搜尋法

8-4 動態規劃技巧 動態規劃技巧有三個主要部份 什麼樣的問題適合用動態規劃技巧來解呢 遞迴關係(recurrence relation) 列表式運算(tabular computation) 路徑迴溯(traceback) 什麼樣的問題適合用動態規劃技巧來解呢 符合最佳化準則,亦即若將最佳答案解構,解構後的子答案仍為對應子問題的最佳解 解題過程中,有許多重複的子問題

費氏數(Fibonacci number)

如何計算 F10? F10 F9 F8 F7 F6 ……

列表式計算 列表式計算可避免重複計算 F0 F1 F2 F3 F4 F5 F6 F7 F8 F9 F10 1 2 3 5 8 13 21 1 2 3 5 8 13 21 34 55

最長共同子序列 子序列就是將一個序列中的一些(可能是零個)字元去掉所得到的序列,例如:pred、sdn、predent等都是 ”president” 的子序列 給定兩序列,最長共同子序列(LCS)問題是決定一個子序列,使得 該子序列是這兩序列的子序列 它的長度是最長的 最長共同子序列不一定是唯一

LCS例題I president providence

LCS例題II a l g o r i t h m a l i g n m e n t

定義遞迴關係式

計算LCS的長度

LCS的長度為6

路徑回溯找出LCS

LCS為priden

8-5 計算難題 有些問題已證明是無解的 NP-Complete 判斷程式是否會停的問題(halting problem) 所有NP-Complete問題,目前都沒有有效的精確解法,而且只要有一個找到有效解法,那所有NP-Complete問題都有有效解法了 許多看似簡單的問題,都已被證明為NP-Complete,例如: 旅行推銷員問題 小偷背包問題