递推算法解析集锦
递推算法集锦
一、编写程序求50以内的勾股弦数。即满足c*c=b*b+a*a的三个自然数，要求
b>a。将所有符合要求的a,b,c组合输出至屏幕。
解答：
采用穷举算法，在主函数中实现。
#include
using namespace std;
int main(){
int a,b,c,count=0;
cout<<"勾股弦数有："< for(c=5;c<=50;c++) //产生50以内的数 for(b=4;b for(a=3;a if(c*c==b*b+a*a){ cout< count++; if(count%10==0) cout< } } cout<<"共计："< return 0; } 二、设计函数factors(num,k)，返回整数m中包含因子k的个数，如果没有该因子，则返回0。 （提示：必须先判断整数m能否被k整除。） 解法一：迭代法 #include int factors(int num,int k){ //缺省返回值为整型 int count=0; while(num%k==0){ count++; num/=k; } return count; } void main(){ cout<<"factors(1875,5)="< cout<<"factors(64,3)="< } 解法二：递归函数，传值调用 # include # include int factors(int m,int k,int num) { if(m%k!=0){num=0; return num;} if(m%k==0) num=1; num+=factors(m/k,k,num); return num; } void main() { int m,k,num=0; cout<<"\n请输入一个整数和一个因子："; cin>>m>>k; cout<<'\n'< cout< cout< } 解法三：递归函数，使用引用参数 #include void factors(int m,int k,int &num) { if(m%k!=0) return ; if(m%k==0) num++; factors(m/k,k,num); return ; } void main() { int m,k,num=0; cout<<"\n请输入一个整数和一个因子："; cin>>m>>k; cout<<'\n'< factors(m,k,num); cout< } 三、歌德巴赫猜想指出：任何一个充分大的偶数都可以表示为两个素数之和。例如：4=2+2 6=3+3 8=3+5 …… 50=3+47 请编写程序将50~100之间的所有偶数用两个素数之和表示。判断一个整数是否为素数用函数prime()完成。 #include #include bool prime(int m){ if(m==1||m==0) return false; if(m==2) return true; int k=(int)sqrt(m); for(int i=2;i<=k;i++) //穷举法 if(m%i==0) break; if(i>k) return true; else return false; } void main(){ for(int n=4;n<=50;n+=2){ for(int i=2;i<=n/2;i++) if(prime(i)&&prime(n-i)) cout< } } 四、利用反正切展开计算π的近似值，要求误差10-5，公式如下： +-+-≈753)(7 53x x x x x arctg 令x=1，可计算出π/4的近似值。要求计算单项值用函数double item(int n,double x)计算，返回后对该项累加。函数item 放在头文件中。再尝试作为外部函数。 解一：采用递推法。每一项全看作奇数项，而偶数项全为零。第1项为x ，第3项为第1项乘以x 的平方除以项序号3乘以-1，其余类推。同时和的误差小于最后一项的绝对值。 #include #include const double e=1e-6; void main(){ double x,a,sum; int i=3; cout<<"请输入弧度值x ："< cin>>x; a=x; sum=x; do{ a*=x*x*(-1); //计算单项值 sum+=a/i; i+=2; }while(fabs(a/i)>e); cout<<"arctg("< cout<<"PI="<<4*sum< } 解二：计算单项值用函数double item(int n,double x)计算 #include #include const double e=1e-3; double item(int n,double x){ //计算单项值 double a=x; for(int i=1;i a*=x; return a/n; } void main(){ double x,d,sum; int i=3,f=1; cout<<"请输入弧度值x："< cin>>x; sum=x; do{ f=-f; d= item(i,x); //函数调用 sum+=f*d; cout<<"s="< i+=2; }while(fabs(d)>e); cout<<"arctg("< cout<<"PI="<<4*sum< } 五、将一个十进制数对m辗转取模，结果按十六进制格式输出（不是数值转换）。递归程序的函数调用 #include void f(int); void main() { f(257); } void f(int n) { if(n>16) f(n/16); //m=16 cout< } 此程序调用2次，输出为0 1 如果原始数据为271则输出为0 F （十六进制） 如果原始数据为272则输出为1 1 0 （3次调用函数） 如果将输出语句移至函数调用前面？ #include void f(int); void main() { f(257); } void f(int n) { cout< if(n>16) f(n/16); //m=16 } 此程序调用2次的方式不变，输出为1 0（先输出，后进行递归调用）注意：以上递归函数中都没有改变参量n的值。 题目： （递推最小二乘法） 考虑如下系统： )()4(5.0)3()2(7.0)1(5.1)(k k u k u k y k y k y ξ+-+-=-+-- 式中，)(k ξ为方差为0.1的白噪声。 取初值I P 610)0(=、00=∧ ）（θ。选择方差为1的白噪声作为输入信号)(k u ，采用PLS 法进行参数估计。 Matlab 代码如下： clear all close all L=400; %仿真长度 uk=zeros(4,1); %输入初值：uk(i)表示u(k-i) yk=zeros(2,1); %输出初值 u=randn(L,1); %输入采用白噪声序列 xi=sqrt(0.1)*randn(L,1); %方差为0.1的白噪声序列 theta=[-1.5;0.7;1.0;0.5]; %对象参数真值 thetae_1=zeros(4,1); %（）θ初值 P=10^6*eye(4); %题目要求的初值 for k=1:L phi=[-yk;uk(3:4)]; %400×4矩阵phi 第k 行对应的y(k-1),y(k-2),u(k-3), u(k-4) y(k)=phi'*theta+xi(k); %采集输出数据 %递推最小二乘法的递推公式 K=P*phi/(1+phi'*P*phi); thetae(:,k)=thetae_1+K*(y(k)-phi'*thetae_1); P=(eye(4)-K*phi')*P; %更新数据 thetae_1=thetae(:,k); for i=4:-1:2 uk(i)=uk(i-1); end uk(1)=u(k); for i=2:-1:2 yk(i)=yk(i-1); 一、 递推最小二乘法 递推最小二乘法的一般步骤： 1. 根据输入输出序列列出最小二乘法估计的观测矩阵?： ] )(u ... )1( )( ... )1([)(T b q n k k u n k y k y k ------=? 没有给出输出序列的还要先算出输出序列。 本例中， 2)]-u(k 1),-u(k 2),-1),-y(k -[-y(k )(T =k ?。 2. 给辨识参数θ和协方差阵P 赋初值。一般取0θ=0或者极小的数，取σσ,20I P =特别大，本例中取σ=100。 3. 按照下式计算增益矩阵G ： ) ()1()(1)()1()(k k P k k k P k G T ???-+-= 4. 按照下式计算要辨识的参数θ： )]1(?)()()[()1(?)(?--+-=k k k y k G k k T θ?θθ 5. 按照下式计算新的协方差阵P ： )1()()()1()(---=k P k k G k P k P T ? 6. 计算辨识参数的相对变化量，看是否满足停机准则。如满足，则不再递推；如不满足， 则从第三步开始进行下一次地推，直至满足要求为止。 停机准则：ε???<--) (?)1(?)(?max k k k i i i i 本例中由于递推次数只有三十次，故不需要停机准则。 7. 分离参数：将a 1….a na b 1….b nb 从辨识参数θ中分离出来。 8. 画出被辨识参数θ的各次递推估计值图形。 为了说明噪声对递推最小二乘法结果的影响，程序5-7-2在计算模拟观测值时不加噪 声， 辨识结果为a1 =1.6417，a2 = 0.7148，b1 = 0.3900，b2 =0.3499，与真实值a1 =1.642， a2 = 0.715， b1 = 0.3900，b2 =0.35相差无几。 程序5-7-2-1在计算模拟观测值时加入了均值为0，方差为0.1的白噪声序列，由于噪 声的影响，此时的结果为变值，但变化范围较小，现任取一组结果作为辨识结果。辨识结果为a1 =1.5371， a2 = 0.6874， b1 = 0.3756，b2 =0.3378。 程序5-7-2-2在计算模拟观测值时加入了有色噪声，有色噪声为 E(k)+1.642E(k-1)+0.715E(k-2)，E(k)是均值为0，方差为0.1的白噪声序列，由于有色噪声的影响，此时的辨识结果变动范围远比白噪声时大，任取一组结果作为辨识结果。辨识结果为a1 =1.6676， a2 = 0.7479， b1 = 0.4254，b2 =0.3965。 可以看出，基本的最小二乘法不适用于有色噪声的场合。 递推算法典型例题 一、教学目标 1、由浅入深，了解递推算法 2、掌握递推算法的经典例题 二、重点难点分析 1、重点：递推关系的建立 2、难点：如何将所求问题转化为数学模型 三、教具或课件 微机 四、主要教学过程 (一)引入新课 客观世界中的各个事物之间或者一个事物的内部各元素之间，往往存在(隐藏)着很多本质上的关联。我们设计程序前．应该要通过细心的观察、丰富的联想、不断的尝试推理．尽可能先归纳总结出其内在规律，然后再把这种规律性的东西抽象成数学模型，最后再去编程实现。递推关系和递归关系都是一种简洁高效的常见数学模型，我们今天先来深入研究一下递推算法如何实现。 (二)教学过程设计 递推法是一种重要的数学方法，在数学的各个领域中都有广泛的运用，也是计算机用于数值计算的一个重要算法。这种算法特点是：一个问题的求解需一系列的计算，在已知条件和所求问题之间总存在着某种相互联系的关系，在计算时，如果可以找到前后过程之间的数量关系（即递推式），那么，这样的问题可以采用递推法来解决。从已知条件出发，逐步推出要解决的问题，叫顺推；从问题出发逐步推到已知条件，此种方法叫逆推。无论顺推还是逆推，其关键是要找到递推式。这种处理问题的方法能使复杂运算化为若干步重复的简单运算，充分发挥出计算机擅长于重复处理的特点。 递推算法的首要问题是得到相邻的数据项间的关系（即递推关系）。递推算法避开了通项公式的麻烦，把一个复杂的问题的求解，分解成了连续的若干步简单运算。一般说来可以将递推算法看成是一种特殊的迭代算法。（在解题时往往还把递推问题表现为迭代形式，用循环处理。所谓“迭代”，就是在程序中用同一个变量来存放每一次推算出来的值，每一次循环都执行同一个语句，给同一变量赋以新的值，即用一个新值代替旧值， AIC 法定阶的依阶次递推算法程序 依阶次递推算法所得到估计θ ?，再按下式计算残差方差的估计值： ∑==N j j e N 122 )?,(1?θσ 由上式的结果计算AIC ： )(2?lg AIC 2b a n n N ++=σ 在结果中找到AIC 最小的模型（阶次和参数）就是估计的模型。 由输出数据可知当k1=5时aic 的值最小。所以最后的辨识结果取阶次为5，参数为： –1.18394，0.813938，–0.518174，0.348744，–0.116818， 1.07998，–0.74386，0.475444，–0.253022，0.122781 判断的阶次的最小aic 值： aic= – 8981.58发生在阶次为5时。 源程序： #include 实验一 用递推公式计算定积分 09信息 符文飞 07 1、实验目的： 由于一个算法是否稳定，十分重要。如果算法不稳定，则数值计算的结果就会严重背离数学模型的真实结果，因此，在选择数值计算公式来进行近似计算时，我们应特别注意选用那些在数值计算过程中不会导致误差迅速增长的公式。体会稳定性在选择算法中的地位．误差扩张的算法是不稳定的，是我们所不期望的；误差衰竭的算法是稳定的．是我们努力寻求的，这是贯穿本课程的目标．通过上机计算，了解舍入误差所引起的数值不稳定性。 2、实验题目： 对n =0,1,2,…,20,计算定积分dx x x y n n ?+=10 5 3、实验原理 由于y(n)= = – 在计算时有两种迭代方法，如下： 方法一： y(n)= – 5*y(n-1),n=1,2,3, (20) 取y(0)= = ln6-ln5 ≈ 0.182322 方法二： 利用递推公式：y(n-1)=-*y(n),n=20,19, (1) 而且，由 = * ≤≤* = 可取：y(20)≈*()≈0.008730. 4、实验内容： 算法1的程序： y0=log(6.0)-log(5.0); y1=0; n=1; while n<=30 y1=1/n-5*y0; fprintf('y[%d]=%-20f',n,y1); y0=y1; n=n+1; if mod(n,1)==0; fprintf('\n') end end 算法2的程序： y0=(1/105+1/126)/2; y1=0; n=1; while n<=30 y1=1/(5*n)-y0/5; fprintf('y[%d]=%-20f',n,y1) y0=y1; n=n+1; if mod(n,1)==0 fprintf('\n') end end 5、实验结果 对于算法1： y[1]=0.088392 y[2]=0.058039 y[3]=0.043139 y[4]=0.034306 y[5]=0.028468 y[6]=0.024325 y[7]=0.021233 y[8]=0.018837 y[9]=0.016926 递推算法 一、学习要点：（经典的五种递推关系） 1.fibonacci（斐波那契）数列 2.hanoi（汉诺）塔 3.平面分割 4.catalan数（卡特兰数） 5.第二类string数 二、重点提示 1.产生catalan数的参考程序： Const max=21; Var c:array[2..max] of longint; n,i,k:integer; total:longint; begin write(‘input n=’);readln(n); c[2]:=1; for i:=3 to n do begin c[i]:=0; for k:=2 to i-1 do c[i]:=c[i]+c[k]*c[i-k+1]; end; writeln(‘catalan=’,c[n]); end. Catalan数，从第二项开始为：1,1,2,5,14,42,132,429,1430,4862,16796,58786,208012, 742900,2674440,9694545,35357670,129644790,477638700,1767263190 2.产生第二类的string数的参考程序： Var n,k:integer; Function s(n,k:integer):longint; Begin If (n 实用算法(基础算法-递推法-01) 有一类试题，每相邻两项数之间的变化有一定的规律性，我们可将这种规律归纳成如下简捷的递推关系式： F n=g(F n-1) 这就在数的序列中，建立起后项和前项之间的关系，然后从初始条件(或最终结果)入手，一步步地按递推关系递推，直至求出最终结果(或初始值)。很多程序就是按这样的方法逐步求解的。如果对一个试题，我们要是能找到后一项与前一项的关系并清楚其起始条件(最终结果)，问题就好解决，让计算机一步步算就是了，让高速的计算机做这种重复运算，可真正起到“物尽其用”的效果。 递推分倒推法和顺推法两种形式。一般分析思路： if求解条件F1 then begin{倒推} 由题意(或递推关系)确定最终结果Fa； 求出倒推关系式F i-1=g'(F i); i=n;{从最终结果Fn出发进行倒推} while 当前结果F i非初始值F1 do由F i-1=g(F1)倒推前项； 输出倒推结果F1和倒推过程； end {then} else begin{顺推} 由题意(或顺推关系)确定初始值F1(边界条件)； 求出顺推关系式F1=g(Fi-1); i=1;{由边界条件F1出发进行顺推} while 当前结果Fi非最终结果Fn do由Fi=g(Fi-1)顺推后项； 输出顺推结果Fn和顺推过程； end; {else} 一、倒推法 所谓倒推法，就是在不知初始值的情况下，经某种递推关系而获知问题的解或目标，再倒推过来，推知它的初始条件。因为这类问题的运算过程是一一映射的，故可分析得其递推公式。然后再从这个解或目标出发，采用倒推手段，一步步地倒推到这个问题的初始陈述。 下面举例说明。 [例1] 贮油点 一辆重型卡车欲穿过1000公里的沙漠，卡车耗油为1升/公里，卡车总载油能力为500公升。显然卡车一次是过不了沙漠的。因此司机必须设法在沿途建立几个储油点，使卡车能顺利穿越沙漠，试问司机如何建立这些储油点？每一储油点应存多 递推算法集锦 一、编写程序求50以内的勾股弦数。即满足c*c=b*b+a*a的三个自然数，要求 b>a。将所有符合要求的a,b,c组合输出至屏幕。 解答： 采用穷举算法，在主函数中实现。 #include 递推最小二乘法的一般步骤： 1. 根据输入输出序列列出最小二乘法估计的观测矩阵?： ] )(u ... )1( )( ... )1([)(T b q n k k u n k y k y k ------=? 没有给出输出序列的还要先算出输出序列。 本例中， 2)]-u(k 1),-u(k 2),-1),-y(k -[-y(k )(T =k ?。 2. 给辨识参数θ和协方差阵P 赋初值。一般取0θ=0或者极小的数，取σσ,20I P =特别 大，本例中取σ=100。 3. 按照下式计算增益矩阵G ： ) ()1()(1)()1()(k k P k k k P k G T ???-+-= 4. 按照下式计算要辨识的参数θ： )]1(?)()()[()1(?)(?--+-=k k k y k G k k T θ?θθ 5. 按照下式计算新的协方差阵P ： )1()()()1()(---=k P k k G k P k P T ? 6. 计算辨识参数的相对变化量，看是否满足停机准则。如满足，则不再递推；如不满足， 则从第三步开始进行下一次地推，直至满足要求为止。 停机准则：ε???<--) (?)1(?)(?max k k k i i i i 本例中由于递推次数只有三十次，故不需要停机准则。 7. 分离参数：将a 1….a na b 1….b nb 从辨识参数θ中分离出来。 8. 画出被辨识参数θ的各次递推估计值图形。 为了说明噪声对递推最小二乘法结果的影响，程序5-7-2在计算模拟观测值时不加噪声， 辨识结果为a1 =1.6417，a2 = 0.7148，b1 = 0.3900，b2 =0.3499，与真实值a1 =1.642， a2 = 0.715， b1 = 0.3900，b2 =0.35相差无几。 程序5-7-2-1在计算模拟观测值时加入了均值为0，方差为0.1的白噪声序列，由于噪声 的影响，此时的结果为变值，但变化范围较小，现任取一组结果作为辨识结果。辨识结果为a1 =1.5371， a2 = 0.6874， b1 = 0.3756，b2 =0.3378。 程序5-7-2-2在计算模拟观测值时加入了有色噪声，有色噪声为 E(k)+1.642E(k-1)+0.715E(k-2)，E(k)是均值为0，方差为0.1的白噪声序列，由于有色噪声的影响，此时的辨识结果变动范围远比白噪声时大，任取一组结果作为辨识结果。辨识结果为a1 =1.6676， a2 = 0.7479， b1 = 0.4254，b2 =0.3965。 可以看出，基本的最小二乘法不适用于有色噪声的场合。 求递推数列通项公式的常用方法归纳 目录 一、概述·································· 二、等差数列通项公式和前n项和公式·································· 1、等差数列通项公式的推导过程································ 2、等差数列前n项和公式的推导过程·································· 三、一般的递推数列通项公式的常用方法·································· 1、公式法·································· 2、归纳猜想法·································· 3、累加法·································· 4、累乘法·································· 5、构造新函数法(待定系数法）·································· 6、倒数变换法·································· 7、特征根法·································· 8、不动点法································· 9、换元法································· 10、取对数法·································· 11、周期法··································递推最小二乘法算法
几种最小二乘法递推算法的小结
递推算法
AIC法定阶的依阶次递推算法程序.
实验一用递推公式计算定积分
递推算法
实用算法(基础算法-递推法)
递推算法解析集锦
几种最小二乘法递推算法的小结
根据递推公式求数列通项公式的常用方法总结归纳(新)