[일반] 하노이탑 물어보러 왔습니다

[익명(39.112)]

5-2번 물어보는데 수갤에는 조무사가 많아서 여기 왔습니다

[ㄱㄴㄷ(218.146)]

12/123/1234/... 이런 식으로 덩어리 만들어가면 2n-1번이면 되는 것 같음

[ㄱㄴㄷ(218.146)]

아 아니구나 이거 원판 하나씩만 이동하는 거였지 ㅋㅋㅋ

[heisenberg(asdf5447)]

https://m.blog.naver.com/pk8716/221335694008

[익명(39.112)]

오

[ns(qwer2357)]

점화식을 세개 잡음. 모두 한 막대로 옮기는데 1. 처음에 홀수가 있는 곳으로 다 옮기는 가지수를 An, 첨에 짝수가 있는 곳으로 다 옮기는 가지수를 Bn, 빈칸으로 다 옮기는 가지수를 Cn

[ns(qwer2357)]

우선 간단히 A1 B1 C1이 3 1 2인건 알거고, Bn을 먼저 생각하면 그림처럼 n=4일때 최종적으론 1-6까지를 3번 판에 보내고 7을 8로 보내고 나머지를 다 2번으로 보내야함

[ns(qwer2357)]

그래서 일반 하노이 n개를 Xn이라고 하면 (Xn=2^n -1이겠지만) Bn = C_(n-1) + 1 + X_(2n-2) 가 됨

[익명(1.234)]

점화식세우면될듯

[ns(qwer2357)]

비슷하게 n=4일때 Cn은 8을 2에서 3으로 옮기기 위해서 1-7이 모두 1번에 모여야하기 때문에, Cn = A_(n-1) + 1 + X_(2n-1) 이 됨.

[ns(qwer2357)]

마지막으로 An은 1-7을 3번으로 보내야 하니 그 전에 1-6이 2번에 모여야 하고 다음 7 보내고 위에 다 옮긴 뒤 8 보내고 다 옮기면 됨. 그래서 An = B_(n-1) + 1 + X_(2n-2) + 1 + X_(2n-1) (단 X0=0) 이 됨

[ns(qwer2357)]

이제 나머진 뭐 연립해서 점화식 풀면 돼 문제에서 구하는 최소는 아마 Bn에서 나올거임