《c++递推算法详解.ppt》由会员分享，可在线阅读，更多相关《c++递推算法详解.ppt（21页珍藏版）》请在三一办公上搜索。
1、递 推 算 法,递推问题求解过程,确定状态,确定递推关系和边界条件,程序实现,例1：计算系数(NOIP2011day2),【题目描述】给定一个多项式(ax+by)k,请求出多项式展开后xnym项的系数【输入】共一行，包含5个整数，分别为a,b,k,n,m，每两个整数之间用一个空格隔开。【输出】输出共1行，包含一个整数，表示所求的系数，这个系数可能很大，输出对10007 取模后的结果。【输入输出样例】factor.in factor.out 1 1 3 1 2 3【数据范围】对于 30%的数据，有0k10；对于 50%的数据，有a=1，b=1；对于 100%的数据，有0k1,000，0n,mk，
2、且n+m=k，0a，b1,000,000。,方法一,根据二项式定理可知：(ax+by)k=取i=n,xnym的系数为其中an和bm可以用快速幂来计算，在lg(n)+lg(m)内完成。计算 可以用递推来求解。状态：fi,j表示从i个数中选j个数的方案数。fk,n就是答案。根据第i数选还是不选来进行分析：1.选择第i个数：此情况的方案数等价于从i-1个数中选择j-1个数的方案数即fi-1,j-1;2.不选第i个数：此情况的方案数等价于从i-1个数中选择j个数的方案数即fi-1,j 所以fi,j=fi-1,j-1+fi-1,j边界条件：fi,0=1,fi,i=1。时间复杂度为O(n*k)。,方法二,
3、当k达到106的时候，方法一会超时。由于10007是素数，在计算C(k,n)mod 10007时可以采用扩展GCD来解决。时间复杂度为O(k)。,参考代码：,#include#include using namespace std;ifstream fin(factor.in);ofstream fout(factor.out);const int MAXN=1005;int dpMAXNMAXN,a,b,k,n,m,ans;int main()finabknm;dp11=dp12=1;for(int i=2;i=k;i+)for(int j=1;j=i+1;j+)dpij=(dpi-1j+d
4、pi-1j-1)%10007;ans=dpkm+1;for(int i=1;i=n;i+)ans=(ans%10007)*(a%10007)%10007;for(int i=1;i=m;i+)ans=(ans%10007)*(b%10007)%10007;foutansendl;return 0;,例2：B光滑数,【问题描述】B为一个正整数，如果一个自然数N的质因子分解式中没有大于B的因子，我们就称N是一个B光滑数。请你编一个程序，求出某个区间中所有的B光滑数的个数。输入：输入文件名为bnum.in，仅有一行，包含三个用空格隔开的整数N,M,B,其中1=N=2，000，000，000,1=M=
5、100，000，000,1=B=1，000，000。输出：输出文件名为bnum.out，仅一行。一个整数，表示区间N,N+M之间的B光滑数的个数。【样例输入】30 10 5【样例输出】4,参考题解,首先我们定义一个表primax,prii表示第i个质数，第一个质数为2.设数组max，其中maxi记录i的最大质因子。定义f(b,x1,x2)表示区间x1,x2之间不包括大于第b个质数的质因子的所有正整数，则有如下递归关系：F(b,x1,x2)=f(b-1,x1,x2)+f(b,(x1-1)div prib+1,x2 div prib)该递归式的边界条件为：F=0 x1x2F=x2-x1+1 x2=
6、prib可直接验证 x1=x2F=trunc(log2(x2)-trunc(log2(x1)b=1,例3：出栈序列统计,【问题描述】栈是常用的一种数据结构，有n个元素在栈顶端一侧等待进栈，栈顶端另一侧是出栈序列。你已经知道栈的操作有两种：push和pop，前者是将一个元素进栈，后者是将栈顶元素弹出。现在要使用这两种操作，由一个操作序列可以得到一系列的输出序列。请你编程求出对于给定的n，计算并输出由操作数序列1，2，n，经过一系列操作可能得到的输出序列总数。【输入】【输出】就一个数n(1n1000)。一个数，即可能输出序列的总数目。【样例】stack.in stack.out3 5,【算法分析】
7、,我们通过回溯的方法计算并输出不同的出栈序列，这里只要求输出不同的出栈序列总数目，所以我们希望能找出相应的递推公式进行处理。从排列组合的数学知识可以对此类问题加以解决。我们先对n个元素在出栈前可能的位置进行分析，它们有n个等待进栈的位置，全部进栈后在栈里也占n个位置，也就是说n个元素在出栈前最多可能分布在2*n位置上。出栈序列其实是从这2n个位置上选择n个位置进行组合，根据组合的原理，从2n个位置选n个，有C(2n,n)个。但是这里不同的是有许多情况是重复的，每次始终有n个连续的空位置，n个连续的空位置在2n个位置里有n+1种，所以重复了n+1次。所以出栈序列的种类数目为：,【算法分析】,C(
8、2n,n)/(n+1)=2n*(2n-1)*(2n-2)*(n+1)/n!/(n+1)=2n*(2n-1)*(2n-2)*(n+2)/n!。考虑到这个数据可能比较大，所以用高精度运算来计算这个结果。本题实际是一个经典的Catalan数模型。有关Catalan数的详细解释请参考组合数学等书。,参考程序：,#include#include using namespace std;typedef long long lld;lld i,n,ans;lld h1000;int main()freopen(stack.in,r,stdin);freopen(stack.out,w,stdout);h2=
9、1;cinn;n=n+2;for(lld i=3;i=n;i+)for(lld k=2;ki;k+)hi=hi+hk*hi-k+1;couthnendl;return 0;,【思考与提高】,我们知道，在某个状态下，所能做的操作(移动方法)无非有两种：（1）将右方的等待进栈的第一个元素进栈；（2）将栈顶的元素出栈，进入左边的出栈序列。设此时右方、栈、左方的元素个数分别为a，b，c。我们就能用(a,b,c)表示出当前的状态。显然n=a+b+c，则c=n-a-b。即已知a和b，c就被确定，所以我们可以用(a,b)来作为状态的表示方法。则起始状态为(n,0)，目标状态为(0,0)。又由上面的两种移动方
10、法，我们可类似的得到两种状态转移方式：,【思考与提高】,【思考与提高】,再设f(a,b)为从状态(a,b)通过移动火车变为状态(0,0)的所有移动方法。类似于动态规划的状态转移方程，我们可写出以下递归式：,边界值：f(0,0)=1。有了这个递归公式后，再写程序就比较简单了。,例4：骨牌覆盖问题,有2行n列的长方形方格，要求用n个1*2的骨牌铺满。有多少种铺法？如n=3时有以下3种覆盖方法：,方法一,状态：fi表示铺满2*i的长方形的方案数找规律,手工或搜索求出i=1,2,3,4,5的方案数分别为1，2，3，5，8,容易发现 fi=fi-1+fi-2(i=3)边界条件：f1=1,f2=2递推关系
11、式 1 i=1fi=2 i=2 fi-1+fi-2 i=3答案为fn，时间复杂度为O(n)。,方法二,对于i=3,分析第一列的两个格子覆盖情况，有两种情况：1.用1*2的骨牌竖着覆盖第一列，这种情况的方案数等于后面2*(i-1)的长方形的覆盖方案数，即fi-1；2.用两个1*2的骨牌横着覆盖，这种情况的方案数等于后面2*(i-2)的长方形的覆盖方案数，即fi-2。所以fi=fi-1+fi-2,方法三,分析用1*2的骨牌覆盖列的位置来计算方案数1.如果i为偶数，覆盖方案分为两类：(1)没有竖立覆盖其中一列的情况：全部用横向覆盖的方案，方案数为1；(2)有竖立覆盖的情况：为了避免重复，考虑第一次竖
12、立覆盖的位置在x列，x必须是奇数，而且前1到x-1列覆盖方法唯一，全部采用横向覆盖，方案数等于后面i-x列的覆盖情况，即fi-x。所以当i为偶数时,fi=1+f1+f3+.+fi-3+fi-1 2.如果i是奇数，一定有竖立覆盖的情况，fi=1+f2+f4+.+fi-3+fi-1如何证明该递推关系式等价于fi=fi-1+fi-2？试着用横向覆盖的来分析递推关系式。,方法四,分治，一分为二来考虑,左边为n div 2列，右边为n-n div 2列，如果左右独立则方案数为fn div 2*fn-n div 2,如果有横向覆盖第n div 2列和第n div 2+1列，则方案数为fn div 2-1*fn-n div 2-1所以fn=fn div 2*fn-n div 2+fn div 2-1*fn-n div 2-1,参考代码：,#include using namespace std;long long f60;ifstream fin(domino.in);ofstream fout(domino.out);int main()int n,i;finn;f1=1;f2=2;for(i=3;i=n;i+)fi=fi-1+fi-2;foutfnendl;return 0;,
