Hanoi qalası

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Məlumat dəsti Fourkites MAQ
Bölün və fəth edin Riyaziyyat Recursion Məktəb Proqramlaşdırması QalaqBaxılıb 78

Hanoi qalası aşağıdakı şərtlərlə riyazi problemdir:

  • Üç qüllə var
  • N üzük sayı mövcud ola bilər
  • Üzüklər müxtəlif ölçülüdür
  • Hər dəfə yalnız bir disk köçürülə bilər
  • Hər hansı bir disk yalnız daha böyük bir diskin üstünə köçürülə bilər
  • Yalnız üst disk çıxarıla bilər

Izahat

İki diskimiz olduqda bu problemin necə həll olunacağına baxaq

Hanoi qalası izah edildiPin

Üst (kiçik) diski növbəti qüllənin üzərinə aparırıq, bundan sonra ikinci diski üçüncü qülləyə aparırıq və sonra ilk diski də üçüncü qülləyə keçiririk. (3 hamle)

Fərziyyə: Disklər əvvəlcə sıralanır

Eynilə 3 disklə işlədiyimiz zaman. Hamısını üçüncü halqaya keçirtmək üçün 7 addım lazımdır.

  • Disk 1 1-dən 3-ə keçdiHanoi qalası
  • İndi Disk 2 1-dən 2-yə keçdiHanoi qalası
  • Disk 1 3-dən 2-ə keçdiHanoi qalası
  • Disk 3 1-dən 3-ə keçdiHanoi qalası
  • İndi Disk 1 2-dən 1-yə keçdi
  • Disk 2 2-dən 3-ə keçdi
  • Disk 1 1-dən 3-ə keçdi

Beləliklə n-1 diskləri ikinci qülləyə, sonuncu disk üçüncü qülləyə və n-1 diskləri birinci disk üzərində hərəkət etdiririk, beləliklə növbəni tamamlayırıq.

İndi baxaq rekursiv eyni tətbiq.

Hanoi Tower Of JAVA Proqramı

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');
  }
}

Hanoi Tower Of C ++ Proqramı

#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

Hanoi Tower Of Nəticə

Beləliklə nəticəyə gəlirik:

15 disk üçün 4 hərəkət

31 disk üçün 5 hərəkət

Beləliklə, belə bir nəticəyə gəlirik n disk üçün etməliyik (2 ^ n) -1 hərəkət.

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

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

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

və s.

Hanoi Tower Of Mürəkkəblik Analizi

Zamanın mürəkkəbliyi

Rekursiv tənlik:  T (n) = 2T (n-1) + 1

T (n) = O (2 ^ {(n + 1)} - 1), yoxsa deyə bilərsən O (2 ^ n) eksponentdir

Kosmik Mürəkkəblik

T (n) = T (n-1) + k
T (0) = k
T (1) = 2k
T (2) = 3k
T (3) = 4k
Beləliklə, kosmik mürəkkəblik O (n) -dir.

References

Translate »