# GESP等级：三级 | GESP Python 三级考点

"""
第2节 枚举法（穷举法）
===================
面向7-10岁少儿 —— 用turtle可视化枚举过程

知识点：
  - 枚举三步法：范围→遍历→判断
  - 水仙花数：153 = 1^3 + 5^3 + 3^3
  - 百钱百鸡：公鸡5/母鸡3/小鸡1元3只
  - 完美数：因子和等于本身
  - 优化思路：缩小枚举范围
"""

import turtle
import time
import random


# ============================================================
# 第一部分：基础枚举演示
# ============================================================

def demo_basic_enum():
    """基础枚举演示：找偶数和倍数"""
    print("=" * 40)
    print("【基础枚举】找1-20之间的偶数")
    print("=" * 40)

    print("范围：1~20")
    print("遍历中...", end=" ")
    for i in range(1, 21):
        if i % 2 == 0:
            print(i, end=" ")
    print("\n")

    print("【基础枚举】找1-50之间3和5的公倍数")
    print("范围：1~50")
    print("遍历中...", end=" ")
    for i in range(1, 51):
        if i % 3 == 0 and i % 5 == 0:
            print(i, end=" ")
    print()


def demo_enum_steps():
    """演示枚举三步法的思考过程"""
    print("=" * 40)
    print("【三步法演示】找1-100之间能被7整除的数")
    print("=" * 40)

    print("第一步：确定范围 → 1到100")
    print("第二步：遍历 → for i in range(1, 101)")
    print("第三步：判断 → if i % 7 == 0")
    print()

    result = []
    for i in range(1, 101):
        if i % 7 == 0:
            result.append(i)

    print(f"结果：{result}")
    print(f"共找到 {len(result)} 个数")


# ============================================================
# 第二部分：经典问题 —— 水仙花数
# ============================================================

def demo_narcissistic():
    """水仙花数 —— 用枚举法找所有三位水仙花数"""
    print("\n" + "=" * 40)
    print("【经典问题】水仙花数")
    print("=" * 40)

    print("分析步骤：")
    print("  ① 范围：所有三位数 100~999")
    print("  ② 遍历：用for循环一个个检查")
    print("  ③ 判断：百位^3 + 十位^3 + 个位^3 == 本身")
    print()

    narcissistic_numbers = []

    for num in range(100, 1000):
        # 取出百位、十位、个位
        bai = num // 100
        shi = (num // 10) % 10
        ge = num % 10

        # 计算立方和
        sum_cube = bai ** 3 + shi ** 3 + ge ** 3

        # 判断是否为水仙花数
        if sum_cube == num:
            narcissistic_numbers.append(num)
            print(f"✓ {num} = {bai}³ + {shi}³ + {ge}³ = {sum_cube}")

    print(f"\n共有 {len(narcissistic_numbers)} 个水仙花数：{narcissistic_numbers}")


# ============================================================
# 第三部分：经典问题 —— 百钱百鸡
# ============================================================

def demo_hundred_chickens():
    """百钱百鸡 —— 枚举法经典问题"""
    print("\n" + "=" * 40)
    print("【经典问题】百钱百鸡")
    print("=" * 40)

    print("问题：公鸡5元/只，母鸡3元/只，小鸡1元/3只")
    print("     用100元买100只鸡，怎么买？")
    print()

    print("第一步：确定范围")
    print("  公鸡最多 100//5 = 20只")
    print("  母鸡最多 100//3 = 33只")
    print("  小鸡 = 100 - 公鸡 - 母鸡")
    print()

    print("第二步：遍历（两层循环）")
    print("第三步：判断总价 == 100")
    print()

    count = 0
    for gong in range(0, 21):          # 公鸡：0~20
        for mu in range(0, 34):         # 母鸡：0~33
            xiao = 100 - gong - mu      # 小鸡的数量
            if xiao >= 0 and xiao % 3 == 0:  # 小鸡数量必须是3的倍数
                if gong * 5 + mu * 3 + xiao // 3 == 100:
                    count += 1
                    print(f"方案{count}：公鸡{gong}只，母鸡{mu}只，小鸡{xiao}只")

    print(f"\n共有 {count} 种买法")


# ============================================================
# 第四部分：经典问题 —— 完美数
# ============================================================

def demo_perfect_numbers():
    """完美数 —— 枚举因子"""
    print("\n" + "=" * 40)
    print("【经典问题】完美数")
    print("=" * 40)

    print("完美数：一个数等于它的所有因子之和（除自身外）")
    print("例如：6 = 1 + 2 + 3")
    print()

    limit = int(input("请输入查找范围（如10000）：") or 10000)

    print(f"\n在1~{limit}之间查找完美数...")
    print("=" * 30)

    perfect_numbers = []
    for num in range(2, limit + 1):
        # 优化：只检查到 num//2
        factors = []
        for i in range(1, num // 2 + 1):
            if num % i == 0:
                factors.append(i)

        if sum(factors) == num:
            perfect_numbers.append(num)
            print(f"✓ 找到完美数：{num} = {' + '.join(map(str, factors))}")

    if perfect_numbers:
        print(f"\n在1~{limit}之间共找到 {len(perfect_numbers)} 个完美数")
        print(f"它们是：{perfect_numbers}")
    else:
        print(f"\n在1~{limit}之间没有找到完美数")


# ============================================================
# 第五部分：枚举优化对比
# ============================================================

def demo_optimization():
    """演示枚举优化的效果"""
    print("\n" + "=" * 40)
    print("【优化对比】枚举优化前后对比")
    print("=" * 40)

    target = 100000

    # 优化前：遍历全部
    import time

    start = time.time()
    count1 = 0
    for i in range(1, target + 1):
        if target % i == 0:
            count1 += 1
    end1 = time.time()
    print(f"优化前（遍历1~{target}）：{count1}个因子，耗时{end1-start:.4f}秒")

    # 优化后：遍历到平方根
    start = time.time()
    count2 = 0
    for i in range(1, int(target ** 0.5) + 1):
        if target % i == 0:
            count2 += 2  # i 和 target//i 都是因子
    end2 = time.time()
    print(f"优化后（遍历1~√{target}）：约{count2}个因子，耗时{end2-start:.4f}秒")

    speed = (end1 - start) / (end2 - start + 0.0001)
    print(f"\n优化后快了约 {speed:.0f} 倍！")
    print("\n口诀：枚举虽然好，范围别太大！")


# ============================================================
# 第六部分：turtle可视化 —— 枚举过程
# ============================================================

def setup_screen():
    """设置画布"""
    screen = turtle.Screen()
    screen.title("枚举法 —— 一个个试，符合条件的变绿色！")
    screen.bgcolor("white")
    screen.setup(800, 600)
    screen.tracer(0)  # 关闭自动刷新，提高速度
    return screen


def draw_number(t, x, y, num, is_match=False):
    """在指定位置画一个数字"""
    t.penup()
    t.goto(x, y)
    t.pendown()

    if is_match:
        t.color("green")
        t.fillcolor("lightgreen")
    else:
        t.color("red")
        t.fillcolor("lightcoral")

    t.begin_fill()
    t.circle(20)
    t.end_fill()

    t.penup()
    t.goto(x, y - 7)
    t.color("black")
    t.write(str(num), align="center", font=("Arial", 12, "bold"))


def turtle_enum_visual():
    """用turtle可视化枚举过程"""
    screen = setup_screen()
    t = turtle.Turtle()
    t.speed(0)
    t.hideturtle()

    # 标题
    t.penup()
    t.goto(0, 260)
    t.color("darkblue")
    t.write("枚举法 —— 找1~50之间的偶数", align="center",
            font=("SimHei", 20, "bold"))

    # 副标题
    t.penup()
    t.goto(0, 230)
    t.color("gray")
    t.write("绿色 = 符合条件  红色 = 不符合条件", align="center",
            font=("SimHei", 14, "normal"))

    # 绘制数字网格
    rows, cols = 5, 10
    start_x = -350
    start_y = 150
    num = 1

    info_t = turtle.Turtle()
    info_t.hideturtle()
    info_t.penup()

    for row in range(rows):
        for col in range(cols):
            x = start_x + col * 80
            y = start_y - row * 80

            is_even = (num % 2 == 0)

            # 画数字
            draw_number(t, x, y, num, is_even)
            screen.update()
            time.sleep(0.1)

            # 显示当前检查的信息
            info_t.clear()
            info_t.goto(0, -250)
            status = "✓ 是偶数！" if is_even else "✗ 不是偶数"
            info_t.write(f"检查 {num} ... {status}",
                         align="center", font=("SimHei", 16, "bold"))

            num += 1

    # 统计结果
    info_t.clear()
    even_count = 50 // 2
    info_t.goto(0, -280)
    info_t.color("darkgreen")
    info_t.write(f"枚举完成！1~50之间有 {even_count} 个偶数",
                 align="center", font=("SimHei", 18, "bold"))

    # 小乌龟总结
    t2 = turtle.Turtle()
    t2.shape("turtle")
    t2.color("green")
    t2.penup()
    t2.goto(-350, -320)
    t2.write("口诀：范围→遍历→判断！", font=("SimHei", 14, "bold"))

    screen.mainloop()


# ============================================================
# 第七部分：互动小游戏 —— 枚举猜数字
# ============================================================

def game_guess_number():
    """枚举法猜数字游戏"""
    print("\n" + "=" * 40)
    print("【互动游戏】枚举法猜数字")
    print("=" * 40)

    secret = random.randint(1, 100)
    print("电脑想了一个1~100之间的数字，你来猜！")
    print("（用枚举法思想：从1开始一个个试）")

    # 计算机用枚举法来猜（作为演示）
    print("\n电脑用枚举法来猜：")
    for guess in range(1, 101):
        print(f"电脑尝试：{guess}")
        if guess == secret:
            print(f"✓ 找到了！秘密数字是 {guess}，用了 {guess} 次枚举")
            break


# ============================================================
# 第八部分：主程序
# ============================================================

def main():
    print("""
    ╔══════════════════════════════════╗
    ║    枚举法（穷举法）学习程序        ║
    ╚══════════════════════════════════╝
    """)

    while True:
        print("\n请选择要运行的功能：")
        print("1. 基础枚举演示（找偶数/倍数）")
        print("2. 枚举三步法详细演示")
        print("3. 水仙花数（经典问题）")
        print("4. 百钱百鸡（经典问题）")
        print("5. 完美数查找（经典问题）")
        print("6. 枚举优化对比")
        print("7. turtle枚举可视化（图形界面）")
        print("8. 枚举法猜数字游戏")
        print("9. 全部运行")
        print("0. 退出")

        choice = input("\n请输入数字（0-9）：").strip()

        if choice == "1":
            demo_basic_enum()
        elif choice == "2":
            demo_enum_steps()
        elif choice == "3":
            demo_narcissistic()
        elif choice == "4":
            demo_hundred_chickens()
        elif choice == "5":
            demo_perfect_numbers()
        elif choice == "6":
            demo_optimization()
        elif choice == "7":
            print("\n正在打开turtle图形窗口...")
            turtle_enum_visual()
        elif choice == "8":
            game_guess_number()
        elif choice == "9":
            demo_basic_enum()
            demo_enum_steps()
            demo_narcissistic()
            demo_hundred_chickens()
            demo_optimization()
            game_guess_number()
        elif choice == "0":
            print("再见！记住枚举三步法：")
            print("范围→遍历→判断！")
            break
        else:
            print("输入有误，请重新选择。")


if __name__ == "__main__":
    main()