하노이 타워

#include <stdio.h>

int count;
void hanoi(int n, int from, int by, int to)
{
count++;
if(n == 1)
printf("\n1Move from %d to %d 1and %d", from, to);
else
{
hanoi(n-1, from, to, by);
printf("\n2Move from %d to %d 2and %d", from, to);
hanoi(n-1, by, from, to);

}
}

void main(void)
{
int i=0;
printf("\nif you want to quit , enter minus interge.");
while(1)
{
printf("\nEnter height of HANOI tower ->");
scanf("%d",&i);
if(i<=0)
break;
else{
hanoi(i, 1, 2, 3);
}
count=0;
}
}

<script LANGUAGE="javaScript">
function HanoiTower(n, from, to, using){
this.n =n
this.from=from
this.to=to
this.using=using
hanoi(n,from,to,using)
}

function hanoi(n,from,to,using)
{
if(n != 0)
{
hanoi(n-1, from, using, to);
print(from,using, to);
hanoi(n-1,using,to,from);
}
}

function print(from,using,to)
{
document.write(from+to+"<br>");
}

</script>
<script LANGUAGE="javaScript">
hanoi=new HanoiTower(4, "A","C","B")
</script>

이것은 자바스크립트 뿐만 아니라, C 언어 등 다른 언어로도 만드는 알고리즘 실습용 프로그램 입니다.

'하노이의 탑' 이라는 알고리즘인데요,

하노이의 탑 아시죠?

원판 이동하는 것 말하는 겁니다.

그것의 이동 경로를 출력하는 겁니다.

인터넷에서 찾아보시면 나오겠으나,

대충 설명 드리겠습니다.

일단, 맨 위 함수 HanoiTower(new 를 통해 객체가 된) 에서,

hanoi(n,from,to,using)

이렇게 부르죠?

n, from, to, using 을 해석하면,

hanoi(4,"A","C","B"); 가 되겠군요.

그럼 hanoi 함수는 뭘까요?

바로, "A" 에서 "C" 로, "B" 를 경유해서 4 개의 원판을 옮긴다는 뜻입니다.

그러니까, hanoi 함수는 정답을 출력하는 함수죠.

그럼, hanoi 함수의 소스를 봅시다:

function hanoi(n,from,to,using)
{
if(n != 0)
{
hanoi(n-1, from, using, to);
print(from,using, to);
hanoi(n-1,using,to,from);
}
}

일단, n 이 0 이면, 옮길 게 없으니, 0 이 아닐 때만 실행되는군요.

그다음,

hanoi(n-1, from, using, to);

이 문을 보십시오.

바로, n-1 개의 원판을, from 에서 using 으로, to 를 경유해서 옮깁니다.

상상이 가십니까?

그다음, 다시

print(from,using, to);

이 함수를 통해, from 에서 to 로 원판이 하나 이동했다는 것을 알리는 거죠.

그다음,

hanoi(n-1,using,to,from);

이 함수로, using 에 보관해 놨던 n-1 개의 원판을 다시 to 로 가져오는 겁니다.

자, 이해 되셨나요?

그런데, 그렇다면, 중간의 2개의 이동 작업은 어떻게 처리하냐구요?

그건 hanoi 함수가 알아서 처리해줍니다.

hanoi 함수가 자기 자신을 다시 호출함으로써, 이 작업이 재귀적으로 처리되는 겁니다. (신기하죠?)

이런 기법을, '재귀 호출' 이라고 합니다.

이것도 검색해 보시면 좋겠죠.

그럼...