[알고리듬] #86 장대 그리기

파이썬 실습창을 열 수 있습니다.실습창 열기

장대 그리기

1. 재귀호출의 흐름은 그림으로 보면 이해하기 쉽다.

위와 같은 그림을 그리려고 한다. 그림을 분석하여 보자.

• 직선의 모임이다.
• 평면에 직선을 그리려면 어떤 정보가 있어야 할까?
  - 시작점의 위치, 방향, 길이를 알아야 한다. 추가적으로 선의 굵기, 색깔 등이 필요하다.
  (시작점을 거북이가 있는 곳으로 하면 시작점 위치는 고려하지 않아도 된다.)
  - 위의 장대를 그리려면 직선의 개수도 알아야 된다. 위의 그림은 8개이다.
  - 직선의 개수, 방향, 길이, 선의 굵기와 같은 정보를 인수(argument)라 한다.
• 위의 그림은 직선이 규칙적으로 반복되어 있다. 
  - 변화 규칙(rule)은 방향은 처음 90도 다음부터 오른쪽으로 돌고, 길이와 굵기는 앞의 직선 보다 짧고 가늘다.
  - 색깔은 변하지 않으므로 변화 규칙에 포함되지 않는다.
•  이와 같이 규칙에 따라 변화하는 구조를 재귀 구조(recursive structure)리 한다.
  - 재귀 구조 문제는 재귀 호출 전략(recursive strategy)으로 코딩할 수 있다.

위의 그림을 그린 코드는 다음과 같다.

def rod(n,a,d,w):            # 개수, 방향, 길이, 굵기(가인수)
    if n==0:return           # 직선의 개수를 헤아린다.
    width(w)                 # 두께 w 
    left(a)                  # 방향 왼쪽으로 a도
    fd(d)                    # 길이 d인 하나의 직선을 그린다. 
    rod(n-1,-20,d*0.8,w*0.8) # 남은 직선 (n-1)개, 방향 오른쪽 20도, 길이와 굵기는 현재의 80%
from turtle import*
shape('turtle')
color('green')
rod(8,90,120,10) # 직선 8개, 처음 방향 90도, 길이 120, 선의 굵기 10(실인수) 
done()

• main에 있는 인수(argument)를 실인수(actual arg.), 함수에 있는 인수를 가인수(dummy arg.)라 한다. 인수는 문제 해결에서 반드시 알아야 되는 정보이다.
• 6번 라인 처럼 함수 속에서 자기 자신을 호출하여 전체 문제를 해결하는 방법을 재귀호출 전략(recursive startegy)이라 한다.
• 재귀 호출의 실행 흐름을 생각하자.
  - 10번 라인에서 실인수가 가인수에 순서대로 바인딩되며 함수를 만들고 그 함수로 제어가 넘어간다.  n이 8로서 0이 아니므로 직선을 그린다.
  - 6번 라인에서 6번에 있는 인수를 바인딩하며 새로운 함수를 만든다.
    n이 7로서 0이 아니므로 새롭게 바인딩 인수로서 직선을 그린다.
  - 이러한 과정을 반복하여 8개의 직선을 그리면 n이 0이 된다.
    n이 0이면 return한다. 즉, 지금의 함수를 호출한 전 단계 함수로 되돌아 간다.
  - 전 단계 함수의 마지막에 있는 return(7번 라인에 생략된 return)을 실행하여 또 전단계로 되돌아 간다.
  - 이러한 과정을 반복하여 최초의 함수 끝에 있는 return을 만나면 main의 done()을 실행하여 종료된다. 

흐름을 완전히 이해하라.

6번과 10번 라인의 인수를 바꾸어 그림을 변화시켜 보라.

 

2. 재귀호출 흐름의 이해를 검정한다.

위의 그림은, 그림을 다 그린 거북이가 원래의 위치로 되돌아 온 그림이다.

거북이를 반대 방향으로 돌게 하려면  left(-a), 거꾸로 가게 하려면 fd(-d) 등으로 코딩할 수 있다.

위와 같이 하여 보라.

위와 같이 할 수 있으면 재귀호출의 흐름을 이해하였다고 할 수 있다.

아래의 숨겨진 코드를 보지말고 끝까지 스스로 해결하라.

경험에 의하면 코드를 본 사람은 높은 수준에 이르기 어렵다.

코드는 스스로 완성한 다음에 비교하라.

def rod(n,a,d,w):
    if n==0:return
    width(w)
    left(a)
    fd(d)
    rod(n-1,-20,d*0.8,w*0.8)
    fd(-d)     # 되돌아 오면 뒷걸음한 다음에 방향을 반대로 돌린다.    
    left(-a)   # 4번과 5번 라인의 역순이다.

from turtle import*
shape('turtle')
color('green')
rod(8,90,120,10)
done()

지금 우리는 본격적인 알고리듬 공부를 시작하고 있다.

빨리 잘 하고 싶은가? 당신은 실패한다.

아무 생각없이 될때까지 그냥하는가? 당신은 성공한다.

성공한 사람은 인생이 바뀐다.

 

수고하셨습니다.

안녕!