第3章 递推算法(C++版).pptVIP

第三章递推算法【例4】昆虫繁殖【问题描述】科学家在热带森林中发现了一种特殊的昆虫，这种昆虫的繁殖能力很强。每对成虫过x个月产y对卵，每对卵要过两个月长成成虫。假设每个成虫不死，第一个月只有一对成虫，且卵长成成虫后的第一个月不产卵(过X个月产卵)，问过Z个月以后，共有成虫多少对？0=X=20,1=Y=20,X=Z=50【输入格式】x,y,z的数值【输出格式】过Z个月以后，共有成虫对数【输入样例】128【输出样例】37【参考程序】#includeiostreamusingnamespacestd;intmain(){longlonga[101]={0},b[101]={0},i,j,x,y,z;cinxyz;for(i=1;i=x;i++){a[i]=1;b[i]=0;}for(i=x+1;i=z+1;i++)//因为要统计到第z个月后，所以要for到z+1{b[i]=y*a[i-x];a[i]=a[i-1]+b[i-2];}couta[z+1]endl;return0;}【例5】位数问题【问题描述】在所有的N位数中，有多少个数中有偶数个数字3？由于结果可能很大，你只需要输出这个答案对12345取余的值。【输入格式】读入一个数N【输出格式】输出有多少个数中有偶数个数字3。【输入样例】2【输出样例】73【数据规模】1=N=1000【样例说明】在所有的2位数字，包含0个3的数有72个，包含2个3的数有1个，共73个【算法分析】方法一：排列组合(但需要运用动态规划)。可以列出公式,在n个格子中放x个3(其中x为偶数,包括0).。c(n,x)*9^(n-x)-c(n-1,x)*9^(n-x-1)含义为在n个格子中取x个3,且不考虑第一位的特殊情况为c(n,x)*9^(n-x)。而第一位为0的情况,为c(n-1,x)*9^(n-x-1),两者减下,就为答案。方法二：递推考虑这种题目,一般来说都是从第i-1位推导第i位,且当前位是取偶数还是取奇数的。恍然大悟.可以用f[i][0]表示前i位取偶数个3有几种情况,f[i][1]表示前i位取奇数个3有几种情况。则状态转移方程可以表示为:f[i][0]=f[i-1][0]*9+f[i-1][1];f[i][1]=f[i-1][0]+f[i-1][1]*9;边界条件:f[1][1]=1;f[1][0]=9;【参考程序】#includeiostreamusingnamespacestd;intmain(){intf[1001][2],n,i,x;cinn;f[1][1]=1;f[1][0]=9;for(i=2;i=n;i++){x=f[1][0];if(i==n)x--;f[i][0]=(f[i-1][0]*x+f[i-1][1])%12345;f[i][1]=(f[i-1][1]*x+f[i-1][0])%12345;}coutf[n][0];return0;}【例6】过河卒（Noip2002）【问题描述】棋盘上A点有一个过河卒，需要走到目标B点。卒行走的规则：可以向下、或者向右。同时在棋盘上的任一点有一个对方的马（如C点），该马所在的点和所有跳跃一步可达的点称为对方马的控制点，如图3-1中的C点和P1，……，P8，卒不能通过对方马的控制点。棋盘用坐标表示，A点(0,0)、B点(n,m)(n,m为不超过20的整数),同样马的位置坐标是需要给出的，C≠A且C≠B。现在要求你计算出卒从A点能够到达B点的路径的条数。【算法分析】跳马是一道老得不能再老的题目，我想每位编程初学者都学过，可能是在学回溯或有哪些信誉好的足球投注网站等算法的时候，很多书上也有类似的题目，一些比赛中也出现过这一问题的变形（如NOIP1997初中组的第三题）。有些同学一看到这条题目就去有哪些信誉好的足球投注网站，即使你编程调试全通过了，运行时你也会发现：当n,m=15就会超时。其实，本题稍加分析就能发现，要到达棋盘上的一个点，只能从左边过来（我们称之为左点）或是从上面过来（我们称之为上点），所以根据加法原理，到达某一点的路