xmtommy
xmtommy
2021-02-23 16:31

python语言,海龟作图,使用递归时,广度优先和深度优先表现不一致

  • python

海龟库本身带了一些demo,其中有一个例子是用递归画一棵树,使用的是广度优先策略,我将其略微改编写成了如下maketree2函数,另外我还写了一个深度优先的版本maketree1。然而在测试的时候出现了让我抓狂的情形,maketree1总是比maketree2少画一层。最后一次的测试是在每画一层的时候均在起笔处写上层序号,依然还是发现maketree1在标注完最后一层之后不作图,请帮忙解答一下。

from turtle import *

# 深度优先版本
# ltur:当前左分支海龟,length:树枝长度,angle:左右分支偏转角度,ratio:下一层长度比例,lenlimit:最短长度限制
def maketree1(ltur, length, angle, ratio, lenlimit=3):
    global count, layer                               # 测试用
    if length>lenlimit:
        layer += 1                                        # 测试用
        print(layer, length)
        turlist = [ltur]
        rtur = ltur.clone()
        ltur.write(str(layer))                          # 测试用
        ltur.lt(angle)
        rtur.rt(angle)
        ltur.fd(length)                                  # 画出左右分支
        rtur.fd(length)
        turlist.append(rtur)
        # count += 2
        # print(count)
        for t in turlist:
            maketree1(t, length*ratio, angle, ratio, lenlimit)
            # count -= 1
            # print(count)
        layer -= 1


# 广度优先版本
# lastlist:本层所有分支列表
# currentlist :下一层将要作图的所有分支
def maketree2(lastlist, length, angle, ratio, lenlimit=3):
    global count, layer
    if length>lenlimit:
        layer += 1
        print(layer, length)
        currentlist = []
        for ltur in lastlist:
            ltur.write(str(layer))
            ltur.fd(length)                             # 画出当前分支
            rtur = ltur.clone()
            ltur.lt(angle)
            rtur.rt(angle)
            currentlist.append(ltur)
            currentlist.append(rtur)
            # count += 2
        # print(count)
        maketree2(currentlist, length*ratio, angle, ratio, lenlimit)
        layer -= 1
        # count -= len(currentlist)
        # print(count)


def main():
    global count, layer
    count = 0
    firstlen = 200
    angle = 65
    ratio = 0.6375
    lenlimit = 60
    t = Turtle()
    # t.setundobuffer(None)
    t.ht()
    t.lt(90)
    t.up()
    t.bk(firstlen)
    t.down()
    # tracer(36, 0)
    tracer(False)
    # 深度优先测试
    layer = 1
    t.fd(firstlen)
    maketree1(t, firstlen*ratio, angle, ratio, lenlimit)
    # 广度优先测试   
    # layer = 0
    # maketree2([t], firstlen, angle, ratio, lenlimit)
    print('time', time.process_time())
    return 'ok'


if __name__=='__main__':
    print(main())
    mainloop()

  • 点赞
  • 回答
  • 收藏
  • 复制链接分享

0条回答

为你推荐

换一换