Archive for the “C/C++” Category

Parece que las malas noticias este mes no paran, si hace unos días nos levantábamos con la muerte de Steve Jobs, esta mañana en clase me he enterado de la muerte de Dennis Ritchie, creador del lenguaje de programación C y co-creador del sistema UNIX (del que deriva de alguna forma Linux).

Seguramente, la inmensa mayoría de los mortales no conocerá a Ritchie, aunque sin su aportación la informática de hoy día podría haber sido algo distinta.

Dejo el enlace a su página de la wikipedia para quien quiera saber más sobre él:

Dennis Ritchie junto a Ken Thompson

Es curioso la repercusión que tuvo hace unos días la muerte de Steve Jobs, y que el fallecimiento del creador de C y UNIX (base de casi toda, por no decir toda, la informática actual) no tenga casi repercusión mediática. Descanse en Paz.

Fuente: http://www.genbeta.com/actualidad/fallece-dennis-ritchie-creador-del-lenguaje-de-programacion-c-y-del-sistema-unix

Comments No Comments »

Con esta entrada vamos a aprender a realizar un simple ejercicio de recursividad en C. Este ejercicio consiste en la suma de los elementos de un vector (ordenado o sin ordenar) de forma recursiva en lenguaje C.

Recursión o recursividad es la forma en la cual se especifica un proceso basado en su propia definición. Siendo un poco más precisos, y para evitar el aparente círculo sin fin en esta definición:

Un problema que pueda ser definido en función de su tamaño, sea este N, pueda ser dividido en instancias más pequeñas (< N) del mismo problema y se conozca la solución explícita a las instancias más simples, lo que se conoce como casos base, se puede aplicar inducción sobre las llamadas más pequeñas y suponer que estas quedan resueltas. Para que se entienda mejor a continuación se exponen algunos ejemplos:

* Factorial(x: Entero): Sea N := x el tamaño del problema, podemos definir el problema de forma recurrente como x*Factorial(x – 1); como el tamaño de Factorial(x – 1) es menor que N podemos aplicar inducción por lo que disponemos del resultado. El caso base es el Factorial(0) que es 1.

* Ordenación por fusión(v: vector): Sea N := tamaño(v), podemos separar el vector en dos mitades. Estas dos mitades tienen tamaño N/2 por lo que por inducción podemos aplicar la ordenación en estos dos subproblemas. Una vez tenemos ambas mitades ordenadas simplemente debemos fusionarlas. El caso base es ordenar un vector de 0 elementos, que está trivialmente ordenado y no hay que hacer nada.

En estos ejemplos podemos observar como un problema se divide en varias (>= 1) instancias del mismo problema, pero de tamaño menor gracias a lo cual se puede aplicar inducción, llegando a un punto donde se conoce el resultado (el caso base)

Fuente: Wikipedia

Si alguien quiere saber más sobre la recursividad, puede leer el artículo entero en la wikipedia.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include
#include
 
int main()
{
    int n = 3;
    int t[] = {1,2,3,4};
 
    printf("Resultado de la suma recursiva: %d", sumaVector(t,n));
    return 0;
}
 
int sumaVector(int t[], int n){
    int r = 0;
 
    if(n==0){
        r += t[0];
    }else{
        r = t[n] + sumaVector(t,n-1);
    }
    return r;
}

Este es el codigo para la realización del ejercicio.

Este ejercicio no es nada complicado. El caso base es cuando llegamos al último elemento del vector, es decir, como vamos a empezar por el final (posición n-1), el final de la ejecución será cuando lleguemos al principio del vector (n=0).

Mientras no lleguemos al principio del vector, sumamos el elemento anterior al que estamos sumando restando en uno la posición (n-1) en la llamada recursiva.

Comments No Comments »

Instalando g++ en ubuntu

Instalando g++ en ubuntu

Bueno, esto es una mini-entrada (después de medio siglo de la última, espero que esto vuelva a coger forma) a modo de recordatorio sobre un pequeño problema a la hora de compilar programas en C desde Linux (en mi caso, Ubuntu 9.10).

Si hemos instalado el compilador GCC, aun no podremos hacerlo, o al menos en mi caso usando el IDE CodeBlocks, ya que necesitaremos la librería G++.

Instalar esto en Ubuntu es tan sencillo como dirigirnos el gestor de paquetes Synaptic y buscar ‘g++’, tal y como aparece en la imagen.

Comments No Comments »

A continuación voy a exponer un ejercicio que hemos tenido que hacer recientemente en la facultad sobre programación dinámica usando C como lenguaje de programación.

El ejercicio en sí consiste en la transformación de cadenas, es decir, obtenemos 2 cadenas de caracteres y debemos averiguar cuantos pasos hay que dar para transformar la primera cadena en la segunda, pero no se cualquier forma, sino buscando la mejor solución para ello.

La definición de programación dinámica se podría decir que es buscar la mejor solución a un problema, no una buena solución, sino la mejor. Para ello nos vamos a basar en una tabla de resultados en las que iremos guardando resultados intermedios para así, no realizar un cálculo dos veces. Aunque el cometido de este post no es el de definir que es la programación dinámica, existen muchos libros y San Google para encontrar la definición de esto.

Pues bien, empecemos.

¿Cual es la idea?, la idea mencionada anteriormente es que tenemos dos adenas (de igual o distinto tamaño) y queremos transformar una en otra, como por ejemplo:

cortejo -> cortijo

Este es el ejemplo típico que suelen dar en todos los libros.

¿Que es lo que hacemos?, lo más fácil es ir recorriendo la primera cadena e ir comparándola con la segunda y realizar alguna de las siguientes operaciones:

  • Insertar un caracter.
  • Sustituir un caracter.
  • Borrar un caracter.

Hagámoslo con un ejemplo visto en varias biografías.

Tenemos dos cadenas de caracteres, siendo la primera ‘abbac’ y queremos pasarla a ‘abcbc’, para ello podemos hacer lo siguiente.

screenshot_03

Aunque estos cambios no conseguimos el principio de optimalidad, es decir, la solución más óptima, ya que los cambios para la solución más óptima son los siguientes.

screenshot_02¿Cual es la función de recurrencia?.

Tenemos una tabla de NxM tabla[N][M] dimensiones y tenemos los siguientes casos bases (siendo i y j los índices que usaremos para recorrer la matriz).

  • Para tabla[0][j], el valor que añadiremos será el de j, ya que los cambios que necesitemos para pasar de una cadena de tamaño cero a la que estemos construyendo, será el tamaño que vaya tomando la misma (j).
  • Para tabla[i][0], el valor que añadiremos será el de i, igual que en el caso anterior pero con i.
  • Para tabla[0][0] el valor será cero, ya que para pasar de una palabra de tamaño cero a otr de tamaño cero no hay que hacer nada.

screenshot_04

for(i=0;i<m;i++){
        tabla[i][0]=i;
        for(j=0;j<n;j++){
            tabla[0][j]=j;
        }
    }

El codigo anterior refleja los casos base mencionados con anterioridad.

El caso general es el siguiente.

screenshot_05En el caso general debemos buscar el mínimo de los pasos que hemos ido dando hasta ese momento, siendo estos el anterior (inserción), el anterior en la diagonal (sustitución) y el que tenemos inmediatamente encima (borrado), a este mínimo le sumamos uno que es la nueva operación que realizamos.

Una vez hecho esto, es decir, definida la función de recurrencia, lo que nos queda es desarrollar el código, el cual quedaría así.

for(i=1;i<n;i++){
        for(j=1;j<m;j++){
            if(u[i]==v[j]){
                tabla[i][j]=tabla[i-1][j-1];
            }else{
/*
La siguiente llamada
la pongo en dos veces
ya que entera
me descuadra el blog
*/
                tabla[i][j]=1+calculaMinimo
(tabla[i][j-1],tabla[i-1][j],tabla[i-1][j-1]);
            }
        }
    }

La función calculaMinimo es una simple función donde calculamos el mínimo entre 3 números dados (los que mencionamos anteriormente).

Para no dejar el post cojo, la función que utilizo para calcularlo es esta:

int calculaMinimo(int a, int b, int c){
    int aux;
    aux = a<b?a:b;
    return aux<c?aux:c;
}

Para compilar el código en Linux me encontré con un problema a la hora de declarar las cabeceras de las funciones, y es que como normalmente las declaro en Windows (que sí funciona), en Linux no funcionaba. En los dos sistemas he usado tanto la IDE codeblocks como el compilador GCC.

Así es como lo declaraba en Windows.

int transformaCadena(int [][], char [], char []);

Y así como se debe hacer en Linux para que compile.

int transformaCadena(int [][M], char [], char []);

Una vez hecho esto, el programa funciona perfectamente tal y como podemos ver en las siguientes capturas.

Ejemplo: ‘abbac’ y queremos pasarla a ‘abcbc’.
pantallazo-ventana-sin-titulo

Ejemplo: cortejo -> cortijo.
pantallazo-ventana-sin-titulo-1

Pues esto es todo hasta aquí, en otro post explicaré que es eso de Modificación 1 y 2.

Comments No Comments »

Estrenando WP_SYNTAX, en el anterior blog no lo podía usar porque nunca conseguía activarlo.

1
2
3
4
5
6
7
8
9
10
11
int busquedaLineal(int x, int v[], int li, int ls){
    int i=li, pos=-1, enc=0;
    while (i<=ls && !enc)
        if (v[i]==x)
            enc=1;
        else
            i++;
    if (enc)
        pos=i;
    return(pos);
}

En este codigo, cuando encontramos el elemento que buscamos devolvemos su posicion.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int busquedaBinaria(int x, int v[], int li, int ls){
    int mitad, pos=-1, enc=0;
    while (li<=ls && !enc) {
        mitad=(li+ls)/2;
        if (v[mitad]==x)
            enc=1;
        else if (x<v[mitad])
            ls=mitad-1;
        else
            li=mitad+1;
    }
    if (enc)
        pos=mitad;
    return(pos);
}

Comments 2 Comments »

Hace poco se ha publicado una nueva versión del IDE NetBeans, en concreto la 6.0

Esta nueva versión soporta estas tecnologías:

Ajax | C/C++ | Databases | Debugger | Desktop | Editor | GUI Builder | Java EE | Java ME | Java SE | Javascript | Mobile | Profiler | Refactor | REST | Rich Client Platform | Ruby | SOA | SOAP | UML | Web | WSDL | XML

 

Además de estar disponible para Windows, Linux, MAC y Solaris.

 

Con lo poco que lo he usado, decir que han mejorado bastante la IDE. Tanto visualmente como a la hora de acceder a métodos en cualquier lenguaje. Una IDE indispensable a la hora de programar en JAVA.

 

La dirección es: http://www.netbeans.org/

Comments No Comments »

A continuación voy a explicar como se multiplican dos matrices de forma recursiva en C.

Además esta técnica nos servirá para pasar funciones iterativas que usen bucles for (y otros) a forma recursiva.

Empezamos…

Primero tenemos el siguiente código en C para multiplicar matrices de forma iterativa:

for(i=0;i
for(j=0;j
for(k=0;k
mC[i][j]+=mA[i][k]*mB[k][j];
}
}
}
//

Vamos a llamar a los bucles primero segundo y tercero leyendo de arriba a abajo, y siendo mA y mB las matrices a multiplicar y mC la matriz resultado.

En las funciones, a y b son el tamaño de la matriz.

El primero for se traduciría así:

void primerFor(matrices, a, b, i){

if(i==a);

else{

segundoFor(matrices, a, b, i, 0);

primerFor(matrices, a, b, i++);

}

}

Si miramos el primer for, la condición para salirnos del bucle es que i sea igual (menor estricto) al tamaño de la matriz, pues ese será nuestro caso base, es decir, i==a.

Al final del bucle incrementamos i, pues eso mismo hacemos en nuestra función con una llamada recursiva.

Antes de eso, deberemos llamar a la seguna función recursiva, la cual sería creada del mismo modo.

void segundoFor(matrices, a, b, i, j){

if(i==a);

else{

tercerFor(matrices, a, b, i, j, 0);

segundoFor(matrices, a, b, i, j++);

}

}

Como se puede ver, cada vez que llemamos a la siguiente función (en definitiva pasamos al siguiente for) pasamos el valor cero inicial de comienzo del bucle.

La tercera y última función sigue el mismo patrón, pero en vez de llamar a una supuesta cuarta función (si hubiera 4 así sería), realizamos la operación que vamos buscando.

void tercerFor(matrices, a, b, i, j, k){

if(i==a);

else{

mC[i][j]+=mA[i][k]*mB[k][j];

tercerFor(matrices, a, b, i, j, k++);

}

}

Este método es una buena aplicación de como pasar funciones iterativas a recursivas.

Comments 1 Comment »

A continuación os presento una pequeña aplicación para programar en C en Linux.

El programita en cuestión se llama OpenLDev, y usa las herramientas de compilación gcc que podemos obtener con la terminal.

Es bastante sencillo de usar y se amolda muy bien a nuestras necesidades.

Aunque, todo hay que decirlo, yo no lo usaría para grandes proyectos (al menos por ahora). Alguna vez me ha dado un fallo de compilación…, no que el programa estuviera mal escrito, si no que no lograba funcionar la propia IDE.

Aunque como suelo decir, cada PC es un mundo y nunca está de más probarlo.

Para probar que usa las herramientas que antes mencioné hacemos algo sencillo.

Cuando compilemos un programa, en la parte de abajo de la IDE tenemos una pestaña para acceder a la terminal, y veremos escrito lo siguiente:

gcc -o programa programa.c

Que no es otra cosa que la instrucción para compilar que se usa en la terminal.

Yo aconsejo que se pruebe dicho programa y se le intente sacar todo el partido que pueda dar (aunque me quedo con Anjuta, en el cual ya confío…).

Es un programa muy joven, sólo tiene una versión estable (la 1.0), y si el proyecto sigue creciendo creo que será un programa para desarrollar a tener en cuenta en un futuro.

Para descargarlo podeis ir a la siguiente dirección:

http://www.openldev.org/

Aunque siempre recomiendan desde su web que utilicéis los repositorios de vuestra distribución para bajarlo.

Comments No Comments »

Si buscamos en Google las mismas palabras que el título de este post encontraremos 396.000 resultados.

Personalmente, llevo un .c en mi pendrive llamado “numerosPrimos.c” el cual me ha sacado de más de un apuro. Es algo que siempre olvido, un algoritmo para calcular si un número es primo y al parecer, no soy el único.

A veces, las cosas más simples son las más difíciles de recordar.

A continuación pondré dicho código por si alguien llega aquí con esa duda le pueda servir, al fin y al cabo, soy estudiante y con este blog lo que pretendo es solucionar posibles problemas que puedan tener aquellos que llegan aquí.

int esPrimo(int a){
int b=0;
int res=0;//Es primo
int i=2;
while(i<a && b==0){
if(a%i==0){
b=1;
res=1;//No es primo
}else i++;
}
return res;
}

Esta función devuelve cero si el número SÍ es primo, y uno si NO lo es.

Comments 11 Comments »

Algunas veces, cuando se empieza a programar en C nos damos de cabezasos en la pared a causa de no saber por que se produce un error, o al menos, eso me pasaba a mi….

El compilador te dice que un puntero se va por algún sitio, revisas el código una, dos,…, y todas las veces que quieras hasta que aparece el dolor de cabeza, y entonces, piensas,…, ¿será error del compilador?.

Es una excusa algo barata, pero los que hayan sufrido el C saben a que me refiero.

El caso es que cuando empezamos en la programación, creo que existen muy pocos entornos de desarrollo para que podamos hacer algo con claridad….., que si programas en MS-DOS, herramientas para el desarrollo (¿y el entorno?).

Siempre podemos bajarnos NetBeans y Eclipse con algún plug-in para programar en C, pero bueno, a continuación voy a poner que programas uso yo para programar en C, con las ventajas e inconvenientes que he podido observar.

Lo más importante de estos entornos es que son gratuitos y/o software libre. Pulsa sobre las imágenes para ir a sus respectivas webs.

Dev-C++

  • A favor:
    1. Es muy estable.
    2. Sirve para programar en C y en C++.
    3. Facilidad de crear el .c (Archivo -> nuevo).
  • En contra:
  1. Para los más puristas, no tabula bien el código.
  2. Al escribir código, no diferencia mucho unas sentencias de otras con colores.
  3. Los ejecutables son algo grandes.
  4. A la hora de hacer trazas, el debugger no funciona bien.


Code::Blocks

  • A favor:
  1. Tabula bien el código.
  2. Diferencia las sentencias con colores de forma que todo esté bien organizado.
  3. Para hacer trazas, el debugger funciona MUY bien.
  4. Para hacer trazas, tiene muchísimas opciones. Puedes ver el valor de las varibles, mirar como cambian el valor de esas variables durante la ejecución. Crear otras variables de las cuales podemos ver sus cambios durante la ejecución.
  • En contra:
    1. Es inestable.
    2. Es algo complicado crear los .c pues hay que crear un proyecto por cada .c que creamos.

Watcom

Desconozco este programita, la vez que lo instalé lo use poco o nada. Demasiado complicado para programar cuatro cosillas en C. Lo pongo aquí ya que es libre, y si alguien quiere aventurarse a probarlo, ahí está.

Comments No Comments »

   Beat diabetes   Diabetes diet