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];
        }
    }

總結

本篇文章就到這裡瞭,希望能夠給你帶來幫助,也希望您能夠多多關註WalkonNet的更多內容!

推薦閱讀: