`

[程序员的数学]notes——chapter 6

阅读更多

第6章 递归——自己定义自己

 

汉诺塔问题

递推公式(recursion relation, recurrence)

解析式:只使用n表示H(n)的式子。

在问题中找出递归结构——> 建立递归公式

 

阶乘的递归定义:n!=n×n(n-1)!

 

递归和归纳

同:都是“将复杂问题简化”;

异:“从一般性前提退出个别性结论”——递归;“从个别性前提推出一般性结论”——归纳。

 

斐波那契数列

思考题:不断繁殖的动物

斐波那契数列例子:

摆砖头、创作旋律、鹦鹉螺的内壁间隔、葵花种子的排法、植物枝叶的长法、“一次走1阶或2阶,爬n层阶梯的方法”

 

帕斯卡三角形:每个数字都是上方与它相邻的两数之和。


帕斯卡三角形中出现组合数的原因:“相邻两数相加”和“n中选k的组合数”的计算对象相同。

 

递归定义组合数:


 组合的数学分析法

 

找出问题中的递归结构的步骤:

从n层的整体问题中隐去部分问题 -> 判断剩余部分是否是n-1层的问题

 

递归图形:树、谢尔平斯基三角形(Sierpinski gasket, Sierpinski triangle)


分形图:含有递归结构的图形。

 

 

  • 大小: 41.4 KB
  • 大小: 23.6 KB
  • 大小: 8.6 KB
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics