如何找到循环不变

我知道循环不变是为了证明问题的正确性，但我无法完全理解如何提出一个问题，无论问题多么微不足道。下面是一个例子，有人能指出我应该考虑采取哪一步来提出一个步骤。我知道循环中所有正在变化的值都必须包含在我的不变量中。请指导我解决这个问题，我也必须找到后期条件。一个解释将不仅仅是一个答案;请帮忙。如何找到循环不变

{M > 0 and N >= 0 } 

a = M; 
b = N; 
k = 1; 

while (b > 0) { 
    if (b % 2 == 0) { 
     a = a * a; 
     b = b/2 
    } else { 
     b = b – 1; 
     k = k * a; 
    } 
} 

{ ? ? }

来源

2015-10-19 Bobby

[我也面临同样的问题，希望这个解释会给你的想法]（http://stackoverflow.com/questions/2935295/what-is-the-best-way-of-determining-a -loop-invariant） –

谢谢你，我会看看那个，希望它能帮助你 – Bobby

关于循环不变量的棘手部分是没有算法（我意识到）会始终保证“正确”的答案。

作为开始，对于您的问题中的算法，请尝试通过程序进行跟踪并找出算法的目标（提示：指数很有趣）。追踪跟踪变量a，b和k。

例如，使用M = 2和N = 1,2,3,...。在N的几个值之后，你会注意到变量a，b和k之间的关系会开始发展。

一旦你发现循环不变，后置条件应该很简单。

希望这会让你的球滚动！

来源

2015-10-25 20:18:34 Amous

那么，你会有点落后。如你所说，循环不变的目的是帮助你证明程序的正确性。我想你没有编写这个程序 - 否则你会知道它是什么，并且在编写循环之前你会想出循环不变的，因为这是理解循环是正确的关键。

那么...该程序是什么？你怎么知道这是正确的？循环不变将成为你对第二个问题的答案的一部分。

听起来像这样：在每次迭代的开始和结束时，k = ... b ....在循环之后，b == 0，所以....和程序是正确的。

我不想拼出答案，因为这可能是作业，如果你自己想出来，你只会学习它。

来源

2015-10-25 21:05:42

如何找到循环不变

回答

相关问题