分形图递归算法15页PPT

ppt课件
14
int fib(int n) { if (n==0) return 0; if (n==1) return 1; return (fib(n-1)+fib(n-2)); }
输入 15 输出 fib(15)=610
//满足边界条件，递归返回 //满足边界条件，递归返回 //递归公式，进一步递归
//调用下一层递归
}

int main()
{
int n,k;

cin >> n >> k;

cout << s(n,k);

return 0;
}
ppt课件
19
【例6】数的计数(Noip2001)
【问题描述】
我们要求找出具有下列性质数的个数（包括输入的自然数n）。先输入一 个自然数n（n≤1000），然后对此自然数按照如下方法进行处理：
8
ppt课件
9
假设把第3步，第4步，第7步抽出来就相当于N=2的情况（把上面2片 捆在一起，视为一片）：
ppt课件
10
所以可按“N=2”的移动步骤设计：
①如果N=0，则退出，即结束程序;否则继续往下执行;
②用C柱作为协助过渡，将A柱上的（N-1）片移到B柱上，调用过程mov(n-1,
a,b,c);
本题是典型的递归程序设计题。 (1)当N=1 时，只有一个盘子，只需要移动一次:A—>C; (2)当N=2时，则需要移动三次：
A------ 1 ------> B, A ------ 2 ------> C, B ------ 1------> C. (3)如果N=3，则具体移动步骤为：

分形作为一种方法，在图形学领域主要是利用迭代、递归等技
术来实现某一具体的分形构造。 分形几何学与计算机图形学相结合，将会产生一门新的学科 — —分形图形学。它的主要任务是以分形几何学为数学基础，构造非规 则的几何图素，从而实现分形体的可视化，以及对自然景物的逼真 模拟。
参考书：《分形算法与程序设计》 9
想用此词来描述自然界中传统欧几里得几何学所不能描述的一大
类复杂无规的几何对象。
参考书：《分形算法与程序设计》
2
1.2 分形的几何特征
自相似性
自相似，便是局部与整体的相似。
自仿射性
自仿射性是自相似性的一种拓展。如果，将自相 似性看成是局部到整体在各个方向上的等比例变 换的结果的话，那么，自仿射性就是局部到整体 在不同方向上的不等比例变换的结果。前者称为 自相似变换，后者称为自仿射变换。
第
2章
分形图的递归算法
2.1 Cantor三分集的递归算法 2.2 Koch曲线的递归算法
2.4 Hilbert-Peano曲线的算法
2.5 分支结构分形递归算法
2.6 分形树递归算法
2.3 Sierpinski垫片的递归算法
参考书：《分形算法与程序设计》
10
递归算法
u 直接递归调用的例子如下：
2.1 Cantor三分集的递归算法
13
2.2 Koch曲线的递归算法
算法：Koch(ax,ay,bx,by,c)
标题：Koch曲线的递归算法
参数：c（终止递归的小量） PI（π值） 函数：plot(x1,y1) –(x2,y2) （画直线函数） sin( ) （正弦函数） cos( ) （余弦函数） ArcTan( ) （反正切函数） sqrt( ) （开平方函数）

开始，每1项等于前面3项的和。
f(n)=f(n-1)+f(n-2)+f(n-3)-----递推公式 f(1)=1 , f(2)=2 , f(3)=4 --------递推边界
27
① #include <stdio.h> //上楼问题
② void main( )
③ { int x,n,i,a,b,c;
3)第二只猴子醒来，又把桃子均分成五堆后，还是多了一 个，它也吃掉这个桃子，并拿走了其中一堆。
第三只，第四只，第五只猴子都依次如此分食桃子。 问：五只猴子采得一堆桃子数最少应该有几个呢？
11
例2：猴子分食桃子---逆推法
算法分析：
先要找第N只猴子和其面前桃子数的关系。如 果从第1只开始往第5只找，不好找，但如果思路 一变，从第N到第1去，可得出下面的推导式：
19
例11.2 骨牌问题---顺推法
➢长度为n时的骨牌铺放方案？ ➢从最简单的情况开始寻找问题解决的规律？--- 顺推 ➢以 f(i) 表示n=i时的铺放方案数目。 ➢当n=1时，只有1种铺法，即f(1)=1，如下左图所示： ➢当n=2时，只有2种铺法，即f(2)=2，如下右图所示。
20
例11.2 骨牌问题---顺推法
n=1
f(n)=1
n=2
f(n)=2
n=3
f(n)=3
n=4
f(n)=3 + 1 =f[3]+ f[1]=4
n=5
f(n)=f(4)+f(2)
n=6
f(n)=f(5)+f(3)
n=7
f(n)=f(6)+f(4)
规律： f(n)=f(n-1)+f(n-3) (n>=4) 17

题的运行效率较低。所以一般不提倡用递归算法 设计程序
递归法的归纳2：
递归算法所体现的“重复”一般有三个要求： 一是每次调用在规模上都有所缩小(通常是减半)； 二是相邻两次重复之间有紧密的联系，前一次要为
后一次做准备(通常前一次的输出就作为后一次的 输入)； 三是在问题的规模极小时必须用直接给出解答而不 再进行递归调用，因而每次递归调用都是有条件 的(以规模未达到直接解答的大小为条件)，无条 件递归调用将会成为死循环而不能正常结束。
• 注意：必须要有一个结束递归的条件，不 得无限递归。
分析步骤：
• 1.决定问题规模的参数。 • 2.问题的边界条件及边界值。 • 3.解决问题的通式。
例:计算一个数的阶乘
• 1!=1 • 2!=1*2 • 3!=1*2*3 • 4!=1*2*3*4 • 5!=1*2*3*4*5 • ……. • n!=1*2*3*4*5*….*n
函数是为了实现某种功能而编写的一段相对独立 的程序。
• 标准函数
Abs( ) 、len( )、mid( )、chr( )、asc( )……
• 自定义函数
自定义函数是指我们自己编写的函数。
自定义函数:
• 在VB中，自定义函数形式如下： • [Public|Private] Function <函数名称> ([参数列表]) [As
f(1)=1 f(2)=f(1)*2 f(3)=f(2)*3 f(4)=f(3)*4 f(5)=f(4)*5 …….. f(n)=f(n-1)*n
递归函数求5！
• Public Function s(n As Integer) As Long
• If n = 1 Then
• s =1
• Else

4563697
4564531 4565926
正中间 的元素
4566088
4572874
17
4120243
4276013
4328968 4397700
4462718
请问： 4565926是否在 此列表当中？ 4565925？
4466240 4475579
4478964
4480332 4494763
4499043
相应的参数来完成，这就是函数或子程序，使用时只需对其名字进行
简单调用就能来完成特定功能。

例如我们把上面的讲故事的过程包装成一个函数，就会得到：
void Story() { puts("从前有座山，山里有座庙，庙里有个老和尚，老和尚在讲故 事，它讲的故事是："); getchar();//按任意键听下一个故事的内容 Story(); //老和尚讲的故事，实际上就是上面那个故事 }
4563697
4564531 4565926
4566088
4572874
16
4120243
4276013
4328968 4397700
4462718
请问： 4565926是否在 此列表当中？
4466240 4475579
4478964
4480332 4494763
4499043
4508710 4549243

(1)对原问题f(s)进行分析,假设出合理的“较小 问题” f(s')( 与数学归纳法中假设 n=k-1时等式 成立相似)； (2)假设f(s')是可解的,在此基础上确定f(s)的解, 即给出 f(s) 与 f(s') 之间的关系 ( 与数学归纳法中 求证n=k时等式成立的过程相似)； (3)确定一个特定情况(如f(1)或f(0))的解,由此 作为递归边界(与数学归纳法中求证n=1时等式 成立相似)。

写成函数形式，则为：
当n 0时 1 f ( n) n * f (n 1) 当n 0时
这种函数定义的方法是用阶乘函数自己本身定义了 阶乘函数，称上式为阶乘函数的递推定义式。
数学归纳法表明，如果我们知道某个论点对最小的情 形成立，并且可以证明一个情形暗示着另一个情形，那么我 们就知道该论点对所有情形都成立。 数学有时是按递归方式定义的。 例1：假设S（n）是前n个整数的和，那么S（1）= 1，并且 我们可以将S（n）写成S（n）= S（n-1）+ n。 根据递归公式，我们可以得到对应的递归函数： int S(int n) { if (n == 1) return 1; else return S(n-1) + n; } 函数由递归公式得到，应该是好理解的，要想求出S （n），得先求出S(n-1)，递归终止的条件（递归出口）是(n == 1)。
↑
low 第二次: 下标 元素值 0 1 1 3 2 4
↑
mid 3 5 4 17 5 18 6 31
↑
high 7 33
↑
low 第三次: 下标 元素值 0 1 1 3 2 4 3 5 4 17
↑
mid 5 18 6 31
↑
high 7 33
↑
low high mid
• Public static void main(String args[]) •{ • int[] shus={1,3,4,5,17,18,31,33};
求Fib(5)的递归计算过程如图所示。
Fib(5) Fib(4) Fib(3) Fib(2) Fib(1) Fib(2) Fib(3) Fib(2) Fib(1) Fib(0)
Fib(1) Fib(0) Fib(1)

(3)编写程序 窗ຫໍສະໝຸດ 中开设一个文本框Text1用于填 人月数N，设置命令框Commandl，点击 它即执行程序求出第N月的兔子数。然后用 文本框Text2输出答案。
根据递推式可以写出递归程序如下：
Function Fib(ByVal N As Integer) As Long If N < 3 Then Fib = 1 Else Fib = Fib(N - 1) + Fib(N - 2) End Function Private Sub Command1_Click() N = Val(Text1.Text) Text2.Text = "第" & N & "月的兔子数目是：" & Fib(N) End Sub
递 归 算 法
什么是递归算法?
递归算法：是一种直接或者间接地调 用自身的算法。在计算机编写程序中，递 归算法对解决一大类问题是十分有效的， 它往往使算法的描述简洁而且易于理解。
斐波那契的兔子问题
某人有一对兔子饲养在围墙中，如 果它们每个月生一对兔子，且新生的兔子 在第二个月后也是每个月生一对兔子，问 一年后围墙中共有多少对兔子。
算法:
① ② ③ ④ ⑤ ⑥ 输入计算兔子的月份数：n If n < 3 Then c = 1 Else a = 1: b = 1 i=3 c = a + b：a = b：b = c i=i+1,如果i≤n则返回④ 结束
Private Sub Command1_Click() n = Val(Text1.Text) If n < 3 Then c = 1 Else a = 1: b = 1 For i = 3 To n c=a+b a=b b=c Next i Text2.Text = "第" & n & "月的兔子数目是：" &c End Sub

递归元
2021/5/21
• 递归算法的思想是将对较大规模的对象的操 作归结为对较小规模的对象实施同样的操作。
• 这种规模的变化就体现在递归算法的变元中 的一类(一个或几个)变元上，这类变元被称 之为递归元。
• 递归元的变化是在递归定义中确定的，它的 变化应能导致递归算法的终止。
• 在递归算法的设计中递归元是非常重要的。
不大于m的划分个数记为q(n, m)，可以建立
如的q(下n二,的元m递)递{归归关函1 系数：：
n=1或
• 最m简i=f (单1n 情< 1形) ：|| ((m1)<q1(n) , 1)r=e1t,uqrn(10,;m) =1 n, q(inf,(nm=) = 1)1|+| (qm(n=,=n–11) )return 1; n ≤ m m≥i1f ;(n == 1)q|(|n(,nm<–m1))+q(rne–tumr,nm1) +nq＞(nm, ＞n–11);
一6,个5+划1分, 4。+2正, 4整+1数+n1的, 3不+同3, 的3+划2+分1的, 个
3数+成1+为1+正1 整数n的划分数，记作ρ(n)。
2+2+2, 2+2+1+1, 2+1+1+1+1,
2021/5/21
1+1+1+1+1+1
5
第5页/共57页
正整数的划分
• 在正整数的所有不同划分中，将最大加数n1
2021/5/21
若~为除法，即n / b，则有：
T(n) = aT(n / b) + D(n)

A(1,1)=2故A(n,1)=2*n ❖ M=2时，A(n,2)=A(A(n-1,2),1)=2A(n-1,2)，和
A(1,2)=A(A(0,2),1)=A(1,1)=2，故A(n,2)= 2^n 。
2 222
❖ M=3时，类似的可以推出
n
❖ M=4时，A(n,4)的增长速度非常快，以至于没有适当的数 学式子来表示这一函数。
❖
move(a,b);
❖
hanoi(n-1, c, b, a);
❖
}
❖}
❖ T(n)=2T(n-1)+O(1) n≥1
T(n)=2n-1
0
n=0
4
27
简单递归式的求解
1.T(n)=T(n-1)+c1 n>1
c2
n=1
2. T(n)=2T(n/2)+c1 n ≥2
c2
n<2
3. T(n)=2T(n/2)+Θ(n) n ≥2
O(1)
n<2
28
T( n/2 ) + T( n/2 ) + 1
例1 T(n) =
0
(n = 1)
解 ：T(n)=2T(n/2)+1
=22T(n/22)+2+1
=23T(n/23)+22+2+1
令2r=n =2rT(1)+2r-1+。。。+2+1
=(1-2r)/(1-2)=n-1
∴ T( n ) = n - 1
25
递归算法的时间复杂度分析
❖ 递归函数求解
简单递归式求解 master method 递推方程的特征方程求解

3
算法总体思想
将要求解的较大规模的问题分割成k个更小规模的子问题。 对这k个子问题分别求解。如果子问题的规模仍然不够小，则
再划分为k个子问题，如此递归的进行下去，直到问题规模足 够小，很容易求出其解为止。
4
算法总体思想
将求出的小规模的问题的解合并为一个更大规模的问 题的解，自底向上逐步求出原来问题的解。
A(1,0)2
A(0,m)1
m0
A(n,0)n2
n2
A(n,m)A(A(n1,m),m1) n,m1
10
2.1 递归的概念
例3 Ackerman函数 A(n，m)的自变量m的每一个值都定义了一个单变
量函数： M=0时，A(n,0) =n+2 M=1时，A(n,1) =A(A(n-1,1),0)=A(n-1,1)+2，
和A(1,1)=2故A(n,1)=2*n M=2时，A(n,2) =A(A(n-1,2),1)=2A(n-1,2)，和
A(1,2)=A(A(0,2),1)=A(1,1)=2，故A(n,2)= 2^n 。
22 2 2
M=3时，类似的可以推出 n
M=4时，A(n,4)的增长速度非常快，以至于没有适源自当的数学式子来表示这一函数。
11
2.1 递归的概念
例4 排列问题 设计一个递归算法生成n个元素{r1,r2,…,rn}的全排列。 设R={r1,r2,…,rn}是要进行排列的n个元素，Ri=R-{ri}。 集合X中元素的全排列记为perm(X)。 (ri)perm(X)表示在全排列perm(X)的每一个排列前加上前 缀得到的排列。R的全排列可归纳定义如下：
(1) q(n,1)=1,n1; 当即最n大1 加 1 数n n 11不大于1时，任何正整数n只有一种划分形式，

3
2.1 Cantor三分集的递归算法
BEGIN IF ((bx-ax)<c) THEN
BEGIN
plot(ax,ay)-(bx,by)
END
ELSE
BEGIN
算法：Cantor(ax,ay,bx,by)
plot(ax,ay)-(bx,by)
标题：Cantor三分集的递归算法 参数：c（终止递归的小量）
函数：plot(x1,y1)-(x2,y2)
（画直线函数）
sin( ) （正弦函数）
cos( ) （余弦函数参考）书：《分形算法与程序设计》
12
写在最后
经常不断地学习,你就什么都知道。你知道得越多,你就越有力量 Study Constantly, And You Will Know Everything. The More
b(n-1)
c(n-1)
y=y+len
x=x+len
lineto (x,y)
lineto (x,y)
a(n-1)
d(n-1)
END
END
END参考书：《分形算法与E程N序D设计》
d(n) BEGIN
IF n>0 THEN
BEGIN a(n-1) y=y-len lineto (x,y) d(n-1) x=x+len lineto (x,y) d(n-1) y=y+len lineto (x,y) c(n-1)
参数：c（终止递归的小量） PI（π值）
变量：ax,ay（线段端点坐标） bx,by（线段端点坐标） cx,xy （线段端点坐标） dx,dy（线段端点坐标） ex,ey （线段端点坐标） L （线段长度） alpha （基线与水平线正 方向夹角）