「Mac玩转仓颉内测版50」小学奥数篇13

「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) 的值。

解题思路

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

二、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 表示程序成功执行
}