中等 · 滑动对

斐波那契数

F(0)=0、F(1)=1、F(n)=F(n−1)+F(n−2)。用滑动对算——再回头对比第 5 课的指数级递归。

题目

输入:一个整数 n(0 ≤ n ≤ 45)。

输出:F(n),其中 F(0) = 0,F(1) = 1。(F(45) = 1,134,903,170 —— 能装进 int 的最大值。)

样例:

输入	输出
`10`	`55`
`20`	`6765`

Program.cs — 你的解答

"用我的输入试跑"的自定义输入

判题完全在你的浏览器里对隐藏测试运行。代码随打随存(本地)。Ctrl+Enter 判题。

提示 1 —— 滑动对

两个变量 a = 0, b = 1。每轮:int t = a + b; a = b; b = t;。n 轮之后,a 就是 F(n)。

提示 2 —— 为什么不用第 5 课的递归?

递归算 Fib(45) 要约 20 亿次调用。滑动对只要 45 次。同样的数学,指数级的成本差——这就是算法思维。

解答(先自己试!)

int n = int.Parse(Console.ReadLine());
int a = 0, b = 1;
for (int i = 0; i < n; i++) { int t = a + b; a = b; b = t; }
Console.WriteLine(a);

你已经到了题库的顶——回目录复习,或去读第 5 课看看递归什么时候才是对的工具。