하노이 타워

난이도 쉽게
자주 묻는 질문 팩트 셋 포카이트 MAQ
분열과 정복 수학 재귀 학교 프로그래밍 스택조회수 76

하노이 타워는 다음 조건에서 수학적 문제입니다.

  • 세 개의 탑이 있습니다
  • n 개의 링이있을 수 있습니다.
  • 반지의 크기가 다릅니다.
  • 한 번에 하나의 디스크 만 이동할 수 있습니다.
  • 모든 디스크는 더 큰 디스크의 상단에서만 이동할 수 있습니다.
  • 상단 디스크 만 제거 할 수 있습니다.

설명

두 개의 디스크가있을 때이 문제를 어떻게 처리 할 수 ​​있는지 살펴 보겠습니다.

하노이 타워 설명핀

상단 (작은) 디스크를 다음 타워로 이동 한 후 두 번째 디스크를 세 번째 타워로 이동 한 다음 결국 첫 번째 디스크도 세 번째 타워로 이동합니다. (3 수)

가정 : 디스크는 처음에 정렬됩니다.

마찬가지로 3 개의 디스크로 작업 할 때도 마찬가지입니다. 세 번째 링으로 모두 이동하려면 7 단계가 필요합니다.

  • 디스크 1이 1에서 3으로 이동했습니다.하노이 타워
  • 이제 디스크 2가 1에서 2로 이동했습니다.하노이 타워
  • 디스크 1이 3에서 2으로 이동했습니다.하노이 타워
  • 디스크 3이 1에서 3으로 이동했습니다.하노이 타워
  • 이제 디스크 1가 2에서 1로 이동했습니다.
  • 디스크 2이 2에서 3으로 이동했습니다.
  • 디스크 1이 1에서 3으로 이동했습니다.

따라서 n-1 개의 디스크를 두 번째 타워로, 마지막 디스크를 세 번째 타워로, n-1 개의 디스크를 첫 번째 디스크로 이동하여 이동을 완료합니다.

이제 우리는 재귀 동일한 구현.

하노이 타워 JAVA 프로그램

public class hanoi
{
  public static void hanoi(int n,char from,char mid,char to)
  {
    if(n==1)
    {
      //Moving disk1 on to the first rod
      System.out.println("Moving disk "+n+"From rod:"+from+"To Rod"+to);
      return;
    }
    //Moving n-1 disks to the second rod
    hanoi(n-1,from,to,mid);
    System.out.println("Moving disk "+n+"From rod:"+from+"To Rod"+to);
    //Moving the disks on top of already moved first disk
    hanoi(n-1,mid,from,to);
  }
  public static void main(String args[])
  {
    int n=3;
    hanoi(n,'A','B','C');
  }
}

하노이 타워를위한 C ++ 프로그램

#include<iostream>
using namespace std;
  void hanoi(int n,char from,char mid,char to)
  {
    if(n==1)
    {
      //Moving disk1 on to the first rod
      cout<<"Moving disk "<< n <<"From rod:"<< from <<" To Rod:"<< to <<endl;
      return;
    }
    //Moving n-1 disks to the second rod
    hanoi(n-1,from,to,mid);
    cout<<"Moving disk "<< n <<"From rod:"<< from <<" To Rod:"<< to <<endl;
    //Moving the disks on top of already moved first disk
    hanoi(n-1,mid,from,to);
  }
  int main()
  {
    int n=4;
    hanoi(n,'A','B','C');
  }
Moving disk 1From rod: A To Rod: B
Moving disk 2From rod:A To Rod:C
Moving disk 1From rod:B To Rod:C
Moving disk 3From rod: A To Rod: B
Moving disk 1From rod:C To Rod:A
Moving disk 2From rod:C To Rod:B
Moving disk 1From rod: A To Rod: B
Moving disk 4From rod:A To Rod:C
Moving disk 1From rod:B To Rod:C
Moving disk 2From rod: B To Rod: A
Moving disk 1From rod:C To Rod:A
Moving disk 3From rod:B To Rod:C
Moving disk 1From rod: A To Rod: B
Moving disk 2From rod:A To Rod:C
Moving disk 1From rod:B To Rod:C

하노이 타워 결론

따라서 우리는 결론에 도달합니다.

디스크 15 개에 대해 4 개 이동

디스크 31 개에 대해 5 개 이동

따라서 우리는 n 디스크 용 우리는 만들 필요가 있습니다 (2 ^ n) -1 이동.

2 disks=(2*2)-1=2 moves

3 disks=(2^3)-1=7 moves

4 disks=(2^4)-1=15 moves

등등.

하노이 타워의 복잡성 분석

시간 복잡성

재귀 방정식 :  T (n) = 2T (n-1) + 1

T (n) = O (2 ^ {(n + 1)}-1), 또는 다음과 같이 말할 수 있습니다. O (2 ^ n) 기하 급수적 인

공간 복잡성

T (n) = T (n-1) + k
T (0) = k
T (1) = 2k
T (2) = 3k
T (3) = 4k
따라서 공간 복잡성은 O (n)입니다.

참조

Translate »