剣指offer-アルゴリズムとデータ操作——再帰と循環

春招刷問題ノート-剣指offer-アルゴリズムとデータ操作

アルゴリズムとデータ操作——再帰的および循環的

再帰サイクル

1.フィボナッチ数列

.段差問題

.変態ジャンプステップ

.矩形カバー

アルゴリズムとデータ操作——再帰と循環
再帰と循環
1.フィボナッチ数列
タイトルはフィボナッチ数列をご存知ですが、現在は整数nを入力してください.フィボナッチ数列のn番目の項目(0から始まり、0番目は0)を出力してください.n<=39

class Solution {
public:
    long long Fibonacci(int n) {
        long long pre0 = 0;
        long long pre1 = 1;
        long long res = 0;
        int rest[2] = {0, 1};
        if (n < 2)
        	return rest[n];
        for (int i = 2; i <= n; i++) {
            res = pre0 + pre1;
            pre0 = pre1;
            pre1 = res;
        }
        return res;
    }
};

2.段差の問題
テーマは一匹のカエルが一回に1段の階段を上がることができます.2段の階段を上がることもできます.このカエルが1つのn級の階段に上がることを求めて、全部でどれだけの種類の跳び方がありますか?
考え方の分析:階段を跳ぶのは変化のフィボナッチの数列の問題で、第n階段を跳ぶのは分解して第n-1階から1階を跳ぶのに加えて第n-2階から2階まで跳ぶことができて、だから第n階のが法を跳ぶのは第n-1階のが第n-2階のをプラスするのに等しいです.

class Solution {
public:
    int jumpFloor(int number) {
        long long pre0 = 1;
        long long pre1 = 1;
        long long res = 0;
        int rest[2] = {0, 1};
        if (number < 2)
        	return rest[number];
        for (int i = 2; i <= number; i++) {
            res = pre0 + pre1;
            pre0 = pre1;
            pre1 = res;
        }
        return res;
    }
};

3.変態ジャンプステップ
テーマは一匹のカエルが一度に1段の階段を上がることができます.2段の階段を上がることもできます.このカエルが1つのn級の階段に跳ぶことを求めて、全部でどれだけの種類の跳躍法の構想がありますか?総階段がn段であれば、f(n)＝f(n−1)＋f(n−2)＋…f(n−1)＋f(n−n)＋f(n−n)である.f(n-1)は、1回目のジャンプの1段目に残りのステップを加え、f(n-2)は1回目のジャンプの2段目に残りのステップを加え、f(n-3)は1回目のジャンプの3段目に残りのステップを加え、f(n-1)は1段目のジャンプの残りの回数を表し、f(n-n)は1段目のジャンプの残りの回数を表します.式の導出は以下の通りです.
f(n)=f(n-1)+f(n-2)+f(n-3)+f(1)+f(0)
f(n-1)=f(n-2)+f(n-3)+f(1)+f(0)
f(n)=2*f(n-1)
本道のテーマを任意に導出する公式は、2^(number-1)

class Solution {
public:
    int jumpFloorII(int number) {
        if (number == 0 || number == 1)
            return number;
        int res = 1;
        for (int i = 1; i < number; i++)
            res *= 2;
        return res;
    }
};

4.長方形のカバー
テーマは私達が21の小さい長方形で横になったり、縦になったりして、より大きな長方形をカバーすることができます.すみません、n個の21の小さい長方形で重複なく2＊nの大きな長方形をカバーするには、いくつの方法がありますか?
考え方の分析:8段階があると仮定して、最初のブロックが縦に置くと、残りの2*7の長方形に相当して保存します.f(7)に保存する方法があります.最初のブロックが横に置くと、最初のブロックの縦方向の位置も横にします.残りの2*6の長方形に相当してf(6)の保存方法があります.つまり、f(8)=f(7)+f(6)+f(6)+f(6).フィボナッチの数列の問題です.

class Solution {
public:
    int rectCover(int number) {
        if (number <= 0 || number == 1 || number == 2)
            return number;
        int res = 0;
        int pre0 = 1;
        int pre1 = 2;
        for (int i = 3; i <= number; i++) {
            res = pre0 + pre1;
            pre0 = pre1;
            pre1 = res;
        }
        return res;
    }
};