思无涯咿呀咿呀：创建页面，内容为“ ==Fibonacci数列== 250px 250px 250px Fibonacci数列是…”

2020-10-16T01:47:25Z

创建页面，内容为“ ==Fibonacci数列== 250px 250px 250px Fibonacci数列是…”

新页面

==Fibonacci数列==

[[File:fractalandrecursive1.svg.png|250px]]
[[File:fractalandrecursive2.svg.png|250px]]
[[File:carrotspiral.jpg|250px]]

Fibonacci数列是一个很有趣的结构，每后一项都等于前两项之和。它的前几位如下：0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 134...我们可以表达该函数如下所示：

fib(0) = 0
fib(1) = 1
fib(n) = fib(n-1) + fib(n-2) for n >= 2

在python里如何表达这样一个函数呢？我们可以用递归来表达。所谓递归，就是一个函数不断引用它自身，直到抵达一个可计算出确定值的初始态。

<syntaxhighlight lang="python">
def fib(n):
if n <= 1:
return n
else:
return fib(n-1) + fib(n-2)
</syntaxhighlight>

==分形结构==

分形概念由法国数学家曼德布罗在1975年提出，用于形容局部与整体相似的形状。如下所示图案叫科赫雪花（Koch fractal），是一个典型的分形。

[[File:koch_0.png|250px]]

[[File:koch_1.png|250px]]

[[File:koch_2.png|250px]]

[[File:koch_3.png|250px]]

如何用计算机制造出这个图像呢？仔细观察并思考这个图像的绘制过程，我们会发现用递归的方式也能解决。我们称第一张图（只有一条直线）为0阶（order）雪花，第二张为1阶，以此类推。我们会发现，例如第二阶的图，可以通过引用三次第一阶的图来绘制。因此这个结构可以使用如下函数实现：

<syntaxhighlight lang="python">
def koch(t, order, size):
if order == 0:
t.forward(size)
else:
for angle in [60, -120, 60, 0]:
koch(t, order-1, size/3)
t.left(angle)
</syntaxhighlight>

其中t是一个移动的小海龟（类似netlogo里的turtle），order是层级，size是整个雪花的线性规模。如果我们不用递归，则有n阶就必须定义n个函数：

<syntaxhighlight lang="python">
def koch_0(t, size):
t.forward(size)

def koch_1(t, size):
for angle in [60, -120, 60, 0]:
koch_0(t, size/3)
t.left(angle)

def koch_2(t, size):
for angle in [60, -120, 60, 0]:
koch_1(t, size/3)
t.left(angle)

def koch_3(t, size):
for angle in [60, -120, 60, 0]:
koch_2(t, size/3)
t.left(angle)
</syntaxhighlight>

可见递归确实是一种非常简洁的思想。

==动态演化的分形结构==

[[File:recursivetree1.png|250px]] [[File:recursivetree2.png|250px]]

我们可以使用递归函数制造出分形结构，并且不断修正其中的参数，来构造动态演化的结构.为了帮助进行动态演示，下面这段程序使用了pygame模块，安装地址见[http://www.pygame.org/download.shtml 这里]。

<syntaxhighlight lang="python">
import pygame, math
pygame.init() # prepare the pygame module for use
# Create a new surface and window.
surface_size = 1024
main_surface = pygame.display.set_mode((surface_size,surface_size))
my_clock = pygame.time.Clock()

def draw_tree(order, theta, sz, posn, heading, color=(0,0,0), depth=0):
trunk_ratio = 0.29 # How big is the trunk relative to whole tree?
trunk = sz * trunk_ratio # length of trunk
delta_x = trunk * math.cos(heading)
delta_y = trunk * math.sin(heading)
(u, v) = posn
newpos = (u + delta_x, v + delta_y)
pygame.draw.line(main_surface, color, posn, newpos)
if order > 0: # Draw another layer of subtrees
# These next six lines are a simple hack to make the two major halves
# of the recursion different colors. Fiddle here to change colors
# at other depths, or when depth is even, or odd, etc.
if depth == 0:
color1 = (255, 0, 0)
color2 = (0, 0, 255)
else:
color1 = color
color2 = color
# make the recursive calls to draw the two subtrees
newsz = sz*(1 - trunk_ratio)
draw_tree(order-1, theta, newsz, newpos, heading-theta, color1, depth+1)
draw_tree(order-1, theta, newsz, newpos, heading+theta, color2, depth+1)

def gameloop():
theta = 0
while True:
# Handle evente from keyboard, mouse, etc.
ev = pygame.event.poll()
if ev.type == pygame.QUIT:
break;
# Updates - change the angle
theta += 0.01
# Draw everything
main_surface.fill((255, 255, 0))
draw_tree(9, theta, surface_size*0.9, (surface_size//2, surface_size-50), -math.pi/2)
pygame.display.flip()
my_clock.tick(120)

gameloop()
pygame.quit()
</syntaxhighlight>

[[category:python]]

[[category:旧词条迁移]]

使用python语言表达分形与递归 - 版本历史

思无涯咿呀咿呀：创建页面，内容为“ ==Fibonacci数列== 250px 250px 250px Fibonacci数列是…”