Comment résoudre le problème de la tour de Hanoi - Un guide d'algorithme illustré

Avant de commencer, parlons de ce qu'est le problème de la tour de Hanoi. Eh bien, c'est un jeu de puzzle amusant où l'objectif est de déplacer une pile entière de disques de la position source à une autre position. Trois règles simples sont suivies:

  1. Un seul disque peut être déplacé à la fois.
  2. Chaque mouvement consiste à prendre le disque supérieur de l'une des piles et à le placer sur une autre pile. En d'autres termes, un disque ne peut être déplacé que s'il s'agit du disque le plus élevé d'une pile.
  3. Aucun disque plus grand ne peut être placé sur un disque plus petit.

Maintenant, essayons d'imaginer un scénario. Supposons que nous ayons une pile de trois disques. Notre travail consiste à déplacer cette pile de source A à destination C . Comment faisons-nous cela?

Avant de pouvoir y arriver, nous allons imaginer il y a un point B intermédiaire .

Nous pouvons utiliser B comme aide pour terminer ce travail. Nous sommes maintenant prêts à passer à autre chose. Passons en revue chacune des étapes:

  1. Déplacez le premier disque de A vers C
  2. Déplacez le premier disque de A vers B
  3. Déplacez le premier disque de C vers B
  4. Déplacez le premier disque de A vers C
  5. Déplacez le premier disque de B vers A
  6. Déplacez le premier disque de B vers C
  7. Déplacez le premier disque de A vers C

Boom! Nous avons résolu notre problème.

Vous pouvez voir l'image animée ci-dessus pour une meilleure compréhension.

Maintenant, essayons de construire l'algorithme pour résoudre le problème. Attendez, nous avons un nouveau mot ici: « Algorithme ». Qu'est-ce que c'est? Une idée? Pas de problème, voyons.

Qu'est-ce qu'un algorithme?

Un algorithme est l'un des concepts les plus importants pour un développeur de logiciels. En fait, je pense que ce n'est pas seulement important pour le développement ou la programmation de logiciels, mais pour tout le monde. Les algorithmes nous affectent dans notre vie quotidienne. Voyons comment.

Supposons que vous travaillez dans un bureau. Ainsi, chaque matin, vous effectuez une série de tâches dans une séquence: d'abord vous vous réveillez, puis vous allez aux toilettes, prenez le petit-déjeuner, préparez-vous pour le bureau, quittez la maison, puis vous pouvez prendre un taxi ou un bus ou commencer à marcher vers le bureau et, après un certain temps, vous atteignez votre bureau. Vous pouvez dire que toutes ces étapes forment un algorithme .

En termes simples, un algorithme est un ensemble de tâches. J'espère que vous n'avez pas oublié les étapes que nous avons suivies pour déplacer trois piles de disques de A à C. Vous pouvez également dire que ces étapes sont l'algorithme pour résoudre le problème de la tour de Hanoi.

En mathématiques et en informatique, un algorithme est une spécification sans ambiguïté de la manière de résoudre une classe de problèmes. Les algorithmes peuvent effectuer des tâches de calcul, de traitement de données et de raisonnement automatisé. - Wikipédia

Si vous jetez un œil à ces étapes, vous pouvez voir que nous faisions la même tâche plusieurs fois - déplacer des disques d'une pile à une autre. Nous pouvons appeler ces étapes à l'intérieur des étapes de récursivité .

Récursion

Récursionappelle la même action à partir de cette action. Tout comme l'image ci-dessus.

Il existe donc une règle pour tout travail récursif: il doit y avoir une condition pour arrêter l'exécution de cette action. J'espère que vous comprenez les bases de la récursivité.

Maintenant, essayons de construire une procédure qui nous aide à résoudre le problème de la tour de Hanoi. Nous essayons de construire la solution en utilisant un pseudocode . Le pseudocode est une méthode d'écriture de code informatique en anglais.

tower(disk, source, intermediate, destination) { }

Tel est le squelette de notre solution. Nous prenons le nombre total de disques comme argument. Ensuite, nous devons passer la source, le lieu intermédiaire et la destination afin que nous puissions comprendre la carte que nous utiliserons pour terminer le travail.

Nous devons maintenant trouver un état terminal . L'état terminal est l'état dans lequel nous n'allons plus appeler cette fonction.

IF disk is equal 1

Dans notre cas, ce serait notre état terminal. Parce que quand il y aura un disque dans notre pile, il est facile de faire cette dernière étape et après cela, notre tâche sera terminée. Ne vous inquiétez pas si ce n'est pas clair pour vous. Lorsque nous atteindrons la fin, ce concept sera plus clair.

D'accord, nous avons trouvé notre point d'état terminal où nous déplaçons notre disque vers la destination comme ceci:

move disk from source to destination

Maintenant, nous appelons à nouveau notre fonction en passant ces arguments. Dans ce cas, nous divisons la pile de disques en deux parties. Le plus grand disque ( nième disque) est dans une partie et tous les autres ( n-1 ) disques sont dans la seconde partie. Là, nous appelons la méthode deux fois pour - (n-1).

tower(disk - 1, source, destination, intermediate)

Comme nous l'avons dit, nous passons total_disks_on_stack - 1 comme argument. Et puis à nouveau nous déplaçons notre disque comme ceci:

move disk from source to destination

Après cela, nous appelons à nouveau notre méthode comme ceci:

tower(disk - 1, intermediate, source, destination)

Voyons notre pseudocode complet:

tower(disk, source, inter, dest) IF disk is equal 1, THEN move disk from source to destination ELSE tower(disk - 1, source, destination, intermediate) // Step 1 move disk from source to destination // Step 2 tower(disk - 1, intermediate, source, destination) // Step 3 END IF END

Voici l'arborescence de trois disques:

Voici le code complet en Ruby:

def tower(disk_numbers, source, auxilary, destination) if disk_numbers == 1 puts "#{source} -> #{destination}" return end tower(disk_numbers - 1, source, destination, auxilary) puts "#{source} -> #{destination}" tower(disk_numbers - 1, auxilary, source, destination) nil end

Appel tower(3, 'source','aux','dest')

Production:

source -> dest source -> aux dest -> aux source -> dest aux -> source aux -> dest source -> dest

Il a fallu sept étapes pour que trois disques atteignent la destination. Nous appelons cela une méthode récursive .

Calculs de complexité temporelle et de complexité spatiale

Complexité temporelle

Lorsque nous exécutons du code ou une application sur notre machine, cela prend du temps - des cycles CPU. Mais ce n'est pas la même chose pour tous les ordinateurs. Par exemple, le temps de traitement d'un core i7 et d'un dual core n'est pas le même. Pour résoudre ce problème, il existe un concept utilisé en informatique appelé complexité temporelle .

La complexité temporelle est un concept en informatique qui traite de la quantification du temps nécessaire à un ensemble de code ou d'algorithme pour traiter ou exécuter en fonction de la quantité d'entrée.

In other words, time complexity is essentially efficiency, or how long a program function takes to process a given input. — techopedia

The time complexity of algorithms is most commonly expressed using big O notation. It’s an asymptotic notation to represent the time complexity.

Now, the time required to move n disks is T(n). There are two recursive calls for (n-1). There is one constant time operation to move a disk from source to the destination, let this be m1. Therefore:

T(n) = 2T(n-1) + m1 ..... eq(1)

And

T(0) = m2, a constant ...... eq(2) From eq (1) T(1) = 2T(1-1) + m1 = 2T(0)+m1 = 2m2 + m1 ..... eq(3) [From eq 2] T(2) = 2T(2-1) + m1 = 2T(1) + m1 = 4m2 + 2m1 + m1 .... eq(4) [From eq(3)] T(3) = 2T(3-1) + m1 = 2T(2) + m1 = 8m2 + 4m1 + 2m1 + m1 [From eq(4)]

From these patterns — eq(2) to the last one — we can say that the time complexity of this algorithm is O(2^n) or O(a^n) where a is a constant greater than 1. So it has exponential time complexity. For the single increase in problem size, the time required is double the previous one. This is computationally very expensive. Most of the recursive programs take exponential time, and that is why it is very hard to write them iteratively.

Space complexity

After the explanation of time complexity analysis, I think you can guess now what this is…This is the calculation of space required in ram for running a code or application.

In our case, the space for the parameter for each call is independent of n,meaning it is constant. Let it be J. When we do the second recursive call, the first one is over. That means that we can reuse the space after finishing the first one. Hence:

T(n) = T(n-1) + k .... eq(1) T(0) = k, [constant] .... eq(2) T(1) = T(1-1) + k = T(0) + k = 2K T(2) = 3k T(3) = 4k

So the space complexity is O(n).

After these analyses, we can see that time complexity of this algorithm is exponential but space complexity is linear.

Conclusion

From this article, I hope you can now understand the Tower of Hanoi puzzle and how to solve it. Also, I tried to give you some basic understanding about algorithms, their importance, recursion, pseudocode, time complexity, and space complexity. If you want to learn these topics in detail, here are some well-known online courses links:

  1. Algorithms, Part I
  2. Algorithms, Part II
  3. The Google course on Udacity
  4. Javascript Algorithms And Data Structures Certification (300 hours)

You can visit my data structures and algorithms repoto see my other problems solutions.

I am on GitHub | Twitter | LinkedIn