算法设计经典代码

4-1阶乘的倒数和阶乘n!定义:n!=1(n=1)；n!=n*(n-1)!(n1)设计求n!的递归函数，调用该函数求!1!21!111ns递归描述#includestdio.hlongf(intn){longg;if(n==1)g=1;elseg=n*f(n-1);return(g);}voidmain(){intk,n;doubles=1;printf(请输入n:);scanf(%d,&n);for(k=1;k=n;k++)s+=(double)1/f(k);printf(s=%f\n,s);}4-3递归求解b数列已知b数列定义：)2(23,2,12121nbbbbbnnn建立b数列的递归函数，求b数列的第n(n≤30)项与前n项之和。解：#includestdio.hlongb(intn){longg;if(n==1)g=1;elseif(n==2)g=2;elseg=3*b(n-1)-2*b(n-2);returng;}voidmain(){intk,n;longs=0;printf(请输入n:);scanf(%d,&n);for(k=1;k=n;k++)s+=b(k);printf(b(%d)=%ld\n,n,b(n));printf(s=%ld\n,s);}4-4递归求解双递推摆动数列已知递推数列：a(1)=1,a(2i)=a(i)+1,a(2i+1)=a(i)+a(i+1)，（i为正整数）试建立递归，求该数列的第n(n100000)项与前n项的和。//摆动数列#includestdio.hinta(intn){intg;if(n==1)g=1;elseif(n%2==0)g=a(n/2)+1;elseg=a((n-1)/2)+a((n+1)/2);returng;}voidmain(){intk,n;longs=0;printf(请输入n:);scanf(%d,&n);for(k=1;k=n;k++)s+=a(k);printf(a(%d)=%d\n,n,a(n));printf(s=%ld\n,s);}4-6顺转矩阵的递归设计当数阵的行数与列数不相等时，数阵称为矩阵。显然，顺转方阵是顺转矩阵的特例。图4-8为5行6列的顺转矩阵。试应用递归设计构造并输出任意指定m行×n列的顺转矩阵。//m×n顺转矩阵递归设计#includestdio.hintm,n,a[20][20]={0};voidmain(){inth,v,b,s,d;printf(数阵为m行n列，请确定m,n：);scanf(%d,%d,&m,&n);s=mn?n:m;b=1;d=1;voidt(intb,ints,intd);//递归函数说明t(b,s,d);//调用递归函数printf(%d×%d顺转矩阵:\n,m,n);for(h=1;h=m;h++){for(v=1;v=n;v++)printf(%3d,a[h][v]);printf(\n);}return;}voidt(intb,ints,intd)//定义递归函数{intj,h=b,v=b;if(s=0)return;//递归出口if(s==1&&m==n)//n=m且n为奇数时的递归出口{a[h][v]=d;return;}for(j=1;j=n+1-2*b;j++)//一圈的上行从左至右递增{a[h][v]=d;v++;d++;}for(j=1;j=m+1-2*b;j++)//一圈的右列从上至下递增{a[h][v]=d;h++;d++;}for(j=1;j=n+1-2*b;j++)//一圈的下行从右至左递增{a[h][v]=d;v--;d++;if(dm*n)break;//min(m,n)为奇数且nm时停止循环}for(j=1;j=m+1-2*b;j++)//一圈的左行从下至上递增{a[h][v]=d;h--;d++;if(dm*n)break;//min(m,n)为偶数或者nm时停止循环}t(b+1,s-2,d);//调用内一圈递归函数}4-7自主设计4-9自主设计