하노이의 탑

티스토리 메뉴 펼치기 댓글수0

프로그래밍/기타

하노이의 탑

snoopybox
댓글수0

재귀 호출 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단계는 출발지와 목적지 위치만 다를 뿐 완전히 동일하다.


참조 영상 :


맨위로

https://www.snoopybox.co.kr/1961

신고하기