하노이탑 급해요!!!!!!!!! 내공 많이 드립니다

비공개 조회수 735 2019.07.09

하노이탑 수학적 귀납법

규칙 1) 원판은 한 번에 한 개씩만 한 기둥에서 다른 기둥으로 옮길 수 있다.

규칙 2) 큰 원판을 작은 원판 위에 놓을 수 있다.

위의 규칙에 따라 크기가 서로 다른 n개의 원판을 옮겨보자.

크기가 서로 다른 n개의 원판을 위의 규칙에 따라 다른 기둥으로 모두 옮기기 위한 최소 이동 횟수를 An이라고 하자.

원판이 1개일 때, 한 번에 옮길 수 있으므로 a1=1

원판이 2개일 때, 다음 그림과 같이 세 번에 옮길 수 있으므로 a2=3

활동 1= 위의 그림을 보고, a3을 a2를 이용하여 나타내 보자.

활동 2= an과 an+1 사이의 관계식을 구해 보자.

이거 풀이 알려주세요 ㅠㅠㅠㅠㅠ 발표 해야 하는 데 막막해요

답변자님,

정보를 공유해 주세요.

1 개 답변

a3은 a2를 실행하고 나서 제일 큰 원판을 빈 기둥에 옮긴 후에

그 큰 원판위에 다시 a2를 실행하면 되므로 a3 = a2+a2+1 = 7

an+1 은 다른 기둥에 an 을 하고나서 제일 큰 an+1원판을 빈 기둥에 옮긴 후에

거기에 다시 an들을 쌓으면 되므로 an+1 = an+1+an = 2an+1

[an+1 개를 an개와 제일아래큰판 1개로 분리하여 an개를 한기둥에 몰아넣은후에

제일 큰원판을 목표기둥에 옮기고 다시 an을 그 기둥위에 몰아넣는 방식]

2019.07.09.

도움이 되었다면 UP 눌러주세요!
UP이 많은 답변일수록 사용자들에게 더 많이 노출됩니다.

NAVER