퍼즐과 게임 (게임- 하노이 탑, 15퍼즐 외)

소개글

퍼즐과 게임 (게임- 하노이 탑, 15퍼즐 외) 에 대한 보고서 자료입니다.

목차

없음.

본문내용

한 퍼즐 사이의 연관성에 대해서는 그저 추측만 할 수 있을 따름이다.)
■하노이 탑 풀이법
하노이의 탑 퍼즐의 풀이는 1884년 앨러디스(R. E. Allardice)와 프레이저(A. Y. Fraser)가 처음 수학 논문으로 발표했다. 사실, 원반 n개가 쌓인 탑을 수학적으로 추상화하면, 탑을 한 막대에서 다른 막대로 옮기는 데 필요한 이동 횟수를 구하는 것은 그렇게 어렵지 않다. 이 문제는 이산수학 기초 과정 연습 문제로 자주 나온다. 먼저 위쪽의 원반 n - 1개짜리 탑을 다른 막대로 옮겨놓은 다음 탑을 옮기려는 막대로 가장 큰 원반을 옮기고 나머지 원반 n - 1개를 가장 큰 원반 위로 옮겨놓으면 되므로 원반 n개짜리 탑을 옮기는 데 필요한 이동 횟수를 hn으로 표기하면 다음과 같은 점화식을 얻는다.
hn = 2hn-1 - 1
여기서 h1 = 1(또는 h0 = 0)이다. 위 점화식을 풀거나 수학적 귀납법을 이용하면 잘 알려진 풀이
hn = 2n - 1
이 나온다(따라서, 브라만 승려들이 원반 1장을 1초에 옮긴다고 해도, h64는 5천 8백억년이 넘으니까, 한 동안 세계는 안전할 것이다!). 문제에서는 암묵적으로 hn이 최소 횟수여야 한다고 가정하고 있지만, 위 풀이에서는 정말로 2n - 1이 최적해인가는 보여주지 못하고 있다. 이와 관련된 증명은 1981년에야 발표되었다―아마 그때까지는 아무도 그런 증명이 필요하다고 생각지 않았을 것이다.
하노이탑 문제 (Hanoi Tower Problem)
동판에 막대가 세 개 있고, 크기가 서로 다른 n 개의
원판이 한 막대에 꽂혀 있다. 이 때, 다음과 같은
규칙으로 원판을 다른 막대로 모두 옮기는 놀이를 한다.

(1) 한 번에 한 개의 원판만을 옮긴다.
(2) 크기가 큰 원판은 반드시 크기가 작은 원판
아래쪽에 있어야 한다.

그러면 원판을 모두 다른 막대로 옮기는데 필요한 이동
(move) 회수는 모두 몇 번 인가 알아보시오.


이러한 문제는 전형적인 귀납적사고를 필요로
하는 문제이다. 즉, 특별한 몇 가지의 경우를
관찰하여 일반적으로 적용할 수 있는 규칙을
추론하고 이를 엄밀하게 수학적으로 증명하는
과정을 거쳐 문제를 해결하도록 합시다.

먼저 원판이 한 개 뿐이라면, 우리가 필요한 원판의 이동회수는 1회 이다.
이제 원판이 두 개 뿐이면, 우리는 다음 그림과 같은 단계로 원판을 움직일
수 있다.
따라서 필요한 원판의 이동회수는 3 회이다.



문제 1. 위의 내용을 참고하여, 하노이탑 문제에서
원판이 세 개일 때 필요한 원판의 최소 이동회수는 모두
몇 회인가 알아보시오.

이제 일반적으로 n개의 원판이 있을 때 필요한 원판의 이동 회수를
알아보도록 하자. 이 경우의 풀이전략은 다음과 같다.

먼저 n개의 원판이 있을 때 모두 옮기는데 필요한 원판의 이동회수를 P(n)
이라고 하자. 그러면,
P(1) = 1
P(2) = 3
P(3) = 7

임을 알 수 있다.
일반적으로 P(n)은 P(n-1)로 부터 유도할 수 있다.
즉, 다음의 그림을 참고하여 생각하여 보자.




위의 그림을 보면, 모든 자연수 n에 대하여 우리는 관계식
P(n) = 2 P(n-1) + 1
등비수열의 합 공식을 이용하면, 일반적으로
■ 15 퍼즐이란?
미국 유명 퍼즐디자이너인 샘로이드가 만들었으며
14-15퍼즐이란 1부터 14까지는 차례대로 나열되어 있고14와 15는 그 순서가 뒤바뀐 것을 모두 순서대로 재배치하는 것.
당시 로이드는 이 퍼즐을 푸는 사람에게 1천 달러를 주겠다고 상금까지 걸었다는데 그 누구도 그것을 풀지 못했다고 합니다.
■ 퍼즐 풀이법
■ 그 외 게임..
게임명: samorost
설명:
이 게임은 플레시 미디어를 이용한 상상력을 자극하는 게임이며 장르는 간단한 어드밴쳐 퍼즐게임입니다. 현재 samorost2 까지 나와 있으면 풀버전은 유료로 서비스 되고 있습니다.
전반 적인 스토리는 주인공이 사는 소행성으로 다른 소행성이 다가와서 충돌하는것을 막으려고 날아오는 소행성으로 날아가서 충돌을 막는다는 이야기입니다. 하지만 요즘 나오는 화려한 게임과 달리 퍼즐적인 요소를 이용해서 게임을 진행시킵니다.
<게임의 진행>
<프롤로그>
게임을 시작하면 우선 주인공이 서식하는(?) 행성이 보여줍니다.
위쪽에 있는 등대를 클릭하면 게임은 진행이 됩니다.
<주인공의 거주지인 행성입니다. 척 보기에도 참신한 디자인을 하고 있습니다.>
<잠옷을 입고 돌아다니는 주인공입니다>

키워드

[자연과학] 퍼즐과 게임 (게임- 하노이 탑,   15퍼즐 외),   하노이 탑이란