什么是不变量？

Question

这个词似乎在许多情况下被使用.我能想到的最好的是它们意味着一个无法改变的变量.是不是常数/决赛(你是Java!)是为了什么？

Answer 1

不变量比变量更"概念化".通常,程序状态的属性始终为true.确保不变量成立的函数或方法据说保持不变量.

例如,二叉搜索树可能具有不变量,即对于每个节点,节点的左子节点的键小于节点自己的键.正确编写此树的插入函数将保持不变.

正如你所知,这不是你可以存储在变量中的那种东西:它更像是关于程序的陈述.通过确定程序应该维护哪种不变量,然后查看代码以确保它实际维护这些不变量,可以避免代码中的逻辑错误.

Answer 2

这是一个条件,你知道在逻辑中的某个特定位置始终是真的,并且可以检查何时调试以找出出错的地方.

Answer 3

我通常在算法或结构方面更多地查看它们.

例如,您可以拥有一个可以断言的循环不变量 - 在每次迭代的开始或结束时始终为true.也就是说,如果你的循环应该处理从一个堆栈到另一个堆栈的对象集合,你可以在循环的顶部或底部说| stack1 | + | stack2 | = c.

如果不变检查失败,则表明出现了问题.在这个例子中,它可能意味着您忘记将已处理的元素推送到最终堆栈等.

Answer 4

维基百科的魔力:不变(计算机科学)

在计算机科学中,如果为真,则在整个特定操作序列中保持为真的谓词被称为(a)对该序列不变.

Answer 5

这个答案是给我 5 岁的孩子的。不要将不变量视为常数或固定数值。但它可以。然而，还不止这些。

相反，不变量类似于不同实体之间的固定关系。例如，与您的亲生父母相比，您的年龄将始终小于该年龄。你的年龄和你父母的年龄都会随着时间的推移而变化，但我上面提到的关系是不变的。

不变量也可以是数值常数。例如， 的值pi是圆的周长与其直径之间的不变比率。不管圆有多大，这个比例永远是pi。

Answer 6

如该行所述：

在计算机科学中，一个谓词（如果为真）将在整个特定操作序列中保持为真，称为该序列的不变式。

为了更好地理解这一希望，C ++中的此示例会有所帮助。

考虑一个场景，您必须获取一些值并在名为as的变量中获取它们的总数，count然后将其添加到称为as的变量中sum

在不变的（再次它更像是一个概念）：

// invariant:
// we have read count grades so far, and
// sum is the sum of the first count grades

上面的代码是这样的，

int count=0;
double sum=0,x=0;
while (cin >> x) {
++count;
sum+=x;
}

上面的代码做什么？

1）从中读取输入cin并将其放入x

2）成功读取一次后，递增count并sum = sum + x

3）重复1-2，直到读取停止（即ctrl + D）

循环不变式：

该不变量必须为True ALWAYS。因此，最初，您仅以此开始代码

while(cin>>x){
  }

该循环从标准输入读取数据并存储在x中。好，好。但是因为我们的不变式的第一部分没有被跟随（或保持为真），所以不变式变为假。

// we have read count grades so far, and

如何保持不变性为真？

简单！增量计数。

这样++count;会很好！现在我们的代码变成这样，

while(cin>>x){
 ++count; 
 }

但

即使现在我们的不变式（必须为TRUE的概念）也为False，因为现在我们不满足我们不变式的第二部分。

// sum is the sum of the first count grades

那么现在该怎么办？

添加x到sum并将其存储在sum（sum+=x），下一次 cin>>x将读取一个新值X。

现在我们的代码变成这样，

while(cin>>x){
 ++count; 
 sum+=x;
 }

让我们检查

代码是否匹配我们的不变式

// invariant:
// we have read count grades so far, and
// sum is the sum of the first count grades

码：

while(cin>>x){
 ++count; 
 sum+=x;
 }

啊！。现在，循环不变式始终为True，并且代码可以正常工作。

上面的示例是从 Andrew-koening和Barbara-E 的《Accelerated C ++》一书中获取并修改的