[one_demo_7]求走到第50个台阶的走法多少种

ゝ一纸荒年。 2022-06-01 11:07 187阅读 0赞

一个楼梯有50个台阶，一次只能走一个台阶或两个台阶，问，从第一台阶走到第50台阶，有多少种走法。

分析

走第1阶，1种走法；

走第2阶，2种走法；

走第3阶，3种走法，因为每次只能走1阶或2阶，所以，走到第3阶最近的阶，只能是从第1阶走来，或从第2阶走来，那么，走到第3阶的走法就是走到第1阶和走到第2阶的走法的和；

走第4阶，5种走法，因为每次只能走1阶或2阶，所以，走到第4阶最近的阶，只能是从第2阶走来，或从第3阶走来，那么，走到第4阶的走法就是走到第2阶和走到第3阶的走法的和；

…

走第48阶，因为每次只能走1阶或2阶，所以，走到第48阶最近的阶，只能是从第46阶走来，或从第47阶走来，那么，走到第48阶的走法就是走到第46阶和走到第47阶的走法的和；

走第49阶，因为每次只能走1阶或2阶，所以，走到第49阶最近的阶，只能是从第47阶走来，或从第48阶走来，那么，走到第49阶的走法就是走到第47阶和走到第48阶的走法的和；

走第50阶，因为每次只能走1阶或2阶，所以，走到第50阶最近的阶，只能是从第48阶走来，或从第49阶走来，那么，走到第50阶的走法就是走到第48阶和走到第49阶的走法的和；

经过分析，这个问题实际上是类斐波那契数列的问题。即从第3项开始，每项都为其前两项之和。这个问题，可以使用递归，循环或数组解决。

//递归解决
    
    double taijie(int n)
    
    {
    
             if (n == 1)
    
             {
    
                       return 1;
    
             }
    
             else if (n == 2)
    
             {
    
                       return 2;
    
             }
    
             else
    
             {
    
                       return taijie(n - 1) +taijie(n - 2);
    
             }
    
    }
    
    //使用循环解决
    
    float taijiexunhuan(intnum)
    
    {
    
             int n1 = 1;
    
             int n2 = 2;
    
             double res = 0.0;
    
             for (int i = 2; i < num; i++)
    
             {
    
                       res = n1 + n2;
    
                       n1 = n2;
    
                       n2 = res;
    
             }
    
             return res;
    
    }
    
    //使用数组解决
    
    float taijieshuzu(intn)
    
    {
    
             float a[50];
    
             a[0] = 1.0;
    
             a[1] = 2.0;
    
             for (int i = 2; i < n; i++)
    
             {
    
                       a[i] = a[i - 1] + a[i - 2];
    
             }
    
             return a[n - 1];
    
    }
    
    void main()
    
    {
    
             printf("%lf", taijie(4));
    
             printf("\n%lf",taijiexunhuan(4));
    
             printf("\n%lf",taijieshuzu(4));
    
             getchar();
    
    }

如果这个问题被扩展了，一次可以走1阶，2阶，3阶，推理的原理是类似的，结果就是从第4阶开始，每阶走法都为前三阶走法之和。变成每次走更多阶也类似。