loop invariants

[nnop]

• Loop Invariants @ cs.miami.edu

Cornell CS 2110 (有video)

• Introduction: Developing and understanding loops
• The loop invariant and four loopy questions
  1. Does it start right: Does the initialization make P true?
  2. Does it stop right: is postcondition R true when the loop terminates?
  3. Does each iteration (each execution of the repetend) make progress toward termination?
  4. Does the repetend keep invariant P true?

[nnop]

Others

• What is a loop invariant?
  • loop invariant should present the goal, not just for itself. ​
• Loop Invariant Proofs
• Lecture 21 - Loop Invariants
• HackerRank - Correctness and the Loop Invariant
• 二分查找有几种写法？它们的区别是什么？@知乎
• 循环不变式与二分查找 by 崔添翼
• “背”算法和写代码

[nnop]

• 白板编程浅谈——Why, What, How

  如果你使用 IDE 只是为了在其帮助下写出能过编译的代码，或是为了调试改 Bug，那么我不认为你是一名合格的程序员——我认为程序员可以被分为两种：

  • 先确认前条件/不变式/终止条件/边界条件，然后写出正确的代码
  • 先编写代码，然后通过各种用例/测试/调试对程序进行调整，最后得到似乎正确的代码

  我个人保守估计前者开发效率至少是后者的 10 倍，因为前者不需要浪费大量时间在 编码-调试-编码 这个极其耗时的循环上。通过白板编程，面试官可以有效的判定出面试者属于前者还是后者，从而招进合适的人才，并把老油条或是嘴遁者排除在外。

[nnop]

The Reinvigorated Programmer系列

• Are you one of the 10% of programmers who can write a binary search?
• Common bugs and why exercises matter (binary search part 2)
• Testing is not a substitute for thinking (binary search part 3)
• Writing correct code, part 1: invariants (binary search part 4a)
• Writing correct code, part 2: bound functions (binary search part 4b)
• Writing correct code, part 3: preconditions and postconditions (binary search part 4c)
• Buffy: Season 1, revisited

Invariants For Binary Search系列

• Invariants For Binary Search, Part 1: A Simple Example
• Invariants for Binary Search, Part 2: Refining The Specifications
• Invariants for Binary Search, Part 3: Improving Our Abstractions
• Invariants for Binary Search, Part 4: Using The Improved Abstractions