循環不變量和用於解決算法？

所以，如果我有以下代碼：循環不變量和用於解決算法？

public int sumSquares(int n){ 
    int sum = 0; 
    for(int i = 1; i <=n; i++){ 
     sum += i*i; 
    } 
    return sum; 
}

我現在必須找到一個循環不變。我被告知，對於這樣的循環，Y = i^2的不變量被認爲是一個循環不變量，但是我不知道我是否知道如何證明它是一個循環不變量。因爲Y只是一些東西，所以它在循環之前，之中和之後都是真的，因爲它是我*我是...無論它是否是一個不變的有效證明？當說到用不變量證明算法時，說sum =從i到i（或Y，環不變）= n（n + 1）（2n + 1）/ 6

然後使用歸納來證明這是正確的？那是否正確使用循環不變式來證明算法？

也許需要一些幫助:)

來源

2015-09-17 Tyler Dahle

總和+（總Ĵ*，j將= i..n）=（總Ĵ*，j將= 1..1） – piotrekg2

什麼？我不相信和數可以在循環不變中，因爲它是不恆定的。算法是i^2的總和1到n，所以這是最後總和相等的結果。 –

整個equasion在迭代之間總是如此。 – piotrekg2

的不變的應該是，入口處的循環，對於任何i，

sum = 0 + 1*1 + 2*2 + ... + (i-1)*(i-1)

上述要求可以通過感應來證明。讓sum是在循環開始時的變量，sum'變量在它的末端，則：

sum' = sum + i*i = 0 + 1*1 + ... + i*i

這使您可以使用一個事實，即在addiiton，當循環終止i=n+1，程序，所以當終止，您可以：

sum = 0 + 1*1 + ... + n*n

來源

2015-09-17 06:12:52 amit

是不是使用兩個不變量與總和和'？我的TA被告知誰在for循環中做了一個非常類似於+ + i + 1的循環，所以你不能在不變量中使用'a'，並且應該使用Y = i + 1。 –

循環不變量和用於解決算法？

回答

相關問題