算法时间复杂度渐进分析实验报告（Python）.doc - CSDN文库

需积分: 1 21 浏览量更新于2023-11-24 收藏 1.74MB DOC 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

资源详情

资源推荐

实验名称：递归和分治

实验时间：2022.05.21

实验目的和要求：

1.递归：掌握递归算法的两个基本组成、编程实现、时间分析；

使用 turtle 模块实现递归可视化。

2.分治：掌握分治法的设计思想、求解步骤、掌握用分治法解题的算法框架。

实验内容和原理：

1.递归：分形树（自相似递归图形）

问题描述：

分形是在不同尺度上都具有相似性的事物，树的树枝形状也具有分形的特点，我们

能看出，一棵树的每个分叉和每条树枝，实际上都具有整棵树的外形特征。这样我们可

以把树分解成三个部分：树干、左边的树枝、右边的树枝。这样的分解正符合递归的定

义：对自身的调用。

编程任务：

用 turtle 模块+递归算法，设计自己的分形树

2.分治：Gray 码问题

问题描述

Gray 码是一个长度为 2n 的序列。序列中无相同的元素，每个元素都是长度为 n 位的串，

相邻元素恰好只有一位不同。用分治策略设计一个算法对任意的 n 构造相应的 Gray 码。

编程任务

利用分治策略试设计一个算法对任意的 n 构造相应的 Gray 码。

数据输入

从键盘输入或程序自动产生随机数作为输入数据 n。

结果输出

程序运行结束时，将得到的所有 Gray 码输出到屏幕

主要仪器设备：

笔记本电脑、window、Jupiter

上机调试修改源程序：

1.分形树：

import turtle as tt

import random

#花朵

def point(n,m,s1,s2):#在当前位置和当前位置附近画点，m：附近距离、s1,s2：点的颜色——

组合成一朵花

tt.dot(n, s1)#n:点的直径，s1:点的颜色

tt.penup()

tt.backward(m)#另一个位置画点

tt.pendown()

tt.dot(n//2, s2)#直径和颜色不一样

tt.penup()

tt.forward(m)#回到原来的位置

tt.pendown()

def branch(l):#产生 4 枝树枝

a=random.randint(0,l/2)#树枝长度随机

剩余18页未读，继续阅读

@小冯@

粉丝: 262
资源: 8

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈