99高中資訊科選修課程 夥伴學習教師 專業進修研習 進階程式設計--演算法 教學示例與研討

Slides:



Advertisements
Similar presentations
酒店绩效考核攻略 一 业务流程再造 管理环节突破 利润急速倍增 专为您企业量身裁衣服务 突破导师 : 周忠亭副教授 北京大学管理案例研究 中心特聘餐饮讲师 北洋战略研究院研究员 北大时代光华高级讲师 中国十大餐饮管理讲师 中华酒店管理专家教授 教育部首批中国餐饮经理人 师资成员.
Advertisements

人力资源工作总结 行政部 人力资源部年度工作 一方面通过招聘管理、劳动合同管理、 入离职管理等,确保各项人事管理工作 的合法性、规范性. 另一方面通过建立员工培训计划,加强 企业文化的贯彻和渗透,提升员工的凝 聚力和归属感,提升员工的敬业度。
第一节三 怎样实现合理膳食. 饮食与健康 探 究 竟探 究 竟 1. 根据课本后的部分食物营养成分表(附表一),分组将聪聪和明明一天所吃的 食物重量分别换算成糖类、蛋白质、脂肪和钙的重量。 聪聪(女 12 岁)明明(男 13 岁) 鸡 蛋 75g 油 条 200g 牛 奶 250g.
配樂:夢的序曲 ( 鋼琴 ) 雁蕩山因山頂有湖,蘆葦茂密,結草為湯,南歸秋雁多宿於此,故名雁蕩。始於 南北朝,興於唐,盛於宋,雁蕩山來晚了一步,未能在 “ 五岳 ” 中占得一席之地。 沒有金碧輝煌的涂飾,村野之山的雁蕩倒因此多了份瀟灑風神。
《地方名人文化资源网站的建设与应用研究》. 乐至名人 叶 镛 KJ09001 乐至县吴仲良中学 邓祖明.
1. 法律學系助教群: 大學部助教 徐碧霜 行政助教 葉靜芳 研究所助教 阮博謙 台中 法政學院 1. 台北 法商學院 民國 50 年 中興大學合併法商學院法律系 民國 89 年 法商學院改制為台北大學.
第一节 职业基础知识 第二节 社会需要剖析 第三节 用人单位认知
第三章 人力資源規劃 授課教師: 人力資源管理:以合作觀點創造價值 3/e.簡建忠著.前程文化 出版.
Course 1 演算法: 效率、分析與量級 Algorithms: Efficiency, Analysis, and Order
基本概論 Basic concepts.
劳动关系法务-实操篇 规章制度修审与员工手册撰写.
Introduction 基本概念 授課老師:蕭志明
《疯 娘》 --100个人看后99个人会落泪的故事 图文:网络
第 九 章 搜尋(Search) 課程名稱:資料結構 授課老師:_____________.
2015届就业指导课程教学大纲介绍.
税收新政 -2008年度.
創意設計思考 創 新紓壓服務 -Relax Space 指導老師:梁直青 組員 :吳晨維 李嘉萍 江承諺 鄭冠迪 何雨青.
人力资源市场统计工作介绍 人力资源市场与人员调配处 郭俊霞 2014年12月.
数据结构(C语言版) Data Structure
学生培养的过程性评价.
2012年度人力资源部工作总结
简单选择排序.
第八章 查找.
第十章 内部排序 10.1 概述 10.2 插入排序 直接插入排序 其他插入排序 希尔排序
执行《劳动合同法》中 应当注意的十大问题.
C语言基础——指针的高级应用 Week 05.
麻疹的院内感染控制 敦煌市医院院感科 梁荣.
課程名稱:資料結構 授課老師:_____________
第5章 函数与模块化设计 学习目的与要求: 掌握函数的定义及调用方法 理解并掌握参数的传递方法 理解函数的嵌套与递归调用
選擇排序法 通訊一甲 B 楊穎穆.
第九章 排序 概述 插入排序 交换排序 选择排序 归并排序 基数排序 外排序.
排序 Sorting.
快速排序法 (Quick Sort).
第9章 排序.
第十章 排序與搜尋.
第 1 章 演算法分析.
搜尋資料結構 Search Structures.
第七章 搜索结构 静态搜索结构 二叉搜索树 AVL树.
第12章 樹狀搜尋結構 (Search Trees)
程式撰寫流程.
第5章 堆疊(Stacks) 5-1 堆疊的基礎 5-2 堆疊的表示法 5-3 堆疊的應用 - 運算式的計算與轉換
第九章 查找 2018/12/9.
C语言 程序设计基础与试验 刘新国、2012年秋.
重點 資料結構之選定會影響演算法 選擇對的資料結構讓您上天堂 程式.
中央广播电视大学开放教育试点课程 数据结构 辅导教师 倪政林.
第9章 内部排序 9.1 概述 9.2 插入排序 9.3 快速排序 9.4 选择排序 9.5 归并排序 9.6 基数排序
Sorting 排序 Bubble Sort O(n2) Insert Sort Selection Sort Quick Sort
数据结构 Data Structure CSU 主讲人:王国军,郑瑾 中南大学信息院计科系
樹 2 Michael Tsai 2013/3/26.
数据结构 第一章 绪论.
黄土高原的水土流失 标题 水土流失的原因 水土流失的危害 治理措施 参考文献 小组成员.
教 师:曾晓东 电 话: E_mail: 计算机软件技术基础 教 师:曾晓东 电 话: E_mail:
鄧姚文 資料結構 第一章:基本概念 鄧姚文
Week 2: 程式設計概念與 演算法的效能評估
資料結構與C++程式設計進階 排序與搜尋 講師:林業峻 CSIE, NTU 6/ 14, 2010.
第1章 绪论 2019/4/16.
计算机算法基础 周中成 苏州科技学院应用数学系 2019/4/18.
第8章 資料排序 資料結構設計與C++程式應用
数据结构选讲 北京大学 陈瑜希.
資料結構與演算法 第一章 基本概念 徐熊健 資料結構與演算法 徐熊健.
綠色能源.
第九章 排序 概述 插入排序 快速排序 交换排序(起泡排序) 选择排序 归并排序.
演算法時間複雜度 (The Complexity of Algorithms)
講師:郭育倫 第2章 效能分析 講師:郭育倫
演算法的效率分析.
演算法分析 (Analyzing Algorithms)
累堆排序法 (Heap Sort).
算法的基本思想: 第6章 内部排序 6.2 气泡排序 将待排序的记录看作是竖着排列的“气泡”,关键字较小 的记录比较轻,从而要往上浮。
第三章 流程控制 程序的运行流程 选择结构语句 循环结构语句 主讲:李祥 时间:2015年10月.
排序 排序(sorting)是计算机程序设计中的一种重要操作,它的功能是将一个数据元素(或记录)的任意序列,重新排列成一个按关键字有序的序列。 由于待排序的记录数量不同,使得排序过程中涉及的存储器不同,可将排序方法分为两大类:一类是内部排序,指的是待排序记录存放在计算机存储器中进行的排序过程;另一类是外部排序,指的是待排序记录的数量很大,以致内存一次不能容纳全部记录,在排序过程中对外存进行访问的排序过程。
Presentation transcript:

99高中資訊科選修課程 夥伴學習教師 專業進修研習 進階程式設計--演算法 教學示例與研討 報告人 國立鳳新高級中學 林光耀 2010.10

高中資訊科課程架構 進階程式設計 (2學分) 「資訊科技概論」必修2~4學分(生活領域) 「資訊科學」選修0~6學分(非升學科目) 2學分必修:核心知識為主 4學分必修: 核心知識+應用軟體 或/及 基礎程式設計 「資訊科學」選修0~6學分(非升學科目) 基礎程式設計 (1~2學分) 進階程式設計 (2學分) 資訊科學與應用專題 (1~4學分) 其它(可依各校課程特色開設,0~2學分)

99總綱選修科目與學分數 選修

基礎程式設計(選修1~2學分) 一、概論 二、基礎觀念 三、流程控制 四、陣列 五、模組化程式設計※ 1.程式設計簡介 2.程式設計工具 1.程式設計簡介 2.程式設計工具 2~4 二、基礎觀念 1.常數與變數 2.基本輸入輸出 3.運算式與指定敍述 4.內建函式※ 4~6 三、流程控制 1.選擇敘述 2.重複敘述 8~14 四、陣列 1.一維陣列 2.多維陣列※ 2~8 五、模組化程式設計※ 1.副程式※ 2.程式庫※ 0~6

四、演算法 進階程式設計(選修2學分) 一、模組化程式設計 二、進階資料型態 三、資料結構 1.排序演算法 2.搜尋演算法 1.副程式 2.程式庫 6~10 二、進階資料型態 1.陣列 2.資料錄 3.指標※ 8~12 三、資料結構 1.佇列 2.堆疊 3.鏈結串列 4.樹狀結構※ 5.集合※ 10~12 四、演算法 1.排序演算法 2.搜尋演算法

單元摘要 本主題旨在介紹常用的演算法,以及如何針對演算法進行效能分析。 授課重點應強調演算法垂直式邏輯思考的精神,以及循序漸進的解題流程,並搭配日常生活實例進行教學。 先備知識 1.必修科目「資訊科技概論」 2.選修科目「基礎程式設計」

課綱範圍 1.排序演算法 約 7HR 2.搜尋演算法 約 5HR 1-1 排序演算法用途 1-2 泡沫排序演算法 1-3 選擇排序演算法 1-4 快速排序演算法※ 1-5 排序演算法效能分析※ 2.搜尋演算法 2-1 搜尋演算法用途 2-2 循序搜尋演算法 2-3 二分搜尋演算法 2-4 搜尋演算法效能分析 約 7HR 約 5HR

學習目標 能分別說明各式常見排序演算法的功能,及其在程式設計中的使用時機。 能說明並比較各式排序演算法的差異。 能利用複雜度分析方法,分析各式排序演算法的效能。 能分別說明各式常見搜尋演算法的功能,及其在程式設計中的使用時機。 能說明並比較各式搜尋演算法的差異。 能利用複雜度分析方法,分析各式搜尋演算法的效能。

第一堂課:排序介紹 一、排序介紹 二、排序演算法分析 1.何謂排序(Sorting)? 2.內部排序 VS 外部排序 1.穩定度 2.時間複雜度 VS 空間複雜度

排序(Sorting) 是指將一群資料,依照特定規則調整位置順序,使資料具有某種次序。 目的在使資料隨著特定順序排列組合。 如班級成績資料,可以使用每個學生的總成績、總平均、名次或座號順序等排列方式,將資料由大至小或是由小至大來排列。 內部排序:排序的資料量小,可以完全在記憶體內進行排序。內部排序法有:泡沫排序法、選擇排序法、快速排序法等。 外部排序:排序的資料量無法直接在記憶體內進行排序,而必須使用到輔助記憶體。外部排序法有:直接合併排序法、堆積合併排序法等。(※)

直接移動 VS 邏輯移動 「直接移動」是直接交換儲存資料的位置。 如圖示。 「邏輯移動」並不會移動資料儲存位置,僅改變指向這些資料的輔助指標的值。 如圖示。

排序穩定度 穩定排序(Stable Sort)是指資料在經過排序後,兩個相同鍵值的記錄仍然保持原來的次序。 舉例說明:如下例中,8左的原始位置本來在8右的左邊(所謂8左及8右是指相同鍵值一個在左,一個在右。),穩定排序後8左仍應在8右的左邊,不穩定排序則有可能8左會跑到8右的右邊去。 原始資料順序: 8左 6 9 8右 7 穩定的排序: 6 7 8左 8右 9 不穩定的排序: 6 7 8右 8左 9

時間複雜度 VS 空間複雜度 時間複雜度(Time complexity): 1.可分為最好情況(Best Case)、最壞情況(Worst Case)及 平均情況(Average Case)。 2.最好情況就是資料已完成排序。例如:原本資料已經完成 遞增(由小至大)排序,如果再進行一次遞增排序所使用的 時間複雜度就是最好情況。 3.最壞情況是指每一鍵值均須重新排列。例如:原本為遞增 排序重新排序成為遞減(由大至小),就是最壞情況。 空間複雜度(Space complexity): 1.指演算法在執行過程所需付出的額外記憶體空間。 2.排序法所使用到的額外空間愈少,空間複雜度就愈佳。 3.例如泡沫排序法在排序過程中僅用到一個額外空間,在所 有的排序演算法中,這樣的空間複雜度就算是最佳情況。

第二堂課:泡沫排序法介紹 1.排序原理: 泡沫排序演算法,又稱為氣泡排序法或交換排序法。是由觀察水中氣泡大小會隨著水深高度壓力變化演進而成。 泡沫排序法的比較方式是由第一個元素開始,比較2個相鄰元素大小,若大小順序有誤,則立即對調,對調後再進行下一個元素的比較。 2.教師舉例:(以五筆隨機資料,用泡沫排序法表示演算法過程。) 例題:「26,5,37,1,61」。結果:「1,5,26,37,61」。 3.學生練習:(可隨機挑選若干位同學,以座號上台操作演練。) 例題:數列「23,36,5,14,9」(隨機挑選同學座號,各班可能不同。)若經由泡沫排序法由小到大的順序排序,過程及結果為何? 隨機挑選若干張撲克牌,由學生(可分組進行)操作泡沫排序法由小到大,互相觀察排序過程。

第三堂課:泡沫排序法程式 程式參考示例與練習:(重點解說) void Bubble_Sort(int n, int *Data) { /* N筆資料儲存於Data[0]….Data[n-1]中 */ int i, j, temp; for (i=0;i<n-1;i++) { for(j=0;j<n-i;j++) { if (Data[j+1]<Data[j]) { temp=Data[j]; Data[j]=Data[j+1]; Data[j+1]=temp; /* 交換資料 swap */ } } printf("第 %d 次排序後的結果:",i+1); ShowData(6,Data); /* 列印每次排序後的資料 */ }

第四堂課:選擇排序法介紹 1.排序原理: 2.教師舉例:(同「26,5,37,1,61」例,用選擇排序法表示過程。) 選擇排序法可使用兩種方式排序,一為在所有的資料中,當由大至小排序,則將最大值放入第一位置;若由小至大排序時,則將最大值放入位置末端。 選擇排序法分析: 1.不是穩定排序法。 2.時間複雜度為O(n2)。 3.只需一個額外的空間,所以空間複雜度為最佳。 4.適用於資料量小或有部份資料已經過排序者。 2.教師舉例:(同「26,5,37,1,61」例,用選擇排序法表示過程。) 3.學生練習:(可隨機挑選若干位同學,以座號上台操作演練。) 例題:隨機挑選同學座號,形成數列「33,17,6,24,9」,經由選擇排序法由小到大的順序排序,過程及結果為何? 隨機挑選若干張撲克牌,由學生(可分組進行)操作選擇排序法由小到大,互相觀察排序過程。

第五堂課:選擇排序法程式 程式參考示例與練習:(重點解說) void Select_Sort(int n, int *Data) { /* N筆資料儲存於Data[0]...Data[n-1]中 */ int i,j,k,temp; for (i=0;i<n-1;i++) { k=i; /* 掃瞄n-1次 */ for(j=i+1;j<n;j++) if(Data[j]<Data[k]) k=j; /* 尋找最小鍵值資料 */ if(i!=k) /*交換資料 swap*/ {temp=Data[i]; Data[i]=Data[k];Data[k]=temp;} /* 使此次掃瞄的最小鍵值資料擺在最前面 */ printf("第 %d 次排序後的結果:",i+1); ShowData(n,Data); } }

第六堂課:快速排序法介紹 1.排序原理: 快速排序法又稱分割交換排序法,是目前公認最佳的排序法。假設有n筆記錄R1,R2,R3,…,Rn,其鍵值分別為k1,k2,k3,…,kn。快速排序法的步驟如下: (1)取K為第一筆鍵值。 (2)由左向右找出一個鍵值Ki使得Ki>K。 (3)由右向左找出一個鍵值Kj使得Kj<K。 (4)若i<j則Ki與Kj交換,並繼續步驟(2)的執行。 (5)若ij則將K與Kj交換,並以j為基準點將資料分為左右兩部份。 (6)以遞迴方式分別為左右兩半繼續分別進行排序,直至完成排序。 快速排序法分析: 1.快速排序法不是穩定排序法。 2.時間複雜度:最快及平均為O(nlog2n),最壞為O(n2)。 3.空間複雜度:最差情況為O(n),最佳情況為O(log2n)。 4.快速排序法是平均執行時間最快的排序法。

第六堂課:快速排序法介紹 2.教師舉例: 可利用以上過程,將左半部與右半部分別排序,形成遞迴,至於排序過程如下:

第七堂課:快速排序法程式 程式參考示例與練習:(重點解說) void q_sort(int *data,int m,int n) { int k,temp,i,j; /* 分割元素 */ if(m<n) /* 是否繼續分割 */ { i = m; /* 分割的最左 */ j = n + 1; /* 分割的最右 */ k = data[m]; /* 取第一個元素 */ do { do /* 由左往右找 */ { i++; } while(data[i]<k); do /* 由右往左找 */ { j--; } while(data[j]>k); if (i<j) /*交換資料*/ { temp=data[i]; data[i]=data[j]; data[j]=temp; } } while(i<j); temp=data[m]; data[m]=data[j]; data[j]=temp; /*交換資料*/ printf("過程輸出: "); for (i=m;i<=n;i++) /*列印過程*/ printf("%3d",data[i]); printf("\n"); q_sort(data,m,j-1); q_sort(data,j+1,n);/*快速排序遞迴呼叫*/ } }

第八堂課:搜尋介紹 一、搜尋介紹 二、常見的搜尋方法 三、循序搜尋演算法介紹 1.何謂搜尋(Search)? 2.靜態搜尋 VS 動態搜尋 1.循序搜尋法。(適合未經排序整理的資料) 2.二元搜尋法。(適合已經排序整理的資料) 3.其他:如內插搜尋法、費氏搜尋法。(斟酌補充※) 三、循序搜尋演算法介紹 1.搜尋原理 2.效能分析

第八堂課:搜尋介紹 靜態搜尋 VS 動態搜尋 1.靜態搜尋:指在搜尋過程中,該資料不會有增加、刪除、或更新等行為。例如符號表搜尋。 2.動態搜尋:指所搜尋的資料,在搜尋過程中會經常性增加、刪除、或更新。例如B-tree搜尋。 內部搜尋 VS 外部搜尋 1.內部搜尋:資料量較小的檔案,可以直接全部載入記憶體中進行搜尋。 2.外部搜尋:資料量大的檔案,無法一次載入記憶體處理,而需使用到輔助記憶體來分次處理。

第八堂課:循序搜尋法介紹 循序搜尋法: 1.又稱為線性搜尋法,是一種最簡單的搜尋法。 2.優點是資料在搜尋之前不需要作任何的前置處理或排 序,缺點為搜尋速度較慢。 3.因此在平均狀況下,循序搜尋法搜尋一筆資料大約需 要(n+1)/2的比較次數。 循序搜尋法分析: 1.時間複雜度:如果資料沒有重覆,找到資料就可中止 搜尋的話,在最差狀況是未找到資料,需作n次比較, 時間複雜度為O(n)。 2.當資料量很大時,不適合使用循序搜尋法。但如果預 估所搜尋的資料在檔案前端則可以減少搜尋的時間。

第九堂課:循序搜尋法程式 程式參考示例與練習:(重點解說) int search(int *data, int n, int key) { /* 資料比對的部分 */ int i; for(i=0; i<n; i++) /* 循序比對資料 */ if(data[i]==key) return i; /*找到傳回第i筆*/ return n; } /* 沒找到資料 */

第十堂課:二分搜尋法介紹 二分搜尋法原理: 將已排序的資料分割成兩等份,再比較鍵值與中間值,如果鍵值小於中間值,可確定要找的資料在前半段,否則在後半部。如此分割數次直到找到或確定找不到(不存在)為止。 二分法分析: 1.時間複雜度:因為每次搜尋都會比上一次少一半的範圍, 最多約只需要比較[log2n]+1,時間複雜度為O(log2n)。 2.二分法必須事先經過排序,且資料量必須能直接在記憶體 中執行。適合用於不需增刪的靜態資料。 舉例說明: 學生練習: 隨機挑選若干張撲克牌,由學生(可分組進行)先操作排序法(演算法不拘)由小到大,再使用二分搜尋法找出指定的牌並互相觀察操作過程。

第十堂課:二分搜尋法介紹 舉例說明: 例如以下已排序數列 2、3、5、8、9、11、12、16、18 ,而所要搜尋值為11時: (1)首先跟第五個數值9比較: (2)因11>9,故和後半部的中間值(第七個數值)12比較: (3)因11<12,故和前半部的中間值(第六個數值)11比較: (4)因為11=11,表示搜尋完成,如果不相等則表示找不到。 9 12

第11堂課:二分搜尋法程式 程式參考示例與練習:(重點解說) int binary(int *k, int n, int key) { int u, l, m; u=n; l=0; while(u>=l) { /*資料比對的迴圈部分*/ m=(u+l)/2; if(k[m]==key) return m; else if(k[m]<key) l=m+1; else u=m-1; } return -1; }

第12堂課:搜尋法分析 一、搜尋演算法程式改進討論: 二、搜尋演算法效能分析: 三、結論: 1.循序搜尋演算法: 2.二分搜尋演算法: (1)無須事先排序。 (2)最好情形為1次。最差情形為n次(找不到)。 (3)與其資料項數成正比,時間複雜度為O(n)。 2.二分搜尋演算法: (1)須事先排序。 (2)最好情形為1次。最差情形為(log2n)+1次。 (3)時間複雜度為O(log2n)。 三、結論: 任何搜尋演算法:時間複雜度≦O(n)

結語 高中資訊課程重視資訊科學基本概念 除必修2學分外,具充分開課彈性 教學方法強調理論與實務並重 重視學生對重要概念的理解 九年一貫電腦課程著重資訊科技應用 除必修2學分外,具充分開課彈性 資訊科技概論 + 程式設計、應用軟體、專題 教學方法強調理論與實務並重 由實作中學習基本概念 重視學生對重要概念的理解 非細節、片段知識之記憶 培養學生對資訊科學的興趣為最重要目標

問題討論 vs 經驗分享 幸福不只是傳說, 學生快樂學習,教師歡喜授課。 你我都能做得到! 謝謝各位指教