Ejercicio usando Colas en C++

[RGT]

Hola amigos,
Resulta que tengo que hacer esto:

Escriba un programa para ejecutar el experimento siguiente:
Genere 100 números aleatorios con valores en el rango entre 1 y 500. Conforme se genera cada número, insértelo en una cola inicialmente vacía. Si el número es de dos dígitos, tiene prioridad sobre números de tres dígitos.

Después de insertar los 100 números, imprima en orden secuencial las posiciones de la cola donde se encuentra el número con mayor valor y el número con menor valor.

Nunca hemos trabajado usando Colas, no entiendo cómo uno puede aprender de esta manera pero bueno, venga...

He investigado cómo crear una Cola y crear los números aleatorios.

Código:

Código:

#include <iostream>
#include <stdlib.h>     // Librería para usar la función srand()
#include <time.h>       // Librería para usar la función time()

using namespace std;

//Declaraciones de tipos para manejar colas en C++
typedef struct _nodo {
   int dato;
   struct _nodo *siguiente;
} tipoNodo;

typedef tipoNodo *pNodo;
typedef tipoNodo *Cola;

int main()
{
    //Declaración de variables
    int i, Numero;
    srand(time(NULL));

    //Procesamiento
    for(i = 1; i <= 100; i++)
    {
        Numero = 1 + rand() % (501 - 1);
        cout << Numero << endl;
    }

    return 0;
}

Screenshot:


Vamos bien, ahora la pregunta es:

• Cómo inserto los números en la Cola?.
• Cómo es eso de prioridad?.
• Cómo hago para que el número de dos dígitos se guarde antes que los de tres dígitos?

Bueno, nunca había visto Colas, espero puedan ayudarme, gracias.

[xKuZz]

Tanto la cola (queue), como la cola con prioridad (priority_queue) son tipos de datos ya existentes en STL, si es que te dejan usarla.

http://www.cplusplus.com/reference/queue/queue/.

http://www.cplusplus.com/reference/q...riority_queue/.

Una cola es una estructura de datos FIFO (First In First Out), es decir que el primero que entre a la cola es el primero que debe de salir.

Una cola con prioridad es una cola en el que existen un valor asignado a cada dato al que denominamos prioridad que nos indica si el elemento debe salir antes, en este caso no nos fijamos en si un elemento tiene más prioridad que otro y, dependiendo del propio diseño que hagas aunque puede ser FIFO o no.

Veamos tu problema en concreto ahora:

a) La prioridad queda definida por:
1-Tiene más prioridad aquel elemento que tenga un menor número de dígitos.
2-En caso de tener igual número de dígitos el menor en el orden usual de los números naturales es el que saco.

En conclusión, tendrás que utilizar una estructura de datos que conozcas y creas eficiente para el uso en la que vas a tener que añadir los elementos uno detrás de otro y tendrás que sacarlos teniendo en cuenta las restricciones de prioridad. El que debes de sacar siempre es el que tenga la mayor prioridad.

Saludos.

[RGT]

Hola, gracias por tratar de ayudarme bro.

Leyendo la documentacion, realmente no entiendo mucho.
Nunca habia visto este tema y estoy muy confundido. Ni siquiera por que es util esto de Colas. Leyendo en internet solo veo cosas ya hechas, no hay explicaciones....

Lo que me dices que debo de hacer lo entiendo, pero como?, no se ni por donde empezar.

[aguml]

Para mi opinión el profesor va muy rápido y no os explica las cosas lo suficiente. En la programación tienes que tener las cosas muy claras y asimilarlas bien y tu hace unos días preguntabas cosas muy básicas y ¿ya estas con las colas? ¿mañana que serán los arboles?

[xKuZz]

Por curiosidad, ¿en qué asignatura te han pedido que hagas esto?.

Vamos al lío, obviamente tienes dos opciones, que más que depender de ti dependerán probablemente del profesor.

1) Utilizo priority_queue de la STL, eso implica que al menos debes comprender como funciona cada uno de sus métodos y saber crear y usar un functor.

2) Utilizo mi propia estructura. Eso implica plantearse las siguiente preguntas.

¿Para mi problema necesito usar memoria dinámica?
En caso afirmativo, o creo mi propia estructura de datos o utilizo una se la STL que ya conozca. En caso negativo puedo utilizar un simple array C.

¿En qué consiste una cola con prioridad?
Una cola con prioridad es aquella en la que debe salir antes el elemento que tenga asignada la mayor prioridad.

¿En qué orden almaceno los elementos?
No tienen por qué estar ordenados, es una cuestión de diseño. Puedes tenerlos organizados en memoria al insertarlos en la estructura o tenerlos desordenados y buscar el que más prioridad tiene al sacarlos.

¿Cómo obtengo la prioridad de un elemento?
Para ello crearás una función que se encargue de la relación de orden prioridad para el problema. Por ejemplo, en el caso dado, crearás una función que devolverá true si cumple los requisitos dados para que el primer argumento sea menor que el segundo, es decir que o bien el primer argumento tenga más dígitos que el segundo o en caso de que tengan los mismos devolverá true si el primero es menor que el segundo.

Por tanto, para cumplir los requisitos dados, tus estructura debería contar AL MENOS con las siguientes funciones para ser una cola con prioridad.

Elementos ordenados en memoria (al insertar)
1- Función de prioridad
Dados dos valores a y b, ambos enteros, devolverá si prioridad(a) < prioridad(b).

2- Función de inserción en cualquier posición de la estructura
Esta función implica que no debe existir ningún problema para introducir un dato en cualquier lugar de la estructura.
a) Busco la posición en la que debo introducir el dato según la PRIORIDAD. Mirar algoritmos de búsqueda binaria (preferible porque es más eficiente) y búsqueda secuencial (más fácil pero menos eficiente) en caso de no conocerlos.
b) Una vez encuentro la posición inserto el dato.

3- Función de devolución/borrado al principio o final
Dependiendo de si al insertar de como hayas ordenado implicará
a) Si ordenaste de menor a mayor prioridad eliminarás siempre el último elemento.
b) Si lo hiciste de mayor a menor eliminarás siempre el primero.
En este método puedes devolver el valor de la posición, o crear otro método aparte
para devolver el dato antes de borrarlo.

Elementos no ordenados en memoria
1- Función de prioridad (Mirar arriba)

2- Función de inserción
En este caso te basta con poder insertar en una posición como la del principio o la del final, no tiene porque ser una posición del centro.

3- Función de devolución/borrado en cualquier posición
Deberás recorrer secuencialmente toda tu estructura con el fin de encontrar el máximo para la relación de prioridad. Ese elemento será el que borraremos, igual que antes puedes devolverlo en una función o en esta misma.
Nota: En caso de que separes los métodos de devolver el dato y borrarlo, recuerda que debes de devolverlo antes de borrarlo, que aunque suene obvio, a mucha gente se le pasa por alto.

Aunque sea mucho texto, no te asustes, es algo que no es difícil pero he intentado dejarte los conceptos lo más claros que he podido. Saludos.

[RGT]

Iniciado por aguml

Para mi opinión el profesor va muy rápido y no os explica las cosas lo suficiente. En la programación tienes que tener las cosas muy claras y asimilarlas bien y tu hace unos días preguntabas cosas muy básicas y ¿ya estas con las colas? ¿mañana que serán los arboles?

Pues mi profesor es loco, no explica nada y hemos hecho muchas cosas y he logrado resolverlas, menos estos temas que he preguntado en el foro :(

La verdad no entiendo como la universidad espera que uno aprenda a programar de esa manera.

[RGT]

Vale xKuZz... leere mas sobre lo que mencionaste y me pongo a tirar codigo a ver que me sale..

[eferion]

Iniciado por RGT

La verdad no entiendo como la universidad espera que uno aprenda a programar de esa manera.

Yo antes de la universidad pasé por FP... y el segundo año había que hacer dos "proyectos" para poder finalizar el curso. Uno de estos proyectos tenía que servir para montar una emisora de televisión operativa, con platós, cámaras, sistemas móviles... Esto incluía mirar equipos que ni sabías que existían, mapear todas las conexiones que había que realizar para conectarlos entre sí y que aquello funcionase, analizar requisitos de consumo eléctrico, diseñar un sistema de evacuación (claro, también había que incorporar nuestros conocimientos de riesgos laborales), etc.

Nuestro conocimiento previo sobre todo el tema tendía en el mejor de los casos a 0 y los proyectos al final salieron adelante.

Lo que tienes que aprender de ese profesor es a buscarte la vida. Si la universidad consistiese en aprenderse los apuntes de clase no sería muy diferente del bachillerato y se aprobaría con la gorra...

[RGT]

Hola amigos, gracias a la documentación en la web oficial de C++, he logrado esto:

Código:

#include <iostream>
#include <stdlib.h>     // Librería para usar la función srand()
#include <time.h>       // Librería para usar la función time()
#include <queue>        // Librería para el uso de priority_queue
#include <vector>       // Librería para el uso de vectores (Arreglos Dinámicos)

/*
    Escriba un programa para ejecutar el experimento siguiente:

    1. Genere 100 números aleatorios con valores en el rango entre 1 y 500.

    2. Conforme se genera cada número, insértelo en una cola inicialmente vacía.

    3. Si el número es de dos dígitos, tiene prioridad sobre números de tres dígitos.

    4. Después de insertar los 100 números, imprima en orden secuencial las posiciones
    de la cola donde se encuentra el número con mayor valor y el número con menor valor.
*/

using namespace std;

int main()
{
    //Declaración de variables
    int i, Numero;
    srand(time(NULL));

    priority_queue<int> numero_aleatorio;

    //Procesamiento
    for(i = 1; i <= 100; i++)
    {
        //Generamos un número aleatorio del 1 al 500
        Numero = 1 + rand() % (501 - 1);

        //Guardamos el número generado
        numero_aleatorio.push(Numero);
    }

    while (!numero_aleatorio.empty())
    {
        cout << numero_aleatorio.top() << ", ";
        numero_aleatorio.pop();
    }

    return 0;
}

El ejercicio casi esta resuelto.

Lo único que no tengo ni idea de como hacerlo es de imprimir las posiciones del numeros mayor y del numero de menor valor, segun dice el ejercicio.

Alguien puede ayudarme?.

[xKuZz]

Para utilizar priority_queue y poner una relación de prioridad personalizada debes pasar al template (Linea 22 de código 1)como primer argumento el tipo de dato, como segundo argumento un contenedor de ese tipo de dato (en este caso uso un vector no olvides #include<vector>) y como tercer argumento el functor.

Te voy a mostrar la alternativa clásica y una versión C++11 de tu código para que veas y compares diferencias. Si no entiendes nada de C++11 te costará entender el segundo código.

¿Qué es un functor?
Es una objeto (instancia de clase) que actúa como una función. La principal ventaja que tienen es que al ser una clase pueden almacenar un estado. La STL los utiliza mucho y para crear uno lo que debes de hacer es una clase en la que esté sobrecargado el operador paréntesis.

Como siempre esto se ve mejor con un ejemplo. Para que sea sencillo voy imprimir una secuencia de enteros. En mi caso va a tener menos prioridad el que sea mayor en el orden usual. Es decir que saldrá antes el número más chico.

Código C++:

#include <queue>
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <vector>
using namespace std;
 
class prioridad { // Implementamos el functor
    public:
        bool operator()(const int &a, const int &b){
        // Aquí va la función de prioridad.
        return a>b; // Tengo menos prioridad si soy un entero mayor
        }
};
 
int main(){ // Para no liarte reutilizo tu código
    //Declaración de variables
        int i, Numero;
        srand(time(NULL));
 
        // MIRAR AQUI: TERCER ARGUMENTO PASAMOS EL FUNCTOR
        priority_queue<int,vector<int>,prioridad> numero_aleatorio;
 
        //Procesamiento
        for(i = 1; i <= 100; i++)
        {
            //Generamos un número aleatorio del 1 al 500
            Numero = 1 + rand() % (501 - 1);
 
            //Guardamos el número generado
            numero_aleatorio.push(Numero);
        }
 
        while (!numero_aleatorio.empty())
        {
            cout << numero_aleatorio.top() << ", ";
            numero_aleatorio.pop();
        }
}
 

En C++11 tienes otras opciones como las lambdas (tienes sus ventajas y sus incovenientes), si por cualquier casualidad sabes usarlas aquí tienes un ejemplo:

Código C++:

#include <random>
#include <queue>
#include <iostream>
 
#include <vector>
using namespace std;
 
int main(){
        // Generador de enteros aleatorios del 1 al 500
        default_random_engine aleatorio;
        uniform_int_distribution<int> entero(1, 500);
 
        // Creamos la lambda que define la prioridad
        auto prioridad= [] (const int &a, const int &b) {
                                     return a>b;
                            };
        // Por lo que podría llamarla así
        priority_queue<int,vector<int>,decltype(prioridad)> cola(prioridad);
 
        // También puedes declarar variables locales al bucle tal que
        // (para eso no hace falta C++11)
        
        for(int i = 0; i < 100; ++i)
            cola.push(entero(aleatorio)); // Añado a la cola enteros aleatorios entre 1 y 500
 
 
        while (!cola.empty())
        {
            cout << cola.top() << ", ";
            cola.pop();
        }
}
 

[RGT]

Hola hermano, te hare una pregunta, por qué se guardan ordenados de mayor a menor o viceversa?, hay forma de que se guarden aleatorios y luego yo al final buscar el mayor, el menor y sus posiciones?.

[xKuZz]

El motivo por el que los introduce ya ordenados es porque utiliza un heap (también conocido como lund, o montículo en español y eso es un árbol binario que representa a un conjunto ordenado, en este caso la relación de prioridad, y el padre siempre es mayor siguiendo dicha relación que los hijos y los hijos menores que el padre dicho brevemente. Para saber más sobre el tema pídele ayuda a tu buscador favorito).

Utilizar esto implica conocer dicha relación de orden desde el principio. Traducido a eficiencia eso quiere decir que las operaciones son:

O(1) para top(), size(), empty()
O(log n) para push(x), pop().

Por lo que como puedes ver realiza sus operaciones de manera muy eficiente. Por si no te habías dado cuenta, cuando no hay una función de prioridad definida al crear la cola automáticamente coge el operador menor para el tipo de datos que existe. De hecho si no existiese el operador menor para int te habría dado un error en tiempo de compilación.

En conclusión:
a) No le tengas miedo a hacer functores, hay varias maneras, cada cual con su ventajas y sus inconvenientes, la más usual es la primera que te he puesto, no es para nada complejo familiarízate con ella y con la STL, porque si sigues con C++ en la universidad, créeme que te hará mucha falta saber usar ambos con soltura y suele ser más eficiente que hacer la implementación nosotros mismos.

b) Si realmente necesitas hacerlo de otra manera, utiliza otra estructura de datos como el vector, deque, la que veas conveniente para solventar el problema de la manera que quieres, o incluso reutiliza alguna que hayas creado en el pasado, pero no priority_queue.

[aguml]

No me equivoque mucho cuando dije que si lo proximo seria los arboles jajaja.
Estoy un poco desacuerdo con lo que opina eferion. Esta bien que te enseñen a buscarte la vida pero si te estan enseñando no creo que sea normal que te digan que te busques la vida y no te expliquen nada de nada.
Imagina un estudiante de medicina que sin haber ni abierto el libro le digan que se busque la vida y que opere a corazon abierto. Por lo menos la teoria se la tendrian que explicar antes para saber como actuar y buscarse la vida desde ahi.

[xKuZz]

Yo actualmente curso 2º de la carrera, tengo 19 años, salido de bachillerato y en mi clase de Estructuras de Datos, yo todavía no he tocado lo que es una priority_queue, pero he sabido explicarle todo eso porque este verano a la vez que estudiaba mis asignaturas para septiembre (vivan las matemáticas jeje) me puse a ver las asignaturas que iba a tener este cuatrimestre y empezar y a buscarme la vida antes de empezar el curso, por que sabes que aunque te expliquen en clase las cosas el tiempo que dura un cuatrimestre y toda la materia que se supone que debes de aprender requiere de muchas horas de trabajo personal.

El hecho de que en la universidad te fuercen mucho más a buscarte la vida, yo pienso que es una ventaja para el futuro por que el día de mañana cuando trabajes en cualquier empresa es muy posible que tengas resolver problemas que en tu vida se te habrían ocurrido. Los árboles los estudié el año en mi asignatura de lógica y métodos discretos (sólo lo matemático nada de programación) y cuando leyendo bibliografía este verano y trabajando con ella no tuve ningún problema en comprenderlo. Existen miles de recursos en la web, los que utilizamos parte de nuestro tiempo libre en resolver dudas en lugares como este foro, una bibliografía impresionante en la biblioteca de tu universidad y siempre puedes pedirle tutoría a tu profesor (o a otro). La única persona que limita el proceso de aprendizaje es uno mismo.

[eferion]

Iniciado por aguml

Estoy un poco desacuerdo con lo que opina eferion. Esta bien que te enseñen a buscarte la vida pero si te estan enseñando no creo que sea normal que te digan que te busques la vida y no te expliquen nada de nada.

Que conste que no he justificado al profesor. Su deber es enseñar y claro está es una premisa que no está cumpliendo.

Lo que sucede es que dependiendo de la forma en que afrontes estos problemas puedes sacar desilusión o un montón de experiencia... puedes optar por culpar al profesor porque no enseña nada (en lo cual tendrías toda la razón del mundo) o puedes lanzarte a la aventura e ir aprendiendo por tu cuenta partiendo de lo poco que te han mostrado en clase. Este camino te demostrará que eres capaz de cosas que ni siquiera te habías imaginado y te aportará bastante seguridad a la hora de afrontar nuevos retos.

La diferencia entre ambos caminos es abismal teniendo en cuenta que el punto de partida es el mismo.

Un saludo.