鄧姚文 ywdeng@mail.knu.edu.tw http://w3.im.knu.edu.tw/~joseph/ 資料結構 第五章:遞迴 鄧姚文 ywdeng@mail.knu.edu.tw http://w3.im.knu.edu.tw/~joseph/

Slides:



Advertisements
Similar presentations
河內塔(Hanoi)問題.
Advertisements

第1单元 操作系统概论 第一节 绪论 操作系统定义.
Introduction 基本概念 授課老師:蕭志明
第7章 樹與二元樹 (Trees and Binary Trees)
黄金分割理论在股市中的应用 包头营业部.
算法设计与分析 李清勇 教授 办公室:第九教学楼北201.
计算学科的基本问题 本章首先介绍一个对问题进行抽象的典型实例——哥尼斯堡七桥问题。然后,通过“梵天塔”问题和“停机问题”分别介绍学科中的可计算问题和不可计算问题。从“梵天塔”问题再引出算法复杂性中的难解性问题、P类问题和NP类问题,证比求易算法,P=NP是否成立的问题。
国王赏麦的故事.
AI人工智慧報告 黑白棋 班級:資工四乙 學號:498G0009 姓名:盧冠妤.
第三章 鏈結串列 Linked List.
数据结构——树和二叉树 1/96.
第8章 字串與陣列 8-1 字串處理 8-2 一維陣列的處理 8-3 建立多維陣列 8-4 不規則陣列與參數傳遞 8-5 陣列排序與搜尋.
C++程序设计 王希 图书馆三楼办公室.
专题研讨课二: 数组在解决复杂问题中的作用
Chap4 Tree.
Tree(樹) 什麼是「樹」? 「樹」的範例 「樹」的定義 「樹」的表示法.
第8章 字元與字串處理 8-1 C語言的字元檢查函數 8-2 C語言的字串 8-3 字串的輸入與輸出 8-4 指標與字串
Introduction to the C Programming Language
物件導向程式設計 (Object-Oriented rogramming)
函數(一) 自訂函數、遞迴函數 綠園.
Chap 10 函数与程序结构 10.1 函数的组织 10.2 递归函数 10.3 宏定义 10.4 编译预处理.
第 1 章 演算法分析.
搜尋資料結構 Search Structures.
第12章 樹狀搜尋結構 (Search Trees)
Function.
程序设计期末复习 黎金宁
程式撰寫流程.
cn/~dongeliu/dsa.html 刘 东 信息学院6系 中国科学技术大学
第5章 堆疊(Stacks) 5-1 堆疊的基礎 5-2 堆疊的表示法 5-3 堆疊的應用 - 運算式的計算與轉換
第5章 堆疊(Stacks) 5-1 堆疊的基礎 5-2 堆疊的表示法 5-3 堆疊的應用 - 運算式的計算與轉換
计算机网络讲义 第5章 批量数据处理—数组 一维数组 排序和查找 二维数组 字符串.
算法设计与分析.
中国科学院软件研究所 计算机科学国家重点实验室 张文辉
6 使用者函數 6.1 函數定義 宣告函數 呼叫函數 呼叫多個函數 6-6
第3章 栈和队列(一).
Linux操作系统分析 中国科学技术大学计算机系 陈香兰(0512- )
第一章 绪论.
第九章 查找 2019/2/16.
資料結構 第4章 堆疊.
第十章 指针.
东北林业大学 陈宇 ACM程序设计 东北林业大学 陈宇
Chapter6 队列(Queues) The Abstract Data Type
Chapter 5 Recursion.
六、函数 教学目标: 函数的概念、定义、调用和返回 带自定义函数的程序设计 递推算法 递归思想及算法实现 函数的参数传递方式 C语言程序设计.
第三章 链表 单链表 循环链表 多项式及其相加 双向链表 稀疏矩阵.
鄧姚文 資料結構 第一章:基本概念 鄧姚文
第五章 递归与广义表 递归的概念 递归过程与递归工作栈 递归与回溯 广义表.
程式結構&語法.
數學遊戲一 河內塔 (Tower of Hanoi)
Chap7 Recursive.
第7章 樹與二元樹(Trees and Binary Trees)
Oop8 function函式.
Lucene 算法介绍 IR-Lab 胡晓光.
演算法時間複雜度 (The Complexity of Algorithms)
第 5 章 遞迴.
資料結構與C++程式設計進階 遞迴(Recursion) 講師:林業峻 CSIE, NTU 6/ 17, 2010.
<编程达人入门课程> 本节内容 为什么要使用变量? 视频提供:昆山爱达人信息技术有限公司 官网地址: 联系QQ:
第二章 Java语法基础.
第二章 类型、对象、运算符和表达式.
单片机原理及应用 实践部分 主讲人:刘 强 四川工商学院单片机教学团队 单片机原理及应用 实践部分 主讲人:刘 强
本节内容 引用类型 视频提供:昆山爱达人信息技术有限公司 官网地址: 联系QQ: QQ交流群 : 联系电话:
問題解決與流程圖 高慧君 台北市立南港高中 2006年12月22日.
授课老师:龚涛 信息科学与技术学院 2016年3月 教材:《Visual C++程序员成长攻略》 《C++ Builder程序员成长攻略》
挑戰C++程式語言 ──第9章 函數.
第二章 Java基本语法 讲师:复凡.
遞迴 Recursion.
第1章 数据结构基础概论 本章主要介绍以下内容 数据结构研究的主要内容 数据结构中涉及的基本概念 算法的概念、描述方法以及评价标准.
第6章 嵌入式软件开发基础.
基本資料型態 變數與常數 運算子 基本的資料處理 授課:ANT 日期:2014/03/03.
第10章 二元搜尋樹 (Binary Search Tree)
Presentation transcript:

鄧姚文 ywdeng@mail.knu.edu.tw http://w3.im.knu.edu.tw/~joseph/ 資料結構 第五章:遞迴 鄧姚文 ywdeng@mail.knu.edu.tw http://w3.im.knu.edu.tw/~joseph/

遞迴函數(Recursive Function) 遞迴函數的特徵: 直接或間接地呼叫自己 在數學上與遞迴定義有關 例如:費氏數列

求算階乘(Factorial) n! = n*(n-1)*(n-2)*…*2*1 遞迴定義: 1!=1 f(n)=n*f(n-1), n>=2 13! = 1932053504,在32位元系統上用long所能算出的最大階乘數 long fact(int n) { if (n == 1) return 1; else return n * fact(n-1); }

費氏數列(Fibonacci Series) 問題:給定一個 n 值,求解費氏數列第 n 項的值。

費氏數列(Fibonacci Series) int fibon(int n) { if (n == 0) return 0; if (n == 1) return 1; return fibon(n-1) + fibon(n-2); } 時間複雜度:O(2n/2)

二元搜尋(Binary Search) 輸入: 輸出: n 筆已排序資料(從小排到大) 欲尋找之資料 target 1 2 3 4 5 6 7 8 9 找 5 大 小 中

二元搜尋(Binary Search) int bin_search(int data[], int left, int right, int target) { int mid = (left + right) / 2; if (left > right) return -1; if (target == data[mid]) return mid; if (target > data[mid]) { return bin_search(data, mid+1, right, target); } else { return bin_search(data, left, mid-1, target); } 用法: bin_search(data, 0, n-1, target)

Tower of Hanoi

Tower of Hanoi

Tower of Hanoi 宣告與用法 #define PEG_A "PEG_A" #define PEG_B "PEG_B" #define PEG_C "PEG_C" int main(int argc, char* argv[]) { … hanoi_move(n, PEG_A, PEG_B, PEG_C); }

Tower of Hanoi 主要邏輯 void hanoi_move(int n, char* from, char* to, char* via) { if (n == 1) { printf("Move ring 1 from %s to %s\n", from, to); } else { hanoi_move(n-1, from, via, to); printf("Move ring %d from %s to %s\n", n, from, to); hanoi_move(n-1, via, to, from); }

Tower of Hanoi 執行結果 1: Move ring 1 from PEG_A to PEG_B 2: Move ring 2 from PEG_A to PEG_C 3: Move ring 1 from PEG_B to PEG_C 4: Move ring 3 from PEG_A to PEG_B 5: Move ring 1 from PEG_C to PEG_A 6: Move ring 2 from PEG_C to PEG_B 7: Move ring 1 from PEG_A to PEG_B

八個皇后 西洋棋盤上,皇后不可以在同一列(row)或同一行(column)或同一對角線(diagonal)上 在一個 8×8 的棋盤上如何放置 8 個皇后? 往回追蹤(Backtracking)又稱『回溯』 如果下一個皇后找不到位置可放,則回頭調整前一個皇后的位置

void place(int q) { int i; i = 0; while (i < MAXQUEEN) { /* 試著將第 q 個皇后放在 (row, col) = (i, q) 的位置 */ if (!attack(i, q)) { /*皇后未受攻擊 */ queen[q] = i; /*儲存皇后所在的列位置 */ /*判斷是否找到一組解 */ if (q == (MAXQUEEN - 1)) output_solution(); /*列出此組解 */ else place(q + 1); /*否則繼續擺下一個皇后 */ } i++;

/* 測試在(row,col)上的皇后是否遭受先前放置的其他皇后攻擊 */ int attack(int row, int col) { int i, atk = FALSE; int offset_row, offset_col; i = 0; while (!atk && i < col) { offset_col = ABS(i - col); offset_row = ABS(queen[i] - row); /*判斷兩皇后是否在同一列,皇后是否在對角線上 */ /*若皇后同列或在對角線上則產生攻擊,atk ==TRUE */ atk = (queen[i] == row) || (offset_row == offset_col); i++; } return atk;

計算組合數 組合數 在 m 個球之中取 n 個,有多少種方式? 遞迴解:

計算組合數 int comb(int m, int n) { if (n == 0) return 1; if (m == n) return 1; return comb(m-1, n) + comb(m-1, n-1); }