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

LIST ALL

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

하노이의 탑 원리와... 프로그래밍 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 2056 창조    미로 충돌 구현 [2] 김대명 2011/08/30  3254 2055 창조    미로 생성 [1] 성인e 2011/08/18  7935 2054 창조    창조로 전역후킹하기 [2] 김대명 2011/08/11  3416 창조    하노이의 탑 원리와... 프로그래밍 [2] 신용주 2011/07/30  4158 2052 창조    mdb 일련번호 초기화 방법좀 부탁드립니다.. [2] 권선중 2011/07/13  7632 2051 창조      [re] mdb 일련번호 초기화 방법좀 부탁드립니다.. [2] 권선중 2011/07/14  5005 2050 창조        질의 명령 실행후 테이블이 내용이 변경이 되... 권선중 2011/07/15  4536 2049 창조          [re] 질의 명령 실행후 테이블이 내용이 변경이 ... [1] 지상현 2011/07/15  3728 2048 창조    양력을 음력으로 변환하는 방법은 없나요? [3] 김대명 2011/07/12  3285 2047 창조      자바 양력->음력 변환 소스 [1] 김대명 2011/07/13  5484 2046 창조    비주얼 베이직 6에서 창조용 DLL 만들기 [2] 김대명 2011/06/21  6222 2045 창조    ... .. 2011/06/12  4318 2044 창조      [re] 그림판 깜빡임 문제 질문드립니다 [3] 지상현 2011/06/13  5051 2043 창조    원주율(파이) 구하기 [4] 김대명 2011/05/26  4076 2042 창조    다른프로그램입력내용받기 만물 2011/05/24  3561 2041 창조    도저히 안되서 여기에 질문합니다. 김대명 2011/05/20  3514 2040 창조      [re] 도저히 안되서 여기에 질문합니다. [3] 성인e 2011/05/20  3582 2039 기타    도와주세요.. 이민수 2011/05/13  3582 2038 창조    백신프로그램이 바이러스르 오진하는데 해결... [4] 이희창 2011/04/28  3042 2037 창조    도움말파일이 윈7에서 열리지 않습니다. [2] 이희창 2011/04/10  3684 2036 창조    SQL 연결시 비번을 물어보는데.. [1] 권선중 2011/03/31  4841 2035 창조    파일찾아 의 한계.. [2] 박재성 2011/03/25  4697 2034 창조    filetr32.dll 포트수정 [1] 유형종 2011/02/28  6139 2033 창조    문법검사 합격인데 왜 컴파일이 안되나요? [3] 김대명 2011/02/24  3747 2032 창조    윈도우 종료시... 또는 시작시... [3] 신용주 2011/02/06  4329
	LIST ALL   Prev [1][2][3][4] 5 [6][7][8][9][10]..[87] Next

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