101北一女中 資訊選手培訓營 遞迴、河內塔與merge sort 2012.07.01 Nan.

Slides:



Advertisements
Similar presentations
定 格 入 格 破 格 —— 新诗仿写复习训练 仿照下列句子,再把 “ 人生 ” 比喻成 “ 大海 ”“ 天空 ” , 造两个句子。 如果说人生是一首优美的乐曲,那么痛苦则 是其中一个不可或缺的音符。 参考答案: 1 、如果说人生是一望无际的大海,那么挫折则 是其中一个骤然翻起的浪花。 2 、如果说人生是一片湛蓝的天空,那么失意则.
Advertisements

發明河內塔 ---- 愛德華盧卡斯 ( EdouardLucas ) 的 ” 一生 ” 盧卡斯曾就讀於 法 國高等師 範學校 , 他 曾在巴黎天文台 工作,後來在巴黎 成為數學教授, 他 也曾在 軍隊。 盧卡斯曾就讀於 法 國高等師 範學校 , 他 曾在巴黎天文台 工作,後來在巴黎 成為數學教授,
用印度数学提高计算速度 段志强. 讲义大纲 速算基础 充满智慧的印度数学 印度数学的十类快速计算 复习和测验 综合应用及思考.
無性生殖是由親代直接產生新的個體,並不涉及配子的生成與結合。
Introduction to C Programming
人生格言: 天道酬勤 学院:自动化与电气工程学院 班级: 自师1201 姓名:刘 威.
(教育学博士,曾任中学副校长,兼职南京大学博士后)
民國88年至99年期間,下列何種空氣品質指標污染物有逐年升高的趨勢?
自然的食物就是你最好的醫生 上課之前先聽一首歌~稻香 歌詞、音樂還不錯和大家分享一下
怎樣吃才健康? 賴亭竹.
胫腓骨骨折.
第23课 美术的辉煌 米勒:《拾穗者》(法国).
第二单元(6-9课) 近代化的探索.
2011年广西高考政治质量分析 广西师范大学附属外国语学校 蒋 楠.
第一单元 生活与消费 目 录 课时1 神奇的货币  课时2 多变的价格 课时3 多彩的消费.
知识回顾 1、通过仔细观察酒精灯的火焰,你可以发现火焰可以分为 、 、 。 外焰 内焰 焰心 外焰 2、温度最高的是 。
2016届高三期初调研 分析 徐国民
新帝國主義開港 (一)臺灣成為侵略者目標 1.背景: A.買賣利豐=鴉片進口+米、糖、樟腦、煤炭出口 B.地理位置優越=航行安全+商貿中心 2.新帝國主義: A.19C中:英、法、美、日為主 B.臺被迫開港通商,割地賠款,簽訂不平等條約.
第5章 排序与查找 PART A 《可视化计算》.
歌仔戲 與 歌舞伎 4a 張淇惠 4a11b025 許巧嬑 4a 倪曼凌 4a1c0004 楊長梵
佳力科技 防爆叉车的应用、发展 浙江佳力科技股份有限公司.
岳阳市教学竞赛课件 勾股定理 授课者 赵真金.
请同学们思考下列问题:.
1 实验目的 观察单缝夫琅和费衍射现象,加深对夫琅和费衍射理论的理解。
烟花爆竹企业开复工 安 全 培 训参考课件 浏 阳 市 安 监 局.
命题与四种命题 高二数学 选修2-1 第一章 常用逻辑用语.
常规免疫接种率 监测 免疫规划科 章梦然.
入托、入学儿童预防接种证查验 武平县疾病预防控制中心 林传贵
面向海洋的开放地区——珠江三角洲 山东省高青县实验中学:郑宝田.
词类活用.
勾股定理 说课人:钱丹.
证券投资基金 投资121 06号余煜欢 09号陈秋婷 33号陈柔韵 08号潘晓峰 10号曾杰 34号谭锐权.
Chapter 5 遞迴 資料結構導論 - C語言實作.
狂賀!妝品系同學美容乙級通過 妝品系三甲 學號 姓名 AB 陳柔諺 AB 陳思妤 AB 張蔡婷安
第七章 财务报告 主讲老师:王琼 上周知识回顾.
遞迴演算法.
101北一女中 資訊選手培訓營 快速排序函式qsort() Nan.
101北一女中 資訊選手培訓營 妳不可不了解的指標 Nan.
101北一女中 資訊選手培訓營 圖論基礎 Nan.
河內之塔(Towers of Hanoi)問題(1/11)
人教版数学四年级(下) 乘法分配律 单击页面即可演示.
如何赢一个机械键盘
Topic Introduction—RMI
第二次電腦實習課 說明者:吳東陽 2003/10/07.
乘法公式 (1) 乘法分配律 (2) 和的平方公式 (3) 差的平方公式 (4) 平方差公式.
數學遊戲一 河內塔 (Tower of Hanoi)
101北一女中 資訊選手培訓營 深度優先搜尋(DFS)的進階應用 Nan.
河內之塔(Towers of Hanoi)問題
蕭志明 老師 Algorithm(演算法) Ext:6779
蕭志明 老師 Algorithm(演算法) /FB:
Welcome 实验:筷子提米.
第一部分 数字电路 第4章 组合逻辑电路 主讲教师:喻红.
第 5 章 遞迴.
C qsort.
第 二 章 遞迴(Recursion) 課程名稱:資料結構 授課老師:________ 2019/5/5.
北一女中 資訊選手培訓營 圖論基礎 By Nan( ).
线段 射线 直线.
9.1.2不等式的性质 周村实验中学 许伟伟.
北一女中 資訊選手培訓營 遞迴、河內塔與merge sort Nan.
12797: Letters ★★★☆☆ 題組:Problem Set Archive with Online Judge
北一女中 資訊選手培訓營 妳不可不了解的指標 Nan.
Chapter 6 遞迴.
本教學投影片係屬教科書著作之延伸,亦受著作權法之保護。
美丽的旋转.
資料結構 老師:李崇明 助教:楊斯竣.
資料結構 老師:李崇明 助教:楊斯竣.
ABAP Basic Concept (2) 運算子 控制式與迴圈 Subroutines Event Block
遞迴
Chapter 16 動態規劃.
ABAP Basic Concept (2) 運算子 控制式與迴圈 Subroutines Event Block
Presentation transcript:

101北一女中 資訊選手培訓營 遞迴、河內塔與merge sort 2012.07.01 Nan

遞迴,原來是這麼回事 讓我們從函數執行來了解遞迴的真義

你一定聽過一種說法…… 「函數,就像一個黑盒子, 你給他input,他就給你output。」 但你知道實際上程式在呼叫與執行函數時是怎麼回事嗎?

讓我們用費伯納基數列來舉例說明……

這是一個可以計算出費伯納基數的函數

他的input是一個數n,代表我們要的是第n項的費伯納基數

而這就是黑盒子裡面做的事情:遞迴呼叫和處理邊界情況

直到輸入為0或1時(邊界情況),結束遞迴 N=n-1 N-1 N-2 … n - 1 n - 2 … M=n-2 M-1 M-2 … …

放到真實的code中來看 每次呼叫實際上是新產生一段會照著這段code的步驟一一執行的CPU指令, 並給他參數n,讓他可以套進這段code所產生的CPU指令裡面。 n = 1 fib(3) fib(3) = 2 回傳值=1 n = 2 回傳值=1 + 0 = 1 n = 0 n = 3 回傳值=0 回傳值=1 + 1 = 2 n = 1 回傳值=1

搬完就世界末日的塔 經典遞迴問題: 河內塔

河內塔的故事與規則 一次只能動一個盤子 小的不能在大的下面 目標是把所有盤子移到第三根柱子 “河內之塔(Towers of Hanoi)是法國人M.Claus(Lucas)於1883年從泰國帶至法國的,河內為越戰時北越的首都,即現在的胡志明市;1883年法國數學家 Edouard Lucas曾提及這個故事,據說創世紀時Benares有一座波羅教塔,是由三支鑽石棒(Pag)所支撐,開始時神在第一根棒上放置64個由上至下依由小 至大排列的金盤(Disc),並命令僧侶將所有的金盤從第一根石棒移至第三根石棒,且搬運過程中遵守大盤子在小盤子之下的原則,若每日僅搬一個盤子,則當 盤子全數搬運完畢之時,此塔將毀損,而也就是世界末日來臨之時。” -- http://caterpillar.onlyfun.net/Gossip/AlgorithmGossip/HanoiTower.htm 一次只能動一個盤子 小的不能在大的下面 目標是把所有盤子移到第三根柱子

http://notepad.yehyeh.net/Content/DS/CH02/4.php

先從基礎的2個盤子開始看 A B C AB A B C A B C A B C AC BC

“把上面的大盤子從A移到B和從B移到C的這件事, 如果是三個以上…… A B C 就把除了最後一個盤子之外的所有盤子看成一個盤子→ AB A B C A B C A B C AC BC “把上面的大盤子從A移到B和從B移到C的這件事, 正是另一個河內塔問題。”

Pseudo Code

講了這麼多, 到底什麼時候會用到遞迴呢? 分而治之 “Divide and Conquer” “大的問題可以切成小的問題來做, 做完再湊出大的問題的解答”

遞迴與分而治之 (Divide and Conquer) 合併排序 Merge Sort 遞迴與分而治之 (Divide and Conquer)

排序問題 “給你一堆數字,請你把他按照大小順序排好。” 之前你可能有學過泡泡排序(bubble sort) 它的worst case複雜度是O(n2),有更好的做法嗎?

有!我們有合併排序(merge sort)! 合併排序的特點: 採用遞迴—分而治之 O(nlogn),排序問題的最佳解之一 用空間換取時間

請準備一副撲克牌,拿出其中一個花色的七張牌, 讓我們來實際操作一下吧! 請準備一副撲克牌,拿出其中一個花色的七張牌, 隨意洗牌,再把它攤在桌上排一排

Pseudo Code