프로그래밍/기타
하노이의 탑
snoopybox
2019. 2. 13. 01:35
재귀 호출 BASH 버전 :
#!/bin/bash
hanoi(){
if [ $1 -eq 1 ]; then
echo "move $1 from $2 to $3"
return
fi
hanoi $(( $1 - 1 )) $2 $4 $3
echo "move $1 from $2 to $3"
hanoi $(( $1 - 1 )) $4 $3 $2
}
hanoi 4 A B C 호출 결과 :
move 1 from A to C move 2 from A to B move 1 from C to B move 3 from A to C move 1 from B to A move 2 from B to C move 1 from A to C move 4 from A to B move 1 from C to B move 2 from C to A move 1 from B to A move 3 from C to B move 1 from A to C move 2 from A to B move 1 from C to B
Comment :
4개의 원판을 A에서 B로 옮기기 위해서는
1단계 - 3개의 원판을 A에서 C로 옮겨놓고
2단계 - 가장 아래에 있던 4번째 원판을 A에서 B로 옮긴 후
3단계 - 다시 C에 있던 3개의 원판을 B로 옮기면 된다.
1단계와 3단계는 출발지와 목적지 위치만 다를 뿐 완전히 동일하다.
참조 영상 :