 Autor
|
Tema: [Duda] Creación de un programa que calcule la moda (Leído 4,442 veces)
|
Denok
 Desconectado
Mensajes: 17
|
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.
|
|
|
|
|
En línea
|
|
|
|
PiroskY
Desconectado
Mensajes: 76
пирожки
|
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.
|
|
|
|
|
En línea
|
|
|
|
Denok
Desconectado
Mensajes: 17
|
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. #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!. |
|
|
|
|
En línea
|
|
|
|
ghastlyX
Ex-Staff
Desconectado
Mensajes: 1.900
|
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 n2.
En el enunciado te dicen que n es como mucho 105 (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 1010 operaciones, que es demasiado. Típicamente, un código es rápido si hace unas 107 o 108 (si son 108, 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.
|
|
|
|
|
En línea
|
|
|
|
Denok
Desconectado
Mensajes: 17
|
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.
|
|
|
|
« Última modificación: 6 Enero 2012, 13:15 pm por Denok »
|
En línea
|
|
|
|
rir3760
Desconectado
Mensajes: 1.639
|
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
|
|
|
|
|
En línea
|
C retains the basic philosophy that programmers know what they are doing; it only requires that they state their intentions explicitly.
--
Kernighan & Ritchie, The C programming language
|
|
|
|
| Mensajes similares |
|
Asunto |
Iniciado por |
Respuestas |
Vistas |
Último mensaje |
|
|
|
Programa que calcule nominas
Programación Visual Basic
|
Ki1L3r
|
0
|
2,050
|
14 Enero 2007, 21:01 pm
por Ki1L3r
|
|
|
|
Programa que calcula el promedio y la moda. duda con la moda
Programación C/C++
|
noobc
|
1
|
5,318
|
27 Mayo 2010, 02:24 am
por h0oke
|
|
|
programa en C++ que calcule un salario neto de un trabajador
Programación C/C++
|
oert
|
1
|
11,131
|
19 Febrero 2011, 03:03 am
por Littlehorse
|
|
|
|
Duda con un programa que hice - Do while y creacion de ficheros/archivos
Programación C/C++
|
Fabi0lo
|
1
|
3,082
|
1 Mayo 2012, 22:52 pm
por exel
|
|
|
|
Duda sobre Windows y la creación de un programa
Programación General
|
bernyx123
|
7
|
3,231
|
28 Agosto 2013, 04:07 am
por bernyx123
|
 |
