关于斐波那契数列的问题

weiyideid823

有N个台阶，每次只能跳1步或者3步，求有多少种跳法 （0 < N <=50)


请教大神这种该怎么写代码啊

嘉岳呀

这是斐波那契数列吗？

weiyideid823

嘉岳呀 发表于 2021-10-30 13:20
这是斐波那契数列吗？

类斐波那契数列吧

weiyideid823

求助求助。。。。。。。。。。。

kogawananari

每次只能跳1步或者2步 才是斐波拉契数列

不过我有个通用解法

import math


def p1(step: int, n: int) -> int:
    m = 0
    sln = 0
    while step >= 0:
        sln += math.factorial(step + m) / \
            math.factorial(step) / math.factorial(m)
        step -= n
        m += 1
    return int(sln)


# n=2时是斐波拉契数列
print(p1(1, 2))
print(p1(2, 2))
print(p1(3, 2))
print(p1(4, 2))
print(p1(5, 2))
# n=3时是你要求的
print(p1(50, 3))

weiyideid823

kogawananari 发表于 2021-10-30 13:45
每次只能跳1步或者2步 才是斐波拉契数列

不过我有个通用解法

大神，能不能加个注释啊啊 多谢！

全桥整流

学习一下

kogawananari

weiyideid823 发表于 2021-10-30 13:50
大神，能不能加个注释啊啊 多谢！

就是高中数学知识 全排列

假装全都是一步3级

然后把其中3步合成一步做排列组合 看有多少种

再把其中6步合成2步做排列组合 以此类推  总数全部相加

kogawananari

kogawananari 发表于 2021-10-30 13:54
就是高中数学知识 全排列

假装全都是一步3级

为什么不用递归 因为递归很卡 算的太慢 不如math库

至于优化递归变成循环 太烧脑了 保头发

100gram

kogawananari 发表于 2021-10-30 13:55
为什么不用递归 因为递归很卡 算的太慢 不如math库

至于优化递归变成循环 太烧脑了 保头发

学到了 实在是大佬

全桥整流

kogawananari 发表于 2021-10-30 13:45
每次只能跳1步或者2步 才是斐波拉契数列

不过我有个通用解法

import math


def p1(step: int, n: int) -> int:
    m = 0
    sln = 0
    while step >= 0:
        sln += math.factorial(step + m) / \   #请问这个地方是什么意思？
            math.factorial(step) / math.factorial(m)    #这个地方也是
        step -= n
        m += 1
    return int(sln)


# n=2时是斐波拉契数列
print(p1(1, 2))
print(p1(2, 2))
print(p1(3, 2))
print(p1(4, 2))
print(p1(5, 2))
# n=3时是你要求的
print(p1(50, 3))

kogawananari

全桥整流 发表于 2021-10-30 15:05

(a+b)!/a!/b!   是组合数C(a+b,a)的化简  即在a+b步中把其中a步变成 一步3级台阶 有多少种变法

心驰神往

搜一搜应该能搜到吧

tianlai7266

傻眼貓咪

最简单，最短解法：

list = [1, 1]
N = int(input("请输入台阶："))
for i in range(2, N):
        list.append((list[i-2]) + (list[i-1]))
print(f"共有 {list[-1]} 跳法")

输入/输出：

请输入台阶：13
共有 233 跳法

帅昊昊昊

有这么多鱼币吗？