当前位置:首页 > 开发 > 编程语言 > 编程 > 正文

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

发表于: 2012-09-26   作者:braveCS   来源:转载   浏览:
摘要: 一个射击运动员打靶,靶一共有10环,连开10枪打中90环的可能性有多少种?请用递归算法编程实现。 public class Cs { public int times; public int score; public int[] loops; public int count=0; public static void main(String[] a
一个射击运动员打靶,靶一共有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];	
			//等到最终结果需要不重复,可以按元素大小排序来得到下一步_loop
			int[] _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] );
}

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

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号