Invariants in Algorithms
바둑알 항아리에 흰 돌과 검은 돌이 담겨있고 항아리 밖에도 바둑알이 널부러져있습니다.
항아리 안에 하나의 돌만 남을 때까지 다음 과정을 반복합니다.
' 항아리에서 돌 두 개를 꺼낸다. 돌이 같은 색이라면 검은 돌을, 다른 색이라면 흰 돌을 항아리에 넣는다. '
과정을 반복할 수록 항아리의 바둑알은 하나씩 줄게 됩니다.
초기에 항아리에 들어 있는 흰 돌과 검음 돌의 개수와 관련하여 항아리에 남아있는 마지막 돌의 색에 대해 논의합니다.
Variables
수치가 변하는 건 검정돌과 흰돌이므로 검정돌을 b, 흰돌을 w로 두겠습니다.
이제 돌을 꺼내는 상황 3가지를 모델링하겠습니다
- 검정돌 2개를 꺼낼 때:
b,w := b+1, w-2 - 흰돌 2개를 꺼낼 때:
b,w := b-1, w - 각 1개씩 꺼낼 때:
b,w := b-1, w
Invariants
위 표현식을 살펴보면 흰돌은 그대로거나 2개가 감소하게 됩니다.
즉 흰돌의 홀짝성이 불변하는 것을 확인할 수 있습니다.
Conclusion
흰돌의 홀짝성에 따라 홀수라면 마지막엔 흰돌이 짝수라면 검정돌이 남게 됩니다.
