欲張り:ジャンプゲーム

1つの配列は非負の整数データを格納し、配列中のi番目の要素a[i]は、配列のi番目の位置から最大で前へジャンプできるa[i]ステップを表す.配列の各要素が既知の場合、配列の0番目の位置から配列の最後の要素の位置にジャンプできるかどうかを求め、trueまたはfalseに戻って最後にジャンプできるかどうかを判断する
例えばnums=[2,3,1,1,4],nums[0]=2からnums[4]=4にジャンプできる.nums=[3,2,1,0,4],nums[0]=3からnums[4]=4にジャンプできない

貪欲な法則:最終的にゴールまでジャンプできるかどうかを判断するには、最も速い方法はジャンプごとに獲得したジャンプ範囲の中で最大のジャンプ点を選択することである.例えばnums=[23 1 1 4]が初めて2にジャンプすると、次に1回ジャンプしてnums[1]=3にジャンプすることができる.あるいはジャンプ2回、nums[2]=1どのように2回目のジャンプを選択するか、欲張りアルゴリズムによると、私たちはもっと早く任務を完成したいと思っています.優先的にジャンプできる回数が最も多い点、すなわちnums[1]を選択します.それは2回目に3回ジャンプできるからです.しかしnums[2]は1回しかジャンプできないので、欲張りの法則はジャンプのたびに落ちる点で、次のジャンプ可能な範囲の中で最大の値です.巨人の肩に立ってもっと遠くまで跳ぶことができます.

反復ポリシー:

第i位置から第index[i]位置まで最も遠いジャンプ可能な位置を求める:第i位置から最も遠いジャンプ可能なnums[i]ステップ:index[i]=nums[i]+i;

初期化:1)設定変数jumpは現在位置を表し、初期化は0である.2)変数max_の設定indexは、0番目の位置からjump番目の位置までの過程で、最も遠くに到達可能な位置を表し、index[0]に初期化される.

jumpを使用してindex配列をスキャンし、jumpがindex配列の末尾に達するか、jumpがmax_を超えるまでindex、スキャン中、max_を更新index.

最終jumpが配列長であればtrueを返し、そうでなければfalseを返す.

実装アルゴリズムは次のとおりです.

bool judge_finish(vector<int> &stage) {
    vector<int> index;
    /*        index  */
    for (int i = 0; i < stage.size(); ++i) {
        index.push_back(i + stage[i]);
    }

    int max_index = stage[0];
    int jump = 0;
    /*        jump       jump    index  ，          */
    while(jump < index.size() && jump <= max_index) {
        if (max_index < index[jump]) {
            max_index = index[jump];
        }
        jump ++;
    }
	/*  jump     ，         */
    if (jump == index.size()) {
        return true;
    }
    return false;
}

テストコードは次のとおりです.

#include 
#include 

using namespace std;

bool judge_finish(vector<int> &stage) {
    vector<int> index;
    for (int i = 0; i < stage.size(); ++i) {
        index.push_back(i + stage[i]);
    }

    int max_index = stage[0];
    int jump = 0;
    while(jump < index.size() && jump <= max_index) {
        if (max_index < index[jump]) {
            max_index = index[jump];
        }
        jump ++;
    }

    if (jump == index.size()) {
        return true;
    }
    return false;
}

int main() {
    vector<int> s;
    int tmp;
    cout << "input arr " <<endl;
    for (int i =0;i < 5; ++i) {
        cin >> tmp;
        s.push_back(tmp);
    }
    cout << "the true or false that judge the result is " << judge_finish(s) << endl;
    return 0;
}

出力は次のとおりです.

input arr 
3 2 2 0 5
the true or false that judge the result is 1