#include <stdio.h>

/* Os vetores que representam as torres terao no máximo 50 discos */
#define MAXN 50

int mov_numero=0;  /* Vamos manter um contador 
                      para o número de movimentos */
int a[MAXN], b[MAXN], c[MAXN];  /* Vetores com os discos */
int topo_a=-1, topo_b=-1, topo_c=-1; /* Posição do disco do topo */

/* imprima_situação: rotina que imprime o conteúdo das torres, 
   isto é, vetores */  
void imprima_situacao()
{
  int i;
  printf("\n  A: ");
  for (i=0; i<=topo_a; i++)
    printf(" %d", a[i]);
  printf("\n  B: ");
  for (i=0; i<=topo_b; i++)
    printf(" %d", b[i]);
  printf("\n  C: ");
  for (i=0; i<=topo_c; i++)
    printf(" %d", c[i]);
  printf("\n");
}

/* monte_config_inicial: a configuração inicial é com os discos na */
/* torre A.  Isto é um pouco não-intuitivo, mas o maior disco se */
/* chama 0, o segundo 1, etc (provavelmente isto não deveria ser */
/* assim.  */
void monte_config_inicial(int n)
{
  int i;
  for (i=0; i<n; i++)
    a[i]=i;
  topo_a=n-1;
}

/* solve: procedimento recursivo principal.  Os vetores u, v e w */
/* representam as torres; topo_u, topo_v e topo_w são os índices dos */
/* discos nos topos destas torres; u_nome, v_nome e w_nome são os nomes */
/* ('A', 'B' ou 'C') das torres representadas pelos vetores u, v e w. */
/* Este procedimento transfere _exatamente_ n_discos discos da torre */
/* representada por u para a torre representada por v. */
void solve(int u[], int *topo_u, char u_nome, 
           int v[], int *topo_v, char v_nome, 
           int w[], int *topo_w, char w_nome,
	   int n_discos)
{
  if (n_discos==1) {
    ++(*topo_v);
    v[*topo_v]=u[*topo_u];
    --(*topo_u);
    ++mov_numero;
    printf("\nMovimento numero %d: disco %d, %c -> %c\n", 
      mov_numero, v[*topo_v], u_nome, v_nome);
    imprima_situacao();
  } else {
    solve(u, topo_u, u_nome, w, topo_w, w_nome, v, topo_v, v_nome, n_discos-1);
    ++(*topo_v); 
    v[*topo_v]=u[*topo_u];
    (*topo_u)--;
    ++mov_numero;
    printf("\nMovimento numero %d: disco %d, %c -> %c\n", 
      mov_numero, v[*topo_v], u_nome, v_nome);
    imprima_situacao();
    solve(w, topo_w, w_nome, v, topo_v, v_nome, u, topo_u, u_nome, n_discos-1);
  }
}

/* Programa principal... auto-explicativo */
main()
{
  int n; /* numero de discos */

  printf("Qual é o numero de discos? ");
  scanf("%d", &n);
  printf("Aqui está uma solução:\n");

  monte_config_inicial(n);
  printf("\nSituação inicial:\n");
  imprima_situacao();
  solve(a, &topo_a, 'A', b, &topo_b, 'B', c, &topo_c, 'C', n);
  printf("\nSituação final (número total de movimentos = %d):\n", 
    mov_numero); 
  imprima_situacao();

  return 0; /* termino normal */
}