[C로 쓴 자료구조론] 1장 연습문제-1번 풀이

 

 

 

제가푼거라 틀릴수도 있습니다. 지적은 언제나 환영

 

 

1. 다음과 같은 두 문장을 생각해보자.

  (a) 양의 정수 x, y 및 z에 대해 x^n+y^n=z^n이 되는 n의 최대 값은 2인가?

  (b) 5를 0으로 나눠 x에 저장하고 10번 명령문으로 분기하라.

 

  두 문장은 알고리즘의 다섯 가지 조건 중 하나를 만족하지 않는다. 어느 조건에 어긋나는가?

 

Sol) 우선 알고리즘의 다섯 가지 조건은 다음과 같습니다.

1. 입력, 출력; 외부에서 0개 이상 입력을 받아 1개 이상 출력을 생성해야 한다.

2. 명확성; 각 단계가 단순해야 하며, 모호하지 않아야 한다.

3. 유한성; 한정된 수의 작업 후에는 반드시 끝나야 한다.

4. 효과성; 모든 명령이 수행 가능하여야 한다.

5. 효율성; 알고리즘이 효율적이여야 한다.

참고로 조금만 덧붙이자면 1번부터 4번까지만 만족해도 문제는 해결 가능합니다. 그러나 알고리즘은 궁극적으로 컴퓨터에서 수행하는 것을 목표로 하므로 실용성이 있어야하므로 효율성도 필요합니다.

 

 

우선 (a)문장을 보면 페르마의 마지막 정리를 인용한 문장이네요. 그러나 알고리즘으로 쓰기에는 말미가 의문문으로 끝나기때문에 명확성을 만족하지 않습니다.

그리고 (b)문장은 수학적으로 틀렸습니다. 수학적으로 어떤 수를 0으로 나누는 것은 정의되지 않았습니다. 이건 효과성을 만족하지 않습니다. 모든 명령은 수행 가능하여야합니다.