「Mac玩转仓颉内测版50」小学奥数篇13 - 动态规划入门

本篇将通过 Python 和 Cangjie 双语介绍动态规划的基本概念，并解决一个经典问题：斐波那契数列。学生将学习如何使用动态规划优化递归计算，并掌握编程中的重要算法思想。

---

关键词

• 小学奥数
• Python + Cangjie
• 动态规划
• 斐波那契数列

---

一、题目描述

斐波那契数列的定义如下：

• F(0) = 0, F(1) = 1
• F(n) = F(n-1) + F(n-2)（当 n ≥ 2）

请编写程序，接收一个非负整数 n，并输出 F(n) 的值。要求使用动态规划解决问题，以避免重复计算。

输入格式：

• 一个非负整数 n。

输出格式：

• 输出 F(n) 的值。

---

解题思路

1. 递归问题的优化：普通递归会导致大量重复计算。使用动态规划将计算结果存储起来，避免重复运算。
2. 动态规划实现方式：采用自底向上的方式，逐步计算每个状态的结果。

---

二、Python 实现

import matplotlib.pyplot as plt# 计算斐波那契数列的第 n 项
def fibonacci(n):dp = [0] * (n + 1)  # 初始化数组if n > 0:dp[1] = 1for i in range(2, n + 1):dp[i] = dp[i - 1] + dp[i - 2]return dp[n], dp  # 返回结果和完整序列# 绘制斐波那契数列的图像并保存
def plot_fibonacci_sequence(n):_, sequence = fibonacci(n)plt.plot(range(n + 1), sequence, marker='o')plt.title(f"斐波那契数列前 {n} 项")plt.xlabel("n")plt.ylabel("F(n)")plt.grid(True)filename = "fibonacci_sequence.png"plt.savefig(filename)  # 保存图像到本地print(f"图形已保存为 {filename}")plt.show()# 输入并计算
n = int(input("请输入一个非负整数 n: "))
result, _ = fibonacci(n)
print(f"F({n}) = {result}")plot_fibonacci_sequence(n)  # 绘制并保存图像

---

三、Cangjie 实现

package cjcDemo// 导入必要的标准库模块
import std.convert.*    // 数据类型转换模块
import std.console.*    // 控制台输入输出模块// 定义一个函数，读取用户输入的整数，并返回 Int64 类型的值
func inputInt(info: String): Int64 {print(info)  // 输出提示信息到控制台let number: Int64 = Int64.parse(Console.stdIn.readln().getOrThrow())  // 读取用户输入并转换为 Int64return number  // 返回输入的整数
}// 计算斐波那契数列的第 n 项，并返回该项的值及完整数列
func fibonacci(n: Int64): (Int64, Array<Int64>) {// 创建一个大小为 n+1 的数组，用于存储斐波那契数列的各项，初始化为 0let dp = Array<Int64>(n + 1, repeat: 0)// 如果 n 大于 0，则设置第一项为 1（F(1) = 1）if (n > 0) {dp[1] = 1}// 使用循环计算斐波那契数列的每一项，避免重复计算for (i in 2..=n) {dp[i] = dp[i - 1] + dp[i - 2]  // 当前项为前两项之和}// 返回第 n 项的值和完整的斐波那契数列数组return (dp[n], dp)
}// 主函数，程序入口
main(): Int64 {// 调用 inputInt 函数，提示用户输入非负整数 nlet n = inputInt("请输入一个非负整数 n: ")// 调用 fibonacci 函数，计算第 n 项及完整的斐波那契数列let (result, sequence) = fibonacci(n)// 输出第 n 项的值println("F(${n}) = ${result}")// 输出斐波那契数列的所有项println("斐波那契序列:")for (i in 0..sequence.size) {println("F(${i}) = ${sequence[i]}")  // 按格式输出每一项的值}return 0  // 返回 0 表示程序成功执行
}

---

代码详解

1. 存储中间结果：使用数组保存每一步计算的结果，避免重复运算。
2. Python 中，绘制斐波那契数列的图像并保存为本地文件。
3. Cangjie 实现输出整个斐波那契序列，帮助学生理解计算过程。

---

示例执行

示例 1：

输入：
n = 5
输出：
F(5) = 5

示例 2：

输入：
n = 10
输出：
F(10) = 55

---

四、图形展示

以下代码展示了斐波那契数列的前 10 项，并保存为 fibonacci_sequence.png：

plot_fibonacci_sequence(10)

生成的图像如下：

---

小结

通过这道斐波那契数列的题目，学生学习了动态规划的思想，并理解了如何使用编程优化递归算法。动态规划是一种重要的算法思想，常用于解决多阶段决策问题。

---

上一篇： 「Mac玩转仓颉内测版49」小学奥数篇12 - 图形变换与坐标计算

下一篇： 「Mac玩转仓颉内测版51」基础篇13 - 高阶函数与闭包

---

作者：SoraLuna
链接：https://www.nutpi.net/thread?topicId=399
來源：坚果派
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

---