0

我被要求实现一个递归函数，它以非负整数 n 作为输入并返回用字母 L、R 和 F 编码的海龟指令，其中 L 表示向左旋转 45 度，R 表示向右旋转 45 度，F 表示前进。

我有 i 的附加信息：对于每个非负整数 n>0，Levy 曲线L(n)可以根据 Levy 曲线定义L(n-1)；Levy曲线L(0)只是一条直线。

    usage:
    >>> lev(0)
    'F'
    >>> lev(1)
    'LFRRFL'

我对此很陌生，我不知道如何开始：

到目前为止，我只得到：

    from turtle import Screen, Turtle
    def lev(n):
        # base case
        if n ==0:
           return 'F'
        # recursive case
        else:
            return lev(n-1)

我需要一些好的指示。

4

3 回答 3

5

由于Levy C的L 系统只有一个规则，因此使用单个替换方法构建结果字符串很简单。

def lev(n):
    if n == 0:
        return "F"
    else:
        symbols = lev(n-1)
        return symbols.replace("F", "LFRRFL")

for i in range(4):
    print lev(i)

结果：

F
LFRRFL
LLFRRFLRRLFRRFLL
LLLFRRFLRRLFRRFLLRRLLFRRFLRRLFRRFLLL

您可以通过想象图中的每条直线被以 90 度角连接的两条较小的线替换来可视化这种替换。像这样：

在此处输入图像描述

于 2013-05-30T19:54:22.097 回答
1

首先，如果这是问题所在：一个大的 Levy 曲线（递归情况）是通过将两个较小的曲线“穿过房间”布置成彼此相对的，另外两个“在地板上”朝上，介于两者之间。一条小的 Levy 曲线（基本情况）只是一条直线。事实上，基本情况是：

def lev(n):
    if n == 0:
        return 'F'
    else:
        # Recursive case here

但是对于递归的情况，你只需调用 lev(n-1)。你是对的，你需要这样做，但你需要做四次，并在两者之间轮换。这将创建所需的“两条彼此相对的较小曲线，中间有两条曲线”。

仔细检查曲线（这里：https ://en.wikipedia.org/wiki/File:Levy_C_construction.png ），我们看到我们需要画一条曲线，然后右转，然后画另一条，然后完全转身，然后画第三条曲线，最后右转，画出最后一条曲线。

这可以相当简单地完成：

dev lev(n):
    if n == 0:
        # Base case
        return 'F'
    else:
        # Recursive case
        # Calculate the smaller curve
        smaller = lev(n-1)
        # Add in the turning in between the smaller curves
        final = smaller        # First curve
        if n%2 == 0:           # Even depths require right turns
            final += 'RR'        # Rotate 90 degrees
            final += smaller     # Second curve
            final += 'RRRR'      # Rotate 180 degrees
            final += smaller     # Third curve
            final += 'RR'        # Rotate 90 degrees
            final += smaller     # Final curve
        else:                  # Odd depths require left turns
            final += 'LL'        # Rotate 90 degrees
            final += smaller     # Second curve
                                 # (No full rotation in odd depths)
            final += smaller     # Third curve
            final += 'LL'        # Rotate 90 degrees
            final += smaller     # Final curve
        return final           # Done!
于 2013-05-30T19:41:59.683 回答
0

我的答案

import turtle

def draw(n):
    l=10
    if n == 0:
        turtle.forward(l)
    else:
         turtle.left(45)
         draw(n - 1)
         turtle.right(45)
         turtle.right(45)
         draw(n-1)
         turtle.left(45)

draw(12)
于 2020-11-10T20:32:25.667 回答