编程计概a00-06函数递归习题

递归算法举例初值defac选择一个分界值dbcade将待排序的数据放入数组a中，下标从l到 数据在a[l],...,a[rB

C什么也不D分区处

我 中采用取第一个元素的方法 5265265555k 52655k 426a[l]=2<k.左探针继续右移,指向5k5 4265k5 4265k5 4265k5 4235k5 4235k5 4235 5 4235 5423 用上述思路去排左右两边的部分。省if(ll<{l=ll;r=rr;if(ll<{l=ll;r=rr;k=//如果ll<rr,则做下列7件事//第1件事，保留//第2件事if(l<{array[l]=

//右边的元素<k//array[r]送给//同时让l往中间}while((l<r)&&(array[l]<=if(l<{array[r]=array[l];r--;}while(l<array[l]=

//左边的元素>k,让array[l]送给//第2件事//第3件事,k已排到voidsort(intarray[],intll,int{intl,r,voidsort(intarray[],intll,int{intl,r,//ll,rr是数组的边//l,r是左右探针，随着交换变couta[”<<Iarray[i];cout //第5件事，换sort(arraylll //第6件事，排左边部sort(arrayl1 //第7件事，排右边部 //7件事结}int inta[10],i;cout10个整数\n"for(i =0;i <10;i++)cin>a[i];sort(a, 0,9 //调用sort函数,实际//参数为数组a和cout<"排序结果为:";for(i =0;i <10;i++)cout<a[i];cout<endl;return0；}

//输出排序结果递归算法举例因数分a=a1*a2*a3*...*并且1a1a2a3an，问这样的分解的种数有多少。注意到a=a也是一种分解。试数据占1行，包括一个正整数a(1a22*2*2*4*Sample22

Sample14因数分for(intiyib if(x%i==(xi,为什么不是2i+因数分{intn,i,a;cin>>n;for(i=0;i<n;i++{cin>>cout<<fj(a,2)<<}}因数分intfj(intx,int{intxnumber=if(x==return0;if(x==2)return

intb=(int)sqrt((double)x);for(inti=y;i<=b;i++)if(xi xnumber+=fj(x/i,return}因数分f(5,xnumber=f(5,xnumber=returnfor(inti=y;i<=b;if(x%i==f(20,xnumber=1+f(10,returnf(20,xnumber=1+f(10,returnf(10,xnumber=1+(1+f(5,returnf(20,xnumber=return递归算法举例 每个人按其在队列中的位置发给一个编号（编号从0开始） 边的男孩可以和他后边相邻 手拉 请根据老师的排队，按 关于输。关于输 格分(()((()(())())(( 013456789例子输2356478

11 0排队游 一样多。如测试数据，“(”和“)”也一样多，且“(”必出现在与之匹配的“)”之前，因此只要找到了和第一个“(”匹配的“排队游返 的位排队游stringstrbg//s字符串，b{b=str[0];g=str[len-1];return0;}排队游{

{

q=match(p+1); cout<<p<<''<<q<<endl; returnmatch(q+1); }

1 递归算法举例前缀表达，例如普通的表达式2+3的逆波兰表示法为+2+3*4的逆波兰表示法为*234。本题求解逆波兰表达式的值，其中运算符包括+-*/四个。前缀表达*+11.012.0+24.0前缀表达前缀表达returnf()*前缀表达#include<string>usingnamespacestd;intmain(){doublev=cout return}

{{

前缀表达前缀表达}}递归算法举例数字旋转方编程输出如图所示的6×6数字旋转方阵，希望编出N×N的数字方阵，4<=N<=1016789每次递归，数组的尺寸减二，结束条件size

{ for(i=0;i<size;for(i=0;i<size1;i++)for(i=0;i<size-1;i++)P[-h][v]=number++;for(i=0;i<size-2;

}{for(i=0;i<n;{for(j=0;j<n;}}{cin>>n;}递归算法举例

y 青蛙过 2 1#L左岸

2#右岸第一步：1第二步：2#从L直接跳至R第三步：1R

叶S=1，y1L2#青蛙从L1Y3#青蛙从L4#青蛙从L3#青蛙从Y－> 1#青蛙从S－>2#青蛙从S1#青蛙从Y

4 32

3# 8为了将过河过程描述得更清楚，我们给出了表。表中L1L2上面，L41

46 现在再看S=2，y=

2 85y

S1 S212(L1yS2S21yR12(L1S2yS3)+(S312yyLRS1S2=2yLRS1S21Jump(3,4A=Jump(2,4

2*2*20=4B=Jump(1,4

2*2*10=2C=Jump(0,4S==4+

2*2*5=1int Jump(int,int);int int //整型变量,sy为荷叶数=";cin>s;cin>y;=Jump(s,y); cout<"Jump("<s<", "<y<")="<<endl;return0;}//以下函数是被主程序调用的函数int Jump(ints, inty){if (s=returny+1;

//如果r为0,则为直接可解结点,//返回return2*Jump(s-1,y); //柱子数减1}总递归算法举例①for(j=1;j<=3;②ij.说明第s步走的台阶比剩下的阶梯数还多。③ij.说明第s步正好走完剩下的阶梯，得到一④ij.说明第sij级阶梯没有走，可以走第s+1步。递归调用。idvoidTry(inti,ints) forj3j>0j if(i<take[s]=j;if(i==j){

for(k=1;k<=s;cout<<endl;}

}主函{cin>>h;Try(h,return0;}递归算法举例跳马问问有多少种方同类问题：请思(x,y)

ii11222132-41x+dx[k],y+voidjump（x1,y1,step+#includeusingstd;constint=8;constint=4;constintP=9;intintintdx[]={0,1,2,2,1};intdy[]={0,2,1,-1,-2}; for(k=1;k<=4;k++){x1=x+dx[k];y1=y+&(1&(1&(1&(1&2&3 for(i=0;i<=step;i++)}}}int{mk[0]=0;m=0;path[0][0]=0;path[0][1]=0;cout<"thereare"<msolutions."<endl;return0;}递归算法举例给A,B,C,D,E五个人，每个人阅读用一个二1Like[i][j]=

i喜欢书 i不喜欢书分书问 书0011011001010011011001011010001001001A分书问{0,1,1,0,1},{0,0,0,1,0}，{0,1,0,0,intbook[5]={0,0,0,0,分书问分书问①查看i是否为4，如果不为4，表示尚未将所有5个人所要的书回溯。恢复j书尚未被选的标志，book[j]=0。这是在已输出for(j=0;j<=4; &] take[i]=j;{将书j分给i}book[j]=1{j书已分} 输出方案

{试分下一个

什么不分书分书问主函-book[j]=0j选分书问{ return0；}{

forj=0j<=4 {&( if(i==

nn coutnendl;fork=0;k<=4;k++)couttake[k} }}

递归算法举例迷s...##..#......s...##..#..............#......#...####...#......e右下角((n-迷迷迷s1s123##..#.4567......8..#.9..######...e if(x<0||y>=size||x>=size||y<returnfalse; if(visit[x][y]==1)

};} intmain() cin>> cin>>for(inti=0;i<size;for(intj=0;j<size;

{}}递归算法举例滑 2425 1211 1234123457912341234579滑cin>>m>>nfor(i=0;i<m;for(j=0;j<n;j++)cin>>h[i][j];for(i=0;i<m;i++)for(j=0;j<n;j++){}}{if(f[x][y if(x>0&(h[x][y]>h[x-if(x<m–1&h[x][y]>h[x+&h[x][y]if(y<n–1&h[x][y]>h[x][y+1])for(i=0;i<4;}} n+(n-1)+(n-2)+ +课堂练习—函数doublefun（intn,double{if(n==returnsqrt(1+x);returnsqrt(n+fun(n-1}课堂练习—多少头Y1=2；Y2=3；Y3=Y4=Y3+Y1=Y2;Y2=Y3;Y3={inty1=2,y2=3;y3=4,i;for(i=4;i<=20;{y4=y3+y1;y1=y2;y2=y3;y3=

{if(n<=if(n==2)if(n==3)}}cout<<y4