Recientemente vi una pregunta de un usuario del foro sobre grafos no dirigidos y distancia mínima entre nodos del mismo. Me puse a invetigar el tema, el cual me pareció realmente interesante y decidí escribir un post al respecto.
El algoritmo de Dijkstra permite encontrar la distancia mínima entre un vértice dado de un grafo no dirigido, y cualquiera otro de sus vértices. No funciona sin embargo si la ponderación entre dos elementos es negativa, es sólo para grafos donde el coste de unir dos nodos cualesquiera es siempre mayor o igual que cero.
Un video de youtube que nos explica este tema de una manera excelente es:
A modo de ejemplo, consideremos el grafo (me disculpan la presentación simplemente me puse a escribir sobre una hoja de papel y le tomé fotografías)
En esta imagen, los valores sobre las aristas representan los pesos o costes de transitar los caminos que unen un nodo con el otro. El algoritmo comienza eligiendo un nodo inicial, en este caso digamos que el nodo 0.
Etiquetado de los nodos
Junto con cada nodo asociaremos una etiqueta o label que se compone de un par de valores: ( peso_acumulado, antecesor )
esto es, como primer elemento el peso total acumulado del nodo actual (la suma de los pesos de las aristas recorridas para llegar desde el nodo inicial hasta el nodo actual), y como segundo elemento denotamos el nodo previo al nodo actual. Esto último es importante para reconstruir la ruta seguida para llegar al nodo.
El nodo inicial tiene un peso de 0 (la distancia que lo separa de sí mismo es lógicamente cero), y no tiene antecesor, por lo que se asigna el par compuesto de un "cero" seguido de una "rayita": (0, -)
Vale decir que los restantes nodos comienzan con un peso o coste "infinito", pues aún no hemos calculado su coste.
Cálculo del coste hasta los nodos sucesivos
El siguiente paso es observar todos los nodos que están directamente conectados con este nodo inicial. En nuestro caso, los nodos 1, 2 y 3. El coste de cada nodo será el coste acumulado de su nodo antecesor, sumado al coste del camino que une al antecesor con el nodo actual:
Código:
coste de nodo 1: (coste acumulado nodo 0) + (coste camino que une nodos 0 y 1) = 0 + 16 = 16 coste de nodo 2: (coste acumulado nodo 0) + (coste camino que une nodos 0 y 2) = 0 + 10 = 10 coste de nodo 3: (coste acumulado nodo 0) + (coste camino que une nodos 0 y 3) = 0 + 5 = 5
por lo tanto etiquetamos estos nodos sucesores del nodo 0 de la siguiente manera:
Código:
nodo 1 ---> ( 16, 0 ) [ pues, su coste acumulado es 16, y procede del nodo 0 ] nodo 2 ---> ( 10, 0 ) [ ídem ] nodo 2 ---> ( 5, 0 ) [ ídem ]
Seguidamente, "tachamos" o "marcamos" el nodo 0 como definitivo, y con ellos hemos terminado el primer ciclio de la ejecución de nuestro algoritmo. Queda resaltar que un nodo "tachado" es un nodo que no se vuelve a revisar. El algoritmo terminará cuando todos los nodos estén "tachados". Hasta ahora vamos así:
Continuación del algoritmo
El algoritmo continúa inspeccionando entre todos los nodos que no han sido tachados o marcados como definiitivos, pero tienen un peso total ya calculado menor a infinito. Esto es, los nodos 1, 2 y 3. De ellos, seleccionamos el de menor coste, que sería el nodo 3 y repetimos el proceso considerándolo como nodo inicial.
Al nodo 3 le suceden, exceptuando el propio nodo 0 que ya fue tachado (repito, los nodos tachados no se vuelven a revisar), los nodos 2 y 4. Sus costes totales se calcularían como:
Código:
coste de nodo 2: (coste acumulado nodo 3) + (coste camino que une nodos 3 y 2) = 5 + 4 = 9 coste de nodo 4: (coste acumulado nodo 3) + (coste camino que une nodos 3 y 4) = 5 + 15 = 20
por lo tanto etiquetamos estos nodos sucesores del nodo 3 de la siguiente manera:
Obsérvese en la última etapa que hasta ahora llevamos del algoritmo, que el coste del nodo 2 mejoró de un valor 10 a un valor 9, al cambiar su antecesor y por lo tanto la ruta seguida.
Para ser más claros, el coste del nodo 2 al tomar la ruta que procede directamente desde el nodo 0 fue de 10. Pero al considerar la ruta que alcanza el nodo 2 desde el nodo 3, o sea la ruta 0-3-2, el coste total acumulado fue 5+4=9. Cuando esto ocurre tachamos la anterior etiqueta del nodo 2 que era (10,0), y la cambiamos por la etiqueta (9,3). Y esto lo debemos hacer cada vez que alcancemos un nodo que habíamos computado, pero esta vez desde una nueva ruta y con un costo menor.
El grafo nos va quedando así, y nótese como se mejora el coste del nodo 2. También nótese que tachamos el nodo 3, es decir lo marcamos como definitivo por eso no lo volveremos a revisar.
Siguiente paso
Revisamos ahora todos los nodos que tienen un coste calculado menor a infinito, en este caso los nodos 1,2 y 4. El de menor coste es el nodo 2, por lo tanto es el nodo que vamos a tomar como inicial.
Los sucesores del nodo 2 son los nodos 1, 4 y 5. Calculamos sus costes:
Código:
nodo 1, a partir de 2: 9 + 2 = 11 (mejora el coste) nodo 5, a partir de 2: 9 + 12 = 21 nodo 4, a partir de 2: 9 + 10 = 19 (mejora el coste)
Marcamos el nodo 2 como definitivo, y continuamos.
Siguiente paso
De los nodos no definitivos que quedan (1, 4 y 5) el de menor coste es el 1. Inspeccionamos sus sucesores, los nodos 5 y 6, al calcular los costes de estos resulta:
Código:
nodo 5, a partir de 1: 11 + 4 = 15 (mejora el coste) nodo 6, a partir de 1: 11 + 6 = 17
Tachamos el nodo 1 y continuamos.
b] Siguiente paso [/b]
De los nodos no definitivos que quedan (4, 5 y 6) el de menor coste es el 5. Inspeccionamos sus sucesores, los nodos 6, 7 y 4, al calcular los costes de estos resulta:
Código:
nodo 6, a partir de 5: 15 + 8 = 23 (empeora el coste) nodo 7, a partir de 5: 15 + 16 = 31 nodo 7, a partir de 5: 15 + 3 = 18
Nótese que al recalcular el nodo 6 desde el nodo 5 se obtiene más bien un costo peor, por lo cual se mantiene su costo anterior que era 17, desde el nodo 1.
Tachamos el nodo 5 y continuamos, nos debe quedar así:
Pasos finales
El algoritmo se continúa repitiendo los pasos anteriores, hasta que no queden nodos sin tachar, es decir, hasta que todos queden como definitivos.
Reconstrucción de la ruta más económica
Una vez terminado, podemos calcular la ruta del coste mínimo desde el nodo inicial 0, hasta cualquiera otro de nuestros nodos. Por ejemplo, desde el nodo 0 hasta el nodo 7, vemos que el coste total es 23 y la ruta se forma regresivamente de la siguiente manera
Código:
el nodo 7, procede del nodo 4 el nodo 4, procede del nodo 5 el nodo 5, procede del nodo 1 el nodo 1, procede del nodo 2
etcétera, hasta llegar al nodo inicial. La ruta por lo tanto sería:
0 - 3 - 2 - 1 - 5 - 4 - 7
=================================================================== PROGRAMA EN C++ PARA EL CALCULO DE LA RUTA MINIMA
Este es un pequeño programa que hice en C++ para computar el grafo anteriormente explicado usando el algoritmo de Dijkstra. Al cambiar la matriz de adyacencia por otra, se puede modificar el programa para trabajar con un grafo diferente. Claro, está un poco rudimentario, lo ideal sería poder pedir al usuario la matriz de adyacencia del grafo de forma interactica a través del teclado, pero hasta ahí no llegué por hoy jeje.
Codifiqué algunos "cout" para que el programa fuese imprimiendo los resultados de las distintas etapas del análisis, de modo que sea más explicativo o pedagógico. Por supuesto, el programa está dado a mejorar ya que esta es una versión muy básica pero es completamente funcional, sólo compilar y probar.
Para nuestro caso la salida final es (luego de imprimir información etapas previas del análisis, jeje)
Por otra parte, creo que el programa no está mal, no es demasiado extenso porque la parte que calcula el Dijkstra sólo llevó 113 líneas de código, el resto del código es inicializando la matriz, declarando los structs, etc.
Código
#include <iostream>
#include <iomanip>
#include <list>
/* Definiendo la estructura etiqueta de nodo. Sus campos incluyen
* el número de nodo, el coste total del nodo, y su precedente. */
struct label {
int nro;/* numero del nodo */
int prev;/* nodo precedente (-1 para el nodo inicial )*/
int peso;/* peso o coste total de la trayectoria que
* conduce al nodo, i.e., el coste total desde
* el nodo inicial hasta el actual. Un valor
* de -1 denota el infinito */
int marca;/* si el nodo ha sido marcado o no */
};
typedefstruct label label_t;
usingnamespace std;
void dijkstra(int, int**, int, int);
int main (){
/* cantidad total de nodos */
int numNodos =8;
/* Definiendo la matriz de adyacencia */
int i, j, **A;
if(( A =newint*[numNodos])==NULL)return1;
for( i =0; i < numNodos; i++)
if(( A[i]=newint[numNodos])==NULL)return1;
for( i =0; i <8; i++)
for( j =0; j <8; j++)
A[i][j]=0;
/* por simplicidad, completamos solo los pares de nodos conectados */
A[0][1]=16;
A[0][2]=10;
A[0][3]=5;
A[1][0]=16;
A[1][2]=2;
A[1][5]=4;
A[1][6]=6;
A[2][0]=10;
A[2][1]=2;
A[2][3]=4;
A[2][4]=10;
A[2][5]=12;
A[3][0]=5;
A[3][2]=4;
A[3][4]=15;
A[4][2]=10;
A[4][3]=15;
A[4][5]=3;
A[4][7]=5;
A[5][1]=4;
A[5][2]=12;
A[5][4]=3;
A[5][6]=8;
A[5][7]=16;
A[6][1]=6;
A[6][5]=8;
A[6][7]=7;
A[7][4]=5;
A[7][5]=16;
A[7][6]=7;
/* Imprimir la matriz de adyacencia */
cout<<"Matriz de adyacencia:"<< endl << endl;
for( i =0; i <8; i++){
for( j =0; j <8; j++)
cout<< setw(2)<< A[i][j]<<" ";
cout<< endl;
}
cout<< endl;
/* calcular dijkstra a partir del nodo 0, a partir del nofo 7 */
dijkstra( numNodos, A, 0, 7);
/* liberar memoria */
delete[] A;
for( i =0; i < numNodos; i++)
delete A[i];
return0;
}
/* Calcula el coste minimo de alcanzar un nodo final 'b'
* grafo no dirigido con N nodos, a partir del nodo inicial 'a',
* dada su matriz de adyacencia A */
void dijkstra(int N, int**A, int a, int b ){
label_t *Labels;
int i, i0, j, peso;
int*ruta;/* array de nodos de la ruta minima */
/* Crea din'amicamente el arreglo de etiquetas de nodo */
if(( Labels =new label_t[N])==NULL)return;
/* nodo inicial 'a' entre 0 y N - 1 */
if( a <0|| a > N -1)return;
/* nodo final 'a' entre 0 y N - 1 */
if( b <0|| b > N -1)return;
/* inicializar las etiquetas de nodo */
for( i =0; i < N; i++){
Labels[i].nro= i;
if( i != a ){
Labels[i].prev=-1;/* a'un no se ha definido predecesor */
Labels[i].peso=-1;/* infinito */
Labels[i].marca=0;
}
else{
Labels[i].prev=-1;/* a'un no se ha definido predecesor */
Labels[i].peso=0;/* coste del nodo inicial a s'i mismo es cero */
Labels[i].marca=0;
}
}
/* continuamos este ciclo mientras existan nodos no marcados */
while(1){
/* busca entre todos los nodos no marcados el de menor peso, descartando los
Cuidado con los tipos. Tengan en cuenta que por defecto C hace promoción de los parámetros pasados, así, si pasan un float, este será promovido a double y la sentencia va_arg(pa,float) será incorrecta. Lo mismo con shorts, etc. Normalmente el compilador nos avisará de esto.
El tema se refiere a funciones con número variable argumentos, donde lógicamente debemos avisar a la macro va_arg sobre el tipo esperado del siguiente argumento de la función. La verdad nunca antes había leído de ésto, pero según entiendo de la cita si se pasa un float a la función, de alguna manera promueve el argumento a double, i.e., reserva en la pila de argumentos, en el lugar asignado para el mismo, el espacio que ocupa un double en lugar del espacio que ocupa un float. En este caso desreferenciar el argumento (usando va_arg) como float dará un error, como es de suponer.
Tengo dos inquietudes: (1) ¿Cuándo ocurren dichas "promociones", y cómo podemos hacer entonces para trabajar de manera segura?
(2) Se me ocurre que una forma de controlar dichas promociones es hacer cast explícito de los argumentos pasados, ejemplo: f( (float) x, (float) y ), así invocará la función reservando en la pila de argumentos el espacio justo para argumentos de tipo float. ¿Es correcto?
Hola a todos. Hace tiempo instalé el escritorio kde pero no me agradó. Mi pregunta es ¿qué ficheros de configuración de inicio debo modificar en Ubuntu, para que arranque con escritorio gnome por defecto, en lugar de kde?
Hola a todos. Mi idea a mediano plazo es construir una calculadora "en linea", o sea por consola. No funcionaría con botones, sino que el usuario debe escribir una expresión algebraica, e.g. 2 + 3*(3-6)^2 la cual será evaluada. En el futuro, incluir funciones trigonométricas, exponenciales, etc., lo cual no debe ser difícil una vez se tenga la estructura básica funcionando. Quizá hasta con la opción de graficar. Es un proyecto bonito, porque al estar desarrollado en C estándar, se pudiera incluso compilar en un microprocesador de bajo costo (compatible con C) y hacer así una calculadora científica. Claro, esto sería bien en el futuro pero con algo hay que comenzar.
El primer reto a que debemos enfrentarnos es el tema de conversión de la notación "infija a posfija". Explico a continuación (es un poco extenso, los impacientes favor ir a dar una vuelta, jeje):
Para los humanos es natural la notación 'infija', donde el operador va en medio de los operandos: "5 + 2*3". En cambio para la máquina es natural la notación 'posfija' donde primero van los operandos y luego el operador. Esto es así porque a nivel de máquina primero deben copiarse los argumentos en los registros adecuados del procesador, y luego invocar la instrucción de suma (binaria). En posfijo, la anterior expresión se escribiría como: 5 2 3 * +
y obśervese como primero debe ejecutarse el operador de mayor prioridad *, y luego +, para cumplir adecuadamente con la asociatividad implícita 5 + (2 * 3).
Ya encontré un algoritmo que explica cómo hacer el paso de una notación a la otra usando pilas, pero más que repetirlo textualmente quisiera encontrarle la lógica. Supóngase que tenemos una expresión del tipo: A op1 B op2 C
donde A, B, C son los operandos, mientras op1 y op2 son operadores. A menos que existan paréntesis explícitos, la asociatividad viene determinada por la precedencia de dichos operadores. Ahora, disponemos de uns string para la notación infija, un string para la posfija (que debemos ir rellenando) y una pila para ir depositando algunos elementos transitorimente.
Caso 1. Si op1 tiene mayor precedencia que op2, ejemplo "A * B + C", primero debe evaluarse el resultado de op1, luego el de op2. Entonces, copiamos A al string de posfijo, metemos op1 en la pila, copiamos B al string posfijo, sacamos op1 de la pila y lo pasamos al posfijo, metemos op2 en la pila, copiamos C al string posfijo, sacamos op2 de la pila y lo pasamos al string. Para explicarlo más claramente en forma de tabla. Paso | Pila | Posfijo ------------------------------------- 1 | | A 2 | op1 | 3 | | A B 4 | op2 | A B op1 <-- sacamos op1 de la pila y lo pasamos al string 5 | op2 | A B op1 C 6 | | A B op1 C op2
Caso 2. Cuando op1 y op2 tienen igual precedencia, ejemplo "A + B + C". En este caso, la asociatividad debe ser de izquierda a derecha "(A + B) + C", por lo que se evalúa primero op1 y luego op2. Se procede exactamente de la misma manera que en el caso 1.
Caso 3. Cuando op1 es de menor prioridad que op2, ejemplo "A + B * C". Aquí debe evaluarse "A + (B * C)". Esto significa que op1 debe esperar por el resultado de op2, el string posfijo deberá quedar "A B C op2 op1". En forma de tabla: Paso | Pila | Posfijo ------------------------------------- 1 | | A 2 | op1 | 3 | | A B 4 | op1, op2 | A B <-- no se saca op1 al momento de colocar op2 5 | | A B op2 op1 <-- vaciamos la pila
La diferencia con el caso 1 es que al momento de introducir op2 en la pila, no se saca antes op1. Esto es porque op2 tiene mayor precedencia que op1 entonces debe evaluarse primero, es decir, debe quitarse primero op2 de la pila y luego op1.
Uno puede resumir diciendo que al momento de colocar un nuevo operador en la pila, se sacan todos los operadores anteriormente depositados y que tengan mayor o igual jerarquía a la suya (y que deben evaluarse antes), estos operadores son pasados al string posfijo y el nuevo operador es depositado en la pila.
Con esta explicación precedente, se puede presentar el algoritmo para convertir infijo a posfijo. Debemos leer la expresión infija de izquierda a derecha y luego
* Los espacios son despreciados. * Si el argumento leido es un operando (número), pasarlo al string posfijo. * Si el argumento leido es un operador entonces: - Si la pila no está vacía, retirar todos los operadores con una precedencia mayor o igual al operador actual y pasarlos al posfijo, en el orden en que son retirados. - Colocar el nuevo operador en la pila. * Si se lee un paréntesis izquierdo '(', depositarlo en la pila. * Si se lee un paréntesis derecho ')', retirar de la pila todos los elementos hasta encontrar un '('. Dichos elementos son pasados al posfijo, menos el paréntesis '(' que es descartado. * Al finalizar el proceso, pasar al posfijo cualquier elemento que haya quedado en la pila.
Entonces me puse manos a la obra. El programa está hecho en C++, que al usar clases STL se simplifica bastante (estoy pensando una versión en C puro, con código más elemental, útil quizás si se piensa migrar a un hardware más básico como un uC).
El programa recibe una cadena de notación infija y la convierte a posfija. Para propósitos de depuración se dan mensajes en pantalla sobre los pasos que van efectuando (funcionalidad que se debe quitar más adelante). Al final, evalúa el resultado y lo imprime. Por ejemplo, una cadena sencilla como: 5 + 2 * 3
produce la salida:
Código:
Intro expresion infija: 5 + 2 * 3
Analizando token: '5' es numero: pasado a posfijo
Analizando token: '+' es operador: colocar '+' en la pila
Analizando token: '2' es numero: pasado a posfijo
Analizando token: '*' es operador: colocar '*' en la pila
Analizando token: '3' es numero: pasado a posfijo
Pasado operador '*' de la pila a posfijo
Pasado operador '+' de la pila a posfijo
Posfijo es: 5 2 3 * +
Evaluando la expresion ... operar 2*3 = 6 operar 5+6 = 11 El resultado es: 11
y un caso más complicado: 5 + 3*(4 - 7)^2 - 1
produce:
Código:
Analizando token: '5' es numero: pasado a posfijo
Analizando token: '+' es operador: colocar '+' en la pila
Analizando token: '3' es numero: pasado a posfijo
Analizando token: '*' es operador: colocar '*' en la pila
Analizando token: '(' pasado a posfijo
Analizando token: '4' es numero: pasado a posfijo
Analizando token: '-' es operador: colocar '-' en la pila
Analizando token: '7' es numero: pasado a posfijo
Analizando token: ')' pasado operador '-' de la pila a posfijo
Analizando token: '^' es operador: colocar '^' en la pila
Analizando token: '2' es numero: pasado a posfijo
Analizando token: '-' es operador: pasado operador '^' de la pila a posfijo pasado operador '*' de la pila a posfijo pasado operador '+' de la pila a posfijo colocar '-' en la pila
Una pregunta a la comunidad. Como sabemos, el estándar POSIX provee un conjunto de métodos para interacción con el sistema operativo (crear o ejecutar procesos, conocer estados y permisos de ficheros, etc). En implementaciones de C para Linux (e UNIX en general) estas funciones están definidas en <unistd.h>. Y sabemos también que Windows es el campeón en desobedecer los estándares.
Mi pregunta es cómo hacer algo similar, por ejemplo crear un proceso hijo con fork(), a través de un programa elaborado en C para el sistema operativo Windows. Y así por ejemplo crear demonios personalizados para tareas de sistema. O también podría ser crear tuberías, comunicar procesos, etc.
La distribucion MinGW para Windows contempla algunas funciones de este tipo, por ejemplo en <dirent.h> está la función de leer directorios readdir(), y en <unistd.h> tenemos chdir() para cambiarnos de directorio. Pero no vi nada de procesos hijos, tuberías, etc.
Buenos días moderadores, la presente es para proponer la siguiente idea para el foro. Habilitar una especie de Salón de la Fama para los temas más destacados. Por ejemplo he visto varios aquí en el foro de C/C++ que merecerían estar allí.
Temas que sobrepasen una simple duda o consulta, y más bien sean aplicaciones desarrolladas entre los distintos miembros de la comunidad, funcionales, depuradas y libres de errores, con sus respectivos y debidos comentarios, ficheros de cabecera, su código claro y legible, macros #define para hacerlo configurable e incluso capacidad para compilarse en varios sistemas, quizá su Makefile, etc., .... en fin algo completo y refinado.
Sería una manera de recompensar a los autores por tan prolijo trabajo, que no tiene que ser extenso, pero sí bien pulido y acabado, y por otra parte enriquecería considerablemente el foro con esos aportes.
Sería bonito, nos repartimos el trabajo entre varios del foro, cada quién hace una parte y luego la ensamblamos. Sería como para abrir una sección de temas y proyectos abiertos en el foro.
Es sólo una propuesta para ser considerada ..... Yoel.
Hace un tiempo un usuario me rcomendó escribir y compartir un programa que trabaje sobre el triángulo de Pascal. La verdad no es difícil generar el triángulo, así que para añadir más gusto decidí ir más allá y generar el binomio de Newton de un exponente arbitario. Pero antes de proseguir en este tema vamos a señalar algunas consideraciones teóricas (tal vez para quiénes ya olvidaron sus clases de mate, jeje).
En álgebra, al desarrollar (a+b)^2, obtenemos: a^2 + 2ab + b^2
y para (a+b)^3: a^3 + 3a^2b + 3ab^2 + b^3
Pues bien, lo que se quiere es el desarrollo para una potencia entera positiva cualquiera, y que lo imprima "con formato". Es decir, una línea para la base y otra para los exponentes: 3 2 2 3 a + 3a b + 3ab + b
y se construye de esta manera: todas las filas empiezan y terminan con 1, además de la tercera filas en adelante cada elemento se obtiene sumando los dos que tiene directamente arriba, uno a la derecha y otro a la izquierda. En la tercera fila, el "2" se obtuvo sumando 1 + 1 de este modo. Vamos con 4 filas: 1 1 1 1 2 1 1 3 3 1
y ahora el primer "3" de la 4ta fila es la suma 1 + 2 de los elementos que tiene arriba suyo, el otro "3" es la suma 2 + 1, y así sucesivamente.
Pues bien, el j-ésimo elemento de la i-ésima fila del triángulo (empezando los índices en cero) se llama coeficiente binomial que por falta de una mejor simbología en este portal representaré como <i,j>. Con ésto, el binomio (a + b)^N se desarrolla como la suma desde i=0 hasta i=N de los términos de la forma <N,i> * a^(N-i) * b^i. O sea, por ejemplo: (a + b)^3 = <3,0>*a^3 + <3,1>*a^2*b + <3,2>*a*b^2 + <3,3>*b^3
los coeficientes binomiales <3,j> no son más que los elementos de la cuarta fila del triángulo: 1 1 1 1 2 1 1 3 3 1
por tanto (a + b)^3 = 1*a^3 + 3*a^2*b + 3*a*b^2 + 1*b^3 = a^3 + 3a^2b + 3ab^2 + b^3
y por supuesto, para desarrollar el binomio de orden N necesitamos construir el triángulo de N+1 filas.
Bueno, y ya . La parte de hacer todos los cálculos no encierra nada que no se pueda comprender leyendo el código fuente, y sus respectivos comentarios. Lo más desafiante (para mí) fue hacer la presentación "formateada" que expliqué antes. Usando algúun tipo de función gotoxy() o su equivalente es fácil, pues nos movemos a la línea de arriba para escribir los exponentes, y a la de abajo para el resto de la expresión. Sin embargo esta función no es portable por lo que decidí no usarla.
En su lugar pensé hacer algo similar a cómo las pantallas LCD que los aparatitos electrónicos. Una matriz de celdas donde cada celda permite representar un carácter. Un programa debe calcular todas las letras y mandar a imprimirlas. Bueno, ..... creo que la idea quedó clara, se debe disponer una matriz "board" o tablero de dos filas, e ir rellenando los caracteres adecuados. Luego que se tenga toda la expresión formada, se imprimen con funciones estándares.
El problema es que se debe calcular en tiempo de ejecución el ancho total de las líneas, dependiendo de la potencia del binomio que se quiera. Tomar en cuenta también que los números ocupan un ancho fijo, porque para potencias grandes pueden ser de una, dos, tres cifras, etc. También tener presente que los coeficientes iguales a 1 no se imprimen, como tampoco los exponentes iguales a 1. Este programa, tal como está desarrollado, está limitado a expresiones cuyo ancho sea menor o igual que la pantall (no hace "salto" de línea).
Otra dificultad fue hacerlo enteramente en C (sin usar clases), por eso malloc() y free() por varias partes, jeje. El argumento (potencia del binomio) está pasado como argumento de la línea de comandos. Así que probándolo con potencia 3: ./binomio 3
nos da: (a + b)^3 es:
3 2 2 3 a + 3a b + 3ab + b
y para divertirnos un poco, con potencia 7: (a + b)^7 es:
7 6 5 2 4 3 3 4 2 5 6 7 a + 7a b + 21a b + 35a b + 35a b + 21a b + 7ab + b
Hola, comparto un programilla que puede ser útil en este mismo foro. Encuentro que al subir código con la etiqueta code, los tabuladores son reemplazados por una cantidad de espacios que a mi entender son demasiados (son como 8). El código entonces toma una aparienci anti-estética . Se me ocurrió hacer un programa llamado "tab" que reemplace todos los TAB en el fichero .c original por una cantidad de espacios determinada, y vuelque su salida a un fichero auxiliar, cuyo contenido copiaré dentro de la etiqueta code.
La sintaxis (UNIX) ./tab fichero_entrada fichero_salida N_spaces
y en DOS quitar el "./" que antecede a tab. Por ejemplo, "tab code.c code2.c 3". Si no se indica N_spaces se toman 3, y si no se indica fichero de salida toma la salida estándar.
Código
#include <stdlib.h>
#include <stdio.h>
/* Este programa reemplaza los caracteres TAB del fichero de texto
* pasado como primer argumento por una cantidad determinada de espacios,
* y escribe su salida en el fichero pasado como segundo argumento.
* El tercer argumento (opcional) especifica cuántos caracteres ' '
* reemplazarán el TAB, y si no se indica, se tomará una cantidad de tres.
Hola, preciso ayuda de los Linuxeros. Este sencillo código (que mide el tiempo transcurrido entre el inicio del programa y la pulsación de ENTER) no funciona como debe en Linux. En Windows lo probé y está Ok.
El problema es que clock() devuelve siempre cero (0), tanto para t1 como para t2, y por eso no mide el tiempo. ¿Qué es lo que le falta "ajustar" para que funcione en plataformas Linux y/ similares?
En esta ocasión quiero compartir un programita divertido que muestra de manera interactiva la ejecución del algoritmo de ordenamiento por inserción. Básicamente va ordenando el arreglo e indicando por pantalla lo que va haciendo: cómo se mueven los elementos y cómo va quedando el vector tras cada paso ....
Un programita amigable y con un propósito bien didáctivo .... enjoy it!!
Código
#include <stdio.h>
#include <stdlib.h>
#define N 5
int main(void){
int x[N]={7, 3, 11, 5, 1};
int i, j, k;
int aux;
printf("Arreglo original: \n");
for(k =0; k < N; k++)
printf(" %d", x[k]);
printf("\n");
for(i =1; i < N; i++){
/* buscamos desde 0 hasta i - 1, el primer elemento que sea
* mayor que x[i] */
printf("ubicando %d ...", x[i]);
j =0;
while(j < i && x[j]<= x[i])
j++;
if( j < i ){
/* insertar x[i] en la posición j, y desplazar los