Duda función barajar

Iniciado por David8, 8 Abril 2014, 15:45 PM

0 Miembros y 1 Visitante están viendo este tema.

David8

Hola, tengo el siguiente fragmento de programa:

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

void baraja( int wMazo[][13] );
// código

int main (void)
{
   //código
   int mazo[4][13] = {0};
   srand(time(0));
   baraja(mazo);
   //código
   return EXIT_SUCCESS;
}

void baraja( int wMazo[][13] )
{
   int fila;
   int columna;
   int carta;

   for(carta=1; carta<=52; carta++){
      do{
         fila = rand() % 4;
         columna = rand() % 13;
      } while(wMazo[fila][columna] != 0);
      wMazo[fila][columna] = carta;
   }
}


No entiendo porqué se pasa wMazo[][13], es decir, porque se deja el primer corchete sin datos, ¿no debería ser wMazo[4][13] ?

Gracias.

amchacon

Esa funcion da problemas, es muy probable que el mazo generado tenga 2 cartas identicas.

Lo ideal esque generes el mazo ordenado y luego hagas intercambios aleatorios.

En cuanto a la pregunta, el primer corchete es opcional. Puedes ponerlo o no, el segundo corchete es necesario para que el compilador traduzca los dos [][] en uno solo.
Por favor, no me manden MP con dudas. Usen el foro, gracias.

¡Visita mi programa estrella!

Rar File Missing: Esteganografía en un Rar

eferion

Como dice amchacon, tu código genera cartas repetidas ( por mera cuestión de estadística es más probable el caso en el que mazo tiene cartas repetidas que el caso en el que todas la cartas son distintas ).

La solución a ese problema pasaría por crear primero un mazo ordenado, lo cual es fácil de generar, y después mezclarlo mediante una serie de permutaciones ( generar un par X, Y e intercambiar sus cartas ). El número de permutaciones necesarias para asegurar una mezcla adecuada variará en función del algoritmo que elijas.

rir3760

Cita de: David8 en  8 Abril 2014, 15:45 PMNo entiendo porqué se pasa wMazo[][13], es decir, porque se deja el primer corchete sin datos, ¿no debería ser wMazo[4][13]?
Puedes declararla así pero no tendrá efecto ya que en C cuando un argumento es de tipo array lo que recibe la función es la dirección en memoria de (un puntero a) su primer elemento. Si el array es de tipo "T [N]" la función recibe un puntero de tipo "T *".

Utilizando tu caso como ejemplo la función la puedes declarar en cualquiera de las dos formas:
void baraja( int wMazo[4][13] );

/* O tambien */
void baraja( int wMazo[][13] );

Pero no importa ya que la función se procesa como si su declaración fuera (y es):
void baraja(int (*wMazo)[13]);

Cita de: amchacon en  8 Abril 2014, 16:02 PMEsa funcion da problemas, es muy probable que el mazo generado tenga 2 cartas identicas.
En buen plan: lo reviso con cuidado y no veo como se pueda duplicar una carta. ¿Se me escapa algo?

Un saludo
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

eferion

Cierto. Vi los random y me cegué jejejeje.

El problema es que llegar a tardar un tiempo infinito en mezclar el mazo.... si una de las combinaciones (fila, columna) no se da hasta pasadas miles de iteraciones... pues ahí que te quedas esperando.

amchacon

Tienes razón Rir, que fallo más tonto :-X

De todas formas, no me gusta ese modo de barajar como ya dije. Me parece mas natural de este modo:

1º Te generas el mazo ordenado.
2º Coges dos elementos al azar y los intercambias
3º Repites el paso 2 tantas veces como creas necesario. Para un mazo tienes de sobra con 1000 iteraciones.

De hecho en C++ (que no C) puedes hacer los dos ultimos pasos en un sola función:
http://www.cplusplus.com/reference/algorithm/random_shuffle/
Por favor, no me manden MP con dudas. Usen el foro, gracias.

¡Visita mi programa estrella!

Rar File Missing: Esteganografía en un Rar

leosansan

Cita de: eferion en  8 Abril 2014, 17:32 PM
..........................................................
El problema es que llegar a tardar un tiempo infinito en mezclar el mazo.... si una de las combinaciones (fila, columna) no se da hasta pasadas miles de iteraciones... pues ahí que te quedas esperando.

Creo que últimamente menospreciamos la potencia de proceso de nuestros PC.

Como media a mi me tarda menos de 0.020s.

Ya hace un tiempo hubo una discusión acerca de cuánto tiempo se emplearía en rellenar, con el mismo método, una matriz 10x10 con números del 1 al 1000 y andaba por los 0.012s y acabó en este otro tema.

Salu2!.

ivancea96

Para barajar, yo lo que hago es ir cogiendo elementos, e ir colocándolos en un array en posiciones aleatorias.

O lo que es lo mismo, ir cogiendo elementos aleatorios, e ir introduciéndolos en el array.
Así para barajar en un tiempo finito.

amchacon

#8
Cita de: ivancea96 en  8 Abril 2014, 19:49 PM
Para barajar, yo lo que hago es ir cogiendo elementos, e ir colocándolos en un array en posiciones aleatorias.

O lo que es lo mismo, ir cogiendo elementos aleatorios, e ir introduciéndolos en el array.
Así para barajar en un tiempo finito.
Pero estás duplicando el array así... Para eso intercambias y ya esta.

Cita de: leosansan en  8 Abril 2014, 19:43 PM
Creo que últimamente menospreciamos la potencia de proceso de nuestros PC.

Como media a mi me tarda menos de 0.020s.

Ya hace un tiempo hubo una discusión acerca de cuánto tiempo se emplearía en rellenar, con el mismo método, una matriz 10x10 con números del 1 al 1000 y andaba por los 0.012s y acabó en este otro tema.

Salu2!.

Por supuesto, pero siempre se busca la máxima eficiencia.

Suponte un servidor de poker con millones de usuarios, dado que tienes que hacer millones de mezclas conviene perder el menor tiempo posible.

Y confiar en el "azar" no suele ser muy buena práctica. Es una buena costumbre garantizar que el algoritmo termine en tiempo finito incluso en el peor caso posible, nos ayudará a evitarnos algunos errores "oscuros".

Como curiosidad de algoritmos basados en el azar, tenemos un algoritmo de ordenación que usa una técnica similar: El bogosort (o stupidsort). Que viene a ser el siguiente:

Dado un conjunto de números desordenados:
    1º Comprobar que esten ordenados, si lo estan termina.
    2º Mezclar los numeros aleatoriamente.

Y aquí una implementación de este algoritmo en C++:

Código (cpp) [Seleccionar]
#include <iostream>
#include <algorithm>
#include <ctime>
#include <iterator>
using namespace std;

void bogo_sort(vector<int>&);

int main()
{
   vector<int> Numeros;
   srand(time(NULL));
   int N;

   cout<<"Introduzca numero de elementos a ordenar: ";
   cin>>N;

   Numeros.resize(N);

   for (int i = 0; i < 10;i++) // 10 intentos
   {
       generate(Numeros.begin(),Numeros.end(),rand); // relleno el vector de numeros aleatorios

         // Muestra los numeros generados por pantalla:
//        copy(Numeros.begin(),Numeros.end(), ostream_iterator<int>(cout, " "));

       time_t inicio = clock();

       bogo_sort(Numeros);

       time_t fin = clock();

       cout<<(double)(fin-inicio)/(CLOCKS_PER_SEC)<<"s en ordenar "<<N<<" elementos"<<endl;

       // muestra los numeros ordenados por pantalla
//        copy(Numeros.begin(),Numeros.end(), ostream_iterator<int>(cout, " "));

      // cout<<endl;
   }
   return 0;
}

bool enOrden(vector<int> &x) {return adjacent_find(x.begin(), x.end(), greater<int>()) == x.end();}

void bogo_sort(vector<int> &Numeros)
{
   while (!enOrden(Numeros))
   {
       random_shuffle(Numeros.begin(),Numeros.end());
   }
}


Dile que genere 10 elementos. A mí los tiempos me salen muy dispares (desde 0,063 hasta 5 segundos). Eso en rangos pequeños, cuanto mayor sea el rango, mayor será la dispersión.

En resumen, trabajar basado en la suerte nos da unos programas muy impredecibles y inestables. A mí personalmente no me gusta nada ;D
Por favor, no me manden MP con dudas. Usen el foro, gracias.

¡Visita mi programa estrella!

Rar File Missing: Esteganografía en un Rar

ivancea96

Cita de: amchacon en  8 Abril 2014, 20:41 PM
Pero estás duplicando el array así... No sé.

Creo que es obvio que se hace en un array temporal >.>