현재 위치

홈 ›› Forums ›› 공부 ›› 프로그래밍 QnA

궁금한것이 있습니다.

Sohard의 이미지
글쓴이: Sohard / 작성시간: 토, 2017/03/11 - 9:25오전

기본적인 하노이의탑을 c로 구현하는데에는 정보가 많아 어려움이 없었으나

변형된 문제가 있는데 초짜라 그런지 너무어렵네요.

문제는 이렇게 됩니다.

원판은 모두 서로 다른크기이며, 1번에 1원판만 옮길수있고, 큰원판이 작은원판 위에 올라갈수없다
----- 여기까지는 기본적인 룰입니다.-------

-하노이 탑 기둥은 3개로 한다.

-첫줄에 원판의 갯수 n과 사이에 공백넣고 목적지 기둥 k를 입력한다.

-원판에는 1~n까지의 번호가 매겨져있다.

-두번째줄에 1번기둥의 원판의개수와 맨아래 원판부터 맨위 원판까지 번호를 입력한다.

-세번째줄에 2번기둥의 원판의개수와 맨아래 원판부터 맨위 원판까지 번호를 입력한다.

-네번째줄에 3번기둥의 원판의개수와 맨아래 원판부터 맨위 원판까지 번호를 입력한다.

이때 목적기둥으로 옮기는 최단횟수를 구하시오.

예시)
입력: 입력:
4 2 4 1
2 4 3 0
1 2 0
1 1 4 4 3 2 1
출력: 출력:
13 15

이런식입니다. 감사합니다.

Forums: 
프로그래밍 QnA
shint의 이미지

글쓴이: shint / 작성시간: 토, 2017/03/11 - 6:43오후

갯수 목적기둥k / 갯수 목적기둥k 4 2 4 1
1번 기둥(갯수) 맨아래번호 맨위번호 2 4 3 0
2번 기둥(갯수) 맨아래번호 맨위번호 1 2 0
3번 기둥(갯수) 맨아래번호 맨위번호 1 1 4 4 3 2 1

목적기둥으로 옮기는 최단횟수를 구하시오. 13 15

스크래치 프로그램 하노이의 탑'
하노이의 탑 C 언어'
하노이의 탑 플래시'를 구글에서 찾아보니. 몇몇 예제가 보이네요.

Tower of Hanoi
https://scratch.mit.edu/projects/28738/#editor

하노이의 탑에서 세 개의 원반 옮기기
https://ko.khanacademy.org/computing/computer-science/algorithms/towers-of-hanoi/e/move-three-disks-in-towers-of-hanoi

언플러그드 SW교육 #4_하노이탑 하며 재귀함수 체험하기
http://manchoikorea.blogspot.kr/2016/06/sw-4.html

[SW 교재3] 스크래치 프로그램으로 수학하기 (제작:창원대학교 과학영재교육원)
https://www.youtube.com/watch?v=gxKUwCWda8g

안드로이드 게임 개발로 배우는 코딩 기본 문법
https://educast.pro/11.421/

----------------------------------------------------------------------------
젊음'은 모든것을 가능하게 만든다.

매일 1억명이 사용하는 프로그램을 함께 만들어보고 싶습니다.
정규 근로 시간을 지키는. 야근 없는 회사와 거래합니다.

각 분야별. 좋은 책'이나 사이트' 블로그' 링크 소개 받습니다. shintx@naver.com

Sohard의 이미지

글쓴이: Sohard / 작성시간: 일, 2017/03/12 - 2:50오후

예제가
4 2 --> 원반4개에 목적기둥은 2번기둥이다
2 4 3 --> 1번기둥 원판은 2개이며 맨아래 4번원판 그위에 3번원판이있다
1 2 --> 2번기둥은 원판이 1개이며 2번원판이 있다.
1 1 --> 3번기둥은 원판이 1개이며 1번원판이 있다.
출력 :13 -->이때 목적기둥2번으로 쌓기위한 최소한의 이동횟수는 13회이다. --> 이것을 구해야함

그옆은 같은식으로
4 1 원판은 4개, 목적기둥은 1번기둥이다.
0 -->1번기둥에 원판 0개
0 -->2번기둥에 원판 0개
4 4 3 2 1 -->3번기둥에 원판4개, 아래에서부터 4 3 2 1원판이 꽂혀있다.
출력:15 -->1번기둥에 쌓기위한 최소한의 이동횟수는 15회이다.

이런식입니다 지금 두개의 예시가 글 올리고나서 붙어버렸네요.

shint의 이미지

글쓴이: shint / 작성시간: 일, 2017/03/12 - 10:32오후

ㅇ_ㅇ'' 저는 그렇네요. 다시 해보니. 13번 나오네요. (15번으로 착각) 2번과 1번을 바꿔도 13번입니다.
역시. 머리로 하면. 안되고. 테스트로 해도 안되고. 하나씩 확인해봐야 되네요.

https://ezgif.com/maker 에서 GIF 파일로 만들어봤습니다. (90 ms 와 50 ms 속도 2가지 입니다.)
테스트가 되었으니. 이제 원리를 만들어봐야죠. ㅇ_ㅇ''

//43 2 1 하노이 정렬 방식
3 2 4 2 3 2
1 3 1 2 1 4 1 2 1 3 1 2 1

1번이 빈곳을 만들었다.
3번이 빈곳에 갔다.
1번이 마지막에 갔다.
2번이 빈곳을 만들었다.
1번이 정리된곳으로 갔다.
4번이 옮겨갔다.

1번이 마지막으로 갔다.
2번이 빈공간으로 갔다.
1번이 정리된곳으로 갔다.
3번이 마지막으로 갔다.
1번이 빈공간으로 갔다.
2번이 정리된곳으로 갔다.
1번이 정리된곳으로 갔다.

//4개인 하노이 정렬 방식
2 3 2 4 2 3 2
1 2 1 3 1 2 1 4 1 2 1 3 1 2 1
1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 15개

패턴'이 만들어지네요. 중간에 무조건 1이 들어갑니다. (인공지능'이네요. DNA 염기 서열' 처럼도 보이네요.)
게다가. 1 3 1 2 1 4 1 2 1 3 1 2 1 이 같네요. 2번 미리 옮겨 간것과 같이 되버리네요.

그리고. 중간이 가장 큰 수'를 기준으로 양옆에 숫자가 같습니다.
5개라면. 2 3 2 4 2 5 2 3 2 4 2 가 될지도 모르겠네요. (예상'입니다.)
1 2 1 3 1 2 1 4 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 (확인해보니. 잘못 적었습니다.)
1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 23개

다시 해봤습니다. 근데. 이거도 아니네요. 역시 대충하니. 안되네요.
1 2 1 3 1 2 1 3 1 4 1 2 1 3 1 4 1 5 1 2 1 3 1 2 1 3 1 4 1 2 1 3 1 4 1 (확인해보니. 잘못 적었습니다.)
1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 35개

1 2 1 3 1 2 1 [3개]는 이렇습니다.
1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 [4개]
1 2 1 3 1 2 1 4 1 5 1 2 1 3 1 2 1 4 1 [5개] 될것 같은데... 모르겠네요. 아니라고 하니. (확인해보니. 잘못 적었습니다.)

그런데. 수학을 확인해보니. 31개가 나오네요.
2 * 2 * 2 * 2 * 2
4 8 16 32-1

하노이의 탑 규칙성
http://secstart.tistory.com/246

하노이의 탑
an=2^n - 1
https://namu.wiki/w/%ED%95%98%EB%85%B8%EC%9D%B4%EC%9D%98%20%ED%83%91

콘솔로 만든 프로그램도 있네요.
[C언어 게임 만들기] 하노이 타워(Hanoi Tower) / 하노이 탑쌓기 게임 프로그래밍 연습 / 프로그래밍
http://blog.naver.com/azure0777/220277982082

2 [3] 2
2 3 2 [4] 2 3 2
2 3 2 4 2 3 2 [5] 2 3 2 4 2 3 2
2 3 2 4 2 3 2 5 2 3 2 4 2 3 2 [6] 2 3 2 4 2 3 2 5 2 3 2 4 2 3 2
2 3 2 4 2 3 2 5 2 3 2 4 2 3 2 6 2 3 2 4 2 3 2 5 2 3 2 4 2 3 2 [7] 2 3 2 4 2 3 2 5 2 3 2 4 2 3 2 6 2 3 2 4 2 3 2 5 2 3 2 4 2 3 2

1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 [5] 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1
1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1

다시 해보니. 31개 되네요. (일단. 기본 규칙'을 찾았습니다.)

가장 쉬운 해결방법은. 모든 이동 위치'를 기록하고. 같은게 있는지 확인하는 겁니다.
아니면. 원반이 위치를 알 수 있는 방법을 구해야죠. (이미 있는 함수에 그냥. 적용이 될지 모르겠네요.)

C언어 함수를 확인해보니. 제가 만든 원반번호'가 이동한 순서 규칙'과 출력결과의 첫자리'가 일치했습니다.
http://codepad.org/ganabVRw

아까 올린 어떤분에 스크랫치 코드 쓸만하네요. 갯수를 약간 줄여서 올려봅니다.
https://scratch.mit.edu/projects/editor/#editor
저는 아직 이해는 안가지만. Solver 객체가 하노이의 탑' 코드를 제어해주는것 같습니다.
스크랫치 예제는 되기는 하는데. 목적지가 정해지지는 않아서. 갯수가 다를 수 있습니다.
그리고. 가끔 중간에서 이동하기도 하는 문제가 보이기도 하네요.

댓글 첨부 파일: 
첨부파일 크기
Image icon 90ms 하노이4개.gif31.59 KB
Image icon 50ms 하노이4개.gif31.59 KB
Image icon 90ms 하노이43 2 1.gif17.55 KB
Image icon 50ms 하노이43 2 1.gif17.55 KB
Package icon Tower of Hanoi.zip189.83 KB

----------------------------------------------------------------------------
젊음'은 모든것을 가능하게 만든다.

매일 1억명이 사용하는 프로그램을 함께 만들어보고 싶습니다.
정규 근로 시간을 지키는. 야근 없는 회사와 거래합니다.

각 분야별. 좋은 책'이나 사이트' 블로그' 링크 소개 받습니다. shintx@naver.com

　의 이미지

글쓴이: 　 / 작성시간: 일, 2017/03/12 - 9:34오후

일반화된 하노이의 탑 문제로군요.

처음에 디스크가 가지런히 쌓여 있는 게 아니라서 조금 복잡하기는 합니다만
원래 문제에 재귀적 해법을 제공하는 기본적인 특성은 그대로 남아 있습니다.

즉, k번째 디스크를 a에서 b로 옮겨야만 한다면, k+1번째 이후의 디스크는 전혀 신경쓸 필요 없고,
1~k-1번째 디스크는 반드시 c에 모조리 옮겨 두어야 한다는 특성 말이지요.
이 특성을 이용하면 n번째 디스크부터 시작해서 작은 디스크로 재귀호출해가며 최적해를 찾을 수 있지요.

원래의 문제처럼 일반항을 구해서 O(1) 해법을 만들어 버릴 수는 없지만,
원래 문제의 일반항을 가져다 쓰면, 이 문제에 O(n) 해법을 만들 수 있습니다.
프로그램이 입력을 받는 데 이미 O(n)의 시간이 걸리므로 이 정도가 최선이라고 해도 큰 문제는 없겠네요.

#include <stdio.h>
#include <stdlib.h>
 
int main(void) {
	unsigned long long int num_disks, num_disks_per_peg, i, disk, move = 0;
	char target_peg, *pegs, peg;
 
	scanf("%llu %c", &num_disks, &target_peg);
	pegs = (char *)malloc(num_disks + 1);
	if (!pegs)
		return EXIT_FAILURE;
	target_peg -= '1';
 
	for (peg = 0; peg != 3; peg++) {
		scanf("%llu", &num_disks_per_peg);
		for (i = 0; i != num_disks_per_peg; i++) {
			scanf("%llu", &disk);
			pegs[disk] = peg;
		}
	}
 
	for (disk = num_disks; disk; disk--) {
		if (pegs[disk] != target_peg) {
			move += (1llu << (disk - 1));
			target_peg = 3 - (target_peg + pegs[disk]);
		}
	}
	printf("%llu\n", move);
	free(pegs);
	return EXIT_SUCCESS;
}
shint의 이미지

글쓴이: shint / 작성시간: 일, 2017/03/12 - 9:48오후

저는 잘 이해가 안가네요.

----------------------------------------------------------------------------
젊음'은 모든것을 가능하게 만든다.

매일 1억명이 사용하는 프로그램을 함께 만들어보고 싶습니다.
정규 근로 시간을 지키는. 야근 없는 회사와 거래합니다.

각 분야별. 좋은 책'이나 사이트' 블로그' 링크 소개 받습니다. shintx@naver.com

raymundo의 이미지

글쓴이: raymundo / 작성시간: 월, 2017/03/13 - 1:35오후

와우,

move += (1llu << (disk - 1));

이게 그러니까 1 + f(n-1) = 1 + ( 2^(n-1) + 1 ) = 2^(n-1) 부분인 거군요. 덕분에 재밌는 문제 하나 배우고 갑니다 감사합니다.

좋은 하루 되세요!

Sohard의 이미지

글쓴이: Sohard / 작성시간: 화, 2017/03/14 - 10:52오후

많은 분들이 도와주셔서 드디어 해결할수있게되었어요.

감사합니다.

좋은 하루 되세요.

세벌의 이미지

글쓴이: 세벌 / 작성시간: 수, 2017/03/15 - 7:06오전

어려운 문제 해결 축하드려요. 기념으로 글 제목을
하노이탑 문제 - 해결
이런 식으로 바꾸면 어떨까요?

세벌 https://sebuls.blogspot.kr/

댓글 달기

텍스트 포맷에 대한 자세한 정보

Filtered HTML

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

BBCode

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param>
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

Textile

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • You can use Textile markup to format text.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Markdown

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • Quick Tips:
    • Two or more spaces at a line's end = Line break
    • Double returns = Paragraph
    • *Single asterisks* or _single underscores_ = Emphasis
    • **Double** or __double__ = Strong
    • This is [a link](http://the.link.example.com "The optional title text")
    For complete details on the Markdown syntax, see the Markdown documentation and Markdown Extra documentation for tables, footnotes, and more.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Plain text

  • HTML 태그를 사용할 수 없습니다.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 줄과 단락은 자동으로 분리됩니다.
댓글 첨부 파일
이 댓글에 이미지나 파일을 업로드 합니다.
파일 크기는 8 MB보다 작아야 합니다.
허용할 파일 형식: txt pdf doc xls gif jpg jpeg mp3 png rar zip.
CAPTCHA
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.