# GESP等级：四级 | GESP Python 四级考点
"""
==================================================
  递推算法 —— 斐波那契数列 + 黄金螺旋
  面向7-10岁少儿编程教学
==================================================

  功能：
  1. 计算斐波那契数列（递推法）
  2. 用turtle画斐波那契正方形和黄金螺旋线
  3. 爬楼梯问题求解

  口诀：
  "斐波那契兔子数列，前两个一后面加前"
  "递推往前推，递归往回拆，递推快如飞，递归慢慢来"
==================================================
"""

import turtle
import time
import math

# ==================================================
# 配置区
# ==================================================

# 画多少个斐波那契正方形（建议6~10个）
NUM_SQUARES = 8

# 每个单位长度对应的像素
SCALE = 15

# 画图速度（1=最快，10=最慢）
DRAW_SPEED = 3

# 颜色列表（正方形颜色）
SQUARE_COLORS = [
    "#FF6B6B",  # 红
    "#FFA94D",  # 橙
    "#FFD43B",  # 黄
    "#69DB7C",  # 绿
    "#4DABF7",  # 蓝
    "#9775FA",  # 紫
    "#F783AC",  # 粉
    "#63E6BE",  # 青
    "#FF8787",  # 浅红
    "#FCC419",  # 金黄
]

# ==================================================
# 递推算法函数
# ==================================================

def fibonacci(n):
    """
    计算斐波那契数列的第n项（递推法）

    口诀：a和b是前两个，循环加出后面的

    参数：
        n: 第几项（从1开始）
    返回：
        第n项的值
    """
    if n <= 0:
        return 0
    if n == 1 or n == 2:
        return 1

    a, b = 1, 1  # f(1) 和 f(2)
    for i in range(3, n + 1):
        c = a + b  # f(i) = f(i-1) + f(i-2)
        a, b = b, c  # 往前推
    return b


def fibonacci_list(n):
    """
    生成斐波那契数列的前n项（列表形式）

    参数：
        n: 项数
    返回：
        包含前n项的列表
    """
    if n <= 0:
        return []
    if n == 1:
        return [1]

    result = [1, 1]
    for i in range(3, n + 1):
        result.append(result[-1] + result[-2])
    return result


def climb_stairs(n):
    """
    爬楼梯问题：每次走1步或2步

    公式：f(n) = f(n-1) + f(n-2)
    初始：f(1) = 1, f(2) = 2

    参数：
        n: 楼梯阶数
    返回：
        走到第n阶的不同走法数量
    """
    if n <= 0:
        return 0
    if n == 1:
        return 1
    if n == 2:
        return 2

    a, b = 1, 2
    for i in range(3, n + 1):
        c = a + b
        a, b = b, c
    return b


def climb_stairs_3steps(n):
    """
    爬楼梯的变种：每次走1步、2步或3步

    公式：f(n) = f(n-1) + f(n-2) + f(n-3)
    初始：f(1)=1, f(2)=2, f(3)=4
    """
    if n <= 0:
        return 0
    if n == 1:
        return 1
    if n == 2:
        return 2
    if n == 3:
        return 4

    a, b, c = 1, 2, 4
    for i in range(4, n + 1):
        d = a + b + c
        a, b, c = b, c, d
    return c


def fibonacci_recursive(n):
    """
    递归法计算斐波那契数列（仅作对比用，速度较慢）

    警告：n > 35 时就会非常慢！
    """
    if n <= 0:
        return 0
    if n == 1 or n == 2:
        return 1
    return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2)


# ==================================================
# turtle绘图 —— 斐波那契螺旋线
# ==================================================

# 创建画布
screen = turtle.Screen()
screen.setup(900, 700)
screen.title("斐波那契螺旋线 —— 递推算法的美")
screen.bgcolor("white")
screen.tracer(0)

# 创建画笔
pen = turtle.Turtle()
pen.speed(DRAW_SPEED)
pen.hideturtle()

# 文字画笔
text_pen = turtle.Turtle()
text_pen.speed(0)
text_pen.hideturtle()
text_pen.penup()


def draw_fibonacci_spiral(num_squares=NUM_SQUARES):
    """
    画斐波那契螺旋线

    原理：
    1. 按斐波那契数列长度画正方形
    2. 在每个正方形中画四分之一圆弧
    3. 所有圆弧连起来就是螺旋线
    """
    # 计算斐波那契数列
    fibs = fibonacci_list(num_squares)
    print(f"斐波那契数列前{num_squares}项：{fibs}")

    # 重置画笔
    pen.clear()
    pen.penup()
    pen.goto(0, 0)
    pen.setheading(0)
    pen.pendown()

    # 当前位置和方向追踪
    x, y = 0, 0
    heading = 0  # 0=右, 90=上, 180=左, 270=下
    scale = SCALE

    # 显示标题
    text_pen.goto(0, 300)
    text_pen.write("🌊 斐波那契螺旋线", align="center", font=("Arial", 20, "bold"))
    text_pen.goto(0, 270)
    text_pen.write(f"前{num_squares}个正方形 | 边长 = 斐波那契数",
                   align="center", font=("Arial", 12, "normal"))

    # 画正方形和弧线
    for i in range(num_squares):
        size = fibs[i] * scale  # 正方形边长（像素）

        # 计算颜色
        color = SQUARE_COLORS[i % len(SQUARE_COLORS)]

        # 显示当前信息
        text_pen.goto(0, -320)
        text_pen.write(f"正方形 {i+1}：边长 = {fibs[i]}（f({i+1})）  当前方向：{heading}°",
                       align="center", font=("Arial", 11, "normal"))
        screen.update()
        time.sleep(0.3)

        # 画正方形（用淡色填充）
        pen.fillcolor(color)
        pen.begin_fill()
        for _ in range(4):
            pen.forward(size)
            pen.left(90)
        pen.end_fill()

        # 在正方形中心写上数字
        pen.penup()
        center_x = x + size / 2
        center_y = y - size / 2
        pen.goto(center_x - 10, center_y - 10)
        pen.write(str(fibs[i]), font=("Arial", 12, "bold"))
        pen.goto(x, y)

        # 画四分之一圆弧（螺旋线）
        pen.penup()
        # 根据方向移动到弧线起点
        if heading == 0:  # 朝右
            pen.goto(x + size, y)
        elif heading == 90:  # 朝上
            pen.goto(x + size, y - size)
        elif heading == 180:  # 朝左
            pen.goto(x, y - size)
        elif heading == 270:  # 朝下
            pen.goto(x, y)

        pen.pendown()
        pen.pencolor("#333")
        pen.width(3)

        # 画90度弧
        if heading == 0:
            pen.circle(-size, 90)
        elif heading == 90:
            pen.circle(size, 90)
        elif heading == 180:
            pen.circle(-size, 90)
        elif heading == 270:
            pen.circle(size, 90)

        # 更新位置和方向
        if heading == 0:
            x += size
            y = y
            heading = 90
        elif heading == 90:
            x = x
            y -= size
            heading = 180
        elif heading == 180:
            x -= fibs[i-1] * scale if i > 0 else 0
            y = y
            heading = 270
        elif heading == 270:
            x = x
            y += fibs[i-1] * scale if i > 0 else 0
            heading = 0

        pen.penup()
        pen.goto(x, y)
        pen.pendown()
        pen.width(1)

        screen.update()
        time.sleep(0.2)

    # 完成信息
    text_pen.goto(0, -340)
    text_pen.write("🎉 斐波那契螺旋线完成！ 看，多美啊！",
                   align="center", font=("Arial", 14, "bold"))
    screen.update()


def draw_fibonacci_bar_chart(n=10):
    """
    画斐波那契柱状图——直观展示数列的增长

    参数：
        n: 显示前几项
    """
    fibs = fibonacci_list(n)

    pen.clear()
    pen.penup()
    pen.goto(-350, -150)
    pen.pendown()

    bar_width = 50
    gap = 10

    for i in range(n):
        height = fibs[i] * 5  # 缩放

        # 颜色渐变：从红到紫
        r = 1.0 - i / n
        g = 0.2
        b = i / n
        pen.fillcolor(r, g, b)

        # 画柱子
        pen.begin_fill()
        x = -350 + i * (bar_width + gap)
        pen.penup()
        pen.goto(x, -150)
        pen.pendown()
        pen.goto(x, -150 + height)
        pen.goto(x + bar_width, -150 + height)
        pen.goto(x + bar_width, -150)
        pen.goto(x, -150)
        pen.end_fill()

        # 写数字
        pen.penup()
        pen.goto(x + bar_width / 2, -150 + height + 10)
        pen.write(str(fibs[i]), align="center", font=("Arial", 10, "bold"))

    # 标题
    text_pen.goto(0, 250)
    text_pen.write("📊 斐波那契数列柱状图", align="center",
                   font=("Arial", 16, "bold"))
    text_pen.goto(0, 220)
    text_pen.write(f"前{n}项 | 递推公式：f(n) = f(n-1) + f(n-2)",
                   align="center", font=("Arial", 11, "normal"))
    screen.update()


# ==================================================
# 主控函数
# ==================================================

def run_demo():
    """运行完整演示"""
    print("🌟 欢迎来到递推算法世界！")
    print("=" * 50)
    print()

    # 1. 显示斐波那契数列
    print("1️⃣ 斐波那契数列（前20项）：")
    print("   ", end="")
    fibs = fibonacci_list(20)
    for i, f in enumerate(fibs):
        print(f, end=" " if (i+1) % 5 else "\n   ")
    print()
    print(f"   f(20) = {fibonacci(20)}")
    print()

    # 2. 速度对比
    print("2️⃣ 递推 vs 递归 速度对比：")
    import time

    start = time.time()
    f = fibonacci(35)
    t_recursion = time.time() - start
    print(f"   递推法 f(35) = {f}，耗时：{t_recursion:.6f}秒")

    start = time.time()
    f = fibonacci_recursive(35)
    t_recursive = time.time() - start
    print(f"   递归法 f(35) = {f}，耗时：{t_recursive:.6f}秒")
    print(f"   递推比递归快 {t_recursive / t_recursion:.0f} 倍！")
    print()

    # 3. 爬楼梯问题
    print("3️⃣ 爬楼梯问题（每次走1或2步）：")
    for i in [1, 2, 3, 5, 10, 15, 20]:
        print(f"   {i}阶楼梯：{climb_stairs(i)}种走法")
    print()

    # 4. 爬楼梯变种
    print("4️⃣ 爬楼梯变种（每次走1、2或3步）：")
    for i in [1, 2, 3, 5, 10, 15]:
        print(f"   {i}阶楼梯：{climb_stairs_3steps(i)}种走法")
    print()

    print("5️⃣ turtle图形演示已打开...")


def show_menu():
    """显示交互菜单"""
    print()
    print("=" * 40)
    print("请选择演示内容：")
    print("1. 斐波那契螺旋线（默认）")
    print("2. 斐波那契柱状图")
    print("3. 先螺旋线再柱状图")
    print("=" * 40)


# ==================================================
# 交互控制
# ==================================================

def on_click_reset(x, y):
    """点击屏幕重新绘图"""
    print("🔄 重新绘制斐波那契螺旋线...")
    text_pen.clear()
    screen.update()
    draw_fibonacci_spiral()


# ==================================================
# 主程序入口
# ==================================================

if __name__ == "__main__":
    import sys

    run_demo()

    # 检查命令行参数
    mode = 1  # 默认螺旋线
    if len(sys.argv) > 1:
        try:
            mode = int(sys.argv[1])
        except ValueError:
            pass

    if mode == 2:
        draw_fibonacci_bar_chart(12)
    elif mode == 3:
        draw_fibonacci_bar_chart(10)
        time.sleep(2)
        pen.clear()
        screen.update()
        draw_fibonacci_spiral(8)
    else:
        draw_fibonacci_spiral(NUM_SQUARES)

    # 点击屏幕重新绘图
    screen.listen()
    screen.onclick(on_click_reset)

    print("\n💡 提示：点击屏幕可以重新画螺旋线！")
    print("💡 按 ESC 或关闭窗口退出程序")

    screen.mainloop()