![Imprimez toutes les sous-séquences en diminuant d’abord puis en augmentant en sélectionnant N/2 éléments de [1, N]](https://geektechnique.net/wp-content/uploads/2021/09/Imprimez-toutes-les-sous-sequences-en-diminuant-dabord-puis-en-augmentant.png)
Étant donné un entier positif N représentant le nombre de disques dans la tour de Hanoï, la tâche consiste à résoudre le Casse-tête Tour de Hanoï en utilisant des représentations binaires.
Exemples:
Saisir: N = 3
Sortir:
Déplacez le disque 1 à la prochaine tige circulaire droite
Déplacez le disque 2 à la prochaine tige circulaire droite
Déplacez le disque 1 à la prochaine tige circulaire droite
Déplacez le disque 3 vers la prochaine tige circulaire droite
Déplacez le disque 1 à la prochaine tige circulaire droite
Déplacez le disque 2 à la prochaine tige circulaire droite
Déplacez le disque 1 à la prochaine tige circulaire droite
Saisir: N = 4
Sortir:
Déplacez le disque 1 à la prochaine tige circulaire droite
Déplacez le disque 2 à la prochaine tige circulaire droite
Déplacez le disque 1 à la prochaine tige circulaire droite
Déplacez le disque 3 vers la prochaine tige circulaire droite
Déplacez le disque 1 à la prochaine tige circulaire droite
Déplacez le disque 2 à la prochaine tige circulaire droite
Déplacez le disque 1 à la prochaine tige circulaire droite
Déplacez le disque 4 à la prochaine tige circulaire droite
Déplacez le disque 1 à la prochaine tige circulaire droite
Déplacez le disque 2 à la prochaine tige circulaire droite
Déplacez le disque 1 à la prochaine tige circulaire droite
Déplacez le disque 3 vers la prochaine tige circulaire droite
Déplacez le disque 1 à la prochaine tige circulaire droite
Déplacez le disque 2 à la prochaine tige circulaire droite
Déplacez le disque 1 à la prochaine tige circulaire droite
Approcher: Le problème donné peut être résolu sur la base des observations suivantes :
- On peut remarquer que pour déplacer le Nième disque, (N – 1)èmele disque doit être déplacé. Par conséquent, pour déplacer (N – 1)ème disque, (N – 2)èmele disque doit être déplacé. Ce processus se poursuit de manière récursive.
- La procédure ci-dessus est similaire à la définition du bit non défini le plus à droite car elle nécessite de définir d’abord tous les bits à sa droite.
- Par conséquent, l’idée est d’imprimer toutes les étapes intermédiaires, en définissant à chaque fois le bit le plus à droite en incrémentant le nombre actuel de 1.
Suivez les étapes ci-dessous pour résoudre le problème :
Vous trouverez ci-dessous la mise en œuvre de l’approche ci-dessus :
C++
|
#include en utilisant l’espace de noms std ; int incrément(int* compteur, int n) { entier je = 0; tandis que (vrai) { int a = compteur[i] ^ 1; int b = compteur[i] & 1; contrer[i] = un; si (b == 0) Pause; je = je + 1 ; } retourner je; } void TowerOfHanoi(int N) { compteur int[N] = { 0 } ; pour (pas int = 1 ; pas <= pow(2, N) - 1 ; étape++) { int x = incrément (compteur, N) + 1 ; cout << "Déplacer le disque" << x << " à la prochaine circulaire" << " barre droite n"; } } int main() { entier N = 3; TowerOfHanoi(N); renvoie 0 ; } |
Java
|
importer java.util.*; classe GFG{ incrément int statique(int[] compteur, entier n) { entier je = 0; tandis que (vrai) { int a = compteur[i] ^ 1; int b = compteur[i] & 1; contrer[i] = un; si (b == 0) Pause; je = je + 1 ; } retourner je; } static void TowerOfHanoi(int N) { entier[] compteur=nouvel entier[N]; for(int step = 1; pas <= Math.pow(2, N) - 1 ; étape++) { int x = incrément (compteur, N) + 1 ; System.out.println(« Déplacer le disque » + x + » à la prochaine circulaire » + « tige droite »); } } public static void main(String[] arguments) { entier N = 3; TowerOfHanoi(N); } } |
Python3
|
importer des mathématiques def incrément (compteur, n): je = 0 tandis que (Vrai): a = compteur[i] ^ 1 b = compteur[i] & 1 contrer[i] = un si (b == 0) : Pause je = je + 1 je reviens def TowerOfHanoi(N): compteur=[0 for i in range(N)] pour le pas dans range(1,int(math.pow(2,N))): x = incrément (compteur, N) + 1 print(« Déplacer le disque « ,x, » vers la prochaine circulaire », » tige de droite ») N = 3 TowerOfHanoi(N) |
C#
|
en utilisant le système ; classe GFG { incrément int statique(int[] compteur, entier n) { entier je = 0; tandis que (vrai) { int a = compteur[i] ^ 1; int b = compteur[i] & 1; contrer[i] = un; si (b == 0) Pause; je = je + 1 ; } retourner je; } static void TowerOfHanoi(int N) { entier[] compteur = nouvel entier[N]; pour (pas int = 1 ; step <= (int)(Math.Pow(2, N) - 1); étape++) { int x = incrément (compteur, N) + 1 ; Console.WriteLine(« Déplacer le disque » + x + » à la prochaine circulaire » + » tige droite « ); } } public statique vide Main() { entier N = 3; TowerOfHanoi(N); } } |
Javascript
Sortir: Déplacer le disque 1 vers la tige circulaire droite suivante Déplacer le disque 2 vers la tige circulaire droite suivante Déplacer le disque 1 vers la tige circulaire droite suivante Déplacer le disque 3 vers la tige circulaire droite suivante Déplacer le disque 1 vers la tige circulaire droite suivante Déplacer le disque 2 vers la tige circulaire droite suivante Déplacer le disque 1 à la prochaine tige circulaire droite
Complexité temporelle : O(N * 2N)
Espace auxiliaire : AU)
Approche efficace : L’approche ci-dessus peut être optimisée sur la base des observations que pour M sur toute la gamme [1, 2N – 1], tige source est égal à (h & (m – 1)) % 3 et la tige de destination est égale à (m | (m – 1) + 1) % 3. Par conséquent, l’idée est d’itérer sur la plage [1, 2N – 1] et imprimer la valeur de (je & (je – 1))%3 comme tige source et (i | (i – 1) + 1)%3 comme tige de destination.
Vous trouverez ci-dessous la mise en œuvre de l’approche ci-dessus :
C++
|
#include en utilisant l’espace de noms std ; void TowerOfHanoi(int N) { pour (entier x = 1; x <= pow(2, N) - 1 ; x++) { cout << " Déplacer de Rod " << ((x & x - 1) % 3 + 1) << " à Rod " << (((x | x - 1) + 1) % 3 + 1) << finl; } } int main() { entier N = 3; TowerOfHanoi(N); renvoie 0 ; } |
Java
|
classe GFG{ static void TowerOfHanoi(int N) { pour(entier x = 1; x <= Math.pow(2, N) - 1 ; x++) { System.out.print(« Déplacer de Rod » + ((x & x – 1) % 3 + 1) + » à la tige » + (((x | x – 1) + 1) % 3 + 1) + « n »); } } public static void main (String[] arguments) { entier N = 3; TowerOfHanoi(N); } } |
Python3
|
importer des mathématiques def TowerOfHanoi(N): pour x dans range(1,int(math.pow(2, N)) ): print(« Déplacer de Rod » , ((x & x – 1) % 3 + 1) , » à Rod » , (((x | x – 1) + 1) % 3 + 1) ) N=3 TowerOfHanoi(N) |
C#
|
en utilisant le système ; classe GFG{ static void TowerOfHanoi(int N) { pour(entier x = 1; x <= Math.Pow(2, N) - 1 ; x++) { Console.Write(« Déplacer de Rod » + ((x & x – 1) % 3 + 1) + » à la tige » + (((x | x – 1) + 1) % 3 + 1) + « n »); } } vide statique Main() { entier N = 3; TowerOfHanoi(N); } } |
![Imprimez toutes les sous-séquences en diminuant d’abord puis en augmentant en sélectionnant N/2 éléments de [1, N]](https://geektechnique.net/wp-content/uploads/2021/09/Imprimez-toutes-les-sous-sequences-en-diminuant-dabord-puis-en-augmentant-75x75.png)
