Mensajes

Con las correcciones propuestas por engelx, creo que quedaría así

Código (cpp) [Seleccionar] Expandir


int lector_de_opciones(int valor_maximo)
{
    int valor_elegido=0;
    cout << " Introduce un numero entre 1 y " << valor_maximo;
    valor_elegido = lector_de_enteros();
     
    while ( valor_elegido <=1 && valor_elegido >= valor_maximo ) {
    {
        cout << "Vuelve a introducir un numero que este dentro del rango, por favor:\n";
        valor_elegido = lector_de_enteros();     // <-- correccion
    }
     
    return valor_elegido;
}

Entiendo el planteamiento al respecto del algoritmo de Floyd, investigaré y posiblemente publique un post al respecto.

Por los momentos estoy terminando algunos detalles que faltaban al programa inicial, pues sabes, un trabajo no está completo hasta que está completo, jejeje

Y sobre todo ayudar a un par de lectores que tenían dudas de este tema en particular, espero que este aporte les disipe al respecto.

Sólo como un comentario, que me parece muy interesante el tema, una manera muy práctica de manejar menús.

Y por supuesto, la sugerencia de ivancea es la apropiada  para el problema planteado, es lo que se hace para manejar funciones con número variable de argumentos.

[Bibliotecas y prototipos]

Ahora sí que sí, ya lo pude terminar jajaja 

El inicio de estre post me referí a un programa que emplea el algoritmo de Dijkstra para calcular la ruta más económica entre dos puntos de un grafo no dirigido. La versión inicialmente publicada fue en C++. Ahora voy con una vesión completamente en C, que además implementa una cola de prioridad para seleccionar más eficientemente el nodo objetivo a analizar en cada ciclo del algoritmo.

El principio es sencillo. Inicialmente la cola contiene únicamente al nodo inicial del grafo. Seguidamente se analizan todos los sucesores (no marcados) del nodo objetivo, y se evalúa o re-evalua su coste, y se coloca ordenadamente como corresponda en la cola de prioridad. La cola siempre permanece ordenada según el coste del nodo, de menor a mayor, puesto que cuando se inserta un nuevo elemento se lo hace en el lugar que corresponde según su valor.

En el caso que un nodo al ser re-evaluado disminuye o mejora su coste, entonces debe ser reubicado en la cola. Para ello, lo que hacemos es retirarlo de la cola y luego reinsertarlo en la posición adecuada.

Luego de ésto, el nodo objetivo es "marcado" y por lo tanto sacado de la cola puesto que no volverá a ser analizado en ejecuciones posteriores del algoritmo.

La versión a C se logró simplemente cambiando algunos "cout" a "printf()", y reemplazando el típico new/delete de C++ por el malloc()/free() de C. Lo que fue un poquito más complicado fue tener que implementar "manualmente" una cola de prioridad en C, porque no podemos usar la clase stack de la STL de C++.

A continuación el programa como quedó, y advierto que ahora si creció un poco superando las 300 líneas por eso lo voy a dividir por partes. Recomiendo leer con atención la función insert() que se ocupa de agregar un elemento a la cola según el coste del número de nodo indicado.

Espero con esto haber disipado las dudas de algunos de los lectores de mi tema, y cualquier sugerencia o recomendación no duden en escribir

Bibliotecas y prototipos

Código (cpp) [Seleccionar] Expandir


/* Programa que utiliza el algoritmo de Dijsktra para encontrar el
* camino más corto o económico entre dos puntos de un grafo
* no dirigido.
*/

#include <stdlib.h>
#include <stdio.h>

/* Definiendo la estructura etiqueta de nodo. Sus campos incluyen
* el n'umero 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 */
};
typedef struct label label_t;

/* Cola de Prioridad de n'umeros de nodo */
struct node {
int data;
struct node * nextPtr; /* apuntador al siguiente nodo de la cola */
};
typedef struct node node_t;

int isEmpty( node_t * ); /* decide si cola es vac'ia */
int insert( node_t **, int, label_t * ); /* agrega un nodo ordenadamente a la cola */
void quit( node_t **, int ); /* retira un nodo espec'ifico de la cola */
int pop( node_t ** ); /* retira el primer nodo de la cola */
void printQueue( node_t * ); /* imprimir los valores almacenados en la cola */

/* Funci'on que calcula la distancia m'inima de cualquiera de los
* nodos al primero */
void dijkstra( int, int **, int, int );

Función MAIN , simplemente crea la matriz de adyacencia y llama al Dijkstra

Código (cpp) [Seleccionar] Expandir


int main () {

int i, j;

/* cantidad total de nodos */
int numNodos = 8;

/* Definiendo la matriz de adyacencia */
int **A;
if ( ( A = (int **) malloc( numNodos * sizeof(int *) ) ) == NULL ) return 1;
for ( i = 0; i < numNodos; i++ )
if ( ( A[i] = (int *) malloc( numNodos * sizeof(int) ) ) == NULL ) return 1;

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 */
printf( "Matriz de adyacencia:\n\n" );
for ( i = 0; i < 8; i++ ) {
for ( j = 0; j < 8; j++ )
printf( "%2d  ", A[i][j] );
printf( "\n" );
}
printf( "\n" );

/* calcular dijkstra a partir del nodo 0, a partir del nofo 7 */
dijkstra( numNodos, A, 0, 7 );

/* liberar memoria */
for ( i = 0; i < numNodos; i++ )
free( A[i] );
free( A );

return 0;
}

Algoritmo de Dijsktra

Código (cpp) [Seleccionar] Expandir


/* Calcula el coste m'inimo 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 */

node_t *Cola = NULL; /* cola de prioridad */

/* Crea din'amicamente el arreglo de etiquetas de nodo */
if ( ( Labels = malloc( N * sizeof( label_t ) ) ) == 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;
}
}

/* agregamos el nodo inicial como primer elemento de la cola */
insert( &Cola, a, Labels );

/* continuamos este ciclo mientras existan nodos en la cola */
while ( !isEmpty( Cola ) ) {

/* toma como objetivo el primer elemento de la cola de prioridad */
i0 = pop( &Cola );

printf( "*** Analizando nodo %d ***\n", i0 );

/* actualiza el peso de todos los sucesores no marcados (si los hay) del nodo
* encontrado y luego se~nala dicho nodo como marcado */
for ( i = 0; i < N; i++ ) {
if ( A[i0][i] > 0 && Labels[i].marca == 0 ) {
/* si el coste es infinito, actualizar y añadir a la cola */
if ( Labels[i].peso == -1 ) {
Labels[i].peso = Labels[i0].peso + A[i0][i];
insert( &Cola, i, Labels );
}
/* si el coste acumulado sumado al coste del enlace del nodo i0 al nodo i
* es menor al coste del nodo i, actualizar al valor del costo menor y
* reubicar en la cola */
else if ( Labels[i0].peso + A[i0][i] < Labels[i].peso ) {
printf( "   * advertencia: mejorando coste de nodo %d\n", i );
Labels[i].peso = Labels[i0].peso + A[i0][i];
quit( &Cola, i ); /* para reubicar, quitamos y luego a~nadimos el nodo */
insert( &Cola, i, Labels );
}
Labels[i].prev = i0;
printf( "   coste de nodo %d desde nodo %d: %d\n", i, i0, Labels[i].peso );
}
}
Labels[i0].marca = 1;
printf( "   * nodo %d marcado\n", i0 );

/* para verificar, imprime los costes calculados hasta el momento */
for ( i = 0; i < N; i++ ) {
printf( "%d: [", i);
if ( Labels[i].peso == -1 ) printf( "Inf" ); else printf( "%d", Labels[i].peso);
printf( ", %d", Labels[i].prev );
if ( Labels[i].marca == 1 ) printf( ", x]\n" ); else printf( "]\n" );
}

/* imprimir cola prioridad de nodos */
printf( "cola de nodos en orden de prioridad es:\n" );
printQueue( Cola );

/* pausa (opcional) */
printf( "\npresione ENTER para continuar ..." );
getchar();
}
printf( "Ya no quedan nodos por analizar.\n" ); /* mensaje final */

/* Ruta desde el nodo 'a' hasta el nodo 'b' */
int longitud = 2;
i = b;
while ( ( i = Labels[i].prev ) != a ) longitud++; /* primero estimamos la longitud de la ruta */
if ( ( ruta = malloc( longitud * sizeof(int) ) ) == NULL ) return;

ruta[longitud - 1] = b; /* luego rellenamos */
i = b;
j = 0;
for ( j = 1; j < longitud; j++ ) {
i = Labels[i].prev;
ruta[longitud - j - 1] = i;
}

printf( "================================================================\n" );
printf( "\nRuta mas economica entre nodo %d y nodo %d:\n\n", a, b );
for ( i = 0; i < longitud; i++ ) {
printf( "%d", ruta[i]);
if ( i < longitud - 1 ) printf( " - " );
}
printf( "\n\nCosto total: %d\n\n", Labels[b].peso );

free( ruta );
free( Labels );
}

Métodos asociados a la cola de prioridad

Código (cpp) [Seleccionar] Expandir


/* Devuelve 1 si la cola está vacía, 0 si no lo está. */
int isEmpty( node_t * head ) {

return head == NULL;
}

/* Insertar ordenadamente en la cola.
* Devuelve 0 si terminó con éxito, y 1 si ocurrió un error
* de asignación de memoria. */
int insert( node_t ** frontPtr, int nodeNumber, label_t * Labels ) {

node_t *newPtr, *currentPtr, *prevPtr;

if ( ( newPtr = malloc( sizeof( node_t ) ) ) == NULL ) return 1;

/* busca el último nodo menor al que se quiere insertar */
currentPtr = *frontPtr;
prevPtr = NULL;
while ( currentPtr != NULL && Labels[currentPtr->data].peso < Labels[nodeNumber].peso ) {
prevPtr = currentPtr;
currentPtr = currentPtr->nextPtr;
}

/* inserta el nuevo nodo */
newPtr->data = nodeNumber;
if ( currentPtr != NULL )
newPtr->nextPtr = currentPtr;
else
newPtr->nextPtr = NULL;

if ( prevPtr != NULL )
prevPtr->nextPtr = newPtr;
else
*frontPtr = newPtr;

return 0;
}

/* Remover de la cola el nodo con el valor específico, si lo encuentra */
void quit( node_t ** frontPtr, int data ) {

node_t *prevPtr = NULL, *currPtr = *frontPtr;

/* busca el nodo con el valor espec'ifico */
while ( currPtr != NULL && currPtr->data != data ) {
prevPtr = currPtr;
currPtr = currPtr->nextPtr;
}
if ( currPtr == NULL ) return; /* y termina si no encuentra */

/* si encuentra el nodo, lo remueve */
if ( prevPtr != NULL )
prevPtr->nextPtr = currPtr->nextPtr;
else
*frontPtr = currPtr->nextPtr;

free( currPtr );
}

/* Retirar el primer elemento de la cola.
* Precaución: Devuelve cero si la cola est'a vacía.
*/
int pop( node_t **frontPtr ) {

node_t *auxPtr;
int data;

if ( *frontPtr != NULL ) {
auxPtr = *frontPtr;
*frontPtr = (*frontPtr)->nextPtr;
data = auxPtr->data;
free( auxPtr );
return data;
}
else
return 0;
}

void printQueue( node_t *queue ) {

node_t *currPtr = queue;

if ( currPtr == NULL ) {
printf( "(vacio)\n" );
return;
}

while ( currPtr != NULL ) {
printf( "%d", currPtr->data );
if ( currPtr->nextPtr != NULL ) printf( " -> " );
currPtr = currPtr->nextPtr;
}
printf( "\n" );
}

Hola sabee

Las cadenas en C son arrays, es decir, arreglos, vectores, de elementos del tipo char. Es decir, las cadenas como tal no existen como tipo de dato básico de C, lo que existen son los caracteres, y las cadenas son arreglos o vectores de caracteres.

Para declarar una cadena en C puedes usar cualquiera de las formas:

Código (cpp) [Seleccionar] Expandir


char str[];
char *str;

donde la primera declara un arreglo de char, y la segunda declara un apuntador a tipo char, ya que en C los arreglos son también apuntadores, pero es otro tema de discusión ...

También se pueden hacer declaraciones donde se inicialice directamente el contenido:

Código [Seleccionar] Expandir


char str[] = "hola mundo";
en la que automáticamente el compilador calcula la cantidad de espacio necesario en el array para albergar la cadena respectiva.

Ten en cuenta que toda cadena en C debe estar terminada por un carácter especial llamado "nulo", simbolizado por '\0'. Esto demarca el fin de la cadena, y por lo tanto la cantidad de espacio de memoria asignado a la cadena. De otro modo, si no se encontrara el fin de cadena, la misma abarcaría consecutivamente todos los bytes de memoria hasta invadir un área prohibida de la misma e incurriendo en lo que se llama violación de segmento.

Por esta razón siempre debes sumar un byte adicional al reservar espacio para tu cadena. Por ejemplo la cadena "hola" ocupa físicamente 5 bytes de la memoria, es decir 4 bytes más el nulo de terminación:

Código [Seleccionar] Expandir


'h'  'o'  'l'  'a'  '\0'

Igualmente,  si una cadena tendrá n caracteres de longitud, debes declarar un arreglo de longitud n+1. Si la cadena msg deberá contener 100 caracteres como máximo entonces se declara:

Código [Seleccionar] Expandir


char msg[101];
y así sucesivamente.

==================================================================
Dos funciones útiles de la biblioteca estándar de C para manipulación de cadenas (<string.h>) son strlen() y strcpy(). La primera calcula la longitud de la cadena, y la segunda copia el contenido de una cadena en otra (suponiendo que la cadena destino posee el espacio disponible suficiente). Ejemplos:

Código (cpp) [Seleccionar] Expandir


char str1[21];
char str2[22];

strcpy( str1, "soy una cadena");
printf( "str1 es: %s\n", str1 );
printf( "longitud de str1 es: %d", (int) strlen(str1) );
strcpy( str2, "soy otra cadena" );
printf( "str2 es: %s\n", str2 );
strcpy( str1, str2 );        /* copia str2 en str1 */
printf( "ahora str1 es: %s\n", str1 );


=========================
Espero haberte ayudado en una introducción al tema, cualquier cosa preguntas 

Voy a trabajar pronto en una versión completamente en C, que implemente cola de prioridad

Te puedo ayudar, pero escríbeme por favor un txt a mano con la apariencia EXACTA que quieres lograr. Puede ser con sólo tres meses a manera de modelo a seguir. Lo subes a drobpox o algún sitio similar y así lo podemos ver y analizar.

Es difícil darte una pista más específica de cómo seguir sin tener claro el resultado exacto que producir.

Saludos, y espero por tu respuesta.

Mmmm, se parece al programa que tiene el gobierno de Venezuela (mi país) con equipos llamados "Canaima", y un SO que dicen propio pero me parece más un clon de Ubuntu y encima sin dar los créditos, ......., en fin así son los políticos.

Sí, trato de ayudar a los que puedo y sería un honor recibir el título de Colaborador, aunque no conozco los requisitos necesarios para ello.

Y aunque no lo parezca, ayudando también se gana, he aprendido mucho respondiendo las preguntas aquí en el foro 

Saludos!

[en C los arreglos comienzan con el índice 0]

Hola furciorita

La idea sería más o menos seguir los siguientes pasos

1.) Recibir a, b, c, d, m, n del teclado. ( Si m > n dar mensaje de error ).
2.) Inicializar r = m. Calcular f(m) e inicializar p = f(m).
3.) Inicializar s = m. Inicializar q = f(m) (ya calculado en el anterior)
4.) Luego en un ciclo, desde x = m + 1 hasta x = n:
     4.1  Si f(x) > p, hacer p = f(x), y hacer también r = x
     4.2  Si f(x) < q, hacer q = f(x), y hacer también s = x

La idea es que p conserve el valor máximo y q el mínimo de los valores evaluados. Si hallas un f(x) mayor que el valor actual de p, entonces p se actualiza a este nuevo valor máximo. Similar lógica respecto al mínimo q.

Luego de recorrer desde x = m + 1 hasta x = n, tendrás los valores p, q, r, s como se pide.

Ah, y recuerda que en C los arreglos comienzan con el índice 0, no el índice 1.

=================================================
Por cierto, la función eval() que defines pareciera querer implementar el llamado "método de Horner" para evaluación de polinomios. Supongo que a[0] representa el coeficiente de menor grado, mientras que a[3] es el de mayor. Pero creo que en este caso está mal implementado, debería ser como:

Código (cpp) [Seleccionar] Expandir


int eval( int a[], int x ) {
    int aux = 1;      /* no aux = 0 !!! */
    int i;

    for ( i = 3; i > 0; i-- )
        aux  = a[i] * aux + a[i-1];

    return aux;
}

Recuerda que en C los arreglos comienzan con el índice 0, por lo tanto el recorrido del vector es desde i=0 hasta i=3, no desde i=1 hasta i=4.

Con todo esto creo que ya puedes terminar tu programa, o al menos encaminarte a ello.

Bueno marrison, si es para C la verdad es que no tienes mucho que cambiar. Tuve cuidado al elaborar el código de modo que fuera en su mayor parte compatible con C.

Lo único que tendrías que adaptar en la gestión dinámica de memoria para los arreglos que se crean en tiempo de ejecución. O sea, el uso de malloc(), realloc() y free(), en lugar de la combinación new y delete de C++.

De todos modos voy a ver si en estos días tengo un tiempo y versiono el código completamente a C.

Y un detalle, en el algoritmo que propuse falta implementar una "cola de prioridad", que puede optimizar la ejecución. En esta cola se van guardando los nodos en función de su peso, colocando de primero los de menor coste. De esta manera no hay que calcular el mínimo con cada ciclo, puesto que dicho nodo más económico siempre de está de primero en la cola y sólo hay que cogerlo de allí.

Un saludo ...