剣指offerアルゴリズム(再帰とサイクル)

タイトルの説明では、フィボナッチ数列を知っていますが、整数nを入力するように要求されています.フィボナッチ数列のn番目の項目を出力してください.

class Solution {
public:
    int Fibonacci(int n) {		
        if(n==0)
            return 0;
        else if(n==1)
            return 1;
        else
        //    return Fibonacci(n-1)+Fibonacci(n-2);
    	{
            int *array;
            array=(int*)malloc(n*sizeof(int));
            array[0]=0;
            array[1]=1;
            for(int i=2;i

タイトルの説明
1匹のカエルは一度に1段の階段を飛び上がることも、2段を飛び上がることもできます.このカエルが1つのn級の階段を跳ぶことを求めて全部で何種類の跳び方があります.
解析:n=1の場合、1中ジャンプしかありません.n=2の場合、2つのジャンプ法があります.n=3の場合、3種類のジャンプ法があります.n=4の場合、5種類のジャンプ法があります.n=5のとき、8種類のジャンプがあります;......法則はFibonacci数列に似ている

class Solution {
public:
    int jumpFloor(int number) {
        if(number==1)
            return 1;
        if(number==2)
            return 2;
        else
            return jumpFloor(number-1)+jumpFloor(number-2);
    }
};

タイトル説明
1匹のカエルは一度に1段の階段を飛び上がることもできるし、2段も飛び上がることもできるし...n段も飛び上がることもできる.このカエルが1つのn級の階段を跳ぶことを求めて全部で何種類の跳び方があります.
解析:Fib(n)でカエルがn段を飛び上がるジャンプ数を表し、カエルがn段を一度に飛び上がるジャンプ数1(n段ジャンプ)、Fib(0)=1を設定する.n=1の場合、1次ジャンプ:Fib(1)=1のみである.n=2の場合,1次ジャンプと2次ジャンプがある:Fib(2)=Fib(1)+Fib(0)=2;n=3の場合、3種類のジャンプ方式があり、初めて1階を飛び出した後、後ろにはFib(3-1)のジャンプ法がある.初めて2階を飛び出した後、後ろにはFib(3-2)のジャンプ法がある.第1回目の3次ジャンプ後、後ろにはFib(3-3)におけるジャンプ法Fib(3)=Fib(2)+Fib(1)+Fib(0)=4がある.n=nの場合、n種類のジャンプ方式があり、初めて1階を飛び出した後、後ろにはFib(n-1)のジャンプ法がある.1回目の2次ジャンプ後、後ろにはFib(n-2)の中ジャンプが・・・・・・1回目にn階を飛び出すと、後ろにはFib(n-n)のジャンプ法もある.Fib(n) = Fib(n-1)+Fib(n-2)+Fib(n-3)+..........+Fib(n-n)=Fib(0)+Fib(1)+Fib(2)+.......+また、Fib(n-1)は、Fib(n-1)=Fib(0)+Fib(1)+Fib(2)+…….+Fib(n-2)の2式は、Fib(n)−Fib(n−1)=Fib(n−1)=>Fib(n)=2*Fib(n−1)(n>=2)に減算される.

class Solution {
public:
    int jumpFloorII(int number) {
		if(number==0||number==1)
            return 1;
        else
            return 2*jumpFloorII(number-1);
    }
};

タイトルの説明
2*1の小さな矩形で横になったり、縦になったりして、より大きな矩形を覆うことができます.すみません、n個の2*1の小さい矩形で重ならずに1個の2*nの大きい矩形を覆って、全部で何種類の方法がありますか?

class Solution {
public:
    int rectCover(int number) {
	if(number==1)
            return 1;
        if(number==2)
            return 2;
        else 
            return rectCover(number-1)+rectCover(number-2);
    }
};

タイトルの説明
2*1の小さな矩形で横になったり、縦になったりして、より大きな矩形を覆うことができます.すみません、n個の2*1の小さい矩形で重ならずに1個の2*nの大きい矩形を覆って、全部で何種類の方法がありますか?
解析:テーマの中の矩形を観察して、2*nの、1つの長尺の形です.単純な長尺形である以上、逆分析である.長尺である以上、後ろから前へ、最後の矩形2*2の場合は、2つのケースしかありません.1つ目は、最後に1つの2*(n-1)の矩形に1つの縦の2*1の矩形を加え、もう1つは2*(n-2)の矩形に2*1の矩形を加え、2つの横の2*1の矩形を加えるので、私たちは得ることができます.第2*n個の矩形の被覆方法は、第(n−1)個の2*1の小矩形に第(n−2)個の2*1の小矩形を加えた方法に等しい.

class Solution {
public:
    int rectCover(int number) {
	if(number==0)
            return 1;
        else if(number==1)
            return 1;
        else if(number==2)
            return 2;
        else 
            return rectCover(number-1)+rectCover(number-2);
        /*
        unsigned int array[71]={1,1,2};
        for(int i=3;i<71;i++)
            {
            array[i]=array[i-1]+array[i-2];
            
        }
        return array[number];
        */
    }
};