본문 바로가기

공부/과제

컴퓨팅적사고 문제해결(2019년 4월 14일 컴퓨팅적 사고 수업 과제) 2, 과제에 대한 반성

하노이의 탑 문제 해결 계획.zip

문제해결을 위해 끄적거린걸 스캔해서 올린다.(보관용)


 문제) "하노이의 탑"이라는 게임이 있다. 이 게임에서는 왼쪽 막대기에 쌓인 디스크를 가장 오른쪽 막대기로 옮기면 된다.

        A, B, C 3개의 기둥에 3개의 원반이 그림처럼 꽂혀있다.

A기둥에 있는 원반을 다른 기둥으로 옮기려고 한다. 한 번에 하나의 원반만 옮길 수 있고, 작은 원반 위에 큰 원반이 놓여서는 안 된다.

하노이 탑 문제를 해결할 때 따라야 하는 규칙은 다음과 같다.

  •   한 번에 하나의 디스크만 이동할 수 있다.
  •   각 이동은 스택 중 하나에서 상위 디스크를 가져 와서 다른 스택 맨 위에 놓는 것이다. 즉, 디스크가 스택의 최상위 디스크인  경우에만 디스크를 이동할 수 있다.
  •   작은 디스크 위에는 큰 디스크를 놓으면 안 된다.

 


1. 최소 몇 번이면 원반을 다 옮길 수 있을까?

  7번


2. 이 게임을 해결할 때 패턴은 무엇인가?

  하노이 탑의 원반의 개수를 2개부터 하나씩 증가시키면 같은 패턴이 반복되는 것을 알 수가 있다. A에 있는 n개의 원반

  중 맨 아래에 있는 1번째 원반을 제외한 나머지 원반을 모두 B로 옮기고, A에 남은 하나의 원반을 C로 옮긴다음, B에

  있던 나머지 모든 원반을 C로 옮기면 해결된다.


3. 순서도로 표현해 봅시다.


4. 알고리즘을 pseudo code로 작성해 봅시다.

 void hanoi(int n, char from, char middle, char to)

   if(n==1) // 원판의 개수가 1일 경우

      printf("원판 %02d 를 %c 로 이동\n", n,from,to); //원판의 이동을 화면에 출력

   else //원판의 개수가 1이 아닐 경우

   {

      hanoi(n-1, from, to, middle); //재귀

      printf("원판 %02d 를 %c 에서 %c 로 이동\n", n,from,to); //원판의 이동을 화면에 출력

      hanoi(n-1,middle,from,to); //재귀

   }

}


int main()

{

   int n = 0; //원판의 개수를 0으로 설정

   printf("원판의 개수를 입력해주세요 : "); //원판의 개수 입력

   scanf(%d", &n); //원판의 개수 입력값 저장

   printf("-----------------------\n"); //구분선

   hanoi(n, 'A', 'B', 'C'); //기둥 이름 설정


   return 0;

}



여담) 교수님께서 이 과제를 내주시고 이걸 슈도코드로 작성하면서 매우 많이 곤란했다.

        제대로 가르쳐주지도 않고 갑자기 이런 재귀호출을 사용하라니.. 아직 C언어를 다배우지못한 나는

        어쩔 수 없이 위키백과와 각종 블로그를 참고했지만 결국 어떠한 방식과 흐름으로 재귀되는지

        이해하지 못했다. 그래서 위에 작성된 pseudo code(사실 C언어이다)를 블로그에서 보고 뺏겨적을 수 밖에

        없었다.

        이런 과제를 내준 교수님이 원망스러웠고, 블로그에서 코드를 그대로 뺏겨 적은 걸 과제로 내는

        나 자신이 부끄러웠다. 물론 많은 현역 프로그래머분들이 구글이나 여러 사이트를 참고하면서  프로그램을

        만드는건 알고있다. 하지만 이렇게 몇줄 안되는 코드도 내 스스로 적지 못한다는 것이 너무 비참했다.

        이를 해결할 수 있는 방법은 알고있다. 바로 치열하게 공부하는것.. 하지만 그게 너무나 어렵다.

        매번 다짐하고 다짐하지만 공부를 꾸준히 계속 한다는것은 역시 어려운 일이다...