이민석/하노이탑 - Revision history

imported>codeonwort at 06:21, 9 February 2015

2015-02-09T06:21:56Z

← Older revision		Revision as of 06:21, 9 February 2015
Line 52:		Line 52:

	* 점화식		* 점화식
			** 계산량은 O(N)
	[[File:HANOI-K_점화식_2.png]]		[[File:HANOI-K_점화식_2.png]]

	* 닫힌 형태		* 닫힌 형태
			** 거듭제곱을 구할 때 Divide & Conquer를 적용하면 계산량은 O(logN)
	[[File:HANOI-K_닫힌형태.png]]		[[File:HANOI-K_닫힌형태.png]]

imported>codeonwort at 06:19, 9 February 2015

2015-02-09T06:19:17Z

← Older revision		Revision as of 06:19, 9 February 2015
Line 52:		Line 52:

	* 점화식		* 점화식
	[[File:HANOI-~~K_점화식_1~~.png]]		[[File:HANOI-K_점화식_2.png]]

	* 닫힌 형태		* 닫힌 형태
	[[File:HANOI-K_닫힌형태.png]]		[[File:HANOI-K_닫힌형태.png]]

imported>codeonwort at 06:18, 9 February 2015

2015-02-09T06:18:27Z

← Older revision		Revision as of 06:18, 9 February 2015
Line 52:		Line 52:

	* 점화식		* 점화식
	[[File:HANOI-~~K_점화식~~.png]]		[[File:HANOI-K_점화식_1.png]]

	* 닫힌 형태		* 닫힌 형태
	[[File:HANOI-K_닫힌형태.png]]		[[File:HANOI-K_닫힌형태.png]]

imported>codeonwort at 06:04, 9 February 2015

2015-02-09T06:04:28Z

← Older revision		Revision as of 06:04, 9 February 2015
Line 52:		Line 52:

	* 점화식		* 점화식
	~~<nowiki>attachment~~:HANOI-~~K_%EC%A0%90%ED%99%94%EC%8B%9D~~.png~~</nowiki>~~		[[File:HANOI-K_점화식.png]]

	* 닫힌 형태		* 닫힌 형태
	~~<nowiki>attachment~~:HANOI-~~K_%EC%A0%90%ED%99%94%EC%8B%9D~~.png~~</nowiki>~~		[[File:HANOI-K_닫힌형태.png]]

imported>codeonwort at 06:04, 9 February 2015

2015-02-09T06:04:04Z

← Older revision		Revision as of 06:04, 9 February 2015
Line 52:		Line 52:

	* 점화식		* 점화식
			<nowiki>attachment:HANOI-K_%EC%A0%90%ED%99%94%EC%8B%9D.png</nowiki>

	* 닫힌 형태		* 닫힌 형태
			<nowiki>attachment:HANOI-K_%EC%A0%90%ED%99%94%EC%8B%9D.png</nowiki>

imported>codeonwort at 06:03, 9 February 2015

2015-02-09T06:03:46Z

New page

=== 직접 플레이하는 버전 ===
[http://wonderfl.net/c/eQC5]

=== 블록 개수 입력하면 이동 순서 출력하는 버전 ===
#include <stdio.h>
#include <stdlib.h>

int count = 0;

void hanoi(int blocks[], int i, int goal) {
int rest;
if (i == 0){
printf("%d: %d -> %d\n", i, blocks[i], goal);
blocks[i] = goal;
count++;
}
else if (blocks[i - 1] == blocks[i]){
rest = 3 - blocks[i] - goal;
hanoi(blocks, i - 1, rest);
hanoi(blocks, i, goal);
hanoi(blocks, i - 1, goal);
}
else{
printf("%d: %d -> %d\n", i, blocks[i], goal);
blocks[i] = goal;
count++;
}
}

void main() {
int numBlocks=0, j;
int *blocks = NULL;
while (1){
printf("Enter the number of blocks: ");
if (scanf_s("%d", &numBlocks) == 0 || numBlocks < 3){
fflush(stdin);
puts("You must input an integer n >= 3");
continue;
}

count = 0;
if (blocks != NULL) free(blocks);
blocks = (int*)malloc(sizeof(int) * numBlocks);
for (j = 0; j < numBlocks; j++) blocks[j] = 0;
hanoi(blocks, numBlocks - 1, 2);
printf("move count: %d\n", count);
}
}

=== 이동 횟수에 관한 공식 ===
기둥이 K개일 때의 하노이 탑 문제를 HANOI-K라고 명명하자. 옮길 블록의 갯수는 N이다. (여기서 K는 3 이상의 정수, N은 자연수)

* 점화식

* 닫힌 형태