开创递归映射的新思路②——破解二叉树的奥秘

方法. 因此递归图，“二叉树”有四种基本的绘制方法.

干二叉树的绘制方法

典型的“干式二叉树” TREE01 80 5和模式图

以上是典型的“二叉树”. 其模式图如下所示: 主干的下端是整个程序的“递归起点”，并且执行FD

: 在B之后，乌龟移至主干顶部. 如果选择先在右侧绘制分支，当然是RT45. 然后执行“中间递归”命令:

TREE01: B / 2: N-1

请注意: 在编写此递归命令后，应理解-稍后绘制的具有更深递归的分支都已移交给计算机.

在此中间递归命令中，: B / 2表示“下一级图形的大小减小到上一级图形的一半”: N-1表示其余系列是前一系列减去1.

处理右叉，也处理左叉. 因此，我希望LT 90转向左侧的分支. 接下来是递归命令，在左侧绘制分支:

TREE01: B / 2: N-1

在所有此类中间递归程序中，必须在最后将乌龟“置零”. 这样，RT 45 BK将最终被执行

: B命令. 乌龟回到起点.

到TREE01

: B: N；第一个用于绘制树的递归程序

使用: N来控制系列

如果: N = 0，那么

停止

FD: B RT

45

;画出行李箱并向右转到执行递归

TREE01: B / 2

: N-1

LT

90

;左转到执行递归

TREE01: B / 2

: N-1

RT 45 BK

: B

;将海龟归零

END

TREE01流程中的以下问题需要澄清:

（1）

“中间递归”程序在计算机内部执行非常复杂，但是它也非常有规律: 每次绘制一定级别的图形时，计算机都会立即记录乌龟的位置和方向，然后移至下一个级别...绘制最后一个级别时，请遵循每个级别的记录位置和方向，并逐渐返回到上一个级别，直到完成所有绘画，然后乌龟返回到起点. 这就是编写此类程序时必须将乌龟“清零”的重要原因.

程序中的IF: N = 0 THEN

STOP命令行并不意味着程序执行将在此时停止，而是将控制“树”的分支执行到指定级别（N = 0），而不再绘制到更深的级别，但逐渐回到以前的水平. 如果尚未完成绘制，请继续绘制其他叉子...

如果在TREE01的过程中添加WAIT

100命令，减慢了计算机执行程序的过程，可以看到乌龟一步步向前和向后前进，最后“归零”的整个过程.

到TREE01

: B: N；演示观察中间递归运动过程的过程

如果: N = 0，那么

停止

FD: B RT 45等待

100

TREE01: B / 2

: N-1

LT 90等待

100

TREE01: B / 2

: N-1

RT 45 BK: B WAIT

100

END

（2）在程序中: B / 2允许多个表达式. 例如: B * 0.5与: B / 2相同. 在某些程序中，将B乘以黄金分割数0.618并写成: B * 0.618. 实际上，写为: B / 3，: B / 4，: B * 0.25，: B * 0.8等，都取决于程序员的需求. 如果要绘制一个分支比上一个分支更低的树，则可以使用: B * 1.5 、: B * 2等. 中间递归程序还允许在多个中间递归中使用不同的减量（增量）索引. 命令在需要时. 例如: 根据程序员的想法，第一行中间的递归命令写为: B / 2，下一行写为: B / 3，依此类推，需要专门设置.

（3）TREE01过程是首先绘制右叉. 只要可以根据新思路调整RT和LT转向指令，也可以先在左侧划叉，然后在右侧划叉. 并且两个叉之间的总角度不必为90度. 您可以通过随机指定角度来绘制不同的形状. 上面绘制的二叉树严格双向对称. 实际上，中间递归程序可能不是双向对称的. 这种类型的程序只需要在最后将乌龟归零即可. 这些原则可以灵活应用.

“干二叉树”的级别也可以通过“检测分支长度”来控制.

到TREE02

: B1: B2；使用“检测分支长度”来控制阶段数

IF: B1 <: B2

停止时；如果分支短于: B2，请停止

FD: B1 RT

45

;画出行李箱并向右转到执行递归

TREE02: B1 / 2

: B2

LT

90

;左转到执行递归

TREE02: B1 / 2

: B2

RT 45 BK

: B1

;将海龟归零

END

该程序其他部分的原理与TREE01相同. 如果执行DRAW TREE02 80

2命令，然后乌龟绘制一个长度为80、40、20、10、5、2.5的6级树. 当2.5 / 2 = 1.25时，满足以下条件: B1 <: B2，并且应停止叉子的递归.

使用N-1和: B1 <: B2来控制递归序列的区别在于: 使用: N-1方法可以准确地预设递归序列，但不能直接确定最后一级的大小（如果您想知道您需要计算的大小）. 使用: B1 <: B2可以准确地预测图形的最后一个级别的大小限制，但不能直接确定递归级别（如果您想知道该级别，则需要计算）.

要绘制递归图形的模式图，您需要使用TOOLS程序. 使用TOOLS文件名保存以下过程，并在需要时调用它们.

工具

;绘制递归图案的工具

DRAW HT

QIDIAN

PU SETX 50 PD

DIGUI

PU SETX 100 PD

CHAHUA

END

去祁店

;绘制起点符号的命令

PU FD 4 RT 90

PD

REPEAT 360 [FD 4 * PI / 180 RT

1];画一个小圆圈起点

PU LT 90 FD 4 RT90

PD

REPEAT 360 [FD 8 * PI / 180 RT

1];画一个大圆圈起点

SETW 3 LT 90 FD 17 YMBK 8

SETW 1

PU BK 8PD

END

去YM

;图纸顶部的羽毛符号开始

SETW1

REPEAT 3 [RT 120 FD 9BK 9 RT

120 FD 9 BK 9 RT 120 BK 3]

END

到DIGUI

;绘制递归点符号的命令

SETW 8 DOT SEXCOR

YCOR;点在画的底部

SETW 3 FD 38 RT 150 FD9 BK 9

;绘图棒和箭头

LT 300 FD 9 BK 9 RT150 BK 38

SETW 1

END

去查华

;绘制插花点符号的命令

SETW 8 DOT SEXCOR

YCOR;点在画的底部

SETW 3 FD 28 LT

60

;绘图栏

REPEAT 5 [PU FD 5 PDFD 7 PU

BK 12 RT 30];图片的顶部是交叉的

LT 90 BK 28 PDSETW

1

END

现在有必要讨论如何绘制“递归模式图”的主题. 以下是一些简单的转换原则:

首先，所有递归模式图都是从原始递归程序转换而来的.

第二，所有原始的条件控制语言，例如IF: N = 0 THEN STOP都被DRAWHT取代

QIDIAN将初始化屏幕并绘制“起点”.

3. 所有递归命令（例如TREE01: B / 2: N-1）都将替换为DIGUI来绘制递归符号.

第四，原始程序中的其他语句将保持不变.

五，在执行上述“重塑”和“翻译”之后运行程序之前，必须首先使用LOAD命令将先前的TOOLS程序转移到计算机的内存中递归图，否则“递归模式图”中的那些特殊符号将无法显示.

在林先生编写的“ LOGO语言竞赛问题集”和“ LOGO语言竞赛教程”中，以类似的方式绘制了数百个递归模式图. 可以根据此转换任何其他类型的“递归模式图”.

下面已转换为TR01MS 100的过程（: B值达到100）绘制了先前的二叉树的“模式图”.

到TR01MS

: B；绘制图案图程序

DRAW HT

QIDIAN

;画出“起点”

FD: B RT

45

;画出行李箱并向右转到执行递归

RT45

DIGUI

;在右侧绘制“递归点”

LT90

DIGUI

;在左侧绘制“递归点”

END

如前所述，“二叉树”有四种绘制方法. 有关更详细的讨论，请参阅Lin编写的“ LOGO语言竞赛问题集”和“ LOGO语言竞赛教程”.

使用“递归模式图”的优势显而易见. 可以通过以下示例进行说明:

这种由球组成的美丽的“二叉树”过去很难解释. 现在看一下右侧的递归模式图，您可以像这样理解它:

整个图形的递归起点在图形的底部；

如果是“顺时针”绘图，则应首先向左旋转90度，然后绘制135度的弧；

现在，我们已经到达左侧的递归点. 此时，您必须向左旋转90度，指向递归方向并执行递归；

向右转90度，并继续在球上方绘制90度弧线；

此时，已经达到第二个递归点，向左旋转90度，指向递归方向并执行第二个递归；

然后右转90度并绘制剩余的135度圆弧；

啊哈！最后，您必须向右转90度，然后乌龟才能恢复其原始状态. 这是“调零”.

关于程序如何绘制整个图形，我们无需考虑. 但是我们心中很清楚的一点是: 递归点包含整个程序的所有信息（因为“递归”是调用自身的整个程序），因此图形的下一层总是非常相似.

根据先前的想法，该程序是这样编写的:

对秋树: R

: N；球树

IF: N = 0

停止

;用途: N以控制系列

LT 90 REPEAT 135 [FD: R * PI / 180 RT 1] LT 90

;转到左侧

QIUSHU: R / 2

: N-1

;左侧递归

RT 90 REPEAT 90 [FD: R * PI / 180 RT 1] LT

90;转到右侧

QIUSHU: R / 2

: N-1]

;右递归

RT 90 REPEAT 135 [FD: R * PI / 180 RT 1] RT 90

;重置为零

END

过去真的没有办法解释这种程序. 但是现在看来似乎更容易理解.

在林先生写的“ LOGO语言竞赛问题集”和“ LOGO语言竞赛教程”中，所有数百种递归图形都标有“递归模式图”，这对LOGO语言学习者来说非常重要. . 非常方便. 让我们自己找一本书.

待续

有关LOGO语言编程最新思想的文章，请参考:

“分形”理论: 实现LOGO编程新飞跃的利器

开创了递归映射的新思路①-认识“递归模式图”

开创递归映射的新思路②——破解二叉树的奥秘

开创递归绘图的新思维③---学习“插花艺术”

有关使用程序换行号“ \”的提示，请参阅:

设置换行号“ \”以重塑LOGO编程风格

这是新的有趣的LOGO，DEV-C语言主页

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-228179-1.html