Hanoi qalası

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

Mündəricat

Izahat

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

Ü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çdi
İndi Disk 2 1-dən 2-yə keçdi
Disk 1 3-dən 2-ə keçdi
Disk 3 1-dən 3-ə keçdi
İ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