代码之家 › 专栏 › 技术社区 › pcp

如何选择和设置正确的循环不变量?

theory

3

pcp · 技术社区 · 16 年前

我得到了关于循环不变量的以下问题:

考虑

x=4; for(i=5;i<k;i++) { a=a+x+i; x=x*2; }

定义使用a和x的闭合公式的近似循环不变量。

现在, 你怎么知道这里有正确的循环不变量?我的意思是,可以将循环不变量设置为: “在第j次迭代中,x小于a”,这将是正确的,但不会使用任何闭合公式,对吗?

当循环结束时,如何使用语句(循环不变量)来确定“a”的值? 我看到的所有例子都只是陈述了循环不变量,它没有被用作一个封闭的公式。

有什么想法吗?

谢谢你的帮助。

1 回复 | 直到 15 年前

1

2

Alex Martelli 16 年前

从闭合公式开始:显然,对于x(j)【对于j,从0到k-5】,x在进入循环的j段时, x(j+1) = x(j) * 2 ,所以, x(j) 是 4 * 2**j (使用) ** “升职”),自 x(0) 是4; a(j+1) = a(j) + x(j) + j + 5 --没有人告诉我们 a(0) 是的,但我们可以把它分解出来写 a(j) 作为 a(0) + 某物。考虑到上面的封闭式解,你能搞清楚那是什么吗? X(j) ?我不愿意做你的家庭作业--你已经开始学习了吗? Concrete Mathematics 或者你的教科书是什么…?

一旦你写下 A(j) 和我提供的那个小东西一样 X(j) ,您能看到它们是如何组合起来使循环保持不变的吗…?