[Duda] Creación de un programa que calcule la moda

[Denok]

Hola de nuevo, he de hacer un programa que encuentre la palabra mas frecuente dentro de cada secuencia de palabras dada y en caso de empate tengo que escribir la palabra mas grande alfabéticamente.

Este es el enunciado, pero no tengo la mínima idea de por donde cogerlo y empezar ha programar, no tengo ningún código.

Mi idea inicial era crear un vector auxiliar donde guardar la frecuencia de cada palabra, es decir, cada vez que me entra una palabra, mirar su posición y sumarle uno, pero no me sirve la idea ya que si el vector es de palabras no lo puedo usar como contador, y tampoco se como, por ejemplo, crear un vector aparte y asignarle a cada posición el contador de una palabra(no se si me explico... xD).

Necesito alguna idea para plantear bien el problema.

Muchas gracias!.
Adiós.

[PiroskY]

2 vectores dinamicos uno para las palabras y otro para la cantidad de veces que aparece

Cada vez que leas un espacio agarras la siguiente palabra, te fijas si aparece en el vector de palabras.
Si la palabra esta en el vector de palabras; en el vector de contadores sumas uno en la posicion donde encontraste la palabra en el vector de palabras.
Si la palabra no esta en el vector de palabras; pedis una nueva variable para meter esa palabra, y en el vector de contadores tambien pedis una nueva variable, y le pones 1.

[Denok]

La idea es muy buena, gracias.
Este es el código que he creado( le he añadido dos condiciones que faltaban en el enunciado, que son que si es 0 el numero de palabras se pare el programa, i un while para utilizarlo las veces que quiera.

Código (cpp) [Seleccionar] Expandir


#include <iostream>
#include <vector>
using namespace std;

int main(){
    int n;
    bool final = false;
    while(cin >> n and not(false) ){
        if(n == 0) final = true;
        else {
            bool paraula = false;
            vector<string> paraules(n);
            vector<int> cont(n);
            for(int i = 0; i < n; ++i){
                string s;
                cin >> s;
                for(int j = 0; j <= i; ++j){
                    if(paraules[j] == s){
                        ++cont[j];
                        paraula = true;
                    }
                }
                if(not(paraula)){
                    paraules[i] = s;
                    ++cont[i];
                }
            }

            int max = 0;
            for(int i = 0; i < n; ++i){
                if(cont[i] > max)
                    max = cont[i];
            }
            cout << paraules[max];
        }
    }

}

Me compila bien pero cuando lo ejecuto no pasa nada, y nose porque.

Alguna idea ?

Gracias y adios!.

[ghastlyX]

Esa opción es demasiado lenta. No se si estarás puesto en complejidad, pero vamos a analizar la de ese algoritmo. Voy a asumir que comparar strings se hace en tiempo constante, cosa que tampoco es cierta, pero no es lo que limita la velocidad.

Para cada palabra de la entrada (n en total) buscas en un vector de las palabras que han salido anteriormente dicha palabra. Supongamos que lees la palabra i-ésima. En caso peor, en el vector de palabras tendrás i - 1 palabras (es decir, hasta ahora todas son diferentes). En el peor de los casos, la nueva palabra no estará tampoco, por lo tanto harás i - 1 comparaciones. Consideremos entonces las comparaciones que harás en caso peor: 0 la primera palabra, 1 la segunda, 2 la tercera, ..., n - 1 la última. Esto suma n(n - 1)/2, que asintóticamente (muy informalmente significa considerando sólo la mayor potencia e ignorando la constante que la multiplica) es equivalente a n².

En el enunciado te dicen que n es como mucho 10⁵ (las restricciones de la entrada son casi lo más importante en un problema de programación, debes tenerlas muy en cuenta y si pides ayuda dilas también). Por lo tanto, con ese algoritmo serían unas 10¹⁰ operaciones, que es demasiado. Típicamente, un código es rápido si hace unas 10⁷ o 10⁸ (si son 10⁸, en general en los jueces online muchas veces ya da Time Limit) operaciones como mucho (siempre habrá que tener en cuenta el tipo de operaciones, no es lo mismo hacer raíces cuadradas que sumas).

Para este problema, una solución sencilla se puede hacer con coste nlogn. Si lees las palabras, las guardas en un vector y lo ordenas, es evidente que palabras iguales irán seguidas. Por lo tanto, bastará hacer una pasada al vector y contar cuántas seguidas iguales hay para cada palabra, puesto que ese número será el número de apariciones totales de la palabra por estar el vector ordenado.

[Denok]

Vaya pues si que seria lento el programa si.
Y cierto, me olvide de poner la restricción en la entrada.
Pero una cosa Ghastlyx, si lo hago como tu dices, como creo una variable para cada palabra? Debo crear otro vector que lo vaya guardando no ? Sino no veo como hacerlo, aun así voy ha intentarlo haber que sale.

Muchas gracias.

Adioos.

PD: Felices reyes xD.

[rir3760]

Pero una cosa Ghastlyx, si lo hago como tu dices, como creo una variable para cada palabra? Debo crear otro vector que lo vaya guardando no ? Sino no veo como hacerlo, aun así voy ha intentarlo haber que sale.

No. No necesitas crear otro vector.

Primero lees cada una de las palabras y las almacenas en el vector de strings, eso ya lo tienes (salvo algunos detalles como el uso de "and not(false)", esa parte hay que cambiarla). Agregas cada palabra al vector mediante la función miembro "push_back" (puedes revisar ejemplos mediante el motor de búsqueda de los foros).

Después ordenas el vector mediante la función "sort", antes de utilizarla debes incluir el encabezado <algorithm>.

Por ultimo revisas los elementos del vector como te indico ghastlyX utilizando el operador "[]" (como si fuera un array).

Un saludo