求机器人可用跳跃方式 (Python 代码实现)

今天在 segmentfault 看到有趣的 编程题
描述如下:
” 一救援机器人有三种跳跃模式,可分别跳跃1m,2m,3m的距离,
请用程序实现该机器人行进n米路程时可用的跳跃方式。

程序语言不限,当距离n值足够大时,程序执行时间尽量小。

例:当距离为4米时,输出结果有7种:

1m,1m,1m,1m
1m,1m,2m
1m,2m,1m
1m,3m
2m,1m,1m
2m,2m
3m,1m

根据另一个用户 AUV_503516 提供的思路,
转会为数学的思考方式:
由条件定义 f(n) 为 n米的可用步骤序列.
f(1) = ( (1), )
f(2) = ( (1, 1), (2,) )
f(3) = ( (1, 1, 1), (1, 2), (2, 1), (3,) )

求 f(n), 每一跳跃可以使用的距离是 1, 2, 3
f(n) = f(1) + f(n-1) = f(2) + f(n-2) = f(3) + f(n-3)
= f(n-1) + f(1) = f(n-2) + f(2) = f(n-3) + f(3)

另外 f(delta) + f(n – delta) 有可能与 f(n – delta) + f(delta) 是用一个序列,
求 f(n) 需要去重.

由公式定义, 使用 Python代码实现如下:

Continue reading