하노이의 탑

하노이의 탑 설명

인도 베나레스에 있는 한 사원에는 세상의 중심을 나타내는 큰 돔이 있고 그 안에 세 개의 다이아몬드 바늘이 동판 위에 세워져 있습니다. 바늘의 높이는 1 큐빗이고 굵기는 벌의 몸통만 합니다. 바늘 가운데 하나에는 신이 64개의 순금 원판을 끼워 놓았습니다. 가장 큰 원판이 바닥에 놓여 있고, 나머지 원판들이 점점 작아지며 꼭대기까지 쌓아 있습니다. 이것은 신성한 브라흐마의 탑입니다. 브라흐마의 지시에 따라 승려들은 모든 원판을 다른 바늘로 옮기기 위해 밤낮 없이 차례로 제단에 올라 규칙에 따라 원판을 하나씩 옮깁니다. 이 일이 끝날 때, 탑은 무너지고 세상은 종말을 맞이하게 됩니다.

참고로, 승려들이 순금원판을 다른 바늘로 모두 옮기는 시간은, 한 번에 1초씩 걸린다고 쳐도 대략 5천 8백억 년 이상 이라는 계산이 나옵니다. (2의 64승 - 1)은 18,446,744,073,709,551,615.

이는 프로그래밍으로도 할 수 있다.

 

물론, int를 사용하면 2^32까지만,

int를 long long으로 대체하면 2^64까지 출력할 수 있다. 

 

 

#include <iostream>

using namespace std;

int main(void)

{

int n, i, d;

cin >> n;

d = 1;

for (i = 1; i <= n; i++) d = d * 2;

cout << d - 1;

}