返回题库

青蛙跳荷叶

Frog and the Lily Pads

专题
Algorithmic Programming / 算法编程
难度
L2

题目详情

青蛙在池塘一边，前方有 nn 块荷叶排成一条直线，最后一块在对岸。

青蛙每次可以跳过 1 块（落到第 2 块），或跳过 2 块（落到第 3 块）。

问：青蛙到达对岸一共有多少种不同跳法？

A frog is at the edge of a pond. There are nn lily pads in a straight line in front of the frog, with the last one being right at the opposite edge of the pond. The frog wishes to get to the other side by hopping on these lily pads. The frog can jump over one lily pad (landing on the second), or make a big leap over two lily pads (landing on the third).
In how many ways can the frog get to the other side?

解析

设 F(i)F(i) 表示到达第 ii 块荷叶的走法数，则

  • F(1)=1F(1)=1，F(2)=2F(2)=2；
  • 对 i≥3i\ge 3，最后一步要么从 i−1i-1 跳 1 格，要么从 i−2i-2 跳 2 格：
F(i)=F(i−1)+F(i−2).F(i)=F(i-1)+F(i-2).

因此走法数是斐波那契数列，对应为第 (n+1)(n+1) 个斐波那契数。

Original Explanation

Let F(i)F(i) denote the number of ways the frog can reach the ithi^{\text{th}} lily pad.

  • For the first lily pad: F(1)=1F(1) = 1 The frog can jump directly onto it.

  • For the second lily pad: F(2)=2F(2) = 2 The frog can either jump directly onto it, or jump to the first pad and then to the second.

  • For any lily pad i≥3i \geq 3, the frog can:

    • Jump from pad i−1i - 1
    • Or leap from pad i−2i - 2

Thus, we have the recurrence relation:

F(i)=F(i−1)+F(i−2)F(i) = F(i - 1) + F(i - 2)

This recurrence is exactly the Fibonacci sequence. So the number of ways the frog can reach the nthn^{\text{th}} lily pad is the (n+1)th(n+1)^{\text{th}} Fibonacci number.

✅ Final Answer:
The number of ways the frog can reach the opposite edge is the (n+1)th(n+1)^{\text{th}} Fibonacci number.