#include <stdio.h>

long unsigned fatorial(long unsigned n){
  if(n == 0){
    return 1;
  }
  return n * fatorial(n-1);
}

//Funcao para imprimir or movimentos para
//levar n discos de ini ateh dest, usando 
//aux para ajudar.
void hanoi(int n, int ini, int dest, int aux){
  if(n == 1){
    printf("Mova disco %d, de Torre %d para Torre %d\n", n, ini, dest);
    return;
  }
  //mover os n-1 de ini ateh aux, posso usar dest como auxiliar
  hanoi(n-1, ini, aux, dest);
  //mover o disco grande de ini ateh dest
  printf("Mova disco %d, de Torre %d para Torre %d\n", n, ini, dest);
  //mover os n-1 discos de aux ate dest, posso ini como auxiliar
  hanoi(n-1, aux, dest, ini);
  return;
}



int encontra(int V[], int n, int x){
  for(int i = 0; i < n; i++){
    if(V[i] == x) return 1;
  }
  return 0;
}

//encontra x em um vetor ORDENADO V
int encontra2(int V[], int n, int x){
  for(int i = 0; i < n; i++){
    if(V[i] == x) return 1;
    if(V[i] > x) return 0;
  }
  return 0;
}

//encontra x em nas posicoes de ini a fim 
//de um vetor ORDENADO 
int busca_binaria(int *V, int ini, int fim, int x){
  if(fim < ini){
    //Vetor vazio
    return 0;
  }

  int meio = (ini+fim) / 2;
  
  if(V[meio] == x) return 1;
  if(V[meio] > x) return busca_binaria(V, ini, meio - 1, x);
  if(V[meio] < x) return busca_binaria(V, meio + 1, fim, x);
  return 0;
} 

int main(int argc, char * argv[]){
  //Recursao para fatorial
  printf("5! = %ld\n", fatorial(5));
  printf("10! = %ld\n", fatorial(10));


  //Torre de hanoi
  hanoi(4, 1, 3, 2);
  
  
  //Busca binaria
  int V[] = { 50, 52, 56, 60, 61, 67, 70, 91};
  int x = 57;
  
  printf("encontrou? %d\n", encontra(V, 8, x));
  
  printf("encontrou 57? %d\n", busca_binaria(V, 0, 7, 57));
  printf("encontrou 50? %d\n", busca_binaria(V, 0, 7, 50));
  printf("encontrou 91? %d\n", busca_binaria(V, 0, 7, 91));
  printf("encontrou 120? %d\n", busca_binaria(V, 0, 7, 120));

  return 0;
}