親愛的老師您好 感謝您選用本書作為授課教材,博碩文化準備本書精選簡報檔,特別摘錄重點提供給您授課專用。 說明: 博碩文化:

Slides:



Advertisements
Similar presentations
While 迴圈 - 不知重複執行次數
Advertisements

CSIM, PU C Language Introduction to the C Programming Language 重覆敘述 (for,while,break,continue) 適合重複性的計算或判斷.
河內塔(Hanoi)問題.
基本概論 Basic concepts.
Introduction 基本概念 授課老師:蕭志明
第一章 資料結構導論 1-1 資料結構簡介 1-2 認識程式設計 1-3 演算法效能分析 1-4 物件導向程式設計與Java.
每节一经典 用系统的观点观察问题 总体设计,逐步求精 计算机科学学院 王小明 (博士/教授/博士生导师)
计算学科的基本问题 本章首先介绍一个对问题进行抽象的典型实例——哥尼斯堡七桥问题。然后,通过“梵天塔”问题和“停机问题”分别介绍学科中的可计算问题和不可计算问题。从“梵天塔”问题再引出算法复杂性中的难解性问题、P类问题和NP类问题,证比求易算法,P=NP是否成立的问题。
计算机三级考试C语言上机试题专题.
“八皇后”问题 崔萌萌 吕金华.
请将手机调整到静音状态 实验网站:program3.ccshu.net 资源网站:class.ccshu.org/ /
C语言程序设计 第八章 函数.
第一章 程序设计入门.
第5章 函数与模块化设计 学习目的与要求: 掌握函数的定义及调用方法 理解并掌握参数的传递方法 理解函数的嵌套与递归调用
C语言程序设计 课程 第5章 数组 主讲:李祥 博士、副教授 单位:软件学院软件工程系.
高级语言程序设计 主讲人:陈玉华.
第一章 C语言概述.
循环结构又称为重复结构:用来处理需要重复处理的问题,它是程序中一种很重要的结构。
Do.For.While.正三角.倒正三角.倒九九乘法表
選擇排序法 通訊一甲 B 楊穎穆.
C的發展史 C程式初體驗 C程式設計基本注意事項 上機實習課程
函數(一) 自訂函數、遞迴函數 綠園.
第3章 顺序结构程序设计 本章要点: 格式化输出函数──printf() 格式输入函数——scanf() 字符输出函数——putchar()
Chap 10 函数与程序结构 10.1 函数的组织 10.2 递归函数 10.3 宏定义 10.4 编译预处理.
If … else 選擇結構 P27.
Chap 2 用C语言编写程序 2.1 在屏幕上显示 Hello World! 2.2 求华氏温度 100°F 对应的摄氏温度
STRUCTURE 授課:ANT 日期:2010/5/12.
第七章 函数 目录 有参的加法函数的开发 函数定义的一般形式 函数参数和函数的值 函数的调用
计算概论 第十八讲 C语言高级编程 结构与习题课 北京大学信息学院.
程式撰寫流程.
第八章 函数.
第5章 堆疊(Stacks) 5-1 堆疊的基礎 5-2 堆疊的表示法 5-3 堆疊的應用 - 運算式的計算與轉換
Introduction to the C Programming Language
CHAP13 演算法概論 高中資訊科技概論 松崗圖書公司.
C语言 程序设计基础与试验 刘新国、2012年秋.
第三章 栈和队列 3.1 栈 3.2 栈的应用举例 3.3 栈与递归的实现 3.4 队列.
本章中將會更詳細地考慮有關重複的概念,並且會 介紹for和do…while等兩種用來控制重複的敘述 式。 也將會介紹switch多重選擇敘述式。 我們會討論直接和迅速離開某種控制敘述式的 break敘述式,以及用來跳過重複敘述式本體剩餘 部份的continue敘述式。 本章會討論用來組合控制條件的邏輯運算子,最後.
計數式重複敘述 for 迴圈 P
C Programming in Action
东北林业大学 陈宇 ACM程序设计 东北林业大学 陈宇
第5讲 结构化程序设计(Part II) 周水庚 2018年10月11日.
第4章 顺序程序设计.
Week 2: 程式設計概念與 演算法的效能評估
C语言概述 第一章.
第1章 绪论 2019/4/16.
计算机算法基础 周中成 苏州科技学院应用数学系 2019/4/18.
資料結構與演算法 第一章 基本概念 徐熊健 資料結構與演算法 徐熊健.
C程序设计.
Main() { Dfas Asdfasf fasdfa } #include <stdio.h> void main( ) {
函数 概述 模块化程序设计 基本思想:将一个大的程序按功能分割成一些小模块, 特点: 开发方法: 自上向下,逐步分解,分而治之
函式庫補充資料.
指標
第1章 绪论(二) 教学目标 理解算法的特性及评价标准 掌握算法时间复杂度和空间复杂度的分析方法 1/
Chap 5 函数 5.1 计算圆柱体积 5.2 使用函数编写程序 5.3 变量与函数.
7.1 C程序的结构 7.2 作用域和作用域规则 7.3 存储属性和生存期 7.4 变量的初始化
資料結構與C++程式設計進階 遞迴(Recursion) 講師:林業峻 CSIE, NTU 6/ 17, 2010.
项目1 C程序设计起步 学习目标: 通过该项目你可以知道: C语言的用途。 C语言的基本符号和关键字。 C语言程序的结构及特点。
資料結構簡介 綠園.
演算法的效率分析.
Introduction to the C Programming Language
問題解決與流程圖 高慧君 台北市立南港高中 2006年12月22日.
本节内容 函数嵌套调用的内存布局 视频提供:昆山爱达人信息技术有限公司 官网地址: 联系QQ: QQ交流群 : 联系电话:
程序设计基础.
程式設計--linear search 通訊一甲 B 楊穎穆.
遞迴 Recursion.
C/C++基礎程式設計班 陣列 講師:林業峻 CSIE, NTU 3/14, 2015.
第三章 流程控制 程序的运行流程 选择结构语句 循环结构语句 主讲:李祥 时间:2015年10月.
本节内容 指针类型 视频提供:昆山爱达人信息技术有限公司 官网地址: 联系QQ: QQ交流群 : 联系电话:
函式庫補充資料 1.
隨機函數.
Presentation transcript:

親愛的老師您好 感謝您選用本書作為授課教材,博碩文化準備本書精選簡報檔,特別摘錄重點提供給您授課專用。 說明: 博碩文化: 1、本教具為非賣品,不得作為商業之用。 2、本教具僅授權使用原著作為授課教材之教師作為教學或研究等學術用途。 3、本教具未授權提供學生任何拷貝、影印、引用、翻印等行為。 4、教師若需申請網站或內容授權,可透過您的博碩業務協助處理,謝謝。 博碩文化: 總公司:台北縣汐止市新台五路一段94號6樓A棟 電話:(02) 2696-2869 分機 313 傳真:(02) 2696-2867 網址:www.drmaster.com.tw 客服信箱:school@drmaster.com.tw 出書提案信箱 schoolbook@drmaster.com.tw

資料結構 請老師填入姓名主講 課本:圖解資料結構 博碩文化出版發行

第一章 資料結構導論 課前指引 資料結構科學可稱得上是近十幾年來蓬勃興起的一門新興科學,他的研究重點是在電腦程式設計領域中,如何將電腦中相關資料的組合,以某種方式組織而成,然後在這樣的定義下,就可以談討各種有意義的操作與關係,藉以提升程式設計上的執行績效。

章節大綱 1-1 資料結構簡介 1-5 遞迴演算法 1-2 資料抽象化 1-6 程式效能分析 1-3 演算法與程式設計 1-4 程式設計的風格 備註:可依進度點選小節

1-1 資料結構簡介 資料結構的應用 樹狀結構 最短路徑 搜尋理論 1-1 資料結構簡介 資料結構的應用 樹狀結構 一種相當重要的非線性資料結構,廣泛運用在如人類社會的族譜或是機關組織、計算機上的MS-DOS和Unix作業系統、平面繪圖應用、遊戲設計等 最短路徑 功用是在眾多不同的路徑中,找尋行經距離最短、或者所花費成本最少的路徑,如都市運輸系統、鐵道運輸系統、通信網路系統等。 搜尋理論 是一種自動從網際網路的眾多網站中蒐集資訊,經過一定整理後,提供給使用者進行查詢的系統,例如Yahoo、Google、蕃薯藤等。

1-1 資料結構簡介 演算法(1/2) 輸入(Input) 有效性(Effectiveness) 明確性(Definiteness) 1-1 資料結構簡介 演算法(1/2) 輸入(Input) 在演算法的處理過程中,通常所輸入資料可有可無,零或一個以上都可以。 有效性(Effectiveness) 每個步驟都可正確執行,即使交給不同的人用手動來計算,也能達成相同效果。 明確性(Definiteness) 每一個步驟或指令必須要敘述的十分明確清楚,不可以模糊不清來造成混淆。

1-1 資料結構簡介 演算法(2/2) 有限性(Finiteness) 輸出(Output) 1-1 資料結構簡介 演算法(2/2) 有限性(Finiteness) 演算法一定在有限步驟後會結束,不會產生無窮迴路,這是相當重要的基本原則。 輸出(Output) 至少會有一個輸出結果,不可以沒有輸出結果。

1-1 資料結構簡介 演算法描述工具(1/5) 流程圖 流程圖的繪製方向應由上至下,由左至右。

1-1 資料結構簡介 演算法描述工具(2/5) 虛擬語言 是一種接近高階程式語言寫法的語言,不過不能直接放進電腦中執行。 1-1 資料結構簡介 演算法描述工具(2/5) 虛擬語言 是一種接近高階程式語言寫法的語言,不過不能直接放進電腦中執行。 以下是利用輾轉相除法求整數m與n的SPARKS遞迴演算法 Procedure GCD(m,n) if n=0 then return (m) else return (GCD(n,m mod n)) endif end

1-1 資料結構簡介 演算法描述工具(3/5) 圖形 如陣列、樹狀圖、矩陣圖等,以下是是井字遊戲的某個決策區域,利用決策樹圖形來表示其演算法:

1-1 資料結構簡介 演算法描述工具(4/5) 敘述表示法 演算法如下: 1-1 資料結構簡介 演算法描述工具(4/5) 敘述表示法 演算法如下: 1.I=1,2,…5循序輸入Student-Name(I)、Chinese(I)、Math(I)、English(I)。 2.計算Average(I)=(Chinese(I)+Math(I)+English(I))/3 3.印出Average(I)及Student-Name(I) 4.如果Average(I)>60,則加印“這位同學的平均分數是及格”。 5.結束

1-1 資料結構簡介 演算法描述工具(5/5) 程式語言 以下演算法是以C/C++語言來計算所輸入兩數x、y的xy值函數Pow(): 1-1 資料結構簡介 演算法描述工具(5/5) 程式語言 以下演算法是以C/C++語言來計算所輸入兩數x、y的xy值函數Pow(): float Pow( float x, int y ) { float p = 1; int i; for( i = 1; i <= y; i++ ) p *= x;   return p; }

1-2 資料抽象化 基本資料型態 如果基本資料型態更高一層,是指一個資料型態包含其他的資料型態,稱為延伸型資料型態(Derived Data Type),或組合資料型態。 例如C中的結構(structure)型態,或C++中的字串(string)或類別(class)型態。

1-2 資料抽象化 抽象資料型態 如果是一種自訂資料型態,可簡化一個資料型態的表現方式及操作運算,並提供使用者以預定的方式來使用這個資料型態。 堆疊(Stack)或佇列(Queue),就是很典型的ADT 堆疊的運作圖示

1-3 演算法與程式設計 認識程式設計(1/2) 需求與目的 設計與規劃 分析與討論 了解程式所要解決的問題,並搜集相關的輸入資訊與期望得到的輸出結果。 設計與規劃 根據撰寫此程式的目的、程式的使用者、滿足需求的軟硬體環境等,來著手設計這個程式演算法的描述。 分析與討論 思考其他可能適合的演算法及資料結構,最後再選出最適當的標的,還必須考慮到可讀性、穩定性及可維護性等因素。

1-3 演算法與程式設計 認識程式設計(2/2) 撰寫與編輯 測試與偵錯 事先必須選擇所需的程式語言,再依據演算法來繪製流程圖,最後進行程式碼的撰寫。 測試與偵錯 最後必需確認程式的輸出是否符合需求,並進行包括所謂「語意錯誤」 (Semantic Error)、「語法錯誤」(Syntax Error)與「邏輯錯誤」(Logical Error)等相關測試與除錯工作。

1-4 程式設計的風格 由上而下與模組化設計 例如C是相當符合模組化設計精神的語言。 C的主程式其實就包含了最大的函數就是main(),還可區分為系統本身提供的標準函數及使用者自行定義的自訂函數。

1-4 程式設計的風格 可讀性設計 適時使用「註解」就是提高程式可讀性的第一步。 程式可讀性和可偵錯性的因素,最好將程式碼中的識別字名稱定義為較具體且有意義。 一個程式的程式碼就像一篇文章一樣,是由一個或數個程式區塊(Block)所構成,而程式區塊就像文章中的段落。 程式區塊,就是由{}左右兩個大括弧所組成,包含了多行或單行的指令。

1-4 程式設計的風格 控制結構設計(1/3) 循序結構 是一個程式敘述由上而下接著一個程式敘述的執行指令,如下圖所示:

1-4 程式設計的風格 控制結構設計(2/3) 選擇結構 是一種條件控制敘述,包含有一個條件判斷式,如果條件為真,則執行某些程式,一旦條件為假,則執行另一些程式。如下圖所示:

1-4 程式設計的風格 控制結構設計(3/3) 重覆結構 主要是迴圈控制的功能。迴圈(Loop)會重複執行一個程式區塊的程式碼,直到符合特定的結束條件為止。依照結束條件的位置不同分為兩種: 前測試型迴圈 後測試型迴圈

1-5 遞迴演算法 遞迴的定義(1/3) C的遞迴函數演算法 int factorial(int i) { int sum; if(i == 0) //跳出執行過程的出口 return(1); else sum = i * factorial(i-1); //反覆執行的遞迴過程 return sum; }

1-5 遞迴演算法 範例 1.5.1 請以C語言,設計一個計算n!的遞迴程式。 /*用遞迴函數求 n階乘的值*/ #include <stdio.h> #include <stdlib.h> int factorial(int); /*函數原型*/ int main() { int i,n; printf("請輸入階乘數:"); scanf("%d",&n); for (i=0;i<=n;i++) printf("%d !值為 %3d\n", i,factorial(i)); system("pause"); return 0; } int factorial(int i) int sum; if(i == 0)/* 遞迴終止的條件 */ return(1); else sum = i * factorial(i-1); /* sum=n*(n-1)!所以直接呼叫本身 */ return sum; 1-5 遞迴演算法 範例 1.5.1 請以C語言,設計一個計算n!的遞迴程式。

1-5 遞迴演算法 遞迴的定義(2/3) 直接遞迴(Direct Recursion) int Fun(...) { . if(...) Fun(...) }

1-5 遞迴演算法 遞迴的定義(3/3) 間接遞迴(Direct Recursion) 指遞迴函數中,如果呼叫其他遞迴函數,再從其他遞迴函數呼叫回原來的遞迴函數,我們就稱做間接遞迴(Indirect Recursion) : int Fun1(...) int Fun2(...) { { . . if(...) if(...) Fun2(...) Fun1(...) } }

1-5 遞迴演算法 費伯那序列 是一序列的第零項是0、第一項是1,其它每一個序列中項目的值是由其本身前面兩項的值相加所得。 從費伯那序列的定義,也可以嘗試把它轉成遞迴的形式: int fib(int n) { if(n==0)return 0; if(n==1) return 1; else return fib(n-1)+fib(n-2);//遞迴引用本身2次 }

1-5 遞迴演算法 範例1.5.2 請以C來設計一個計算第n項費伯那序列的遞迴程式 #include <stdio.h> #include <stdlib.h> int fib(int); /* fib()函數的原型宣告 */ int main() { int i,n; printf("請輸入所要計算第幾個費式數列:"); scanf("%d",&n); for(i=0;i<=n;i++) /* 計算前1n個費氏數列 */ printf("fib(%d)=%d\n",i,fib(i)); system("pause"); return 0; } int fib(int n) /* 定義函數fib()*/ if (n==0) return 0; /* 如果n=0 則傳回 0*/ else if(n==1 || n==2) /* 如果n=1或n=2,則傳回1 */ return 1; else /* 否則傳回 fib(n-1)+fib(n-2) */ return (fib(n-1)+fib(n-2)); 1-5 遞迴演算法 範例1.5.2 請以C來設計一個計算第n項費伯那序列的遞迴程式

1-5 遞迴演算法 河內塔問題(1/9) 河內塔問題可以這樣形容:假設有A、B、C三個木樁和n個大小均不相同的套環(Disc),由小到大編號為1,2,3…n,編號越大直徑越大。 開始的時候,n個套環境套在A木樁上,現在希望能找到將A木樁上的套環藉著B木樁當中間橋樑,全部移到C木樁上最少次數的方法。不過在搬動時還必須遵守下列規則: 1.直徑較小的套環永遠置於直徑較大的套環上。 2.套環可任意地由任何一個木樁移到其他的木樁上。 3.每一次僅能移動一個套環,而且只能從最上面的套環開始移動。

1-5 遞迴演算法 河內塔問題(2/9) 現在我們考慮n=1~3的狀況,以圖示方式示範處理河內塔問題的步驟: n=1個套環 n=2個套環 (當然是直接把盤子從1號木樁移動到3號木樁。) n=2個套環 1.將套環從1號木樁移動到2號木樁

1-5 遞迴演算法 河內塔問題(3/9) n=2個套環 2.將套環從1號木樁移動到3號木樁 3.將套環從2號木樁移動到3號木樁,就完成了

1-5 遞迴演算法 河內塔問題(4/9) n=2個套環 結論:移動了22-1=3次,盤子移動的次序為1,2,1(此處為盤子次序) 完成 步驟為:1→2,1→3,2→3(此處為木樁次序)

1-5 遞迴演算法 河內塔問題(5/9) n=3個套環 1.將套環從1號木樁移動到3號木樁 2.將套環從1號木樁移動到2號木樁

1-5 遞迴演算法 河內塔問題(6/9) n=3個套環 3.將套環從3號木樁移動到2號木樁 4.將套環從1號木樁移動到3號木樁

1-5 遞迴演算法 河內塔問題(7/9) n=3個套環 5.將套環從2號木樁移動到1號木樁 6.將套環從2號木樁移動到3號木樁

1-5 遞迴演算法 河內塔問題(8/9) n=3個套環 7.將套環從1號木樁移動到3號木樁,就完成了 結論:移動了23-1=7次,盤子移動的次序為1,2,1,3,1,2,1(盤子次序) 步驟為1→3,1→2,3→2,1→3,2→1,2→3,1→3(木樁次序)

1-5 遞迴演算法 河內塔問題(9/9) 以下以遞迴式來表示河內塔遞迴函數演算法: void hanoi(int n, int p1, int p2, int p3) { if (n==1) //遞迴出口 printf("套環從 %d 移到 %d\n", p1, p3); else hanoi(n-1, p1, p3, p2); hanoi(n-1, p2, p1, p3); }

1-5 遞迴演算法 範例 1.5.3 請設計一支C語言程式,以遞迴式來實作河內塔演算法的求解。 #include <stdio.h> #include <stdlib.h> void hanoi(int, int, int, int); /* 函數原型 */ int main() { int j; printf("請輸入所移動套環數量:"); scanf("%d", &j); hanoi(j,1, 2, 3); system("pause"); return 0; } void hanoi(int n, int p1, int p2, int p3) if (n==1) /* 遞迴出口 */ printf("套環從 %d 移到 %d\n", p1, p3); else hanoi(n-1, p1, p3, p2); hanoi(n-1, p2, p1, p3); 1-5 遞迴演算法 範例 1.5.3 請設計一支C語言程式,以遞迴式來實作河內塔演算法的求解。

1-5 遞迴演算法 範例 1.5.4 請問河內塔問題中,移動n個盤子所需的最小移動次數?試說明之。 解答 課文中曾經提過當有n 個盤子時,可將河內塔問題歸納成三個步驟,其中an為移動n個盤子所需要的最少移動次數,an-1為移動n-1個盤子所需要的最少移動次數,a1=1為只剩一個盤子時的次數,因此可得如下式子: an= an-1+1+ an-1 =2an-1+1 =2(an-2+1) =4an-2+2+1 =4(2an-3+1)+2+1

1-5 遞迴演算法 =16an-4+8+4+2+1 =... =2n-1a1+ 因此,an=2n-1*1+ =8an-3+4+2+1 =8(2an-4+1)+4+2+1 =16an-4+8+4+2+1 =... =2n-1a1+ 因此,an=2n-1*1+ =2n-1+2n-1-1=2n-1,得知要移動n個盤子所需的最小移動次數為2n-1次

1-6 程式效能分析 程式效能分析(1/3) 範例 1.6.1 考慮下列x←x+1的執行次數。 解答 (1)1次(2)n次(3)n*m次 for i←1 to n do : x←x+1 : end (3) for i←1 to n do : for j←1 to m do : x←x+1 : end : end 解答 (1)1次(2)n次(3)n*m次

1-6 程式效能分析 程式效能分析(2/3) 範例 1.6.2 考慮下列x←x+1的執行次數。 for i←1 to n do j←i for k←j+1 to n do x←x+1 end 解答 因為j←i,且k←j+1所以可用以下數學式表示,所以其執行次數為

1-6 程式效能分析 程式效能分析(3/3) 範例 1.6.3 請決定以下片斷程式的執行時間。 k=100000 while k<>5 do k=k DIV 10 end 解答 因為k=k DIV 10,所以一直到k=0時,都不會出現k=5的情況,整個迴路為無窮迴路,執行時間為無限長。

1-6 程式效能分析 Big-oh(1/3) 範例 1.6.4 請證明 =O(n2) 解答

1-6 程式效能分析 Big-oh(2/3) 常見的Big-oh有下列幾種:

1-6 程式效能分析

1-6 程式效能分析 Big-oh(3/3) 對於n≥16時,時間複雜度的優劣比較關係如下: 範例 1.6.5 請問河內塔遞迴氏的時間複雜度為何? O(1)<O(log2n)<O(n)<O(nlog2n)<O(n2)<O(n3)<O(2n) 解答:由範例1.5.1中,可以得到以下結論: an== an-1+1+ an-1 =2n-1 → O(2n)

1-6 程式效能分析 Ω(omega) 以下是Ω的定義: 範例1.6.6 f(n)=6n2+3n+2,請利用Ω來表示f(n)的時間複雜度。 對f(n)= Ω(g(n))(讀作”big-omega of g(n)”),意思是存在常數c和n0,對所有的n值而言,n>= n0時,f(n)≧cg(n)均成立。例如f(n)=5n+6,存在c=5 n0=1,對所有n≧1時,5n+6≧5n,因此f(n)= Ω(n)而言,n就是成長的最大函數。 f(n)= 6n2+3n+2,存在c=6 ,n0≧1,對所有的n≧n0,使得6n2+3n+2>=6n2,所以f(n)= Ω(n2)

1-6 程式效能分析 θ(theta) 是一種比Big-O與Ω更精確時間複雜度的漸近表示法。定義如下: 例如以f(n)=n2+2n為例,當n≧0時,n2+2n≦3n2,可得f(n)=O(n2)。同理,n≧0時, n2+2n≧n2,可得f(n)=Ω(n2)。所以f(n)=n2+2n=θ(n2) f(n)= θ(g(n))(讀作”big-theta of g(n)”),意是存在常數c1、c2、n0,對所有的n≧n0時,c1g(n)≦f(n)≦c2g(n)均成立。換句話說,當f(n)=θ(g(n))時,就表示g(n)可代表f(n)的上限與下限。

本章結束 Q&A討論時間