英文:
Find loop invariant of this function
问题
我需要找到gcd（欧几里德算法）的循环不变式，但我不知道从何处开始或者要查找什么。
int f(int x, int y) {
while (true) {
int m = x % y;
if(m == 0) return y;
x = y;
y = m;
}
}
英文:
I need to find the loop invariant of gcd (euclid algorithm) but i don't know from where to start or what to look
int f(int x, int y) {
while (true) {
int m = x % y;
if(m == 0) return y;
x = y;
y = m;
}
}
答案1
得分: 3
最大公约数 x 和 y 在整个循环过程中保持不变。因此，循环不变式是 gcd(x, y) = c，其中 c 是一个常数。
英文:
The greatest common divisor of x and y remains the same throughout the loop. Therefore, a loop invariant is gcd(x,y) = c where c is a constant.
答案2
得分: 2
一个循环不变式是在每次循环迭代中都满足的条件。在你的情况下，你没有基于可以改变的条件进行循环，所以如果循环不变式不是“循环条件始终为真”，那么在每次迭代中唯一成立的另一件事是“变量 m 的值始终显示 x 是否可以被 y 整除”。
英文:
A loop invariant is a condition that is met in every iteration of the loop. In your case, you're not looping on a condition that can change, so if the loop invariant isn't "the loop condition is always true", the only other thing that holds true for every iteration is "the value of m always shows whether x can be divided by y".
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论