네 기둥 HanoiTower - --- 달콤 한 지 고민 하 는 지

나 는 많은 사람들 이 처음 공부 하고 돌아 올 때 선생님 이나 책 에 한 노 타의 예 를 들 수 있 을 것 이 라 고 생각한다.
그러나 오늘 우리 가 토론 하 는 중점 은 간단 한 한 노 타 알고리즘 이 아니 라 세 기둥 한 노 타의 연장 이다.먼저 전형 적 인 삼 주 한 노 타 를 살 펴 보 자.
 
1, 3 주 한 노 타 (Hanoi Three):
삼 주 한 노 타 에 대한 이해 와 알고리즘 실현 에 익숙 하 실 거 라 고 생각 합 니 다.
나 는 여기 서 삼 주 한 노 타의 알고리즘 사상 을 간단하게 한 번 살 펴 보 았 다.
A, B, C 세 개의 기둥 이 있 고 A 기둥 에 n 개의 접시 가 있 는데 지금 은 A 에 있 는 모든 접 시 를 C 로 옮 겨 야 하 니 운반 횟수 가 가장 적은 절 차 를 밟 아 주세요.
 
알고리즘 사상:
1. A 위의 n - 1 개의 접 시 를 C 로 캐 시 하고 모두 B 기둥 으로 옮 깁 니 다.
2. A 에 남 긴 n 번 째 접 시 를 C 로 옮 깁 니 다.  기둥 위.
3. B 에 있 는 n - 1 개의 접 시 를 A 를 캐 시 로 하고 모두 C 기둥 으로 옮 깁 니 다.
 
알고리즘 을 쉽게 얻 을 수 있 는 재 귀 방정식 은 T (n) = 2 * T (n - 1) + 1 이 고 걸음 수 는 T (n) = 2 ^ n - 1 이 라 고 계산 하기 어렵 지 않다.
 
구체 적 인 코드 는 다음 과 같다.

void Move( char x, char y )
{
	printf("%c --> %c
", x, y);	//    ，x-->y
}

void Hanoi_Three( int n, char a, char b, char c )
{
	if( n <= 0 )
		return ;	
	
	step++;		//  +1
	
	if( n == 1 )
	{
		Move( a, c );	// a            c 
		return ;	
	}
	else
	{
		Hanoi_Three( n-1, a, c, b);		// a n-1    c   ，      b   
		Move( a, c );					// A     n   ，      C    
		Hanoi_Three( n-1, b, a, c);		// b  n-1   ， a   ，      c   
	}
}

2. 사주 한 노 타 (Hanoi Four):
 
기둥 이 네 개 일 때 접 시 를 모두 다른 기둥 으로 옮 기 는 것 만으로 도 난이 도 를 크게 낮 추 었 고 알고리즘 의 복잡 도 도 를 크게 낮 추 었 다.그러나 이때 가장 좋 고 절차 가 가장 적은 실현 방법 을 찾 으 려 면 난이 도 는 수량 급 을 올 린 것 이 라 고 할 수 있다.
어떤 사람들 은 왜 내 가 삼 주 한 노 타의 사상 을 사용 하 는 것 이 최적화 되 지 않 았 는 지 의심 할 수도 있다.
서 두 르 지 말고 내 가 천천히 너 에 게 말 할 게.
 
먼저 이런 '합 리 적 으로 보인다' 는 해법 을 살 펴 보 자.
가설, A, B, C, D 는 각각 소스 위치, 캐 시, 캐 시, 목적 위치 이다.
세 기둥 이 있 을 때, 우 리 는 A 의 앞 n - 1 접 시 를 B 에 캐 시 한 다음, n 접 시 를 C 기둥 에 놓 기 때문이다.
현재 상황 이 매우 좋 습 니 다. 캐 시 할 수 있 는 기둥 이 두 개 있 기 때문에 이동 이 더욱 편리 해 보 입 니 다. 원래 B 에 캐 시 할 n - 1 개의 접시 가 있 었 는데 지금 은 n - 2 개의 접시 일 뿐 이 고 n - 1 개의 접 시 를 C 에 캐 시 할 수 있 습 니 다.
 
구체 적 인 절 차 는 다음 과 같다.
1. A 에서 C, D 를 빌려 n - 2 개의 접 시 를 B 위로 이동한다.
2. n - 1 번 접 시 를 C 위로 옮 깁 니 다.
3. n 번 째 접 시 를 D 위로 옮 깁 니 다.
4. n - 1 번 접 시 를 D 위로 이동 합 니 다.
5. B 에서 A, C 를 빌려 n - 2 개의 접 시 를 모두 D 위로 이동한다.
 
보기에 매우 완벽 하 다. 필 자 는 한때 이 사상 이 허점 이 없다 고 생각 했다. 심지어 나 는 k 개의 기둥 인 한 노 타의 통용 방법 을 찾 았 다 고 생각 했다.내 가 이 글 을 볼 때 까지: 다 주 한 노 타 최 우수 알고리즘 디자인 탐구.
    접시 가 최대한 겹 치지 않도록 걸음 수 를 최소 화 하 겠 다 고 생각 했 지만 절대 장담 할 수 는 없 었 다.아마도 접시 가 비교적 적은 상황 에서 가능 할 것 이다. 그러나 접시 가 증가 할 때, 그 남 은 것 은 단지 한 접시 의 기둥 만 이용 할 수 있다 (가능 한 최 적 화 는 여기에 있다).이렇게 하면 매번 이동 걸음 수 를 늘 렸 지만 다른 측면 에서 재 귀 수량 을 줄 였 기 때문에 우 리 는 이 안에서 균형 점 을 찾 아야 한다.
 
다음은 1941 년 에 미국의 J. S. Frame 이 제시 한 사주 한 노 타의 알고리즘 사상 을 Frame 알고리즘 이 라 고도 부른다.
1. 4 주 한 노 타 알고리즘 으로 A 기둥 윗부분 의 n - r 개의 접 시 를 C 기둥 과 D 기둥 을 통 해 B 기둥 위로 옮 깁 니 다 [F (n - r) 걸음].
2. 3 주 한 노 타 고전 알고리즘 으로 A 기둥 에 남 은 r 개의 접 시 를 C 기둥 을 통 해 D 기둥 으로 옮 깁 니 다 [2 ^ r - 1 단계] (상기 3 기둥 의 상황 참조).
3. 4 주 한 노 타 알고리즘 으로 B 기둥 에 있 는 n - r 개의 접 시 를 A 기둥 과 C 기둥 을 통 해 D 기둥 위로 옮 깁 니 다 [F (n - r) 보].
4. 위의 규칙 에 따라 모든 r (1 ≤ r ≤ n) 상황 에서 걸음 수 f (n) 를 구하 고 최소 로 최종 적 으로 해석 할 가치 가 있다.
 
따라서 Frame 알고리즘 의 귀속 방정식 은 다음 과 같다.
F(n)=min(2*F(n-r)+2^r-1)，（1≤r≤n）。
 
여러분 은 사실 이 알고리즘 사상 은 우리 가 이전에 합 리 적 이 라 고 생각 했 던 알고리즘 과 대체적으로 일치 합 니 다. 차 이 는 그 가 우리 의 n - 2 개의 접 시 를 B 에 캐 시 하고 n - r 개의 접 시 를 B 기둥 에 옮 기 는 것 입 니 다.
차이 가 핵심 이라도 이 알고리즘 의 핵심 은 n 개의 접 시 를 계산 하 는 상황 에서 r 가 왜 값 을 계산 할 때 알고리즘 을 가장 잘 만 들 수 있 습 니까?
 
핵심 을 찾 으 면 우리 의 현재 임 무 는 명확 해진 다. 바로 r 값 에 대한 계산 이다.
여기 서 비교적 어 리 석 은 방법 인 매 거 를 제시 했다.일정한 범위 내의 n 과 r 의 모든 값 을 가 져 와 F (n) 를 최소 값 으로 만족 시 키 는 r 의 값 을 얻 고 K [n] = r 로 기록 하 는 것 입 니 다.
구체 적 인 코드 는 다음 과 같다.

void Init_K(void )
{
	int i, k;	
	__int64 temp;	
	__int64 m[Max+1] = {0};		
	
	for( i = 1; i <= Max; i++ )
	{
		m[i] = INT_MAX;		
		for( k = 1; k <= i; k++ )
		{
			temp = 2*m[i-k] + (__int64)pow(2,k) - 1;	
			if( temp < m[i] )
			{
				m[i] = temp;	
				K[i] = k;	
				//printf("K[%d] = %d, m[i] = %d
", i, k, temp );	
			}
		}
	}
}

각 n 쌍 의 r 를 얻 은 후에 알고리즘 은 매우 간단 해 지고 구체 적 으로 다음 과 같이 실현 된다.

#include 
#include 
#define Max 100	
#define INT_MAX 0xfffffffffffffff
int K[Max+1] = {0};	
int step = 0;	

void Hanoi_Four( int n, char a, char b, char c, char d );	
void Hanoi_Three( int n, char a, char b, char c );	
void Move( char x, char y );	

void Move( char x, char y )
{
	printf("%c --> %c
", x, y);	//    ，x-->y
}

void Hanoi_Three( int n, char a, char b, char c )
{
	if( n <= 0 )
		return ;	
	
	step++;		//  +1
	
	if( n == 1 )
	{
		Move( a, c );	// a            c 
		return ;	
	}
	else
	{
		Hanoi_Three( n-1, a, c, b);		// a n-1    c   ，      b   
		Move( a, c );					// A     n   ，      C    
		Hanoi_Three( n-1, b, a, c);		// b  n-1   ， a   ，      c   
	}
}

void Hanoi_Four( int n, char a, char b, char c, char d )
{
	if( n <= 0 )
		return ;	
	
	if( n == 1 )
	{
		step++;	
		Move( a, d );	
		return ;	
	}
	else
	{
		int kn = K[n];	
		//printf("kn = %d
", K[n]);	
		Hanoi_Four( n-kn, a, c, d, b );		// 4       A     n- kn     C  D   B  
		Hanoi_Three( kn, a, c, d );			// 3         A     kn     C   D  。
		Hanoi_Four( n-kn, b, a, c, d );		// 4       B   n-r     A  C   D  
	}
}

void Init_K(void )
{
	int i, k;	
	__int64 temp;	
	__int64 m[Max+1] = {0};		
	
	for( i = 1; i <= Max; i++ )
	{
		m[i] = INT_MAX;		
		for( k = 1; k <= i; k++ )
		{
			temp = 2*m[i-k] + (__int64)pow(2,k) - 1;	
			if( temp < m[i] )
			{
				m[i] = temp;	
				K[i] = k;	
				//printf("K[%d] = %d, m[i] = %d
", i, k, temp );	
			}
		}
	}
}

int main()
{
	int n;	
	Init_K();	

	printf("Please enter the number of the Plates: 
");
	while( scanf("%d", &n) != EOF )
	{
		step = 0;	
		Hanoi_Four( n, 'A', 'B', 'C', 'D' );	
		//Hanoi_Three( n, 'A', 'B', 'C' );	
		printf("**************************
Total Step: %d
", step );	

		printf("Please enter the number of the Plates: 
");
	}
	
	return 0;	
}

 
여기까지 사주 한 노 타의 알고리즘 은 기본적으로 끝났다.
관심 있 는 학생 들 은 다 주 한 노 타의 실현 방법 을 계속 요약 할 수 있 습 니 다. 교류 지 도 를 환영 합 니 다!
 
 
 합 리 적 으로 보 이 는 배후 가 사실은 일종 의 사고 정세 일 때 가 많다.
 
 
 
 
 
년 10 월 5 일 22: 54: 17