第1章递归问题.pptx

第1章递归问题(Recurrent Problems)
鞠成东
E-mail:******@hrbeu.
M. P. :**********
参考教材与书目
。
参考教材与书目
书名:具体数学:计算机科学基础(第2版)
原书名:Concrete Mathematics: A Foundation puter Science (2nd Edition)
作者:(美)Ronald L. Graham, Donald E. Knuth, Oren Patashnik
译者:张明尧,张凡
出版社:人民邮电出版社
ISBN:978-7-115-30810-8
课程教学内容
●第1章递归问题
●第2章和式(选讲)
●第3章整值函数
●第4章数论
●第5章二项式系数
●第6章特殊的数
●第7章生成函数
●第8章离散概率
●第9章渐进式
课程教学内容
● It introduces the mathematics that supports the analysis of algorithms, modeling probems in real world. See,
Chap. 1 – Recurrence 递归的计数
Chap. 2 – Sum 各种求和,用于算法复杂度计算等
Chap. 6 – Special Numbers 调和数列及有关求和问题
● Concrete mathematics is a blending of continuous and discrete mathematics. See,
Chap. 3 – Integer Functions 实数的整数部分运算
Chap. 9 – Asymptotics 离散到连续的渐进
课程教学内容
● The goal is for the student to have mathematical skills to plex problems, and to discover subtle patterns in data.
Chap. 7 – Generating Functions 用于概率计算的母函数
Chap. 8 – Discrete Probability 离散问题概率(最有趣)
本章教学目标
●理解递归的思想
●掌握递归问题的分析思路及方法
●掌握递归式及其封闭形式的求解方法
本章教学内容
● 河内塔
● 平面上的直线
● 约瑟夫问题
9
河内塔
递归的思想
每一个问题的解都依赖于同一个问题的更小实例的解。
什么是河内塔
法国数学家爱德华·卢卡斯于1883年提出的一个精巧智力题。
10
。
给定一个由八个大小不同的圆盘组成的塔,最初圆盘按尺寸递减的次序自底而上地堆放到三根杆中的一根上。类似的问题是婆罗门塔(64个盘子)。
目的:将整个塔移动到另一根桩柱上。
规则:每次移动一个圆盘;小盘总在大盘上面。
求解:必须且足够的移动次数?(必要且充分)