本篇将通过 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) 的值。
解题思路
- 递归问题的优化：普通递归会导致大量重复计算。使用动态规划将计算结果存储起来，避免重复运算。
- 动态规划实现方式：采用自底向上的方式，逐步计算每个状态的结果。
二、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 表示程序成功执行
}
代码详解
- 存储中间结果：使用数组保存每一步计算的结果，避免重复运算。
- Python 中，绘制斐波那契数列的图像并保存为本地文件。
- 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
來源：坚果派
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。