[已解决]斐波那契数列 兔子问题

galaxyhhn

小甲鱼课里面的斐波那契数列。这个兔子问题都不太懂，有人解释一下吗

最佳答案

月排行榜 / 总排行榜

kogawananari

2020-9-24 21:09:39

'''经典斐波拉契问题：
李老师爬楼梯，他每次可以走1级或2级，
输入楼梯的级数，求不同的走法数'''

#f1普通递归
def f1(step: int) -> int:
    if step <= 2:
        return step
    return f1(step - 1) + f1(step - 2)

#f2尾递归法
def f2(step: int, a1: int = 1, a2: int = 2) -> int:
    if step == 1:
        return a1
    if step == 2:
        return a2
    return f2(step - 1, a2, a1 + a2)

#f3标准答案
def f3(step: int, a1: int = 1, a2: int = 2) -> int:
    for x in range(step - 1):
        a1, a2 = a2, a1 + a2
    return a1

跳转到最佳答案楼层

昨非

问题发一下，题目代码都不给吗

qin_yin

如果你不了解斐波那契数列本身，建议你去看看李永乐的斐波那契，如果对代码有疑问，请把代码发出来

风过无痕1989

昨非 发表于 2020-9-24 20:30
问题发一下，题目代码都不给吗

我这里有C语言的，程序中要求输入三次出错退出，是我自己写程序时加的，不是题目要求。我不会 Python 语言，你改给他吧

//求斐波那契数列前N项的和

#include<stdio.h>
#include <math.h>
void main()
{
        int i = 1,j = 1,k,n;                           // n 为需要计算的前几项之和
        int f1 = 1 ;
        int f2 = 1 ;
    while(j<4)
        {
                j++;
                while(1)
                {
                        scanf("%d",&n);
                        if(n>0) break;
                        printf("项数不能为负数，请重新输入!\n");
                }
                while(1)
                {
                        if(n>0) break;
                        scanf("%d",&n); 
                        if(floor(n) != ceil(n))
                                printf("项数只能为整数，请重新输入!\n");
                        break;
                }
                break;
        }
    if (j==3)
        {
        printf("你输入错误超过三次，请想清楚了再试\n");
        goto loop;                               // 输错三次，无条件退出程序
        }
        if(n % 2 != 0)
        {
                n = (n - 1) / 2;
                k = 1;
        }        
        else 
           {
                n = n / 2;
                k = 0;
           }
        for(;i < n;i++)
        { 
                f1 = f1 + f2 ;                            // 计算出下一个数，并存放于 f1 中
                f2 = f2 + f1 ;                            // 计算出下两个数，并存放于 f2 中
        }
        if(k == 1)
        {
                f1 = f1 + f2 ;
                printf("%d\n",f1);
        }
        else
                printf("%d\n",f2);
loop :  printf("\n");

}

kogawananari

'''经典斐波拉契问题：
李老师爬楼梯，他每次可以走1级或2级，
输入楼梯的级数，求不同的走法数'''

#f1普通递归
def f1(step: int) -> int:
    if step <= 2:
        return step
    return f1(step - 1) + f1(step - 2)

#f2尾递归法
def f2(step: int, a1: int = 1, a2: int = 2) -> int:
    if step == 1:
        return a1
    if step == 2:
        return a2
    return f2(step - 1, a2, a1 + a2)

#f3标准答案
def f3(step: int, a1: int = 1, a2: int = 2) -> int:
    for x in range(step - 1):
        a1, a2 = a2, a1 + a2
    return a1