Tower of Hanoi Divide Et Impera

Hanoi.java

import java.util.Scanner;
//Turnurile din Hanoi (DIVIDE ET IMPERA)


/*

Problema:

Se dau 3 tije simbolizate a, b, c.

Pe tija a se gasesc discuri cu dimetre diferite, asezate in ordine descrescatoare a diametrelor
privite de jos in sus. 

Se cere sa se mute discurile de pe tija a pe tija b, utilizand ca tija intermediara tija c

respectand urmatoarele reguli:

- la fiecare pas se muta un singur DISC

- nu este permis sa se aseze un disc cu diametrul mai mare peste un disc cu diametru mai mic

- daca n = 1, se face mutare ab, adica se muta discul de pe tija a pe tija b

- daca n = 2, se fac mutarile AC, AB, CB


      |        |            |
      |        |            | 
      |        |            |
      ==       |            |
    ======     |            |
      |        |            |
      a        b            c 


in cazul in care n > 2, problema se complica..


Notam cu H(n, a, b, c) sirul mutarilor celor n discuri de pe tija a pe tija b, utilizand tija intermediara c

Conform strategiei DIVIDE ET IMPERA , incercam sa descompunem problema in alte doua subproblem de acelasi tip, urmand apoi 

combinarea solutiilor. In acest sens, observam ca mutarea celor n discuri de pe dija a pe tija b, utilizand tija

intermediara c, este echivalent cu:

- mutarea a n-1 discuri de pe tija a , pe tija c, utilizand tija intemediara b

- mutarea discului ramans pe tija b

- mutarea a n-1 discuri de pe tija c , pe tija b , utilizand tija intermediara a

Parcurgerea celor 3 etape permite definirea recursiva a sirului H(n,a,b,c)


                  ab, ,,,,daca n = 1  
H(n, a, b, c) =

                  H(n-1, a, c, b), ab, H(n-1, c, b, a) pentru n > 1



pentru n = 2, avem: H(2, a, b, c) = H(1, a, c, b), ab, H(1, c, b, a) = ac, ab, cb;

pentru n = 3, avem H(3, a, b, c) = H(2, a, c, b), ab, H(2, c, b, a) = H(1, a, b, c), ac, H(1, b, c, a), ab, H(1, c, a, b), cb, H(1, a, b, c) = 

ab, ac, bc, ab, ca, cb, ab

//2^n - 1 = (1<<n)-1 
//0000 00001 << 1
//0000 10000 

64 discuri 

2^64 -1 = mutari

0000 00001

*/

public class Hanoi {
                                         //a          b                 c  
         static void hanoi(int n, char source, char destination, char aux) {


         	     if(n == 1) 
         	     {

         	     	System.out.println(source + " " + destination);

         	     } else {


                    hanoi(n-1, source, aux, destination);
                    System.out.println(source + " " + destination);
                    hanoi(n-1, aux, destination, source);

         	     }
         }

         public static void main(String[] args) {

                Scanner scanner = new Scanner(System.in);

                char a = 'a', b = 'b', c = 'c';

                int n = scanner.nextInt();

                System.out.println((1<<n)-1);

                hanoi(n, a, b, c);
         }

}