基础算法--递推算法[信奥一本通]

2024-08-26 12:36

本文主要是介绍基础算法--递推算法[信奥一本通],希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

本节所讲题源自【信奥一本通】C++版:基础算法-第三章-递推算法


相信大家应该都接触过数列的概念。哎哟,一直在跟数组打交道,说数列感觉好陌生,哈哈。数列中的迭代法大家都还记得吗:通过反复应用特定规则,推导出某一点起始的连续的后续数列。

我们的递推也是这样,给出一些初始值,从题目中找出后续数据应该与已知数据存在哪些关系,能不能写出一个公式或者经过同种操作进行反复推导,得出结论。在数学中我们是数列+递推公式+迭代计算,对应到我们的编码中,就是数组+递推公式+循环实现。

我们前几篇讲的前缀和,高精度计算都有递推的思想在其中,包括后续的递归,搜索,动态规划,回溯等等等大概念算法和小概念算法都需要本节作为基础。 本节就由浅入深练习一些递推的题目。

Part_1:数列部分

1188:菲波那契数列(2)

时间限制: 1000 ms         内存限制: 65536 KB
提交数:80480    通过数: 30981

【题目描述】

菲波那契数列是指这样的数列: 数列的第一个和第二个数都为1,接下来每个数都等于前面2个数之和。

给出一个正整数a,要求菲波那契数列中第a个数对1000取模的结果是多少。

【输入】

第1行是测试数据的组数n,后面跟着n行输入。每组测试数据占1行,包括一个正整数a(1≤a≤1000000)。

【输出】

n行,每行输出对应一个输入。输出应是一个正整数,为菲波那契数列中第a个数对1000取模得到的结果。

本题不难发现以下规律:

a[1]=1,a[2]=1,a[3]=a[2]+a[1]=2,a[4]=a[3]+a[2]=3,a[5]=a[4]+a[3]=5......a[n]+a[n-1]+a[n];

而且本题不同于传统的斐波那契数列编程题,还需要注意以下编程细节:

1.由于越往后计算,数就越大,1000000(1e6)这个数字本身int能够存下,但这是递推啊,int就别用了,尽量用long long类型。但题目告诉我们需要结果对1000取模,这说明好像longlong也存不下,需要进行特殊的处理--取余。

2.多行输入,如果每次我们都进行一次递推,当然可以,但是你想过吗:我先说求斐波那契数列第100项的结果,下面紧跟着就又要第99项,恼不恼火,没办法,人家就这么测试你,你有办法吗,没事,我有,而且我也打算告诉你:求出斐波那契数列的每一项存到数组中,用的时候直接访问即可。这里又要问了:我怎么知道我一开始要求出多少项才够。我只能说:施主,你着相了。那a的范围搁那摆着呢,你求前1e6项就完了呗。你觉得浪费空间,还可能浪费时间,没事,还有办法,我们一开始可以设置一个max,等我们输入完之后再动态开辟max+1的数组空间,我们只求前max项就行了。

ok,重点都分析完了,开始敲代码!!!

#include <bits/stdc++.h>
using namespace std;
#define Long long longint main()
{int n; cin >> n;vector<int> v(n);int max = 0;for (int i = 0; i < n; i++) {cin >> v[i];if (v[i] > max)max = v[i];}vector<Long> fib(max + 1);fib[1] = 1;for (int i = 2; i <= max; i++) {fib[i] = (fib[i - 1]%1000 + fib[i - 2]%1000)%1000;}for (auto e : v) {cout << fib[e] << endl;}return 0;

在编码过程中,你有可能会遇到的问题是:模运算问题。

如果我们相求(a+b)%mod,但是a+b的结果可能会超出范围,再求模取余会影响结果。(当然,本题对1000取模,不影响啥结果,你直接写(a+b)%mod没事)。在初等数论中,我们有一个正规公式:

(a+b)%mod=(a%mod+b%mod)%mod 

首先我们分别对a, b取模, 保证数据小于mod, 然后将数据相加, 再取模, 才能保证结果仍然小于mod

举个例子:(5+2)%3=1,其中5%3=2,2%3=2,相加结果为4,取模4%3=1,即(5%3+2%3)%3。

这时候你该问了,那我直接取余不行嘛。那我们分开求模的目的就是为了解决数据存不下的问题,加入我们数据只能存的下5,连6都存不下,你说5+2存储的时候会是多少,你无法保证这样存储方式下你的数据不会出现丢失等错误,那我们提前对每个数求模取余的必要性就是这样的。

总之一句话:让你求模时,就用这个模运算公式,包不会错。

1189:Pell数列

时间限制: 1000 ms         内存限制: 65536 KB
提交数:53473    通过数: 26840

【题目描述】

Pell数列a1,a2,a3,...的定义是这样的,a1=1,a2=2,...,an=2an−1+an−2(n>2)。

给出一个正整数k,要求Pell数列的第k项模上32767是多少。

【输入】

第1行是测试数据的组数n,后面跟着n行输入。每组测试数据占1行,包括一个正整数k (1≤k<1000000)。

【输出】

n行,每行输出对应一个输入。输出应是一个非负整数。

本题的规律:

a[1]=1,a[2]=2, ...... a[n]=2*a[n-1]+a[n-2];

需要注意的点:

1.取余,利用模运算公式

2.多行输入,采取数组存储

敲代码!!!

#include <bits/stdc++.h>
using namespace std;
#define Long long long/*Pell数列*/
int main() {int n; cin >> n;vector<int> v(n);int upper = 0;for (int i = 0; i < n; i++) {cin >> v[i];upper = max(upper, v[i]);}vector<Long> pell(upper+1);pell[1] = 1;for (int i = 2; i <= upper;i++) {pell[i] = (2*pell[i - 1] % 32767 + pell[i - 2] % 32767) % 32767;}for (auto e : v) {cout << pell[e] << endl;}return 0;
}

对比一下上面两道题,是不是一个模子里刻出来的两兄弟。递推难吗?不难,只要有公式,那就是一通循环。不难嘛?递推公式题目不给你,你能发现嘛。

Part_2:找规律

1190:上台阶

时间限制: 1000 ms         内存限制: 65536 KB
提交数:83331    通过数: 28970

【题目描述】

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

【输入】

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

【输出】

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

不就是找规律嘛,我们可以用归纳总结的方法,对吧。(哎呀,突然发现数学有点重要了,数学知识+数论学习+数学方法,搞算法嘛,数学这个工具重要的很,不想在算法领域进军的话,有基础就行)

让我们发现规律:

台阶数为n,假设上台阶的走法有为f[n]。

n=1, f[n]=1;(我只能走一步嘛,就这一种方法)

n=2, f[n]=2;(我能一步一步走,走两步,也能走两步一次到位)

n=3, f[n]=4;(一步一步走+1,先走一步再走两步+1,先走两步再走一步+1,一下三步+1)

n=4, f[n]=7;  n=5, f[n]=13;  n=6, f[n]=24......(自己列一下喽)

那么你发现规律了嘛:f[1]=1,f[2]=2,f[3]=4....f[n]=f[n-1]+f[n-2]+f[n-3]

这是根据数据方面发现的规律,但你知道,为什么是这么个规律嘛?

假设当前台阶阶数为m阶,我开局的选择只有3条路:跳1阶,跳2阶,跳3阶。然后呢,假设我选第一条路,剩下还有几阶m-1阶,但是我们一路递推过来到了m阶,m-1阶我们能不知道?这样的话,我们将三条路的情况加起来就是f[m]=f[m-1]+f[m-2]+f[m-3]。此刻的你应该恍然大悟:这代码不用你说,我会了!

#include <bits/stdc++.h>
using namespace std;
#define Long long longint main() {vector<int> v;int input;while(1){cin >> input;if (input == 0)break;else v.push_back(input);}vector<Long> ans(71);ans[1] = 1; ans[2] = 2; ans[3] = 4;for (int i = 4; i < 71; i++) {ans[i] = ans[i - 1] + ans[i - 2] + ans[i - 3];//第一步跳1个台阶,剩下i-1个台阶取i-1阶台阶的跳法//第一步跳2个台阶,剩下i-2个台阶取i-2阶台阶的跳法//第一步跳3个台阶,剩下i-3个台阶取i-3阶台阶的跳法}for (auto e : v) {cout << ans[e] << endl;}return 0;
}

 

1194:移动路线


时间限制: 1000 ms         内存限制: 65536 KB
提交数:25983    通过数: 19703

【题目描述】

X桌子上有一个m行n列的方格矩阵,将每个方格用坐标表示,行坐标从下到上依次递增,列坐标从左至右依次递增,左下角方格的坐标为(1,1),则右上角方格的坐标为(m,n)。

小明是个调皮的孩子,一天他捉来一只蚂蚁,不小心把蚂蚁的右脚弄伤了,于是蚂蚁只能向上或向右移动。小明把这只蚂蚁放在左下角的方格中,蚂蚁从左下角的方格中移动到右上角的方格中,每步移动一个方格。蚂蚁始终在方格矩阵内移动,请计算出不同的移动路线的数目。

对于1行1列的方格矩阵,蚂蚁原地移动,移动路线数为1;对于1行2列(或2行1列)的方格矩阵,蚂蚁只需一次向右(或向上)移动,移动路线数也为1……对于一个2行3列的方格矩阵,如下图所示:

(2,1)(2,2)(2,3)
(1,1)(1,2)(1,3)

蚂蚁共有3种移动路线:

路线1:(1,1) → (1,2) → (1,3) → (2,3)

路线2:(1,1) → (1,2) → (2,2) → (2,3)

路线3:(1,1) → (2,1) → (2,2) → (2,3)

【输入】

输入只有一行,包括两个整数m和n(0 < m+n ≤ 20),代表方格矩阵的行数和列数,m、n之间用空格隔开。

【输出】

输出只有一行,为不同的移动路线的数目。

仔细读题,这是个二维问题,但是不妨碍我们找规律啊给大家画个网格模拟移动路线:

按照数学思维,你习惯题目所述的左下角为原点,但是在计算机中,用数组模拟二维时,将坐标系顺时针旋转90°更合适。然后让我们开始找规律:

首先我们知道,蚂蚁的行走规则是,只能沿x-y轴的正方向进行移动,小蚂蚁在1行1列的方格是原地踏步,结果为1。小蚂蚁移动到(1,2)的方式也为1,移动到(2,1)的方式也为1,但是移动到(2,2)的方式为2,因为小蚂蚁可以从上方过来,也可以从左方过来。小蚂蚁移动到(1,3)的方式为1,他只能一步步从左方走过来。移动到(2,3)的方式却为3,同样的道理,它上一步一定在(1,3)或者在(2,2),它到(1,3)只有一种方式,再向下走一步就到了(2,3),它到(2,2)有两种方式,每种方式都再向右走一步,就到了(2,3),到达这个位置又多了两种方式。规律已经呼之欲出了。

我们定义一个二维数组a[m+1][n+1];那么到达某一个方格的方式就是a[i][1]=1,a[1][j]=1;a[x][y]=a[x-1][y]+a[x][y-1]。

#include <bits/stdc++.h>
using namespace std;
#define Long long longint main() {int n, m; cin >> n >> m;vector<vector<int>> v(n+1, vector<int>(m+1));v[1][1] = 1;for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {if(i==1||j==1) v[i][j]=1;else v[i][j] = v[i - 1][j] + v[i][j - 1];}}cout << v[n][m];return 0;
}

这像不像求前缀和的步骤,前缀和其实就是简单的递推。

让我们换个方式,模拟一下:

一开始我们假设到达所有方格都是0种方式,然后根据题意给(1,1)赋上初值1。开始从a[1][1]遍历,如果a[1][1]右面还有路,到达右面方格的路线就等于原来的方式加上从左面来的这个方格原来的方式。如果a[1][1]下面还有路,到达下面方格的路线就等于原来的方式加上从上面来的这个方格原来的方式。遍历一次,就能将所有的方格的路线数确定,其实这才是从前往后的递推思想 ,从一开始往后推(但是我们的编码中并没有明确的递推公式,所以说这个方式为递推也不合适,但你只要知道这个推导的思想就可以了),前面我们说的都是带点递归的思想,从某一个值往前推,推到已知的值,然后反向得出递推的公式。

#include <bits/stdc++.h>
using namespace std;
#define Long long longint main() {int n, m; cin >> n >> m;vector<vector<int>> v(n+1, vector<int>(m+1));v[1][1] = 1;for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {if(i+1<=n) v[i+1][j]+=v[i][j];if(j+1<=m) v[i][j+1]+=v[i][j];}}cout << v[n][m];return 0;
}

Part_3:作业(附参考答案)

昆虫繁殖

信息学奥赛一本通(C++版)在线评测系统 (ssoier.cn)icon-default.png?t=N7T8http://ybt.ssoier.cn:8088/problem_show.php?pid=1312

#include <bits/stdc++.h>
using namespace std;
#define Long long longLong ans[52];//第i月成虫数量
Long tmp[52];//第i月卵的数量
/*昆虫繁殖*/
int main() {int x, y, z; cin >> x >> y >> z;ans[1] = 1; for (int i = 1; i <= x; i++) {ans[i] = 1; }for (int i = x+1; i <= z+1; i++) {ans[i]=ans[i-1]+tmp[i-2];//该月的成虫=上月的成虫+上上个月的卵数tmp[i] = ans[i - x] * y;//该月为成虫产卵数=x月前成虫*y}cout << ans[z+1] << endl;return 0;
}

位数问题

信息学奥赛一本通(C++版)在线评测系统 (ssoier.cn)icon-default.png?t=N7T8http://ybt.ssoier.cn:8088/problem_show.php?pid=1313

#include <bits/stdc++.h>
using namespace std;
#define Long long long/*位数问题*/
const int MAX_N = 1001;
Long os[MAX_N];//偶数个数
Long js[MAX_N];//奇数个数
int main() {int n; cin >> n;os[1] = 8;js[1] = 1;for (int i = 2; i <= n; i++) {os[i] = ((9 * os[i - 1]) % 12345 + (js[i - 1]) % 12345) % 12345;js[i] = ((9 * js[i - 1]) % 12345 + (os[i - 1]) % 12345) % 12345;}os[1] += 1;//把0加上cout << os[n];return 0;
}

过河卒 

信息学奥赛一本通(C++版)在线评测系统 (ssoier.cn)icon-default.png?t=N7T8http://ybt.ssoier.cn:8088/problem_show.php?pid=1314

	
#include <bits/stdc++.h>
using namespace std;
#define Long long longint main() {int n, m; cin >> n >> m;vector<vector<Long>> v(n+1, vector<Long>(m+1));int cx, cy; cin >> cx >> cy;v[0][0] = 1;for (int i = 0; i <= n; i++) {for (int j = 0; j <= m; j++) {if (i == 0 || j == 0) {if (i == 0 && j > 0) v[i][j] = v[i][j - 1];if (j == 0 && i > 0) v[i][j] = v[i - 1][j];}else v[i][j] = v[i - 1][j] + v[i][j - 1];//九大控制点if (i == cx && j == cy)v[i][j] = 0;if ((i == cx - 1 || i == cx + 1) && (j == cy - 2 || j == cy + 2))v[i][j] = 0;if ((i == cx - 2 || i == cx + 2) && (j == cy - 1 || j == cy + 1))v[i][j] = 0;}}cout << v[n][m];return 0;
}


感谢大家!

这篇关于基础算法--递推算法[信奥一本通]的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1108581

相关文章

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系

康拓展开(hash算法中会用到)

康拓展开是一个全排列到一个自然数的双射(也就是某个全排列与某个自然数一一对应) 公式: X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。(a[i]在不同应用中的含义不同); 典型应用: 计算当前排列在所有由小到大全排列中的顺序,也就是说求当前排列是第

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动,这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升:减少抖动,提高图像的清晰度和细节表现力,使得监控画面更加真实可信。 - 细节增强:在低光条件下,抖

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

零基础学习Redis(10) -- zset类型命令使用

zset是有序集合,内部除了存储元素外,还会存储一个score,存储在zset中的元素会按照score的大小升序排列,不同元素的score可以重复,score相同的元素会按照元素的字典序排列。 1. zset常用命令 1.1 zadd  zadd key [NX | XX] [GT | LT]   [CH] [INCR] score member [score member ...]

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

uva 568 Just the Facts(n!打表递推)

题意是求n!的末尾第一个不为0的数字。 不用大数,特别的处理。 代码: #include <stdio.h>const int maxn = 10000 + 1;int f[maxn];int main(){#ifdef LOCALfreopen("in.txt", "r", stdin);#endif // LOCALf[0] = 1;for (int i = 1; i <=

秋招最新大模型算法面试,熬夜都要肝完它

💥大家在面试大模型LLM这个板块的时候,不知道面试完会不会复盘、总结,做笔记的习惯,这份大模型算法岗面试八股笔记也帮助不少人拿到过offer ✨对于面试大模型算法工程师会有一定的帮助,都附有完整答案,熬夜也要看完,祝大家一臂之力 这份《大模型算法工程师面试题》已经上传CSDN,还有完整版的大模型 AI 学习资料,朋友们如果需要可以微信扫描下方CSDN官方认证二维码免费领取【保证100%免费

dp算法练习题【8】

不同二叉搜索树 96. 不同的二叉搜索树 给你一个整数 n ,求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种?返回满足题意的二叉搜索树的种数。 示例 1: 输入:n = 3输出:5 示例 2: 输入:n = 1输出:1 class Solution {public int numTrees(int n) {int[] dp = new int