算法设计与分析实用教程杨克昌 第3章 递推

《算法设计与分析实用教程杨克昌 第3章 递推》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、教学要求了解递推算法的概念与各类递推设计要领应用递推算法求解典型的数列与数阵案例本章重点对某些实际问题设计多种递推算法对某些递推算法进行改进与优化第3章递推3.1递推概述1.递推的概念(1)递推是利用问题本身所具有的递推关系求解问题的一种方法，是在命题归纳时，可以由n−k,…,n−1的情形推得n的情形。(2)递推算法的基本思想是把一个复杂的庞大的计算过程转化为简单过程的多次重复，该算法充分利用了计算机的运算速度快和不知疲倦的特点，从头开始一步步地推出问题最终的结果。(3)一个有规律的序列的相邻位置上的项之间通常存在着一定的关系，可以借助已知的项，利用特定的关系逐项推算出它的后继

2、项的值，直到找到所需的那一项为止。2.递推关系递推算法的首要问题是得到相邻的数据项之间的关系，即递推关系。递推关系是一种高效的数学模型，是递推应用的核心。递推关系不仅在各数学分支中发挥着重要的作用，由它所体现出来的递推思想在各学科领域中更是显示出其独特的魅力。3.递推的实施步骤（1）确定递推变量递推变量可以是简单变量，也可以是一维或多维数组。（2）建立递推关系递推关系是递推的依据，是解决递推问题的关键。（3）确定初始（边界）条件根据问题最简单情形的数据确定递推变量的初始（边界）值，这是递推的基础。（4）对递推过程进行控制递推过程控制：递推在什么时候结束，满足什么条件结束。4.递推算

3、法框架描述（1）简单顺推算法顺推即从前往后推，从已求得的规模为1,2,…,i-1的一系列解，推出问题规模为i的解，直至得到规模为n的解：f(1—i-1)=<初始值>；//确定初始值for(k=i;k<=n;k++)f(k)=<递推关系式>；//根据递推关系实施顺推print(f(n))；//输出n规模的解f(n)（2）简单逆推算法逆推即从后往前推，从已求得的规模为n,n−1,…,i+1的一系列解，推出问题规模为i的解，直至得到规模为1的解：f(n—i+1)=<初始值>；//确定初始值for(k=i;k>=1;k--)f(k)=<递推关系式>；//实施逆推print(f(1))；（3

4、）较复杂的递推问题需设置多重循环递推。（4）多关系分级递推算法当递推关系包含两个或两个以上关系式时，通常应用多关系分级递推算法求解。f(1：i-1)=<初始值>；//赋初始值for(k=i;k<=n;k++){if(<条件1>)f(k)=<递推关系式1>；//根据关系1递推……if(<条件m>)f(k)=<递推关系式m>；//根据关系m递推}print(f(n))；//输出n规模的解f(n)3.2递推数列3.2.1双关系递推数列设集合M定义如下:(1)1∈M(2)x∈M=>2x+1∈M,5x-1∈M(3)再无其它的数属于M。试求集合M元素从小到大排列所得序列的第n（n<10000）

5、项与前n项之和。1.递推设计要点该题有2x+1,5x-1两个递推关系，设置数组m(i)存储M元素从小到大排列序列的第i项，显然m(1)=1，这是递推的初始条件。同时设置两个队列：2*m(p2)+1,p2=1,2,3,…5*m(p5)-1,p5=1,2,3,…这里用p2表示2x+1这一队列的下标，用p5表示5x-1这一队列的下标。　　从两队列中选一排头，通过比较选数值较小者送入数组m中。所谓“排头”就是队列中尚未选入m的最小的下标。若2*m(p2)+1<5*m(p5)-1,则m(i)=2*m(p2)+1;下标p2增1；若2*m(p2)+1>5*m(p5)-1,则m(i)=5*

6、m(p5)-1;下标p5增1；若2*m(p2)+1=5*m(p5)-1,则m(i)=5*m(p5)-1;下标p2与p5同时增1。2.递推设计描述scanf("%ld",&n);m[1]=1;s=1;p2=1;p5=1;for(i=2;i<=n;i++){if(2*m[p2]+1<5*m[p5]-1){m[i]=2*m[p2]+1;p2++;}else{m[i]=5*m[p5]-1;if(2*m[p2]+1==5*m[p5]-1)p2++;p5++;}s+=m[i];}printf("m(%ld)=%ld,s=%ld",n,m[n],s);3.2.2振动数列（1）递推产生各项根

7、据递推式，在i循环中据项序号i(2─n)为奇或偶作不同递推:mod(i,2)=0(即i为偶数)时,a(i)=a(i/2)+2mod(i,2)=1(即i为奇数)时,a(i)=a((i+1)/2)-a((i-1)/2)（2）统计平台数与波峰数在对项a[i]（m+1≤i≤n-1）操作时标记j=i,在条件(a[i]==a[i+1])循环中项号i实施增1：若i>j，表明存在i-j+1>2项相等，应用p++统计平台数。若a[i]同时大于其前项a[j-1]与后项a[i+1]，即为一