제어 흐름: 종합과 도전 과제

요약

이 수업은 제어 흐름을 다루는 강좌의 4단원을 마무리한다. 조건에서 수치 알고리즘에 이르는 개념의 사슬을, 조건문과 경우 나누기, 반복문과 그 세 가지 형태, 반복문의 패턴, 불변식과 변량을 거쳐 다시 세운다. 그 가운데 어느 언어에서나 통하는 것과 C++에 고유한 것을 구별한다. 단원의 정의되지 않은 동작을 모으는데, 그것은 오버플로가 나는 카운터, 누산기, 조건에 집중되어 있으며, 그것을 보여 주는 프로그램과 그 수정을 함께 싣는다. 마무리 평가에서 입문 평가의 기능을 되풀이한다. 그리고 확장 유클리드 호제법에서 한 달 달력에 이르기까지 단원 전체를 엮는 여섯 도전 과제로 끝난다.

학습 목표

경우가 겹치지 않고 빠짐없는 조건문을 설계하고, 경우마다 그리고 경계마다 입력 하나로 시험한다.
종료하는 올바른 반복문을 설계하되, 그 형태와 패턴을 명세에서 출발하여 고른다.
반복문의 올바름을 불변식으로, 종료성을 변량으로 정당화하며, 단원의 수치 알고리즘에서도 그렇게 한다.
단원의 정의되지 않은 동작(오버플로가 나는 카운터, 누산기, 조건, 그리고 조건이 막았어야 할 나눗셈)을 알아보고, 그것이 없도록 반복문을 다시 쓴다.
단원에서 배운 것 가운데 어느 언어에서나 통하는 것과 C++에 고유한 것을 구별한다.

단원에서 이룬 것

이 단원은 조건문과 반복문으로 실행 순서를 다스리고, 그 올바름에 대해 추론하는 법을 가르치려 했다. 모든 경우가 처리되고, 모든 반복문이 해야 할 일을 하며, 종료한다는 것이다. 이 목적은 도입 수업이 이미 아는 것으로 선언한 것에만 기대어 이루어졌다. 3단원의 조건, 2단원의 자료형, 그리고 1.1강의 추적과 변량이다. 최대공약수를 고정된 세 단계로 계산하던, 그래서 데이터에 따라 틀린 답을 내거나 0으로 나누던 프로그램은 세 줄짜리 반복문으로 바뀌었고, 이제는 그 반복문이 음이 아닌 모든 데이터에 대해 올바르다는 것을 증명할 수 있다.

조건문

조건문 수업은 늘 중괄호를 붙인 if 문을 가르쳤다. else if 연쇄에서는 조건이 참인 첫 번째 가지가 실행되며, 따라서 각 가지의 실제 경우는 그 조건에 앞선 모든 조건의 부정을 더한 것임을 보였다. 순서가 중요하다는 것, 그리고 가지 하나가 아무 경고 없이 도달할 수 없게 될 수 있다는 것은 여기서 나온다. 모든 조건문의 올바름의 기준을 세웠다. 그 경우들은 겹치지 않아야 하고(연쇄의 형태가 이를 보장한다) 빠짐없어야 하며(연쇄가 else 절로 끝나면 그렇다), 명세의 경우와 일치해야 한다. 이것은 각 경우의 내부와 각 경계의 양쪽에서 시험한다. 조건문 전체를 쓰지 않고 두 짧은 값 가운데 하나를 고르는 조건 연산자를 소개했다. 마지막으로 enum class 타입과 switch 문을 다루었는데, 뒤의 것에서 빠뜨린 경우는 컴파일러가 경고한다.

반복문

반복문 수업은 while, do, for 문을 하나의 메커니즘의 세 형태로 제시했다. while 문은 각 회차 전에 조건을 계산하며 한 번도 돌지 않을 수 있다. do 문은 적어도 한 번 돈다. for 문은 머리에 초기화, 조건, 증감을 모으며, 그 제어 변수는 반복문 안에서만 산다. 그것들의 동치 관계와 추적표를 가르쳤는데, 조건 때문에 종료하는 while 문에서는 조건 계산이 $k + 1$ 번, 회차가 $k$ 번이다(do 문에서는 계산이 $k$ 번). 또 머리에서 회차를 세는 법을 가르쳤고, 이것이 하나 차이 오류를 막는다. break, continue, 그리고 중첩 반복문을 더했는데, 중첩 반복문의 안쪽 본문이 실행되는 횟수는 합으로 주어진다. 범위가 고정되면 $m \cdot p$ , 삼각형이면 $n(n + 1)/2$ 의 횟수이다.

올바른 반복문 설계

올바른 반복문 설계 수업은 반복문을 설계의 대상으로 만들었다. 패턴들(카운터, 누산기, 최댓값과 최솟값, 보초, 플래그)을 모았고, 각각을 매 회차 뒤에 그 변수가 무엇을 뜻하는지로 정의했다. 불변식을 조건이 계산될 때마다 성립하는 주장으로 정의하고, 그 세 가지 의무인 초기화, 유지, 종료를 제시했는데, 종료는 거짓인 조건과 함께 사후 조건을 준다. 그리고 불변식을 회차 수에 대한 귀납법으로 알아보았다. 사후 조건에서 불변식으로, 불변식에서 본문으로 거꾸로 설계하는 법을 가르쳤다. 종료성을 변량으로 정당화했고, C++의 산술이 변량을 무효로 만드는 세 반복문을 보였다. 1.0을 건너뛰는 실수 반복문, 한 바퀴 도는 부호 없는 카운터, 오버플로가 나는 부호 있는 카운터이다. 끝으로 디버거와의 첫 만남을 마련했다.

수치 알고리즘

수치 알고리즘 수업은 앞의 내용을 네 가지 고전 알고리즘에 적용했는데, 모두 main 함수 안에 쓰였고 증명되었다. 시험 나눗셈에 의한 소수 판정에서는 $\sqrt{n}$ 의 값까지만 가면 충분하다는 명제와 d <= n / d 조건을 다루었는데, 이 조건은 d * d <= n 조건이 오버플로가 나는 곳에서도 오버플로가 나지 않는다. 유클리드 호제법에서는 불변식 $\operatorname{gcd}(a, b) = \operatorname{gcd}(a_0, b_0)$ 의 성질과 변량 $b$ 의 값, 그리고 C++에서의 두 가지 위험, 곧 음의 결과와 본문 뒤에 조건을 계산할 때의 0으로 나누기를 다루었다. 연이은 나눗셈에 의한 진법 변환과, 계수 하나에 곱셈 한 번으로 다항식의 값을 계산하는 호너의 방법을 다루었다. 그리고 이분법을 다루었는데, 이것은 중간값 정리가 보장하고 정수 카운터가 다스리며, 그 회차 수는 미리 계산된다.