#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#define TAM 1000

main(){
int opcion;
void ejemplo1(), ejemplo2(), ejemplo3();

do {
  printf ("\nPrograma de ejemplo.\n");
  printf ("\t1. Tiempo y espacio.\n\t2. Eficiencia.\n\t3. Tamagno\n");
  printf ("Escoge una opcion (0 termina):");
  do 
    scanf ("%d", &opcion); 
  while (opcion <0 || opcion > 3);
  
  switch (opcion) {
  case 1: 
	  ejemplo1();	  
	  break;
  case 2: 
	  ejemplo2(); 
	  break;
  case 3:
	  ejemplo3();
  };
} while (opcion != 0);
}

void ejemplo1(){
int op, i;
long int datos[TAM], tam;
char seguir = 's';
clock_t clock(), t;

do {
	printf ("\nGeneracion de x datos aleatorios. Máximo %d ¿Cuantos? ", TAM);
	do {
		scanf ("%d", &tam);
	}while (tam < 0 || tam > TAM);
	
	printf("\nGeneraré %d datos.\n\t1. Sin mostrarlos.\n\t2. Mostrandolos.\n", tam);
	
    do {
	  scanf ("%d", &op); 
	} while (op != 1 && op != 2);
	t = clock();
	for (i=0; i< tam; i++) {
      datos[i] = rand();
     if (op == 2) {
	   printf ("%8ld", datos[i]);
	   if (i % 9 == 0) printf ("\n");
	 }
	};
	t = clock() - t;
  printf("\nTiempo transcurrido en ciclos de instruccion: %ld, para %ld elementos\n",t, tam); 
  
  printf ("\n¿Quieres seguir (s/n)?");   
  do scanf("%c", &seguir); while (seguir == '\n');
} while (seguir == 's') ;
}

void ejemplo3(){
clock_t t;
unsigned long int fibo_i(long int ), fibo_r(unsigned long int);

unsigned long int n, res;

printf ("\nIntroduce el termino de la serie de fibonacci a buscar (max. 40):\n");
scanf ("%d", &n);

do {
  t = clock();
  res = fibo_i(n);
  t = clock() - t;
  printf ("\nEl %ld termino es %ld", n, res);
  printf("\nTiempo de procesador transcurrido con version iterativa: %ld\n", (long int ) t);
  t = clock();
  res = fibo_r(n);
  t = clock() - t;
  printf ("\nEl %ld termino es %ld", n, res);
  printf("\nTiempo de procesador transcurrido con version recursiva: %ld\n", (long int )t);

  printf ("\nIntroduce el termino de la serie a buscar (0 termina)\n");
  scanf ("%d", &n);
} while (n);
}

unsigned long int fibo_i (long int n) {
 long int ant1, ant2, res; 
 int i;

 ant1 = 0;
 ant2 = 1;
 if (n == 1) return ant1;
 else {
   if (n == 2) return ant2;
   else {
    i = 2;
	while (i <= n) {
      res = ant1 + ant2;
	  ant2 = ant1;
	  ant1 = res;
      i++;
	}
   }
 }
 return res;
}


unsigned long int fibo_r (unsigned long int n) {
	if (n == 1) return 0;
	else 
		if(n == 2) return 1;
	    else 
			return (fibo_r (n-1) + fibo_r (n-2));
}


#define TAM2 2000
int busqueda_secuencial(int *, int, int*);
int busqueda_binaria(int *, int, int *);

void ejemplo2(){
clock_t clock(), t; 

int i, pos, iter;
int datos[TAM2], x;

/* Obtención de datos ordenados para un vector de TAM2 elementos */
for (i=0; i<TAM2; i++) {
  datos[i] = 2*i+1;
  /* printf ("%ld\n", datos[i]); */
}

/* Búsqueda secuencial o dicotomica de un elemento */

do {
  printf ("\n Busqueda de un elemento en un vector. 0 termina\n");
  printf ("\nDame un numero entre %d y %d\n", 1, 2*TAM2+1); 
  scanf ("%ld", &x);

  t = clock();
  pos = busqueda_secuencial (datos, x, &iter); 
  t = (clock() - t);

  if (pos >= 0) 
    printf("\n%d esta en la posicion %d\n", x, pos);
  else
    printf("\n%d no esta en el vector\n", x);

  printf("\nTiempo de procesador transcurrido con busqueda secuencial: %ld, tras %ld iteraciones \n",t, iter);

  t = clock();

  pos = busqueda_binaria (datos, x, &iter); 
  t = clock() - t;

  if (pos >= 0) 
    printf("\n%d esta en la posicion %d\n", x, pos);
  else
    printf("\n%d no esta en el vector\n", x);

  printf("\nTiempo de procesador transcurrido con busqueda dicotomica: %ld, tras %ld iteraciones \n", t, iter);
} while (x != 0); 

}

int busqueda_secuencial (v, x, iteraciones)
int v[TAM2], x;
int *iteraciones;
{
int p, encontrado;

p=0; 
encontrado = 0;
*iteraciones = 0;

while (! encontrado && p < TAM2) {
	if (v[p] == x) 
		encontrado = 1;
    else
		p++;

	*iteraciones = *iteraciones + 1;
}
	
if (encontrado) return p; else return -p;
}

int busqueda_binaria (v, x, iteraciones)
int v[TAM2], x;
int *iteraciones;
{
int inf, sup, encontrado;
int med;

inf = 0;
sup = TAM2 - 1;
encontrado = 0;
*iteraciones = 0;

while ((inf != sup) && !encontrado) {
  med = (inf + sup)/2;
  printf ("\nAnalizo inf=%d, sup=%d, med=%d, x=%d y v[med]=%d", inf, sup, med, x, v[med]);
  if (x == v[med]) {
	  encontrado = 1;
	  inf = sup = med;
  }
  else
    if (x > v[med])  
		inf = med + 1;		  
	  else 
	    sup = med;
  *iteraciones= *iteraciones + 1;
}
if (encontrado) 
  return med; 
else 
  if (v[inf] == x) 
	  return inf; 
  else 
	  return -inf;
}