1）1、1、2、3、5、8.......用遞歸算法求第30位數(shù)的值？

首先我們能夠發(fā)現(xiàn)從第3位數(shù)起后一位數(shù)等于前兩位數(shù)值之和，即：x=（x-1）+（x-2），x>2;

這里須要不斷的相加，第一時(shí)刻就會(huì)想到循環(huán)處理，我們嘗試用數(shù)組去裝載這些數(shù)值，即：

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位數(shù)的值，遞歸該怎樣處理呢？相同定義函數(shù)

fun(n)
{
    return fun(n-1)+fun(n-2)//n為第幾位數(shù)，第n位數(shù)返回值等于第n-1位數(shù)的值與第n-2位數(shù)的值之和
}

僅僅有當(dāng)n>2為這樣的情況，就能夠做個(gè)推斷

fun(n)
{
     if(n==1 || n==2)
          return 1;
     else
          return fun(n-1)+fun(n-2);
}

求fun(30);

2）編寫計(jì)算斐波那契（Fibonacci）數(shù)列的第n項(xiàng)函數(shù)fib（n）斐波那契數(shù)列為：0、1、1、2、3、……，

即：

fib(0)=0;

fib(1)=1;

fib(n)=fib(n-1)+fib(n-2) （當(dāng)n>1時(shí)）

寫成遞歸函數(shù)有：

int fib(int n) 
{
　 if (n==0) return 0; 
　 if (n==1) return 1; 
　 if (n>1) return fib(n-1)+fib(n-2); 
}

遞歸算法的運(yùn)行過(guò)程分遞推和回歸兩個(gè)階段。在遞推階段，把較復(fù)雜的問題（規(guī)模為n）的求解推到比原問題簡(jiǎn)單一些的問題（規(guī)模小于n）的求解。

比如上例中，求解fib(n)，把它推到求解fib(n-1)和fib(n-2)。也就是說(shuō)，為計(jì)算fib(n)，必須先計(jì)算fib(n-1)和fib(n-2)，而計(jì)算fib(n-1)和fib(n-2)，又必須先計(jì)算fib(n-3)和fib(n-4)。依次類推，直至計(jì)算fib(1)和fib(0)，分別能馬上得到結(jié)果1和0。在遞推階段，必需要有終止遞歸的

情況。比如在函數(shù)fib中，當(dāng)n為1和0的情況。

在回歸階段，當(dāng)獲得最簡(jiǎn)單情況的解后，逐級(jí)返回，依次得到稍復(fù)雜問題的解，比如得到fib(1)和fib(0)后，返回得到fib(2)的結(jié)果，……，在得到了fib(n-1)和fib(n-2)的結(jié)果后，返回得到fib(n)的結(jié)果。

在編寫遞歸函數(shù)時(shí)要注意，函數(shù)中的局部變量和參數(shù)知識(shí)局限于當(dāng)前調(diào)用層，當(dāng)遞推進(jìn)入“簡(jiǎn)單問題”層時(shí)，原來(lái)層次上的參數(shù)和局部變量便被隱蔽起來(lái)。在一系列“簡(jiǎn)單問題”層，它們各有自己的參數(shù)和局部變量。

因?yàn)檫f歸引起一系列的函數(shù)調(diào)用，而且可能會(huì)有一系列的反復(fù)計(jì)算，遞歸算法的運(yùn)行效率相對(duì)較低。當(dāng)某個(gè)遞歸算法能較方便地轉(zhuǎn)換成遞推算法時(shí)，通常按遞推算法編敲代碼。比如上例計(jì)算斐波那契數(shù)列的第n項(xiàng)的函數(shù)fib(n)應(yīng)採(cǎi)用遞推算法，即從斐波那契數(shù)列的前兩項(xiàng)出發(fā)，逐次由前兩項(xiàng)計(jì)算出下一項(xiàng)，直至計(jì)算出要求的第n項(xiàng)。

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

Fun(n)=n+Fun(n-1)
n=1時(shí)為1
Fun(n)
{
     if(n==1)
       return 1;
     else
      return n+Fun(n-1);
}

4）有兩個(gè)整數(shù)型數(shù)組，從小到大排列，編寫一個(gè)算法將其合并到一個(gè)數(shù)組中，并從小到大排列

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)
        {  //循環(huán)比較把小的放到前面
            if (a[i] < b[j])
            {
                al.Add(a[i++]);
            }
            else
            {
                al.Add(b[j++]);
            }
        }
        //兩個(gè)數(shù)組的長(zhǎng)度不一樣，必有個(gè)數(shù)組沒比較完
        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];
        }
    }

總結(jié)

本篇文章就到這里了，希望能夠給你帶來(lái)幫助，也希望您能夠多多關(guān)注腳本之家的更多內(nèi)容！

最新評(píng)論