我正在学习数据结构和算法的基础课程,我们使用的书是CLRS的开创性工作.我在理解循环不变量时遇到一些问题,如第2.1章:插入排序中所述.
这本书说:
在第1-8行的for循环的每次迭代开始时,子目标A [1..j -1]由最初在A [1..j-1]中的元素组成,但是按排序顺序.
现在,这让我很困惑.为什么在第一次迭代开始时它会成立？假设要排序的数组看起来像{5,2,4,6,1,3}.现在,当for循环的第一次迭代开始时,A [1 .. j-1]不是按排序顺序,但是当迭代结束时它就是.
我在这里错过了什么？
我试图找到循环的不变量（例如在下面的代码中）我真的不知道如何找到一般的不变量。任何人都可以帮助我如何找到不变量，并帮助我找到以下代码的不变量吗？谢谢
public static int div(int a, int b)
{
int q = 0;
while(a >= b)
{
a -= b;
q++;
}
return q;
}
我有我的测试代码(研究WP循环不变量),它在数组单元格中添加两个长整数,每个数字的表示形式:
int main(int argc, const char * argv[]) {
char a[32], b[32];//size can be very big
memset(a, 0, sizeof(a));
memset(b, 0, sizeof(b));
scanf("%s %s", a, b);
unsigned int size1 = strlen(a);
unsigned int size2 = strlen(b);
//code to reverse a string. currently proved
reverse(a, size1);
reverse(b, size2);
for (unsigned int i = 0; i < size1; i++) a[i]-='0'; //move from chars to integers
for (unsigned int j = 0; j < size2; j++) b[j]-='0';
unsigned int maxsize = size1;
if …此示例使用的不变量来自https://www.win.tue.nl/~kbuchin/teaching/JBP030/notebooks/loop-invariants.html
我很困惑。示例中的代码使用循环for。
我将其翻译为while循环，因为我更好地理解这一点，并且添加了断言来测试不变量。
这个while例子对我来说完全有意义，我可以看到不变量在每个断言点上是如何成立的。
然而，在该for示例中，断言assert total == sum(A[0:i]) and i >= len(A)失败。
我可以理解为什么它可能会影响该i值，因为i在 处停止递增4。但我不确定为什么总和的最终断言需要是assert total == sum(A[0:i + 1])。
这似乎是一件非常微妙的事情，围绕着“差一个错误”。我对不变量的“硬编码”也有点不舒服assert total == sum(A[0:0])
while任何人都可以提供我的代码版本到版本的精确转换for，以及不变量的所有必要断言，并解释它们如何/为什么不同？
非常感谢任何帮助。
def my_sum_while(A):
"""
Loop Invariant: At the start of iteration i of the loop, the variable
`total` should contain the sum of the numbers from the subarray A[0:i].
"""
i = 0 …我的问题是关于时间优化。通过执行以下操作，for 循环是否更快：
std::vector<int> myVec = {0,1,2,3};
for(int i = 0; i < myVec.size(); i++){}
或者最好的做法是预先计算大小？
std::vector<int> myVec = {0,1,2,3};
int myVecSize = myVec.size();
for(int i = 0; i < myVecSize ; i++){}
我在这里不仅想知道纯粹的时间执行，还想知道它是否会导致以某种方式出现一些问题