질문게시판 - 반드시 검색을 하신 후 원하는 답변을 찾을 수 없을 때, 질문을 올려주세요.

LIST ALL

Posted by 신용주 2011-07-30 20:01:23, Hit : 4181

하노이의 탑 원리와... 프로그래밍 Homepage : http://eteatime.co.kr Post URL : http://cugz.sjworks.net/bbs/zboard.php?id=qna&no=2476

프로그래밍으로 한번 도전해보고 싶은데... 시작을 못하겠어요.. 원리 좀 설명해주시미...

지상현   2011-07-30 PM 10:15:44   이렇게 생각하시면 됩니다. A 슬롯에 접시가 4개 있을 때, C 슬롯으로 옮기고 싶다면, 가장 큰 접시 빼고 접시 3개를 먼저 B 슬롯으로 옮깁니다. 그 다음 가장 큰 접시를 C로 옮기고, B 슬롯에 옮겼던 접시 3개를 다시 C로 옮깁니다. 접시는 한 번에 하나밖에 못 움직이잖아요? 위 과정 중 접시 3개를 B 슬롯으로 옮겨야 하는데, 그것도 마찬가지로 접시 2개를 C 슬롯에 옮기고 3번 접시를 B로 옮깁니다. 그리고 C에 옮겨놨던 접시 2개를 다시 B로 옮깁니다. 이번엔 접시 2개를 C 슬롯으로 옮겨야 하지요? 접시 2개 중 1개를 B 슬롯에 옮기고 큰 접시 1개를 C 슬롯에 놓고, 다시 B 슬롯에 놨던 접시 1개를 C 슬롯에 두면 해결됩니다. 접시 n개를 풀기 전에 먼저 n-1개 짜리 문제를 풀면 맨 마지막 접시만 옮기면 해결되는 것이죠. n-1개짜리 문제는 n-2개짜리 문제를 풀면 되고, n-2개짜리는 n-3개짜리를 풀면 됩니다. 이런 식으로 해서 n-1이 0에 도달할 때까지 재귀호출 하면 됩니다.

성인e   2011-08-03 PM 2:19:15   어떻게 프로그래밍하는지는 위에 지상현님이 잘 설명해 주셨습니다. 헌데 최적 경로가 왜 저렇게 되는지는 안써주셔서 참고 되라고 올립니다. 위키피디아에 설명이 잘 되어있습니다: http://en.wikipedia.org/wiki/Tower_of_Hanoi 여기서 특히 Graphical representation 부분을 잘 째려보시면 시어핀스키 삼각형이 나오는데, 왜 최적 경로가 저렇게 되는지, 그리고 최적 경로의 스텝 수를 알게됩니다. 보다 넓은 경우에까지 확장이 가능합니다. 왜 최적 경로가 저렇게 되는지 의문을 가지며 넷을 뒤져보다 나왔길래 올립니다.

LIST ALL

GO TO THE TOP

	N Category    Subject Posted by Date H notice 창조   반드시 검색 후 질문을 올려주세요.<... 박종훈 2007/09/24  6102 notice 창조   단순 소스제작 부탁은 예고없이 삭제합니... [2] 손상진 2007/04/11  5931 notice 창조   답변소스 등록 관련 안내입니다. [7] 변혁수 2006/01/11  7795 2154 창조    메모장 자동 폭 가능할까요? 날아라KTX 2024/04/29  14 2153 창조    풍선말 글꼴, 크기 날아라KTX 2024/03/26  60 2152 창조    네이버 증권페이지 가격 [2] 날아라KTX 2024/02/22  88 2151 창조    문자창, 대화창 프로그램 가운데 출력하기 날아라KTX 2023/02/27  311 2150 창조    리스트박스 질문드려요. 날아라KTX 2022/10/25  370 2149 창조    메모내용 코마를 구분으로 리스트박스에 정렬... [3] 날아라KTX 2022/10/02  389 2148 창조    문자표 글꼴 색상 질문드려요 날아라KTX 2022/09/24  426 2147 창조    멀티버튼이 마우스 따라다니기 [1] 날아라KTX 2022/09/17  415 2146 창조    카카오톡 다중 접속기도 만들 수 있을까요? 김지훈 2022/04/19  614 2145 창조    레지스트리...문제점이 뭘까요???? [3] 날아라KTX 2022/04/14  521 2144 창조    자판을 뗄때 사건에서 띵띵소리 [1] 날아라KTX 2022/04/09  552 2143 창조    메모 상단줄 질문드려요. 날아라KTX 2022/04/05  516 2142 창조    폴더명추출 [1] 날아라KTX 2022/01/24  596 2141 창조    문자표 질문드려요. [1] 날아라KTX 2021/10/19  589 2140 창조    성인e님께서 도움주셨던 글자 찾아 색상바꾸... [5] 날아라KTX 2021/10/01  665 2139 창조    리스트박스에 파일명+파일내용 추가하기 [3] 날아라KTX 2020/07/26  1303 2138 창조    리스트박스 줄위치에 해당하는 버튼 클릭하기 [2] 날아라KTX 2020/03/11  1501 2137 창조    에디트0 영역에 문자추가 삭제하기 [2] 날아라KTX 2019/10/15  1603 2136 창조    이진읽어를 10진으로 바꾼다음에 1과 0만으로... [1] 박재성 2019/06/12  1790 2135 창조    알파벳순서대로 정렬도 창조로 가능할까요? 날아라KTX 2019/05/12  1582 2134 창조      [re] 알파벳순서대로 정렬도 창조로 가능할까요? [2] 성인e 2019/05/12  1865 2133      리스트박스1 * 문자가 있는 이름을 리스트박... [3] 날아라KTX 2019/04/17  1802
	LIST ALL   1 [2][3][4][5][6][7][8][9][10]..[87] Next

Copyright 1999-2024 Zeroboard / skin by reedyfox in miniwini style