求助大佬递归和递推（python）

pallas

问题：假设一段楼梯共 15 个台阶，小明一步最多能上 3 个台阶。编写程序计算小明上这段楼梯一共有多少种方法。

劳烦大佬们写个注释，万分感谢！！

qq1151985918

def res(n):
    if n < 1:
        raise ValueError("ValueError")
    elif n == 1:
        return 1
    elif n == 2:
        return 2
    elif n == 3:
        return 4
    else:
        return res(n-1) + res(n-2) + res(n-3)


if __name__ == "__main__":
    print(res(15))

人造人

#include <stdio.h>

void output(size_t buff[], size_t index, size_t begin, size_t step, size_t end, size_t *count) {
    if(begin > end) return;
    if(begin == end) {
        printf("%lu: ", (*count)++);
        for(size_t i = 0; i < index; ++i) {
            printf("%lu ", buff[i]);
        }
        printf("\n");
        return;
    }
    for(size_t i = 1; i <= step; ++i) {
        buff[index] = i;
        output(buff, index + 1, begin + i, step, end, count);
    }
}

int main(void) {
    size_t buff[1024];
    size_t count = 0;
    output(buff, 0, 0, 3, 15, &count);
    return 0;
}

#!/usr/bin/env python
#coding=utf-8

def output(buff, index, begin, step, end, count):
    if begin > end: return
    if begin == end:
        print('%d: ' % count[0], end = '')
        count[0] += 1
        for i in range(index):
            print(buff[i], end = ' ')
        print('')
    for i in range(1, step + 1):
        buff[index] = i
        output(buff, index + 1, begin + i, step, end, count)

buff = [0] * 1024
count = [0]
output(buff, 0, 0, 3, 15, count)

傻眼貓咪

C 代码：

#include <stdio.h>
int step(int n){ return !n ? 0 : n < 3 ? n : n == 3 ? 4 : step(n-3) + step(n-2) + step(n-1); }
int main(){
    printf("%d", step(15));
    return 0;
}

Python 代码：

step = lambda n: 0 if n == 0 else n if n < 3 else 4 if n == 3 else step(n-3) + step(n-2) + step(n-1)
print(step(15))

输出结果：

5768

kogawananari

傻眼貓咪 发表于 2021-11-7 17:17
C 代码：Python 代码：输出结果：

就当无事发生

傻眼貓咪

kogawananari 发表于 2021-11-7 18:10
结果写错了哥是189

你意思是说除了我，二楼、三楼的大佬也是错？你的189才是正确？

kogawananari

傻眼貓咪 发表于 2021-11-7 18:23
你意思是说除了我，二楼、三楼的大佬也是错？你的189才是正确？

离谱 离谱 我之前用你的和二楼的算是189 我以为你是结果写错了草

kogawananari

w = (3**.5)*.5j -.5
d33 = 3*(33**.5)
d19 = 19
l3 = lambda x:x**(1/3)
x = (1+l3(d19-d33)+l3(d19+d33))/3
y = (1+l3(d19-d33)*w+l3(d19+d33)*w.conjugate())/3
z = (1+l3(d19-d33)*w.conjugate()+l3(d19+d33)*w)/3

# xyz是方程 x**3 - x**2 - x - 1 = 0的3个解
def tori(n,a,b,c):
    return (a**n)/(a-b)/(a-c)
def T(n):
    n += 2
    return (tori(n,x,y,z)+tori(n,y,x,z)+tori(n,z,x,y)).real

print(T(15))
print(T(50))

输出

5767.999999999993
10562230626641.951