最新04.递推算法(C++版包括习题参考答案)ppt课件.ppt

《最新04.递推算法(C++版包括习题参考答案)ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、04.递推算法(C++版包括习题参考答案)递推法是一种重要的数学方法，在数学的各个领域中都有广泛的运用，也是计算机用于数值计算的一个重要算法。这种算法特点是：一个问题的求解需一系列的计算，在已知条件和所求问题之间总存在着某种相互联系的关系，在计算时，如果可以找到前后过程之间的数量关系（即递推式），那么，从问题出发逐步推到已知条件，此种方法叫逆推。无论顺推还是逆推，其关键是要找到递推式。这种处理问题的方法能使复杂运算化为若干步重复的简单运算，充分发挥出计算机擅长于重复处理的特点。递推算法的首要问题是得到相邻的数据项间的关系

2、（即递推关系）。递推算法避开了求通项公式的麻烦，把一个复杂的问题的求解，分解成了连续的若干步简单运算。一般说来，可以将递推算法看成是一种特殊的迭代算法。【例1】数字三角形。如下所示为一个数字三角形。请编一个程序计算从顶到底的某处的一条路径，使该路径所经过的数字总和最大。只要求输出总和。1、一步可沿左斜线向下或右斜线向下走；2、三角形行数小于等于100；3、三角形中的数字为0，1，…，99；测试数据通过键盘逐行输入，如上例数据应以如下所示格式输入：5738810274445265【算法分析】此题解法有多种，从递推的思想出发

3、，设想，当从顶层沿某条路径走到第i层向第i+1层前进时，我们的选择一定是沿其下两条可行路径中最大数字的方向前进，为此，我们可以采用倒推的手法，设a[i][j]存放从i,j出发到达n层的最大值，则a[i][j]=max{a[i][j]+a[i+1][j]，a[i][j]+a[i+1][j+1]}，a[1][1]即为所求的数字总和的最大值。下面是输入n，输出x1~xn的c++程序：#includeusingnamespacestd;intmain(){intn,i,j,a[101];cout<<"inpu

4、tn:";//输入骨牌数cin>>n;a[1]=1;a[2]=2;cout<<"x[1]="<

5、盘格数设有一个N*M方格的棋盘（l≤N≤100，1≤M≤100）。求出该棋盘中包含有多少个正方形、多少个长方形（不包括正方形）。例如：当N=2，M＝3时：正方形的个数有8个：即边长为1的正方形有6个；边长为2的正方形有2个。长方形的个数有10个：即2*1的长方形有4个：1*2的长方形有3个：3*1的长方形有2个：3*2的长方形有1个：程序要求：输入：N，M输出：正方形的个数与长方形的个数如上例：输入：23输出：810【算法分析】1.计算正方形的个数s1边长为1的正方形个数为n*m边长为2的正方形个数为(n-1)*(m-1

6、)边长为3的正方形个数为(n-2)*(m-2)…………边长为min{n，m}的正方形个数为(m-min{n，m}+1)*(n-min{n，m}+1)根据加法原理得出s1=2.长方形和正方形的个数之和s宽为1的长方形和正方形有m个，宽为2的长方形和正方形有m-1个，┉┉，宽为m的长方形和正方形有1个；长为1的长方形和正方形有n个，长为2的长方形和正方形有n-1个，┉┉，长为n的长方形和正方形有1个；根据乘法原理s=(1+2+┉┉+n)*(1+2+┉┉+m)=3.长宽不等的长方形个数s2显然，s2=s-s1=-由此得出算法：

7、#includeusingnamespacestd;intmain(){intn,m;cin>>m>>n;intm1=m,n1=n,s1=m*n;//计算正方形的个数s1while(m1!=0&&n1!=0){m1--;n1--;s1+=m1*n1;}ints2=((m+1)*(n+1)*m*n)/4-s1;//计算长方形的个数s2cout<

8、要过两个月长成成虫。假设每个成虫不死，第一个月只有一对成虫，且卵长成成虫后的第一个月不产卵(过X个月产卵)，问过Z个月以后，共有成虫多少对？0=