算法01 递推算法及相关问题详解【C++实现】

#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long n,f1,f2,f3;
    cin>>n;
    f1=f2=f3=1;//初始化,f3表示第n项
    for(long long i=3;i<=n;i++)
    {
        f3=f1+f2;
        f1=f2;
        f2=f3;
    }
    cout<<f3;
    return 0;
}

训练：上台阶

楼梯有n(1<=n<=100)阶台阶,上楼时可以一步上1阶,也可以一步上2阶,也可以一步上3阶，编程计算共有多少种不同的走法。

【输入描述】输入的每一行包括一组测试数据，即为台阶数n。最后一行为0，表示测试结束。

【输出描述】每一行输出对应一行输入的结果，即为走法的数目。

【样例输入】

【样例输出】

参考代码

#include<bits/stdc++.h>
using namespace std;
long long a[105];
//a[i]表示i层楼梯方案数
int main()
{
    int n,t;
    a[1]=1,a[2]=2,a[3]=4;
    //边界条件
    while(1)
    {
        cin>>t;
        if(!t) break;
        if(a[t]){           //如果已经计算过，直接输出
            cout<<a[t]<<endl;
            continue;
        }
        for(int i=4;i<=t;i++)
            a[i]=a[i-1]+a[i-2]+a[i-3];
        //从第4层楼梯开始
        //每一步有3种方案：1阶、2阶、3阶
        //分别对应 a[i-1]、a[i-2]、a[i-3]
        cout<<a[t]<<endl;
    }
    return 0;
}

训练：信封

现在有n封信和n个信封，如果所有的信都装错了信封。求所有信都装错信封共有多少种不同情况。

【输入描述】1行：输入一个整数n。

【输出描述】1行：输出一个整数，表示所有的情况数。

【样例输入】4

【样例输出】9

解析

先任取一封信，此时可供选择的信封有：n-1种情况。

每种情况下，我们在放置这封信的时候有2种方案：

这封信的位置，不与剩余的任意一封信互换，此时，剩余的问题就是：将n-1封信，错放在n-1个信封里，即f(n-1)
这封信的位置，与剩余的任意一封信互换，此时会有2个信封被使用掉。剩余的问题就是：将n-2封信,错放在n-2个信封里，即f(n-2)，得出递推式：f(n)=(n-1)*(f(n-1)+f(n-2))。边界是：f(1)=0,f(2)=1。

参考代码

#include<bits/stdc++.h>
using namespace std;
long long f[25];
int main()
{
    int n;
    cin>>n;
    f[1]=0,f[2]=1;
    for(int i=3;i<=n;i++)
    {
        f[i]=(i-1)*(f[i-1]+f[i-2]);
    }
    cout<<f[n];
    return 0;
}

从入门到算法，再到数据结构，查看全部文章请点击此处http://www.bigbigli.com/

原文地址:https://blog.csdn.net/qq_39434533/article/details/139624689 本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：https://www.suanlizi.com/kf/1802540680908771328.html 如若内容造成侵权/违法违规/事实不符，请联系《酸梨子》网邮箱：1419361763@qq.com进行投诉反馈，一经查实，立即删除！

阅读全部