递归算法 递推公式求解

简单递推公式转换矩阵求解

对于许多递推题⽬，由于数据范围太⼤直接循环写会爆掉，这时⾸先想到的就是矩阵优化，把递推式转换成01矩阵通过快速幂优化。

⽐如最简单的斐波纳挈，如果n⾮常⼤，循环递推肯定是不合适的，那么可以考虑下⾯的公式 (f[n],f[n-1])=(f[n-1],f[n-2])*A; 这⾥的A是⼀个

01矩阵，此时的A={1,1,1,0} 2*2的矩阵， 可想⽽知 f[3] = A的n-2次幂*(f[2],f[1]); 形如斐波纳挈的递推公式转换矩阵都很简单， 顺便附上

POJ3070的 斐波纳挈转矩阵快速幂的代码

#include

#include

#include

#define MOD 10000

using namespace std;

struct mac

{

int frob[2][2];

}pri,unit;

mac power(mac x,mac y)

{

mac temp;

for(int i=0;i<2;i++)

{

for(int j=0;j<2;j++)

{

temp.frob[i][j]=0;

for(int k=0;k<2;k++)

{

temp.frob[i][j]=(temp.frob[i][j]+x.frob[i][k]*y.frob[k][j])%MOD;

}

}

}

return temp;

}

void eachother(int n)

{

pri.frob[0][0]=pri.frob[0][1]=pri.frob[1][0]=1;

pri.frob[1][1]=unit.frob[0][1]=unit.frob[1][0]=0;

unit.frob[0][0]=unit.frob[1][1]=1;

while(n)

{

if(n&1)

{

unit = power(unit,pri);

}

pri = power(pri,pri);

n >>= 1;

}

printf("%d\n",unit.frob[0][1]);

递推公式解决复杂问题实例

递推公式解决复杂问题实例

一、递推公式的基本概念与原理

（一）递推公式的定义

递推公式是一种数学表达式，它通过已知的项来计算后续的项。在数列中，递推公式可以描述数列中相邻项之间的关系。例如，对于数列\(a_n\)，其递推公式可能表示为\(a_{n}=f(a_{n - 1})\)，其中\(f\)是一个关于前一项\(a_{n - 1}\)的函数。这意味着，要计算第\(n\)项的值，我们需要先知道第\(n - 1\)项的值，然后通过特定的规则（即函数\(f\)）来计算得到。

（二）递推公式的原理

递推公式的原理基于数学归纳法的思想。它假设已经知道了数列的初始项（或前几项），然后利用这些已知的项，通过递推关系逐步计算出后续的项。这种方法的优势在于，它将复杂的问题分解为一系列简单的、基于已知条件的计算步骤。每一步的计算都依赖于前一步的结果，从而形成一个连锁反应，最终得到整个数列的各项。例如，斐波那契数列的递推公式\(F_{n}=F_{n - 1}+F_{n - 2}\)（其中\(F_0 = 0\)，\(F_1 = 1\)），就是通过不断地将前两项相加来得到后续的项。这种逐步计算的方式使得我们能够处理那些直接计算通项公式可能非常困难甚至无法得到通项公式的数列问题。

（三）递推公式在数学和其他领域的重要性

在数学领域，递推公式是研究数列、递归函数等概念的重要工具。它为解决各种数学问题提供了一种系统的方法，例如计算组合数、排列数等。在计算机科学中，递推公式也有着广泛的应用。许多算法和程序设计中都使用了递推的思想，如动态规划算法，通过将一个复杂问题分解为一系列重叠子问题，并利用递推关系来求解这些子问题，从而提高了算法的效率。在物理学、经济学等其他领域，递推公式也被用于描述和分析一些动态变化的过程，如物理系统的演化、经济增长模型等。它帮助我们理解和预测这些系统在不同阶段的状态，从而为决策和研究提供依据。

必备算法：递归！⽆论你是前端开发，还是后端开发，都需要掌握它！

递归是⼀种⾮常重要的算法思想，⽆论你是前端开发，还是后端开发，都需要掌握它。在⽇常⼯作中，统计⽂件夹⼤⼩，解析xml⽂件等等，都需要⽤到递归算法。它太基础太重要了，这也是为什么⾯试的时候，⾯试官经常让我们⼿写递归算法。本⽂呢，将跟⼤家⼀起深⼊挖掘⼀下递归算法~

什么是递归？

递归，在计算机科学中是指⼀种通过重复将问题分解为同类的⼦问题⽽解决问题的⽅法。简单来说，递归表现为函数调⽤函数本⾝。在知乎看到⼀个⽐喻递归的例⼦，个⼈觉得⾮常形象，⼤家看⼀下：

❝

递归最恰当的⽐喻，就是查词典。我们使⽤的词典，本⾝就是递归，为了解释⼀个词，需要使⽤更多的词。当你查⼀个词，发现这个词的解释中某个词仍然不懂，于是你开始查这第⼆个词，可惜，第⼆个词⾥仍然有不懂的词，于是查第三个词，这样查下去，直到有⼀个词的解释是你完全能看懂的，那么递归⾛到了尽头，然后你开始后退，逐个明⽩之前查过的每⼀个词，最终，你明⽩了最开始那个词的意思。

❞

来试试⽔，看⼀个递归的代码例⼦吧，如下：

递归的特点

实际上，递归有两个显著的特征,终⽌条件和⾃⾝调⽤: ✿ ⾃⾝调⽤：原问题可以分解为⼦问题，⼦问题和原问题的求解⽅法是⼀致的，即都是调⽤⾃⾝的同⼀个函数。

✿ 终⽌条件：递归必须有⼀个终⽌的条件，即不能⽆限循环地调⽤本⾝。

结合以上demo代码例⼦，看下递归的特点：

递归与栈的关系

其实，递归的过程，可以理解为出⼊栈的过程的，这个⽐喻呢，只是为了⽅便读者朋友更好理解递归哈。以上代码例⼦计算sum（n=3）的出⼊栈图如下：

为了更容易理解⼀些，我们来看⼀下 函数sum（n=5）的递归执⾏过程，如下：

✿ 计算sum（5）时，先sum（5）⼊栈，然后原问题sum（5）拆分为⼦问题sum（4），再⼊栈，直到终⽌条件sum（n=1）=1，就开始出栈。

✿ sum（1）出栈后，sum（2）开始出栈，接着sum（3）。

递归算法：

递归算法（英语：recursion algorithm）在计算机科学中是指一种通过重复将问题分解为同类的子问题而解决问题的方法。递归式方法可以被用于解决很多的计算机科学问题，因此它是计算机科学中十分重要的一个概念。绝大多数编程语言支持函数的自调用，在这些语言中函数可以通过调用自身来进行递归。计算理论可以证明递归的作用可以完全取代循环，因此在很多函数编程语言（如Scheme）中习惯用递归来实现循环。

能够解决的问题：

数据的定义是按递归定义的。如Fibonacci函数。

问题解法按递归算法实现。如Hanoi问题。

数据的结构形式是按递归定义的。如二叉树、广义表等。

递归数据：

数据类型可以通过递归来进行定义，比如一个简单的递归定义为自然数的定义：“一个自然数或等于0，或等于另一个自然数加上1”。Haskell中可以定义链表为：

data ListOfStrings = EmptyList | Cons String ListOfStrings

这一定义相当于宣告“一个链表或是空串列，或是一个链表之前加上一个字符串”。可以看出所有链表都可以通过这一递归定义来达到。

尾部递归:

尾部递归是指递归函数在调用自身后直接传回其值，而不对其再加运算。尾部递归与循环是等价的，而且在一些语言（如Scheme中）可以被优化为循环指令。

不动点组合子：

即使一个编程语言不支持自调用，如果在这语言中函数是第一类对象（即可以在运行期创建并作为变量处理），递归可以通过不动点组合子（英语：Fixed-point combinator）来产生。