首页 > 编程语言 >算法 —— 递推

算法 —— 递推

时间:2024-08-03 13:55:19浏览次数:15  
标签:count 数列 int long 算法 递推 卡特兰

目录

递推

数楼梯

斐波那契数列

一维数组递推

P1002 过河卒

二维数组递推 

P1044 栈

卡特兰数


递推

将一个很大的任务分解成规模小一些的子任务,子任务分成更小的子任务,直到遇到初始条件,最后整理归纳解决大任务的思想就是递推与递归思想,不过这两者还是有一些区别:

  • 递归:从上到下 从未知到已知解决问题
  • 递推:从下到上 从已知到未知解决问题

数楼梯


斐波那契数列

此题很像斐波那契数列的解决方式,斐波那契数列是指这样一个数列:1,1,2,3,5,8,13,21,34,55,89……这个数列从第3项开始 ,每一项都等于前两项之和。我们先看斐波那契在百度百科上的定义:

 一开始尝试用递归函数进行尝试,但是很不幸超时了:

int count_ways(int x)
{
	if (x == 1)
		return 1;
	else if (x == 2)
		return 2;
	else
		return count_ways(x - 1) + count_ways(x - 2);
}

一维数组递推

之后修改了数据类型以及计算方式,打算尝试利用递推算法:

#include<bits/stdc++.h>
using namespace std;

long long stairs[5001] = { 0 };

int main()
{
	int n; cin >> n;
	stairs[1] = 1, stairs[2] = 2;
	for (int i = 3; i <= n; i++)
		stairs[i] = stairs[i - 1] + stairs[i - 2];
	cout << stairs[n] << endl;
	return 0;
}

虽然这次没有超时,但是long long还是不够存放最大数据,很显然要利用高精度加递推解决:

轻松解决,大家对高精度感兴趣的可以看我的这篇博客:算法 —— 高精度(模拟)

接着说一下,为什么这个动态转移方程可行:

 stairs[i] = stairs[i - 1]+stairs[i - 2]

由此我们得出规律,方法数为前2次与前1次之和。 


P1002 过河卒

由于士卒只能向下或者向右走,从题目中可以得出此动态转移方程 :

f[i][j] = f[i-1][j] + f[i][j-1]

以样例6 x 6的棋盘为例,作出以下图像:

 可以看到我们把棋盘扩大了两行两列,避免出现越界访问的情况,此处越界访问共有两处:

  1. 马的坐标如果在边界,他可跳跃的点出现越界访问
  2. 动态转移方程的左、上坐标也会出现越界访问

二维数组递推 

 代码如下所示,这里用到了模拟与递推算法:

#include<bits/stdc++.h>
using namespace std;

const int fx[] = { 0, -2, -1, 1, 2, 2, 1, -1, -2 };
const int fy[] = { 0, 1, 2, 2, 1, -1, -2, -2, -1 };
//马可以走到的位置

int bx, by, hx, hy;
long long f[40][40];   //只有路的棋盘
bool s[40][40]; //只有马的棋盘
int main() {
    cin >> bx >> by >> hx >> hy;
    bx += 2; by += 2; hx += 2; hy += 2;
    //坐标+2以防越界
    f[2][1] = 1;//初始化
    for (int i = 0; i <= 8; i++) //标记不能过的点
        s[hx + fx[i]][hy + fy[i]] = 1;
    for (int i = 2; i <= bx; i++) {
        for (int j = 2; j <= by; j++) {
            if (s[i][j]) continue; // 如果被马拦住就直接跳过

            f[i][j] = f[i - 1][j] + f[i][j - 1];
        }
    }
    cout << f[bx][by] << endl;
    return 0;
}

为什么这样可行?由于士卒棋只能向下或者向右走,所以从一个对角到另外一个对角只存在两种可能情况,如下图所示:

 由图可知,动态转移方程可以表述此过程,因此方法可行。


P1044 栈

 在解决这道题之前先了解一个新概念:卡特兰数


卡特兰数

卡特兰数(英语:Catalan number),又称卡塔兰数、明安图数,是组合数学中一种常出现于各种计数问题中的数列。以比利时数学家欧仁·查理·卡特兰的名字命名。1730年,清代蒙古族数学家明安图在对三角函数幂级数的推导过程中首次发现,1774年被发表在《割圜密率捷法》。百度百科是这样定义卡特兰数的:

我们看一下卡特兰数的概述图:

如果一个点从坐标A(0,0)开始移动到坐标B(n,n),只允许向上或向右,并且存在约束条件 :路径只能在y = x以下,那么我们可以看到,如果要移动到B点,总路程为2n,左图绿色路径为刚好越过约束条件的情况,我们可以看到,绿色非法路径的突出点与橙色路径都不约而同的经过右图蓝色直线,意味着路径只要碰到蓝色直线即变成非法 

我们利用数学方法对这个图形进行分析:

 再次对非法路径进行分析可以得出以下结论:

合法路径方程为:C_{2n}^{ n} - C_{2n}^{n+1} = \frac{C_{2n}^{ n}}{n+1}此式得证。

 这时候将理论运用到实际,我们把右移看作入栈,上移看作出栈,同上出栈数始终比入栈大1才为非法,很显然这是一个卡特兰数问题,注意卡特兰数后面数据过大,long long存不下,很显然还需要结合高精度模拟。(此题给了限定范围最大为卡特兰数第18项即129644790)

#include <iostream>
using namespace std;

long long count_C(int n)
{
	long long tmp = 1; int d = n;
	for (int i = 2 * n; i > n; i--)
	{
		if (i % d == 0 && d > 1)
		{
			tmp *= (i / d); //尽可能缩小乘数
			d--;
		}
		else
			tmp *= i;
	}
	while (d > 1)
		tmp /= d--;
	return tmp;
}

int main()
{
	int n; cin >> n;
	long long ret = count_C(n);
	cout << ret / (n + 1) << endl;
	return 0;
}

感兴趣的小可爱们可以试着加上高精度解决n更大的情况。

如需科普请看这篇博客:「算法入门笔记」卡特兰数

标签:count,数列,int,long,算法,递推,卡特兰
From: https://blog.csdn.net/fen_0108/article/details/140730720

相关文章

  • 【创新未发表】Matlab实现蚁狮优化算法ALO-Kmean-Transformer-LSTM组合状态识别算法研
    蚁狮优化算法(AntLionOptimisation,ALO)是一种启发式优化算法,灵感来源于蚁狮捕食过程中的行为。这种算法模拟了蚁狮捕食中的策略,其中蚁狮通过在环境中设置虚拟陷阱来吸引蚂蚁,然后捕食这些落入陷阱的蚂蚁。在算法中,蚁狮代表潜在解决方案,而虚拟陷阱代表目标函数的局部最小值。......
  • 【Rust光年纪】提升数据安全性与完整性:Rust语言哈希算法库深度对比
    深入探索Rust中的哈希算法库:安装配置与API解析前言在现代软件开发中,数据的安全性和完整性是至关重要的。哈希算法作为一种常见的数据加密和校验手段,在Rust语言中有着广泛的应用。本文将介绍几个用于Rust语言的常见哈希算法库,包括blake2、sha2、md5、crc32、xxhash以及siph......
  • Tarjan算法和连通性相关(三)
    上一篇博客我们介绍了割点和桥,本文我们继续学习与连通性有关的一些概念边双连通分量什么是边双连通分量?在一张连通的无向图中,对于两个点u和v,如果无论删去哪条边(只能删去一条)都不能使它们不连通,我们就说u和v边双连通,边双联通分量是极大的边双连通子图怎么求边双连通......
  • 「代码随想录算法训练营」第二十八天 | 动态规划 part1
    509.斐波那契数题目链接:https://leetcode.cn/problems/fibonacci-number/题目难度:简单文章讲解:https://programmercarl.com/0509.斐波那契数.html视频讲解:https://www.bilibili.com/video/BV1f5411K7mo题目状态:过!思路:当n=0时,返回0;当n=1时,返回1;当n>=2时,返回fib(......
  • 匈牙利算法--二分图的最大匹配
    匈牙利算法--二分图的最大匹配给定一个二分图,其中左半部包含 n1个点(编号 1∼n1),右半部包含 n2 个点(编号 1∼n2),二分图共包含 m 条边。数据保证任意一条边的两个端点都不可能在同一部分中。请你求出二分图的最大匹配数。二分图的匹配:给定一个二分图 G,在 G的一个子......
  • 基础算法:离散化(C++实现)
    文章目录1.离散化的定义2.离散化例题2.1离散化+二分2.2离散化+哈希表1.离散化的定义离散化是一种在程序设计和算法优化中常用的技术,其核心思想是将无限空间中有限的个体映射到有限的空间中去,以此提高算法的时空效率。具体来说,离散化是在不改变数据相对大小的条......
  • 2024“钉耙编程”中国大学生算法设计超级联赛(5)
    目录写在前面101110131006100810021005写在最后写在前面补题地址:https://acm.hdu.edu.cn/listproblem.php?vol=65,题号7481~7493。以下按个人难度向排序。比较顺利的一场,今天双人双题环节没有卡太久,赢!置顶广告:中南大学ACM集训队绝赞招新中!有信息奥赛基础,获得NOIP省一等......
  • (算法)组合总和————<递归>
    1.题⽬链接:39.组合总和 2.题⽬描述:3.解法:算法思路:candidates的所有元素互不相同,因此我们在递归状态时只需要对每个元素进⾏如下判断:1.跳过,对下⼀个元素进⾏判断;2.将其添加⾄当前状态中,我们在选择添加当前元素时,之后仍可以继续选择当前元素(可以重复选择同⼀元素......
  • 算法·理论:KMP 笔记
    \(\text{KMP}\)笔记!上次比赛,出题人出了一个\(\text{KMP}\)模板,我敲了个\(\text{SAM}\)跑了,但是学长给的好题中又有很多\(\text{KMP}\),于是滚回来恶补字符串基本算法。\(\text{KMP}\)是上个寒假学的,为什么最近才完全理解,但\(\text{KMP}\)短小精悍,极其精简,确实难懂,所以很......
  • 2024“钉耙编程”中国大学生算法设计超级联赛(5)
    Preface唉感觉最近把把红温负作用啊,这场就中期写05被卡常了就红温了一整场,放着更简单的题不写就疯狂乱搞结果不出所料地被打爆了,只能说是好似,赛后发现甚至有个题是去年一轮的原,结果比赛的时候没一个人看题意,属实绷不住了感觉现在每场的策略和心态都有很大问题啊,不把这些问题......