freedomgod

解题思路：对任意一个n，要求从0级到n级的方案数，可以转换成有不同顺序的加法问题（直译）。例如：n=7
![](/image_editor_upload/20190827063219_27087.png)
上面是不考虑顺序的方案，7个1，4个1加1个3，1个1加2个3，考虑顺序就要对这每一种情况计算不同的方案。
这里如果知道怎么解决高中数学的排列组合问题，那么就可以很快算出不同情况的方案数了。
这种含有重复元素的排列叫做重复排列。如果有四个互不相同的数字排列，就有4！种，有重复元素时，可以用下面的公式计算种数：
![](/image_editor_upload/20190827065512_17227.png)
p和q等都是重复数字的个数。如1 1 2 2 2 3排列就是6!/(2!*3!)
每一种情况的方案数会求之后，要把所有情况考虑进来，可以记录走1级台阶或3级台阶的个数。上面n=7有3种情况，7个一级，4个一级，1个一级或是0个、1个、2个三级台阶。走一级台阶的个数每次减一直到不足3个，三级台阶每次加一，这样可以把所有情况考虑进来。最后把所有方案数加总就是答案。
代码如下：

```cpp
#include <iostream>
using namespace std;

long long factorial(int x)                                   //构造求阶乘的函数，注意返回值要是long long型，不然会溢出，
{
    long long y;
    if (x==0||x==1)
        return 1;
    else
        y=x*factorial(x-1);
    return y;
}

int main()
{
    int i,n,number;                                          //i用来记录走3级台阶的个数，number是总方案数
    while (cin>>n){
        i=0,number=0;                                        //每次计算方案前初始化值
        while (n>=0){                                        //循环条件是走1级台阶的个数大于等于0，这里每次输入的n一开始是总台阶数，我用来记录走1级台阶的个数，所以不是固定的，这不会影响最终结果
            number+=factorial(n+i)/factorial(n)/factorial(i);//每次加上不同情况的方案数
            n=n-3;                                           //走1级台阶数减3
            i++;                                             //走3级台阶数加1
        }
        cout<<number<<endl;
    }
    return 0;
}
```

以上很需要注意的就是求阶乘函数需要用long long型，不然结果是不对的。

# 二
第二种解法是利用其中蕴含的规律解答。规律和斐波那契数列的f(n)=f(n-1)+f(n-2)形式一致。
分析：
令f(n)表示台阶数为n时的方案数。
n=1；方案：f(1)=1
n=2；方案：f(2)=1
n=3；方案：f(3)=2
n=4；方案：f(4)=3
n=5；方案：f(5)=4
n=6；方案：f(6)=6
n=7；方案：f(7)=9
...  ...   ...
（供验证结论）
n>3时，思考f(n)、f(n-1)和f(n-3)之间存在的联系。
一种较好理解的方式：
本来走n级台阶方案数为f(n),如果少走一级台阶即n-1时方案数为f(n-1)，这时减少的方案数就是相差多走一次台阶（这里一次就是一级台阶）的情况，又因为只能走1级或3级台阶，那么相差的走一次台阶的方案数和f(n-3)是相等的，这时走一次就是三级台阶。于是就有：
              f(n)-f(n-1)=f(n-3)
所以这个规律就可以用一个递归函数实现，直接求得f(n).
代码如下：
```cpp
#include <iostream>
using namespace std;

int Fbonaqi(int n)                                      //递归函数求f(n)
{
    if (n==1||n==2)                                     //n=1、2、3都是初值
        return 1;
    else if (n==3)
        return 2;
    else                                                //n>3，递归
        return Fbonaqi(n-1)+Fbonaqi(n-3);
}

int main()
{
    int n;
    while (cin>>n)                                      //处理多组数据
        cout<<Fbonaqi(n)<<endl;
    return 0;
}
```

以上补充的就是第二种解法。

0.0分

12 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

　　评论区

徐梓涵

2019-09-08 09:08:39

987456321

这是一个简单的斐波那契数列

2019-09-05 21:13:49

freedomgod

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

C语言程序设计教程（第三版）课后习题7.4 （C语言代码）

C语言程序设计教程（第三版）课后习题7.5 （C语言代码）

C语言程序设计教程（第三版）课后习题10.2 （C语言代码）

C语言程序设计教程（第三版）课后习题8.2 （Java代码）

程序员爬楼梯 ——数学排列直译和斐波那契规律两种解法（C++代码）

评论区

精彩推荐

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

九宫重排（C++代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

【魔板】（C++代码）(时间超限，希望会的帮我改正一下)

C语言程序设计教程（第三版）课后习题6.3 （C语言代码）

【绝对值排序】（C语言代码）

【蟠桃记】（C语言代码）

A+B for Input-Output Practice (IV) （C语言代码）

freedomgod

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

C语言程序设计教程（第三版）课后习题7.4 （C语言代码）

C语言程序设计教程（第三版）课后习题7.5 （C语言代码）

C语言程序设计教程（第三版）课后习题10.2 （C语言代码）

C语言程序设计教程（第三版）课后习题8.2 （Java代码）

程序员爬楼梯 ——数学排列直译和斐波那契规律两种解法（C++代码）

评论区

精彩推荐

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

九宫重排 （C++代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

【魔板】 （C++代码）(时间超限，希望会的帮我改正一下)

C语言程序设计教程（第三版）课后习题6.3 （C语言代码）

【绝对值排序】 （C语言代码）

【蟠桃记】 （C语言代码）

A+B for Input-Output Practice (IV) （C语言代码）

　　评论区

九宫重排（C++代码）

【魔板】（C++代码）(时间超限，希望会的帮我改正一下)

【绝对值排序】（C语言代码）

【蟠桃记】（C语言代码）