Java循环不变式

|
int logarithmCeiling(int x) {
    int power = 1;
    int count = 0;

    while (power < x) {
        power = 2 *power;
        count = count +1;
    }
    return count;
}
上面的代码旨在成为Java中使用while循环计算并返回给定正整数的下对数的方法。如何为以上循环提供不变式?即在每次循环主体结束以及循环条件的否定之前保持有效。     
已邀请:
在循环的开始和结束时,功效始终等于2 ^ count。对于求反,当循环结束时,x <= power = 2 ^ count。     
power
的值与
count
的值之间有一个简单的关系:power = 2count。这适用于循环的开始和结束,但不适用于循环体内的某些位置。     
寻找始终为真的变量或条件。每个迭代计数总是增加1,幂总是乘以2。由于该函数的目的是找到给定参数的下对数,因此可以说循环不变式是,计数始终等于n的对数。 x,四舍五入。另一个可能是,计数始终等于幂的对数。     
我猜您正在寻找一个适合证明该方法的部分正确性的不变式?否则,\“ true \”或\“ false \”始终是不变的。我会选择这样的东西:
I: {(power <= x) AND (power == 2 ^ count) AND (x > 2 ^ count -1) AND (power >= 1)}
r.h.s.可以从您的初始化中暗示出来,并有助于确保x的下限。 与否定的循环条件一起,您以后可以暗示。
{(x <= 2 ^ count) AND (x > 2 ^ (count -1))}
这正是显示整个功能的部分正确性所要的。     

要回复问题请先登录注册