#include <stdio.h>


int mov_numero=0;  /* Vamos manter um contador 
                      para o número de movimentos */

/* solve: procedimento recursivo principal.  u_name, v_name e w_name
   são os nomes ('A', 'B' ou 'C') das torres.  Este procedimento imprime uma
   seqüência de movimentos que transfere _exatamente_ n_discos discos da torre
   u_name para a torre v_name. */
void solve(char u_name, char v_name, char w_name, int n_discos)
{
  if (n_discos==1) {
    ++mov_numero;
    printf("Movimento numero %d: %c -> %c\n", 
      mov_numero, u_name, v_name); 
  } else {
    solve(u_name, w_name, v_name, n_discos-1);
    ++mov_numero;
    printf("Movimento numero %d: %c -> %c\n", 
      mov_numero, u_name, v_name);
    solve(w_name, v_name, u_name, 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");

  solve('A', 'B', 'C', n);

  printf("\nNúmero total de movimentos: %d\n", mov_numero);

  return 0; /* termino normal */
}