0

単純なプログラムの正しさを証明する方法を常に考えています。たとえば、First Missing Positiveのようなインタビューの問題です。プログラムは次のようになります。

public class Solution{
    public int firstMissingPositive(int[] A){
        int i = 0;
        while(i < A.length){
            if(A[i] != (i+1) && A[i] >= 1 && A[i] <= A.length && A[A[i]-1] != A[i]){
                int tmp = A[A[i]-1];
                A[A[i]-1] = A[i];
                A[i] = tmp;
            }
            else{
                i++;
            }
        }
        for(i = 0; i < A.length; i++){
            if(A[i] != (i+1))
                return i+1;
        }
        return A.length+1;
    }
}

このプログラムの不変式を構築する方法は? 単純なアルゴリズムの不変式を構築するための一般的なヒントは何ですか?

4

0 に答える 0