c++递推算法详解ppt课件.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,递 推 算 法,1,递推问题求解过程,确定状态,确定递推关系和边界条件,程序实现,2,例1：计算系数(NOIP2011day2),【题目描述】给定一个多项式(ax+by),k,请求出多项式展开后x,n,y,m,项的系数,【输入】共一行，包含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，,且n+m=k，0a，b1,000,000。,3,方法一,根据二项式定理可知：,(ax+by),k,=,=,取i=n,x,n,y,m,的系数为,其中a,n,和b,m,可以用快速幂来计算，在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)。,4,方法二,当k达到10,6,的时候，方法一会超时。,由于10007是素数，在计算C(k,n)mod 10007时可以采用扩展GCD来解决。,时间复杂度为O(k)。,5,参考代码：,#include,#include,using namespace std;,ifstream fin(factor.in);,ofstream fout(factor.out);,const int MAXN=1005;,int dpMAXNMAXNa,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+dpi-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;,6,例,2,：,B,光滑数,【,问题描述,】,B,为一个正整数，如果一个自然数,N,的质因子分解式中没有大于,B,的因子，我们就称,N,是一个,B,光滑数。请你编一个程序，求出某个区间中所有的,B,光滑数的个数。,输入：,输入文件名为,bnum.in,，仅有一行，包含三个用空格隔开的整数,N,M,B,其中,1=N=2,，,000,，,000,，,000,1=M=100,，,000,，,000,1=Bx2,F=x2-x1+1 x2n;,n=n+2;,for(lld i=3;i=n;i+),for(lld k=2;ki;k+),hi=hi+hk*hi-k+1;,couthn=3),边界条件：f1=1,f2=2,递推关系式,1 i=1,fi=2 i=2,fi-1+fi-2 i=3,答案为fn，时间复杂度为O(n),。,17,方法二,对于i=3,分析第一列的两个格子覆盖情况，有两种情况：,1.用1*2的骨牌竖着覆盖第一列，这种情况的方案数等于后面2*(i-1)的长方形的覆盖方案数，即fi-1；,2.用两个1*2的骨牌横着覆盖，这种情况的方案数等于后面2*(i-2)的长方形的覆盖方案数，即fi-2。,所以fi=fi-1+fi-2,18,方法三,分析用1*2的骨牌覆盖列的位置来计算方案数,1.如果i为偶数，覆盖方案分为两类：,(1)没有竖立覆盖其中一列的情况：全部用横向覆盖的方案，方案数为1；,(2)有竖立覆盖的情况：为了避免重复，考虑第一次竖立覆盖的位置在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？,试着用横向覆盖的来分析递推关系式。,19,方法四,分治，一分为二来考虑,左边为,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,20,参考代码：,#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;,21,