首页 > 编程语言 >算法01 递推算法及相关问题详解

算法01 递推算法及相关问题详解

时间:2024-06-12 14:30:15浏览次数:23  
标签:信封 01 int 样例 long fib 算法 递推

目录

递推的概念

训练:斐波那契数列

解析

参考代码

训练:上台阶

参考代码

训练:信封

解析

参考代码

递推的概念

递推是一种处理问题的重要方法。

递推通过对问题的分析,找到问题相邻项之间的关系(递推式),从起点出发(首项或者末项)然后使用循环不断地迭代,得到最后需要的结果。

训练:斐波那契数列

对于Fibonacci数列,已知:fib(1) = 1; fib(2) = 1; 从第三项开始满足公式fib(i) = fib(i-1) + fib(i-2)。输入一个整数n(1<=n<=100),求fib(n)的值。

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

【输出描述】一行:feibonacci数列第n项的值

【样例输入】5

【样例输出】5

解析

1.问题求的是斐波那契数列第i项的数值。

2.前两项的数值,题目中已经给出,分别为:

fib(1) = 1; fib(2) = 1;

3.从第3项开始,满足如下规律:

fib(i) = fib(i-1) + fib(i-2);

即当前项由前两项之和构成。

4.我们可以根据题目给出的fib(1)、fib(2)推出fib(3),

再按照顺序由fib(2)、fib(3)推出fib(4),以此类推。

参考代码

#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,表示测试结束。

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

【样例输入】

1
2
3
4
0

【样例输出】

1
2
4
7

参考代码

#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种方案:

  1. 这封信的位置,不与剩余的任意一封信互换,此时,剩余的问题就是:将n-1封信,错放在n-1个信封里,即f(n-1)
  2. 这封信的位置,与剩余的任意一封信互换,此时会有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;
}

 从入门到算法,再到数据结构,查看全部文章请点击此处​icon-default.png?t=N7T8http://www.bigbigli.com/

标签:信封,01,int,样例,long,fib,算法,递推
From: https://blog.csdn.net/qq_39434533/article/details/139624689

相关文章

  • 【CMake系列】01-CMake是什么
    在很多开源项目中,经常可以看到CMakeLists.txt这一文件,依靠它才能完成项目的配置运行过程。那它是什么?接下来,在这个专栏中,我们将系统学习CMake这一个重要工具。本专栏的实践代码全部放在github上,欢迎star!!!如有问题,欢迎留言、或加群【392784757】交流CMake是什么CMake......
  • 小宋的SpringCloud学习记录day01
    MybatisPlus条件构造器基于QueryWrapper的查询MybatisPlus中写好的QueryWrapper方法省去了编写复杂sql语句的繁琐,直接把各种条件集成为对应的方法需求:1.查询出名字中带o的,存款大于等于10000的人的id、username、info、balance字段2.更新用户名为jack的用户余额为2000......
  • c语言实现密码学算法应用
    一实验目的   1、掌握对称密钥密码体制的基本概念;   2、掌握对称密钥密码体制DES加密/解密的工作原理;   3、掌握非对称密码算法RSA加密/解密的基本原;   4、通过用DES和RSA算法对实际的数据进行加密/解密运算深刻理解加密算法原理。二实验内容   根据给......
  • 【代码+详解】算法题 : 金银岛
    ❗❗❗必看:下列题我全部都使用Java语言写的,并且均可以提交成功,获得Accepted结果的.如果代码和详解看了之后,对答案有任何疑问,都可以在评论区提出来,我都会一个一个回答.❗❗❗感谢大家的支持,如果喜欢我的博客,关注点赞收藏评论一波,非常感谢!!!文章目录......
  • 【近邻算法】近邻算法详解——深入理解K-近邻(KNN)
    目录1引言2算法基础2.1核心原理2.2算法步骤3关键参数与优化3.1K值选择3.2距离度量4优缺点分析4.1优点4.2缺点5改进策略6应用案例深度解析:K-近邻算法在客户细分中的应用6.1引言6.2数据准备与预处理6.3特征选择与编码6.4K-近邻算法应用6.5模型......
  • 一种改进盲解卷积算法在旋转机械故障诊断中的应用(MATLAB)
    滚动轴承故障形成后,故障区与其他零部件表面接触将产生循环平稳的瞬态脉冲。由于受到系统传递函数、轴转频和环境噪声的干扰,故障脉冲特征受到大幅衰减,在测得信号中表现十分微弱甚至完全不可见。盲解卷积算法通过搜索一个最优的有限脉冲响应滤波器来降低信号传输路径、轴转频和环......
  • 实现EM算法的单次迭代过程
    编程要求根据提示,在右侧编辑器补充Begin-End段中的代码,完成em_single(priors,observations)函数。该函数需要完成的功能是模拟抛掷硬币实验并估计在一次迭代中,硬币A与硬币B正面朝上的概率。其中:init_values:硬币A与硬币B正面朝上的概率的初始值,类型为list,如[......
  • 如何评估pcdn调度算法的优化效果(贰)
    PCDN(PersonalizedContentDeliveryNetwork)调度算法的优化可以通过以下几个方面来进行:1、性能指标:首先确定要评估的关键性能指标(KPIs),如平均响应时间、内容分发速度、缓存命中率、用户满意度等。这些指标应直接反映算法优化后的效果。2、基准测试:在优化之前,进行基准测试以......
  • 第6篇:Milvus检索算法详解:从原理到应用
    欢迎来到Milvus检索算法的世界!在本文,我将带你深入了解Milvus的向量相似度计算和常用的检索算法。通过这篇博客,你将了解Milvus是如何高效计算向量相似度并进行向量检索的。准备好了吗?让我们开始这段知识之旅吧!文章目录Milvus的向量相似度计算向量相似度计算的原理......
  • 代码随想录算法训练营第第35天 | 977.有序数组的平方1005.K次取反后最大化的数组和 、
    1005.K次取反后最大化的数组和本题简单一些,估计大家不用想着贪心,用自己直觉也会有思路。https://programmercarl.com/1005.K次取反后最大化的数组和.html自己写的时间复杂度太高,看答案优化/***@param{number[]}nums*@param{number}k*@return{number}*/varl......