递归(网下搜的一些笔试题)

递归(网上搜的一些笔试题)
一个射击运动员打靶，靶一共有10环，连开10枪打中90环的可能性有多少种？请用递归算法编程实现。

public class Cs {public int times;public int score;public int[] loops;public int count=0;public static void main(String[] args){ Cs cs=new Cs(10,90);cs.loop(10);System.out.println(cs.count);    } public Cs(int times,int score){this.times=times;this.score=score;loops=new int[times];}public void loop(int cur){if(cur==0){if(score!=0)return;count++;return;}cur--;for(int i=10;i>0;i--){loops[cur]=i;score-=i;//模拟嵌套for循环 loop(cur);score+=i;   //状态恢复}}}

输入两个整数n和m，从数列1、2、3、...n中任意取几个数，使其和等于m，要求将其中所有可能的组合都列出来

public class Cs {public int n;public int m;public int[] result;public int count=0;public static void main(String[] args){ Cs cs=new Cs(10,50);cs.loop();System.out.println(cs.count);    } public Cs(int n,int m){this.n=n;this.m=m;result=new int[n];}public void loop(){int[] loops=new int[n];result=new int[n];for(int i=0;i<n;i++)loops[i]=i+1;loop(n,loops);}private void loop(int cur,int[] _loop){if(m<=0||_loop.length==0){if(m!=0)return;count++;for(int i=0;i<result.length;i++)System.out.print(result[i]+",");System.out.println("");return;}cur--;for(int i=0;i<_loop.length;i++){result[cur]=_loop[i];m-=_loop[i];//等到最终结果需要不重复，可以按元素大小排序来得到下一步_loopint[] _loop_=new int[cur];for(int j=i+1;j<_loop.length;j++)_loop_[j-i-1]=_loop[j];loop(cur,_loop_);m+=_loop[i];  //状态恢复}}}

原文地址: http://www.cnblogs.com/hujian/archive/2012/03/09/2388430.html
有长宽分别为1x1和1x2的小格子，现在要用这两种小格子拼接成1xN的大格子，请问一共有多少种拼接方案？编程实现之，N可由用户输入。
难点在于想清楚这道题的实质是什么，考察对递归的理解和应用。考虑1xN的大格子最右边的那个格子，如果这个格子是1x1的，则剩余N-1个格子；如果这个格子是1x2的，则剩余N-2个格子，于是得到F(N)=F(N-1)+F(N-2)。可以看到，拼接方案的序列实际上构成了一个Fibonacci数列。



用递归算法判断数组a[N]是否为一个递增数组。
递归的方法，记录当前最大的，并且判断当前的是否比这个还大，大则继续，否则返回false结束：

bool fun( int a[], int n ){if( n= =1 )return true;if( n= =2 )return a[n-1] >= a[n-2];return fun( a,n-1) && ( a[n-1] >= a[n-2] );}

查看更多 下一篇