爬 n 步梯子，只爬 1、3 或 5 步

Question

我有一个练习，我应该计算爬 n 步梯子的方式，有以下限制：你只能上 1、3 或 5 步。

我读到我应该使用 Fibonacci 递归。因此，我将该限制应用于我能找到的 1、2 和 3 步规则示例。

(define (climb n)
   (cond [(<= n 0) 0]
         [(<= n 2) 1]
         [(= n 3) 2]
         [(> n 1) (+ (climb (- n 1)) (climb (- n 3)) (climb (- n 5)))]
   )
)

但这不起作用，例如：使用 (climb 5) 输出是 4，应该是 5:

(1 1 1 1 1)、(1 3)、(3 1)、(3 1 1)、(1 3 1)、(1 1 3)、(5)。爬梯子的5种方法。

Answer 1

更新你的基本条件，return 1 当输入值等于 0 时。例如，对于输入 5，您可以仅使用步骤 5 爬梯子。这会产生类似 climb(5): 5-5 = 0.

的情况

以下修复将有所帮助：

(define (climb n)
   (cond [(< n 0) 0]   <---- updated here
         [(<= n 2) 1]
         [(= n 3) 2]
         [(> n 1) (+ (climb (- n 1)) (climb (- n 3)) (climb (- n 5)))]
   )
)

另一个有效的解决方案：

(define (climb n)
   (cond [(< n 0) 0]
         [(= n 0) 1]
         [(> n 0) (+ (climb (- n 1)) (climb (- n 3)) (climb (- n 5)))]
   )
)

算法：

func Count(x):
 if x < 0: return 0
 if x == 0: return 1
 return Count(x-1)+Count(x-3)+Count(x-5)
end

Answer 2

一个简单的动态规划算法可以解决这个问题。

函数是这样的：

f(n < 1) = 0,
f(1) = 1,
f(2) = 1,
f(3) = 2,
f(4) = 3,
f(5) = 5,
f(n > 5) = f(n - 1) + f(n - 3) + f(n - 5)

一开始它可能看起来像斐波那契数列，但很快您就会发现它是不同的。

f(7) =         f(6)         + f(4) + f(2)
f(7) = (f(5) + f(3) + f(1)) + f(4) + f(2)
f(7) =   5   +  2   +  1    +  3   +  1
f(7) = 12  //fibonacci value should be 13

爬 n 步梯子，只爬 1、3 或 5 步

Climb a ladder with n steps, only going by 1, 3 or 5 steps

algorithm

scheme

fibonacci

racket