# GESP等级：四级 | GESP Python 四级考点 """ 第1节 GESP真题实战 —— 综合算法实战课 本文件包含4个核心程序： 程序1：枚举法 —— 完全平方数（GESP三级真题） 程序2：模拟法 —— 小猫分鱼（GESP四级真题） 程序3：排序法 —— 图形大小排序 程序4：递推法 —— 斐波那契螺旋 + 爬楼梯走法 使用方法： 每个程序独立运行，取消对应的注释即可。 建议按顺序逐个运行学习。 """ # ============================================================ # 程序1：枚举法 —— 完全平方数 # GESP三级真题：找出1~1000之间的所有完全平方数 # ============================================================ def program1_perfect_squares(): """ 功能：用枚举法找出1~1000之间所有完全平方数，并用turtle可视化 知识点：math.sqrt(), 枚举思想, turtle.write() """ import math import turtle # ---- 初始化 ---- t = turtle.Turtle() t.speed(5) # 速度适中，不要太快也不要太慢 t.penup() t.goto(-350, 200) # 从屏幕左上角开始写 # ---- 变量准备 ---- count = 0 # 计数器：找到了几个完全平方数 numbers_per_line = 10 # 每行显示几个数 # ---- 枚举：从1到1000挨个检查 ---- for n in range(1, 1001): # 计算平方根 root = math.sqrt(n) # 判断平方根是不是整数 # 如果是整数，说明n是完全平方数 if root == int(root): count += 1 # 在屏幕上写出这个数 t.write(n, font=("Arial", 12, "normal")) t.forward(50) # 每写满一行就换行 if count % numbers_per_line == 0: t.backward(numbers_per_line * 50) t.right(90) t.forward(25) t.left(90) # ---- 输出统计结果 ---- t.goto(-350, -50) t.write(f"找到啦！1~1000之间共有 {count} 个完全平方数！", font=("SimHei", 16, "bold")) # ---- 用print再输出一次（方便看） ---- print("1~1000之间的完全平方数：") print(f"一共找到了 {count} 个！") t.hideturtle() turtle.done() # ============================================================ # 程序2：模拟法 —— 小猫分鱼 # GESP四级真题：逆推模拟分鱼过程 # ============================================================ def program2_cat_fish(): """ 功能：用模拟法（逆向思维）解决小猫分鱼问题 知识点：逆向模拟, for循环, turtle可视化 题目：小猫每天吃掉一半鱼加1条，第5天剩1条，一开始有多少？ """ import turtle # ---- 初始化 ---- t = turtle.Turtle() t.speed(2) t.penup() # ---- 标题 ---- t.goto(-200, 200) t.write("小猫分鱼——逆向模拟过程", font=("SimHei", 18, "bold")) # ---- 模拟逆推过程 ---- fish = 1 # 第5天吃完后只剩1条 y_pos = 150 # 从第5天倒推到第1天 for day in range(5, 0, -1): # 逆推公式：吃之前 = (吃之后 + 1) * 2 fish = (fish + 1) * 2 # 在屏幕上显示 t.goto(-150, y_pos) t.write(f"第{day}天吃之前有 {fish} 条鱼", font=("Arial", 14, "normal")) # 画鱼的数量（用圆圈表示） t.goto(150, y_pos) for i in range(min(fish, 20)): # 最多画20条 t.dot(8, "orange") t.forward(15) y_pos -= 40 # ---- 输出最终答案 ---- t.goto(-200, y_pos - 20) t.write(f"答案：一开始有 {fish} 条鱼！", font=("SimHei", 16, "bold")) print("=== 小猫分鱼问题 ===") print(f"一开始有 {fish} 条鱼") t.hideturtle() turtle.done() # ============================================================ # 程序3：排序法 —— 图形大小排序 # 用选择排序对turtle画的图形按面积排序 # ============================================================ def program3_sort_shapes(): """ 功能：画出5个大小不同的正方形，按面积从小到大排序 知识点：选择排序, turtle绘图, random随机数 """ import turtle import random # ---- 初始化 ---- t = turtle.Turtle() t.speed(3) # ---- 生成5个随机大小的正方形 ---- squares = [] # 存面积 sizes = [] # 存边长 for i in range(5): size = random.randint(30, 80) area = size * size squares.append(area) sizes.append(size) print("排序前的面积：", squares) # ---- 定义画正方形的函数 ---- def draw_square(t, size, x, y): """在(x, y)位置画一个边长为size的正方形，下面标面积""" t.penup() t.goto(x, y) t.pendown() t.color("blue") t.begin_fill() for _ in range(4): t.forward(size) t.right(90) t.end_fill() # 标面积 t.penup() t.goto(x, y - 25) t.color("red") t.write(f"面积={size*size}", font=("Arial", 10, "normal")) # ---- 画排序前的图形 ---- t.goto(-300, 100) t.write("排序前：", font=("SimHei", 14, "normal")) x_start = -250 for i in range(5): draw_square(t, sizes[i], x_start + i * 120, 50) # ---- 选择排序（带可视化） ---- t.goto(-300, -20) t.write("排序过程：", font=("SimHei", 14, "normal")) # 复制一份用于排序 arr = squares[:] size_arr = sizes[:] for i in range(len(arr)): # 找从i到末尾的最小值 min_idx = i for j in range(i + 1, len(arr)): if arr[j] < arr[min_idx]: min_idx = j # 交换面积和边长 arr[i], arr[min_idx] = arr[min_idx], arr[i] size_arr[i], size_arr[min_idx] = size_arr[min_idx], size_arr[i] # 画出当前状态 t.color("green") draw_square(t, size_arr[i], x_start + i * 120, -70) # 在控制台输出 print(f"第{i+1}轮：选面积{arr[i]}放到第{i+1}位") # ---- 输出排序结果 ---- print("排序后的面积：", arr) t.penup() t.goto(-300, -130) t.color("purple") t.write("排序完成！面积从小到大排列", font=("SimHei", 16, "bold")) t.hideturtle() turtle.done() # ============================================================ # 程序4：递推法 —— 斐波那契螺旋 + 爬楼梯走法 # ============================================================ def program4_fibonacci_spiral(): """ 功能：用斐波那契数列画螺旋线 知识点：递推思想, turtle.circle(), 斐波那契数列 """ import turtle # ---- 初始化 ---- t = turtle.Turtle() t.speed(0) # 最快速度 t.pensize(2) t.color("blue") # ---- 生成斐波那契数列 ---- fib = [1, 1] for i in range(15): # 生成15个斐波那契数 fib.append(fib[-1] + fib[-2]) print("斐波那契数列前17项：", fib[:17]) # ---- 画螺旋 ---- t.penup() t.goto(0, 0) t.pendown() for i in range(17): t.circle(fib[i], 90) # 画90度圆弧，半径=斐波那契数 # 写上数字 t.write(fib[i], font=("Arial", 8, "normal")) t.hideturtle() turtle.done() def program4_stair_climbing(): """ 功能：计算爬楼梯走法并可视化 知识点：递推公式 f(n) = f(n-1) + f(n-2), 递归/循环两种实现 """ import turtle # ---- 方法1：循环递推（推荐） ---- def count_ways_loop(n): """用循环递推算爬楼梯走法数""" if n == 1: return 1 if n == 2: return 2 a, b = 1, 2 for i in range(3, n + 1): a, b = b, a + b return b # ---- 方法2：递归（理解原理用） ---- def count_ways_recursive(n): """用递归算爬楼梯走法数（效率低，仅用于理解）""" if n == 1: return 1 if n == 2: return 2 return count_ways_recursive(n - 1) + count_ways_recursive(n - 2) # ---- 方法3：递归 + 可视化所有走法 ---- def draw_all_ways(t, n, path="", x=0, y=0): """递归画出所有走法""" if n == 0: # 画出台阶 for step in path: if step == "1": t.write("1步", font=("Arial", 10, "normal")) t.forward(60) else: t.write("2步", font=("Arial", 10, "normal")) t.forward(80) # 换行 t.backward(len(path) * 50) t.right(90) t.forward(25) t.left(90) return if n >= 1: draw_all_ways(t, n - 1, path + "1") if n >= 2: draw_all_ways(t, n - 2, path + "2") # ---- 主程序 ---- t = turtle.Turtle() t.speed(2) t.penup() # 题目 t.goto(-200, 250) t.write("爬楼梯问题：每次走1阶或2阶", font=("SimHei", 16, "bold")) # 计算走法数 n = 10 ways_loop = count_ways_loop(n) ways_recursive = count_ways_recursive(n) t.goto(-200, 210) t.write(f"上{n}阶楼梯共有 {ways_loop} 种走法", font=("SimHei", 14, "normal")) print(f"=== 爬楼梯问题（n={n}）===") print(f"循环递推结果：{ways_loop}") print(f"递归结果：{ways_recursive}") # 展示走法（用较小的n=5展示） show_n = 5 show_ways = count_ways_loop(show_n) t.goto(-200, 160) t.write(f"下面展示n={show_n}时的{show_ways}种走法：", font=("SimHei", 12, "normal")) # 画所有走法 t.goto(-200, 120) draw_all_ways(t, show_n, "", -200, 120) t.hideturtle() turtle.done() # ============================================================ # 程序入口：选择想运行的程序 # ============================================================ if __name__ == "__main__": print("=" * 50) print(" GESP真题实战 —— 四大算法演示") print("=" * 50) print("请选择要运行的程序：") print("1 - 枚举法：完全平方数") print("2 - 模拟法：小猫分鱼") print("3 - 排序法：图形大小排序") print("4 - 递推法：斐波那契螺旋") print("5 - 递推法：爬楼梯走法") print("=" * 50) choice = input("请输入数字(1-5)，直接回车默认运行全部：") if choice == "1": program1_perfect_squares() elif choice == "2": program2_cat_fish() elif choice == "3": program3_sort_shapes() elif choice == "4": program4_fibonacci_spiral() elif choice == "5": program4_stair_climbing() else: # 默认运行全部（需要关闭一个窗口才能运行下一个） print("\n正在运行程序1：完全平方数") print("关闭turtle窗口后自动运行下一个程序\n") # 注意：实际运行时建议逐个取消注释 # program1_perfect_squares() # program2_cat_fish() # program3_sort_shapes() # program4_fibonacci_spiral() # program4_stair_climbing() print("请取消注释你想运行的程序，或输入数字选择。")