Archivo

Entradas Etiquetadas ‘numeros’

Algoritmos: generar números aleatorios para la lotería

Lunes, 9 de Abril de 2012 Gaspar Fernández Sin comentarios

Es un ejemplo típico y nos muestra el uso de rand() con arrays para generar varios números aleatorios y no repetidos.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
/**
*************************************************************
* @file loteria.c
* @brief Saca números aleatorios para la lotería
* Basado en el sorteo de la primitiva, hay que sacar 7 números
* del 1 al 49, sin repetir
*
* @author Gaspar Fernández <blakeyed@totaki.com>
* http://totaki.com/poesiabinaria/algoritmos/
*************************************************************/

#include <stdlib.h>
#include <stdio.h>
#include <time.h>       /* para time() */


int numero_aleatorio(int desde, int hasta)
{
  return desde+rand()%(hasta-desde+1);
}

short numero_repetido(int numeros[7], int n)
{
  int i=0;

  while (i<n)
    {
      /* Si un número sacado anteriormente es igual al número
         en la posición n, decidido, está repetido. */
      if (numeros[i]==numeros[n])
    return 1;
      i++;
    }

  /* Si llegamos hasta aquí, el número no se ha repetido */
  return 0;
}

void numeros_loteria(int numeros[7])
{
  int i;

  /* El primer número lo generamos, este no se repetirá con nadie
     anterior */
  numeros[0]=numero_aleatorio(1, 49);

  /* A partir del segundo número tenemos que verificar que no se
     repite. */
  for (i=1; i<7; i++)
    {
      do
    {
      /* Generamos un número */
      numeros[i]=numero_aleatorio(1,49);
      /* Si el número está repetido, volvemos a generar */
    } while (numero_repetido(numeros, i));
    }
}

int main(int argc, char *argv[])
{
  int numeros_premiados[7];
  int i;
  srand(time(NULL));        /* Una nueva semilla de números aleatorios */

  numeros_loteria(numeros_premiados);
  for (i=0; i<7; i++)
    printf ("Numero %d -> %d\n", i+1, numeros_premiados[i]);
 
  return EXIT_SUCCESS;
}

Descargar: loteria.c (1.6Kb)

En este ejemplo vamos guardando todos los números en un array y vamos comparando los nuevos números que vamos generando con los antiguos.

Categories: C/C++, Clases particulares, algoritmos Tags: , , , , , , , ,

Números grandes en C usando GMP. Resolución del primer reto de #tuentiContest (Super Hard Sum)

Viernes, 24 de Junio de 2011 Gaspar Fernández Sin comentarios

Aquí llega mi primera aportación a las soluciones de los retos del I concurso de programación de Tuenti. La utilización de números grandes es algo que siempre me llamó la atención, y normalmente utilizo bc cuando necesito algún cálculo. Este reto se podía resolver con bash/sed/bc y, aunque varios lenguajes permiten la utilización de números de precisión arbitraria “de serie”  como python y Java, yo decidí hacerlo en C, utilizando la biblioteca GMP.

En un lenguaje como C, es normal que no podamos utilizar números de precisión arbitraria con los operadores normales (+, -, *,…), en este caso tendremos que hacer llamadas a funciones de la biblioteca para realizar las operaciones, tampoco podremos utilizar un printf() normal para mostrarlos.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
/**
*************************************************************
* @file hardsum.c
* @brief Tuenti Contest Test Phase
* Sum numbers separated by space line by line
*
* @author Gaspar Fernández <blakeyed@totaki.com>
* @version 0.0.2
* @date 12 jun 2011
*
* http://totaki.com/poesiabinaria
*
*************************************************************/

#include <stdio.h>
#include <string.h>
#include <gmp.h>

/* Huge string */
#define STRSIZE 1000

int main()
{
  char bigstr[STRSIZE];
  mpz_t tmp, sum;
  char * token;

  /* Initialize gmp numbers */
  mpz_init(tmp);
  mpz_init(sum);
 
  /* Read until EOF in stdin */
  while (fgets(bigstr, STRSIZE, stdin)!=NULL)
    {
      /* reset sum */
      mpz_set_si(sum, 0);
      token=strtok(bigstr, " \n");
      while (token!=NULL)
        {
          gmp_sscanf(token, "%Zd", &tmp); /* Extract number from token string */
          mpz_add(sum, sum, tmp);         /* Adds numbers */
          token=strtok(NULL, " \n");
        }
      gmp_printf("%Zd\n", sum);
    }

   return 0;
}

Para compilar, debemos incluir gmp:

$ gcc -o hardsum hardsum.c -lgmp

Para utilizar este tipo de variables numéricas, primero tendremos que inicializarlas con mpz_init(), otras funciones interesantes son:

  • mpz_set_si(): inicializa el número con un valor entero.
  • gmp_sscanf(): igual que scanf(), pero con la posibilidad de utilizar estas nuevas variables.
  • mpz_add(): realiza la suma de dos números
  • gmp_printf(): igual que printf(), pero con la posibilidad de utilizar estas nuevas variables.

GMP tiene muchísimas funciones para realizar gran cantidad de operaciones, se puede consultar la documentación aquí.

Categories: C/C++ Tags: , , , , , , , , , , , , ,

Recopilación de soluciones para los retos de #tuentiContest . Challenge #1

Miércoles, 22 de Junio de 2011 Gaspar Fernández 5 comentarios

Últimamente he hablado acerca del I concurso de programación de Tuenti. Un concurso de programación Online que se llevó acabo durante la semana pasada (del 13 al 20 de Junio, muy mala fecha).

Podéis ver los enunciados de todos los problemas, con ejemplos sobre la entrada y salida (aunque a veces no hay que haerles mucho caso) en la web oficial del concurso, pero en Vidas Concurrentes lo encontramos todo en español.

Challenge #1 : Super Hard Sum

Recibimos por la entrada estándar una serie de números separados por espacios, y nosotros debemos sumarlos. Eso sí, a veces nos podemos encontrar muchos espacios, ceros a la izquierda o números excesivamente grandes (tipo 9999999999999999999 , diecinueve nueves, necesitamos 64bit, aunque también puede venir negativo, resultando un número de 65bit.)

Soluciones:

Si no estás en la lista y quieres plantear tu solución, deja un comentario con tu link !

Actualización: 2011/06/22 11:45 : Añadidas soluciones de Rodrigo Díaz
Actualización: 2011/06/22 13:20 : Arreglada la autoría de las soluciones de @brok3r. Link a @manufloresv
Actualización: 2011/06/22 19:45 : Añadida solución en ensamblador por ThD
Actualización: 2011/06/22 20:00 : Añadida solución de @Puigcerber
Actualización: 2011/06/24 11:35 : Añadida mi solución.
Actualización: 2011/06/27 22:30 : Añadida solución de @theom3ga
Actualización: 2011/07/02 22:30 : Añadida solución de @frisco82
Actualización: 2011/07/03 13:30 : Añadida solución de @Rosapolis

Categories: #tuentiContest, Bash, C/C++, General, Linux, PHP Tags: , , , , , , , ,

Fibonacci recursivo en C [ intentemos no repetir operaciones! ]

Lunes, 21 de Junio de 2010 Gaspar Fernández Sin comentarios

fibo
Es un ejercicio muy típico cuando se está aprendiendo con funciones recursivas es la sucesión de Fibonacci, aquella en la que F(n)=F(n-1)+F(n-2).
Aunque esta técnica podemos (y deberíamos) utilizarla para una gran cantidad de algoritmos. A veces es necesario sacrificar un poco la memoria del sistema (sin pasarnos) para agilizar y hacer más rápido el programa. Debemos adoptar una solución que beneficie al usuario, no es plan de dejarlo sin memoria, pero tampoco es plan de que la solución se eternice.

Una primera implementación puede ser la siguiente:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int fibonacci_simple(int n)
{
  /* La función normal, recursiva */
  if (n>2)
    return fibonacci_simple(n-1) + fibonacci_simple(n-2);
  /* Este es el caso más común,  */
  else if (n==2)        /* Ponemos esto para agilizar un poco el proceso */
    return 1;
  else if (n==1)       
    return 1;
  else if (n==0)
    return 0;
  else
    return -1;          /* Error */
}

Si creamos un programa de ejemplo como este:

1
2
3
4
5
6
7
8
9
10
int main(int argc, char *argv[])
{
    unsigned int numero;

    /* Generamos Fibonaccis */
    for (numero=0; numero<48; numero++)
      printf("%u\n", fibonacci_simple(numero));

    return 0;
}

Podemos observar que para generar la secuencia de 48 números (he escogido este valor, porque a partir de ahí no tenemos suficiente de 32bits para almacenar el valor obtenido), tardamos varios minutos, en concreto, en mi equipo (Pentium M 1.73MHz), echó algo más de 10 minutos. ¡ 10 minutos ! Es un buen rato para lo que ha hecho.
Si lo estudiamos detenidamente (en negrita pongo las veces que llamamos a fibonacci_simple() sin necesidad):

  • fibonacci_simple(0)
  • fibonacci_simple(1)
  • fibonacci_simple(2)
  • fibonacci_simple(3) (que llama a fibonacci_simple(2) y fibonacci_simple(1) )
  • fibonacci_simple(4) (que llama a fibonacci_simple(3) ( que llama a fibonacci_simple(2) y fibonacci_simple(1) ) y a fibonacci_simple(2) )
  • fibonacci_simple(5) (que llama a fibonacci_simple(4) ( que llama a fibonacci_simple(3) ( que llama a fibonacci_simple(2) y fibonacci_simple(1) ) y a fibonacci_simple(2) ) y a fibonacci_simple(3) ( que llama a fibonacci_simple(2) y fibonacci_simple(1) )

Yo creo que con esto nos hacemos una idea de lo que quiero decir, se repiten demasiadas operaciones, seguro que hay alguna forma de solucionar esto.

Propongo lo siguiente:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
int fibonacci_buffer(int n)
{
  static int *fbuffer=NULL; /* Buffer */
  static int bufsize=0; /* Tamaño de buffer */
  int n3;           /* n-2 */
  int i;            /* Recorre buffers */

  if (n>2)
    {
      n3=n-2;
      if (fbuffer==NULL)
    {
      fbuffer = (int*) malloc((n3 * sizeof(int)));
      for (i=0; i<n3; i++)
        fbuffer[i]=0;   /* Ponemos buffer a 0 */

/*    printf("Creo buffer: %d -- %d\n", n3*sizeof(int), errno); */

      bufsize=n3;
    }
      else if (bufsize<n3)
    {
      fbuffer = (int*) realloc(fbuffer, n3 * sizeof(int));
/*    printf("Amplio buffer\n"); */

      for (i=bufsize; i<n3; i++) /* Ponemos a 0 la memoria nueva */
        fbuffer[i]=0;

      bufsize=n3;
    }
/*       printf("-%d--%d\n", n, fbuffer[n3-1]); */
      if (fbuffer[n3-1]!=0) /* Si se encuentra el fibonacci del número que buscamos  */
    return fbuffer[n3-1];   /* en memoria, lo devolvemos directamente */
      else
    {
      /* Si el fibonacci no se encuentra, vamos a generarlo */
      fbuffer[n3-1] = fibonacci_buffer(n-1) + fibonacci_buffer(n-2);
      //      printf("He generado con éxito fbuffer[%d]\n", n3-1);
      return fbuffer[n3-1];
    }

/*       return fibonacci_simple(n-1) + fibonacci_simple(n-2); */
    }
  else if (n==2)        /* Ponemos esto para agilizar un poco el proceso */
    return 1;
  else if (n==1)
    return 1;
  else if (n==0)
    return 0;
  else if (n==-1)       /* Un caso nuevo n==-1 */
    free(fbuffer);      /* Liberamos memoria */

  return -1;            /* Error */
}

Es algo más enrevesado, ya que usamos variables estáticas (podríamos hacer variables globales, con cuidado), así evitamos que la información que vamos almacenando se pierda entre ejecuciones de la función; por otra parte, utilizamos malloc() y realloc() para reservar sólo la memoria que vamos necesitando.
Por otra parte para reducir la memoria utilizada, hacemos que fibonacci(3) se almacene en la posición 0 del buffer (porque el de 2, 1 y 0, ya nos los sabemos); por otra parte… la variable n3 vale n-2; esto es simplemente porque si tenemos que calcular fibonacci(5), y sabemos que fibonacci(3) está almacenado en fbuffer[0], fibonacci(4) estará en fbuffer[1] y fibonacci(5) estará en fbuffer[2]; es decir tenemos que almacenar 3 valores de fibonacci (5-2=3).
Por otra parte, siempre que reservamos memoria ponemos los nuevos espacios a 0, ya que comprobamos que no hay ningún valor almacenado si éstos son 0.

Con el almacén de los números conseguimos que el esquema anterior se quede en:

  • fibonacci_buffer(0)
  • fibonacci_buffer(1)
  • fibonacci_buffer(2)
  • fibonacci_buffer(3) (que llama a fibonacci_buffer(2) y fibonacci_buffer(1)
  • fibonacci_buffer(4) (que llama a fibonacci_buffer(3) ( que saca el valor del buffer ) y a fibonacci_simple(2) )
  • fibonacci_buffer(5) (que llama a fibonacci_buffer(4) (que saca el valor del buffer) y a fibonacci_buffer(3) (que saca el valor del buffer)

Con este algoritmo consigo generar todos los números en 4ms.

¿Será posible simplificarlo un poco más?
Sólo hay que ver cómo se hace la generación de valores de forma recursiva. Si lo pensamos bien, cuando llamamos a fibonacci_buffer(5) la primera vez y lo queremos almacenar en fbuffer[2] llamaremos a fibonacci_buffer(4) (que se almacenará en fbuffer[1], y éste llamará a fibonacci_buffer(3) (que se almacenará en fbuffer[0]); es decir, lo primero que se generará será fbuffer[0], luego fbuffer[1] y por último fbuffer[2]… ¡ vamos por orden ! Sabiendo esto, nos podremos ahorrar el código de poner a 0 los elementos del buffer sabiendo cuál es el último elemento generado.

Para los incrédulos, podemos eliminar el comentario de la línea:

1
//    printf("He generado con éxito fbuffer[%d]\n", n3-1);

y ejecutar… veremos con qué orden se van generando los números.

Bien, intentemos eliminar las puestas a 0 de los elementos del buffer.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
int fibonacci_buffer2(int n)
{
  static int *fbuffer=NULL; /* Buffer */
  static int bufsize=0;         /* Tamaño de buffer */
  static int bpos=0;            /* Recorre buffers */
  int n3;           /* n-2 */

  if (n>2)
    {
      n3=n-2;
      if (fbuffer==NULL)
    {
      fbuffer = (int*) malloc((n3 * sizeof(int)));
      bufsize=n3;   /* Mantenemos bufsize por si redimensionamos el buffer */
    }
      else if (bufsize<n3)
    {
      fbuffer = (int*) realloc(fbuffer, n3 * sizeof(int));
      bufsize=n3;      
    }

      /* Utilizamos bpos para saber cuál es el último elemento del buffer */
      /* que hemos rellenado. */
      if (bpos>=n3)         /* Si se encuentra el fibonacci del número que buscamos  */
    return fbuffer[n3-1];   /* en memoria, lo devolvemos directamente */
      else
    {
      /* Si el fibonacci no se encuentra, vamos a generarlo */
      fbuffer[n3-1] = fibonacci_buffer(n-1) + fibonacci_buffer(n-2);
      bpos=n3;
      return fbuffer[n3-1];
    }

/*       return fibonacci_simple(n-1) + fibonacci_simple(n-2); */
    }
  else if (n==2)        /* Ponemos esto para agilizar un poco el proceso */
    return 1;
  else if (n==1)
    return 1;
  else if (n==0)
    return 0;
  else if (n==-1)       /* Un caso nuevo n==-1 */
    free(fbuffer);      /* Liberamos memoria */

  return -1;            /* Error */
}

Con este algoritmo, consigo generar la secuencia en 2ms. Bastante más rápido que con el primer algoritmo, parece que la puesta a 0 del buffer llevaba su tiempo.

Para concluir, quiero proponer otra solución basada en arrays, supongo que muchos estaréis más familiarizados con estos:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
int fibonacci_buffer3(int n)
{
  static int fbuffer[MAX_FIB];
  static int bufsize=0;         /* Tamaño de buffer */
  int n3;           /* n-3 */

  if (n>2)
    {
      n3=n-3;

      if (bufsize>n3)           /* Si se encuentra el fibonacci del número que buscaos  */
    return fbuffer[n3]; /* en memoria, lo devolvemos directamente */
      else
    {
      /* Si el fibonacci no se encuentra, vamos a generarlo */
      fbuffer[n3] = fibonacci_buffer(n-1) + fibonacci_buffer(n-2); /* y lo guardamos */
      bufsize=n3+1;
      /* Al ser fibonacci recursivo, y asignar el tamaño después de la generación */
      /* el buffer se rellenará por orden, es decir, el primero que se rellenará */
      /* será el [0], luego el [1], luego el [2]... */
      return fbuffer[n3];
    }

    }
  else if (n==2)        /* Ponemos esto para agilizar un poco el proceso */
    return 1;
  else if (n==1)
    return 1;
  else if (n==0)
    return 0;

  return -1;            /* Error, seguramente me hayan pasado un n negativo*/
}

Esta solución es muy parecida a las anteriores, aunque nos quitamos del medio la reserva de memoria, reducimos las líneas de código, ya que no vamos a alojar tantos valores diferentes… para esta secuencia serían unos 48 * 4 (sizeof(int)) = 192 bytes, y bufsize la utilizamos para ver cuál es el último elemento del buffer con información válida (como vimos antes, se rellenarán por orden, así que sólo tendríamos que llevar la cuenta). Las variables estáticas, como dije, podemos hacerlas globales (y quitarles el static, aunque queda más elegante como static).

Con esta solución tardo unos 5ms de media en generar la secuencia de números.

Foto: Eustaquio Santimano (Flickr)

Categories: C/C++ Tags: , , , , , , , , , , , , , , , ,

Uso de llaves en BASH

Sábado, 15 de Mayo de 2010 Gaspar Fernández 1 comentario

llaves
Leo en el blog de Thalskarth (proveniente de Tux Files, que a su vez venía de Slice of Linux) un truco para hacer copias de seguridad de un archivo con bash de la siguiente forma:

cp archivo{,.bk}

Lo que hacemos es parecido a escribir esto otro:

cp archivo archivo.bk

Por lo que podemos intuir fácilmente para qué valen las llaves en este contexto: replicar alternativas. Es decir escribiremos lo que hay antes de la llave, y lo terminaremos con cada una de las opciones de dentro de las llaves que están separadas por comas. Y lo más fácil para entender esto es utilizar echo.
Probaremos lo siguiente:

$ echo “Voy a pintar mi casa de “{verde,azul,rojo,amarillo}
Voy a pintar mi casa de verde Voy a pintar mi casa de azul Voy a pintar mi casa de rojo Voy a pintar mi casa de amarillo

Bien, el mensaje se replica con un espacio entre réplicas. Podemos ahora probar algo más:

$ echo -e “Voy a pintar mi casa de “{verde,azul,rojo,amarillo}”.\n”
Voy a pintar mi casa de verde.
Voy a pintar mi casa de azul.
Voy a pintar mi casa de rojo.
Voy a pintar mi casa de amarillo.

Además, podemos ver que la llave no tiene por qué estar al final del parámetro, podemos ponerla en mitad y sigue funcionando. Hay un espacio al principio de la línea, como mencioné antes, las frases irán separadas por un espacio (es normal, las llaves nos sirven para introducir nuevos parámetros). Podremos solucionarlo con \b (backspace).

echo -e “\bVoy a pintar mi casa de “{verde,azul,rojo,amarillo}”.\n”
Voy a pintar mi casa de verde.
Voy a pintar mi casa de azul.
Voy a pintar mi casa de rojo.
Voy a pintar mi casa de amarillo.

Antes de nada un apunte, no debemos dejar espacios dentro de las llaves, ni entre las comas, ni dentro de cada opción, no olvidemos que son parámetros, aunque sí que podríamos poner un espacio si éste va entre comillas (igual que ocurre con los parámetros).

Crear PDFs

Y a partir de aquí, sólo necesitamos imaginación, por ejemplo podemos ver cómo lo usamos para crear un pdf con imágenes en jpeg (de una carpeta llamadas test-N.jpg). Lo creamos con ImageMagick y sólo queremos de la 1 a la 12:

$ convert test-{?.,10.,11.,12.}jpg todos.pdf

Aunque hay un método mejor, {} (las llaves) soportan rangos, por lo que podemos hacer:

$ convert test-{1..12}.jpg todos.pdf

Comprimir directorios

Podemos, por ejemplo crear un archivo comprimido de un directorio con el mismo nombre de la siguiente manera:

$ tar cvjf test{.tar.bz2,/}

como sustitución a:

$ tar cvjf test.tar.bz2 test/

Diferencias

Encontrar la diferencia de un archivo con su backup (suponemos que el backup es el mismo nombre terminado en ~ (tilde de la ñ):

$ diff test{,~}

O para diferencias rutas (recordemos que podemos poner llaves entre parámetros:

$ diff ~/proyectos/www/{proyecto1,proyecto2}/www/lib/my_lib.h

Que es lo mismo que:

$ diff ~/proyectos/www/proyecto1/www/lib/my_lib.h ~/proyectos/www/proyecto2/www/lib/my_lib.h

Lectura de datos en scripts

Para leer desde la entrada estandar tenemos read, y si queremos introducir cada palabra en una variable podemos usar read palabra1 palabra2 palabra3, y si queremos que estas variables tengan un prefijo común:

$ read palabra{A,B,C}

Combinaciones y juegos

Vamos a hacer múltiples sumas con bc:

$ echo -e {1..4}”+”{4..1}”\n” | bc

Esto pondrá en pantalla el resultado de: 1+4, 1+3, 1+2, 1+1, …, 4+3, 4+2, 4+1.
Con esto vemos que los rangos no sólo van en incremento sino también en decremento.
Pero aún más si hacemos:

echo test{a..z}

Nos completará con testa testb testc…testx, testy, testz

Por último, un ejemplo más complicado, y que, aunque pocas veces nos sirva (más que nada por no acordarnos), ahí queda, llaves anidadas:

$ echo test-{1{10..12},3{9..1}}
test-110 test-111 test-112 test-39 test-38 test-37 test-36 test-35 test-34 test-33 test-32 test-31

Tenemos la posibilidad de introducir opciones dentro de otras opciones y todas se representarán seguidas. ¿Tal vez nos sirva alguna vez para crear un fichero de texto con datos de prueba? Para crear un archivo con temperaturas de varias ciudades:

$ echo -e “\b”{”Madrid 1″{1..4},”Barcelona 1″{3..5},”Malaga “{19..22},”Sevilla 2″{3..4}}”\n” > test

Esto creará un fichero llamado test con el siguiente contenido:

Madrid 11
Madrid 12
Madrid 13
Madrid 14
Barcelona 13
Barcelona 14
Barcelona 15
Malaga 19
Malaga 20
Malaga 21
Malaga 22
Sevilla 23
Sevilla 24

Foto: bohman (Flickr)

Categories: Bash, General Tags: , , , , , , , , , , , , , , , , , ,

Cambio de base (de base b1 a b2… hasta base36 o tal vez más)

Viernes, 22 de Mayo de 2009 blakeyed Sin comentarios

Hace tiempo tuve la necesidad de hacer una función de cambios de base, pero que no estuviera limitada, es decir, no tuviera definido qué base vamos a introducir y qué base debe devolver. Es decir, convertiremos un número en base b1 a base b2; la limitación, el número de caracteres con los que contemos, en el ejemplo hay hasta base 36, y es fácil extenderlo hasta base256… un número en hexadecimal no tiene desde el 0 al 9 y de la A a la F, pues un base36, del 0 al 9 y de la A a la Z. Con un poco de imaginación podremos sacar muchas ideas de este fragmento. Incluye programa de ejemplo:

Hace tiempo tuve la necesidad de hacer una función de cambios de base, pero que no estuviera limitada, es decir, no tuviera definido qué base vamos a introducir y qué base debe devolver. Es decir, convertiremos un número en base b1 a base b2; la limitación, el número de caracteres con los que contemos, en el ejemplo hay hasta base 36, y es fácil extenderlo hasta base64, base256, por ejemplo… con un poco de imaginación podremos sacar muchas ideas de este fragmento. Incluye programa de ejemplo:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <stdio.h>
#include <string.h>
#include "strutils.h"

void cambiobase (char *n1, int b1, char *n2, int b2)
{
  int lnum = strlen(n1);        /* Longitud de nuestro número */
  /* Caracteres que forman todos los posibles números hasta base 36 */
  char numeros[37]="0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
  int divide;
  int i;
  int posn=0;
  int long2;

  do
    {
      divide = 0;
      long2 = 0;                /* Será un puntero de n1, */
                                /* ya que iremos modificando su valor, long2 */
                                /* nos indicará por dónde vamos */

      for (i=0; i<lnum; i++)
        {
          /* divide vale lo que valía antes multiplicado por la base + el número que acabamos de extraer */
          /* que coincidirá con la posición del carácter dentro del array de numeros[] */
          divide=divide*b1+strchr(numeros, n1[i])-(char*)&numeros;

          if (divide>=b2)
            {
              /* Si el número resultante es mayor o igual a la base */
              n1[long2] = numeros [(int) divide / b2]; /* Modificaremos el dígito long2 de n1, */
                                /*  y este será el número divide/b2 en base b1  */
              divide = divide % b2; /* divide será el resto de la división */
              long2++;
            }
          else if (long2>0)
            {
              n1[long2] = '0';  /* divide<b2, pero en iteraciones anteriores ha sido >= */
              long2++;
            }
        }

      lnum=long2;
      /* hemos hallado un dígito de n2. Su valor será divide */
      n2[posn] = numeros[divide];
      posn++;                   /* posn es el puntero del nuevo número */
    } while (long2!=0);

  n2[posn] = '\0';
  n2=strrev(n2, posn);
}

int main()
{
  char num1[20], num2[20];
  int base1, base2;
  printf("Numero a convertir:");
  scanf("%s", num1);
  printf("¿En qué base está ese número? ");
  scanf("%d", &base1);
  printf("¿A qué base quieres convertirlo? ");
  scanf("%d", &base2);

  cambiobase(num1, base1, num2, base2);

  printf("\n%s\n", num2);

  return 0;
}

La idea principal la saqué hace tiempo de un código escrito en otro lenguaje.
Tenemos que tener en cuenta que esta función utiliza a strutils.h (ver anterior post), aunque también podéis copiar directamente la función strrev y a compilar!!
Todo esto es debido a que el algoritmo para cambiar la base genera el número (como una cadena, pero al fin y al cabo un número) al revés, es decir el dígito de menor peso primero.

Categories: C/C++ Tags: , , , ,

Visita otras webs de la red