|
|||||||
|
|
|
|||||
|
|
|||||||
|
|||||||
|
|
|
|||||
|
|
|||||||
Implementar un programa que genere aleatoriamente N
combinaciones del tipo LOTO (cartillas de 6 numeros distintos
del 1 al 36).
En una lista se guardará la información correspondiente al
número y su repitencia.
Después de haber realizado las N combinaciones (dato ingresado por el usuario) , mostrar en pantalla los 36 numeros y su respectiva probabilidad de salir en un sorteo hipotético.
Bajar codigo fuente y TAD Lista
Finalmente, se debe dejar en una lista, los 6 números con mayor probabilidad de ocurrencia, mostrándolos en pantalla con su respectiva probabilidad.
SOLUCION
Objetivos
Crear una lista con la siguiente forma :
(1,45) -> (2,25) -> (3,11) -> ... (35,40) -> (36,34)
Encontrar los numeros con mayor probabilidad de salir.
Definicion de constantes
Como hay juegos similares , algunos con cartones de 15 numeros , definimos una
constante llamada MAX_JUEGO inicializada en 6.
De igual forma , definimos una constante llamada NUM_POSIBLES que indica cual es el numero
maximo que se puede elegir aleatoriamente. En este caso (LOTO) es el 36.
#define MAX_JUEGO 6 #define NUM_POSIBLES 36
Definicion de la estructura o el tipo de dato de la lista (TipoL)
Como debemos almacenar un numero (1..36) y su repitencia (0 ... desconocido) creamos una estructura con dos campos enteros : num y rep.
typedef struct
{
int num;
int rep;
} TLoto;
Declaracion explicita de TipoL e incorporacion del TAD LISTA
typedef TLoto TipoL; #include "tadlista.h"
Creacion e Inicializacion de la Lista
Creamos una Lista y una variable auxiliar de tipo TipoL.
Como al comienzo todas las repitencias son cero se asigna
aux.rep = 0 , para luego con un ciclo iterativo, anexar a la
lista los elementos.
(1,0) -> (2,0) -> ... (35,0) -> (36,0)
Lista crearListaLoto(void)
{
Lista lst = inicLista();
TipoL aux;
aux.rep = 0;
for(int i = 1; i <= NUM_POSIBLES ; i++ )
{
aux.num = i;
anxLista(lst,aux);
}
return lst;
}
Generacion de un carton
Queremos generar aleatoriamente 6 numeros distintos del 1 al 36.
Se opta por asignar a un arreglo de longitud 6 dichos numeros, comprobando
en cada asignación, que el numero no se encuentre previamente asignado.
Para comprobar que un numero no se encuentre en el arreglo, implementamos la
función existeNumero que retorna 0 si el elemento no se encuentra y 1 en caso
contrario.
Para ello pasamos como parametros el arreglo, y el elemento a buscar.
Para hacer mas eficiente la busqueda , se pasa el parametro long_actual que representa
la cantidad de elementos (validamente asignados) que hay actualmente en el arreglo.
Por eso es que el indice i recorre desde 0 hasta long_actual.
int existeNumero(int *arr,int long_actual,int elem)
{
int existe = 0;
for(int i = 0; i < long_actual && !existe ; i++)
if(arr[i] == elem) existe = 1;
return existe;
}
Luego, implementamos la función generar_carton , que consiste en ir generando aleatoriamente numeros del 1 al 36 . En cada iteración se comprueba la existencia del numero generado y el proceso iterativo sigue mientras no se complete el carton.
void generar_carton(int *arr)
{
int cont = 0,na;
while(cont < MAX_JUEGO)
{
na = rand() % NUM_POSIBLES + 1;
if(!existeNumero(arr,cont,na)) arr[cont++] = na;
}
}
Para hacer referencia a un solo arreglo, necesitamos una función que asigne al arreglo, solo ceros.
void inicializar_carton(int *arr)
{
for(int i = 0; i < MAX_JUEGO ; i++) arr[i] = 0;
}
Generacion de la simulacion
Finalmente implementamos una función que realice todo el proceso de creación y asignación. Como parametros le pasamos la lista y el numero de combinaciones (num_comb) a realizar.
Ejemplo :
En cada iteración se hace lo siguiente :
inicializar_carton --> carton : { 0 , 0 , 0 , 0 , 0 , 0 };
generar_carton --> carton : { 4 , 16 ,20 , 25 , 28 , 32 }
ir a posicion 4 de la lista e incrementar su campo rep.
ir a posicion 16 de la lista e incrementar su campo rep.
:
:
ir a posicion 32 de la lista e incrementar su campo rep.
Lista simulacion(Lista lst,int num_comb)
{
int *carton = (int *) calloc(MAX_JUEGO, sizeof(int));
for(int i = 0; i < num_comb; i++)
{
inicializar_carton(carton);
generar_carton(carton);
for(int j = 0; j < MAX_JUEGO; j++)
{
posLista(lst,carton[j]);
lst->ventana->info.rep++;
}
}
free(carton);
return lst;
}
Mostrar las probabilidades en pantalla
La probabilidad de escoger un numero del conjunto L : {1..36} entre la totalidad de cartones (N) simulados es :
prob = repeticiones / (6*N)
Como la probabilidad esperada es (100 / 36) = 2.77777 los resultados de la probabilidad sera cercana a 0.0277. Para tener la salida a pantalla que se encuentra al comienzo se siguio con el siguiente razonamiento.
Los numeros calculados se multiplicaran por 100 y se sacaran con un formato
de 4 digitos con 3 decimales (%4.3lf ).
Ademas para imprimir en tres columnas , se usara la tabulacion (\t), saltando
una linea cada tres salidas. Cada salida sera tabulada adicionalmente gracias a un
contador de columnas (cont).
Ademas para que no haya desfase entre numeros con uno y dos digitos
(ejemplo) 8 : 3.452% 10 : 2.456%se reservan 2 digitos para el numero con el formato : %2d.
Como parametro se espera la lista y el numero de cartones generados. Para simplificar el calculo de la probabilidad, el parametro num_comb se multiplica por 6.
void imprimirLista(Lista lst,int num_comb)
{
num_comb *= MAX_JUEGO;
int cont = 0;
for(primLista(lst); !finLista(lst);sigLista(lst))
{
printf("\t%2d :",infoLista(lst).num);
printf("\t%4.3lf%%",(double) 100 * infoLista(lst).rep / num_comb);
cont++;
if(cont % 3 == 0) printf("\n");
else printf("\t");
}
}
Encontrar las seis mayores repitencias
El algoritmo que se va a realizar es el de eliminar los 30 elementos que tengan la menor repitencia.
Pasos generales :
1) Buscar en la lista, el elemento con menor repitencia.
2) Ir a la posicion de la lista correspondiente.
3) Eliminar elemento.
Para empezar se debe definir una funcion que compare si una variable de tipo TipoL
es menor que otra variable de su mismo tipo.
Como el criterio de comparación es de acuerdo a el campo de repitencia (rep), se implementa
lo siguiente :
int menor(TipoL a,TipoL b)
{
return a.rep < b.rep;
}
Ahora, definiremos una función (generica) que busque el menor elemento de una lista, segun criterio pasado como función. Esto nos permite reutilizar la misma función para cualquier tipo TipoL, preocupandonos solo de implementar las funciones especificas de comparacion, como en este caso es la función menor.
TipoL menorLista(Lista lst, int (*func_menor)(TipoL,TipoL))
{
primLista(lst);
TipoL menor = infoLista(lst);
for(primLista(lst); !finLista(lst); sigLista(lst))
if( func_menor(infoLista(lst) , menor) ) menor = infoLista(lst);
return menor;
}
Una vez encontrado el elemento, necesitamos ir a la posicion de este, dentro de la lista. Para ello necesitamos dos cosas ; una función de comparación (especifica) que verifique si dos elementos de tipo TipoL son iguales y una función (generica) que recorra la lista evaluando la funcion de comparacion, para situar la ventana en el elemento buscado.
Como el criterio para comparar si dos variables de tipo TipoL son iguales es segun su campo num, se tiene :
int comparacion(TipoL a,TipoL b)
{
return a.num == b.num;
}
A la funcion generica de busqueda ,se le pasan como parametros la lista, el elemento a buscar (de TipoL) y la funcion de comparacion.
void buscarLista(Lista lst,TipoL elem,int (*comp)(TipoL,TipoL))
{
primLista(lst);
while(!finLista(lst) && !comp(infoLista(lst),elem))
{
sigLista(lst);
}
}
Finalmente, implementamos una funcion que reciba como parametros la lista y dos funciones de comparacion (menor e igualdad). Esta lleva a cabo los tres pasos señalados al comienzo.
void elim_mayores(Lista lst, int (*f_comp)(TipoL,TipoL), int (*f_menor)(TipoL,TipoL))
{
TipoL aux;
for(int i = 0; i < NUM_POSIBLES - MAX_JUEGO; i++)
{
aux = menorLista(lst , f_menor);
buscarLista(lst , aux , f_comp);
elimLista(lst);
}
}
PROGRAMA PRINCIPAL
int main()
{
/* Inicia la semilla aleatoria */
randomize();
int num_comb;
printf("\n Ingrese numero de combinaciones : ");
scanf("%d",&num_comb);
/* Crea la lista */
Lista lst = crearListaLoto();
/* Genera los cartones */
lst = simulacion(lst,num_comb);
printf("\n");
imprimirLista(lst,num_comb);
/* Elimina los 30 mayores nodos */
elim_mayores(lst,comparacion,menor);
printf("\n Numeros con mayor repitencia \n\n");
imprimirLista(lst,num_comb);
printf("\n");
/* Libera memoria para la lista */
destruirLista(lst);
return 0;
}