C# 递归算法详解

  目录

  1)1、1、2、3、5、8.......用递归算法求第30位数的值?

  首先我们能够发现从第3位数起后一位数等于前两位数值之和,即:x=(x-1)+(x-2),x>2;

  这里须要不断的相加,第一时刻就会想到循环处理,我们尝试用数组去装载这些数值,即:

  int[] a=new int[30];

  a[0]=1;

  a[1]=1;

  for(int i=2;i<30;i++)

  {

  a[i]=a[i-1]+a[i-2];

  }

  求a[29]的值即为第30位数的值,递归该怎样处理呢?相同定义函数

  fun(n)

  {

  return fun(n-1)+fun(n-2)//n为第几位数,第n位数返回值等于第n-1位数的值与第n-2位数的值之和

  }

  仅仅有当n>2为这样的情况,就能够做个推断

  fun(n)

  {

  if(n==1 || n==2)

  return 1;

  else

  return fun(n-1)+fun(n-2);

  }

  求fun(30);

  2)编写计算斐波那契(Fibonacci)数列的第n项函数fib(n)斐波那契数列为:0、1、1、2、3、……,

  即:

  fib(0)=0;

  fib(1)=1;

  fib(n)=fib(n-1)+fib(n-2) (当n>1时)

  写成递归函数有:

  int fib(int n)

  {

  if (n==0) return 0;

  if (n==1) return 1;

  if (n>1) return fib(n-1)+fib(n-2);

  }

  递归算法的运行过程分递推和回归两个阶段。在递推阶段,把较复杂的问题(规模为n)的求解推到比原问题简单一些的问题(规模小于n)的求解。

  比如上例中,求解fib(n),把它推到求解fib(n-1)和fib(n-2)。也就是说,为计算fib(n),必须先计算fib(n-1)和fib(n-2),而计算fib(n-1)和fib(n-2),又必须先计算fib(n-3)和fib(n-4)。依次类推,直至计算fib(1)和fib(0),分别能马上得到结果1和0。在递推阶段,必需要有终止递归的

  情况。比如在函数fib中,当n为1和0的情况。

  在回归阶段,当获得最简单情况的解后,逐级返回,依次得到稍复杂问题的解,比如得到fib(1)和fib(0)后,返回得到fib(2)的结果,……,在得到了fib(n-1)和fib(n-2)的结果后,返回得到fib(n)的结果。

  在编写递归函数时要注意,函数中的局部变量和參数知识局限于当前调用层,当递推进入“简单问题”层时,原来层次上的參数和局部变量便被隐蔽起来。在一系列“简单问题”层,它们各有自己的參数和局部变量。

  因为递归引起一系列的函数调用,而且可能会有一系列的反复计算,递归算法的运行效率相对较低。当某个递归算法能较方便地转换成递推算法时,通常按递推算法编敲代码。比如上例计算斐波那契数列的第n项的函数fib(n)应採用递推算法,即从斐波那契数列的前两项出发,逐次由前两项计算出下一项,直至计算出要求的第n项。

  3)求1+2+3+4+5+....+n的值

  Fun(n)=n+Fun(n-1)

  n=1时为1

  Fun(n)

  {

  if(n==1)

  return 1;

  else

  return n+Fun(n-1);

  }

  4)有两个整数型数组,从小到大排列,编写一个算法将其合并到一个数组中,并从小到大排列

  public void Fun()

  {

  int[] a = { 1, 3, 5, 7, 9, 10 };

  int[] b = { 2, 4, 6, 8, 11, 12, 15 };

  int[] c = new int[a.Length + b.Length];

  ArrayList al=new ArrayList();

  int i=0;

  int j=0;

  while (i <= a.Length - 1 && j <= b.Length - 1)

  { //循环比較把小的放到前面

  if (a[i] < b[j])

  {

  al.Add(a[i++]);

  }

  else

  {

  al.Add(b[j++]);

  }

  }

  //两个数组的长度不一样,必有个数组没比較完

  while (i <= a.Length - 1)//加入a中剩下的

  {

  al.Add(a[i++]);

  }

  while (j <= b.Length - 1)//加入b中剩下的

  {

  al.Add(b[j++]);

  }

  for (int ii = 0; ii <= c.Length-1 ; ii++)

  {

  c[ii] = (int)al[ii];

  }

  }

  总结

  本篇文章就到这里了,希望能够给你带来帮助,也希望您能够多多关注脚本之家的更多内容!

  您可能感兴趣的文章:

相关文章