Questo sito utilizza cookies, anche di terze parti, per mostrare pubblicità e servizi in linea con il tuo account. Leggi l'informativa sui cookies.
Username: Password: oppure
C/C++ - Mescolare un mazzo di carte [C++]
Forum - C/C++ - Mescolare un mazzo di carte [C++]

Avatar
AlesPalla (Normal User)
Rookie


Messaggi: 25
Iscritto: 23/11/2008

Segnala al moderatore
Postato alle 20:30
Lunedì, 23/11/2009
Allora ho appena creato un algoritmo che mescola un mazzo da 40 carte..
Per generarlo ho pensato di creare un vettore di 40 int che associa ad ogni numero la sua posizione...

Per creare il vettore io ho usato questo algoritmo fatto da me:

Codice sorgente - presumibilmente C++

  1. void genera_pos(int*p){
  2.  
  3.     int c;
  4.     srand(time(0));
  5.     unsigned long int a=0;          //vettore di bit utilizzato come contatore
  6.  
  7.     for (int i=0;i<40;i++){
  8.         c=numero_cas(0,40);
  9.  
  10.         if (((1<<c)&a)==0){         //verifica se il c-esimo bit è acceso
  11.             p[i]=c;
  12.             a|=(1<<c);              //accende il c-esimo bit
  13.         }
  14.         else {
  15.             i--;                    //decrementa e fa in modo di reiterare il ciclo
  16.         }
  17.     }



e per generare il numero casuale ho usato questo che è + o - standard:

Codice sorgente - presumibilmente C/C++

  1. int numero_cas(int iniz,int fin){
  2.      return rand()%fin +iniz ;
  3. }



Il problema è che l'algoritmo funziona BENISSIMO fino tipo al 24 numero...poi si blocca inspiegabilmente...

secondo voi cosa è sbagliato?


...
PM Quote
Avatar
AlesPalla (Normal User)
Rookie


Messaggi: 25
Iscritto: 23/11/2008

Segnala al moderatore
Postato alle 20:40
Lunedì, 23/11/2009
Ho scoperto cosa non andava:
Vacendo correre il programma diverse volte ho osservato che si bloccava sempre in punti diversi ho ipotizzato che finissero i numeri della sequenza e ho modificato in questa maniera il codice:
Codice sorgente - presumibilmente C++

  1. void genera_pos(int*p){
  2.  
  3.     int c,d=0;
  4.     srand(time(0));
  5.     unsigned long int a=0;          //contatore
  6.  
  7.     for (int i=0;i<40;i++){
  8.         c=numero_cas(0,40);
  9.  
  10.         if (((1<<c)&a)==0){         //verifica se il c-esimo bit è acceso
  11.             p[i]=c;
  12.             a|=(1<<c);              //accende il c-esimo bit
  13.             d=0;
  14.         }
  15.         else {
  16.             i--;                    //decrementa e fa in modo di reiterare il ciclo
  17.             if(++d>100) {cout<<"Hey srand si e' bloccato!\n";return;}
  18.  
  19.         }
  20.     }
  21.     cout<<'\n';
  22.  
  23. }



E sembrerebbe che abbia ragione.. come posso fare per porvi rimedio?


...
PM Quote
Avatar
Lawliet (Normal User)
Expert


Messaggi: 386
Iscritto: 09/04/2009

Segnala al moderatore
Postato alle 22:40
Lunedì, 23/11/2009
Testo quotato

Postato originariamente da pierotofy:
operazioni bit-wise


Ecco cosa sono, non ho mai avuto a che fare con questi tipo di operazioni.

EDIT: ho cancellato ciò che ho scritto prima ^^'

Ultima modifica effettuata da Lawliet il 23/11/2009 alle 22:56


"Dai un pesce (programma) a un uomo e lo nutrirai per un giorno. Insegnagli a pescare (programmare) e lo nutrirai per tutta la vita." (niente pappa pronta)
cit. theprogrammer
PM Quote
Avatar
pierotofy (Admin)
Guru^2


Messaggi: 6110
Iscritto: 04/12/2003

Segnala al moderatore
Postato alle 22:43
Lunedì, 23/11/2009
Non ho eseguito il codice e non ho analizzato per bene tutto il funzionamento, ma so che non dovresti mai modificare il valore di 'i' all'interno del ciclo (e' semanticamente sbagliato). Mi sembra che con tutti questi puntatori e operazioni bit-wise stai ingrandendo il problema... per mescolare un mazzo di carte assegni ad ogni carta un valore casuale (da 1 a N anche con ripetizioni, dove N >= 40), dopodiche' ordini la lista di carte in base al valore assegnato casualmente.

Perche' tirare in ballo operazioni bit-wise? A meno che non stai mescolando un mazzo di qualche migliaio di milioni di carte la differenza non si nota usando operatorazioni normali (e piu' leggibile da parte di un altro programmatore).

Ultima modifica effettuata da pierotofy il 23/11/2009 alle 22:47


Seguimi su Twitter: http://www.twitter.com/pierotofy

Fai quello che ti piace, e fallo bene.
PM Quote
Avatar
gigisoft (Member)
Guru


Messaggi: 695
Iscritto: 11/10/2008

Segnala al moderatore
Postato alle 16:52
Martedì, 24/11/2009
Testo quotato

Postato originariamente da pierotofy:

Non ho eseguito il codice e non ho analizzato per bene tutto il funzionamento, ma so che non dovresti mai modificare il valore di 'i' all'interno del ciclo (e' semanticamente sbagliato). Mi sembra che con tutti questi puntatori e operazioni bit-wise stai ingrandendo il problema... per mescolare un mazzo di carte assegni ad ogni carta un valore casuale (da 1 a N anche con ripetizioni, dove N >= 40), dopodiche' ordini la lista di carte in base al valore assegnato casualmente.

Perche' tirare in ballo operazioni bit-wise? A meno che non stai mescolando un mazzo di qualche migliaio di milioni di carte la differenza non si nota usando operatorazioni normali (e piu' leggibile da parte di un altro programmatore).



Concordo pienamente,
in alternativa, volendo rendere il mescolamento un po' meno pseudo e piu' casuale, nel progetto Clondike io usai un algoritmo forse piu' complesso, ma che simulava meglio un mescolamento reale, in pratica usavo una lista di oggetti "Carta" dopodiche' per un alto numero di volte ( 1000 se non ricordo male ) prendevo la prima carta della lista e la mettevo in una posizione scelta a caso, poi ripetevo lo stesso procedimento, però prendendo l'ultima.
Ciao. :k:

Luigi.


Le cose si fanno per bene o non si fanno affatto
PM Quote
Avatar
TheKaneB (Member)
Guru^2


Messaggi: 1787
Iscritto: 26/06/2009

Segnala al moderatore
Postato alle 20:01
Martedì, 24/11/2009
Per mescolare un mazzo di carte esiste un algoritmo molto semplice e molto efficiente inventato da Knuth.

In sostanza funziona così:

Hai un array di MAX elementi.
Hai bisogno di mescolare un numero di elementi pari a M.

0) LIMITE = MAX - M
1) N = MAX - 1
2) se N == LIMITE vai a 7)
3) fai il random tra 0 e N, chiamiamolo R.
4) prendi il numero di posto R e lo scambi con il numero di posto N
5) N = N - 1
6) ritorna al 2)
7) metti in output tutti gli elementi dal posto LIMITE al posto MAX-1

Come caso particolare, se vuoi mescolare tutto il mazzo, basta porre M = MAX, oppure (che è uguale) basta mettere LIMITE = 0.

Spero ti sia utile ;)

PS: Riguardo al tuo codice, non puoi shiftare a sinistra di 40 bit un intero di tipo long, perchè normalmente un long ha 32bit su una tipica macchina desktop. Usa long long se proprio vuoi 64 bit di dati, ma ti sconsiglio questo approccio perchè non è generico e non è portabile, e inoltre le operazioni bitwise dovrebbero essere usate solo in caso di necessità ben precise; ad esempio nel digital signal processing, oppure in routine estremamente ottimizzate per funzionare su particolari architetture che hanno gli shift "gratis" come ARM.


Software Failure: Guru Meditation
Forum su Informatica, Elettronica, Robotica e Tecnologia: http://www.nonsoloamiga.com
PM Quote
Avatar
HeDo (Founder Member)
Guru^2


Messaggi: 2763
Iscritto: 21/09/2007

Segnala al moderatore
Postato alle 20:13
Mercoledì, 25/11/2009

non per sminuire la soluzione di kane ma potresti semplicemente generare un mazzo ordinato e poi scambiare 2 carte a caso tante volte quante sono le carte del mazzo. dovrebbe essere sufficiente no?

oltretutto lo trovo il modo più semplice :D


Ingegnere Informatico
https://ldlagency.it
PM Quote
Avatar
TheKaneB (Member)
Guru^2


Messaggi: 1787
Iscritto: 26/06/2009

Segnala al moderatore
Postato alle 23:28
Mercoledì, 25/11/2009
Certo anche la tua è un'ottima soluzione. Ho voluto citare l'algoritmo di Knuth giusto per mettere un po' di "letteratura classica" in gioco :)
Oltretutto è un sistema generico, che ti consente di avere anche soltanto un sottoinsieme scombinato, in modo semplice ed efficiente. Comunque è sempre divertente confrontare gli algoritmi per così dire "greedy", cioè quelli che ci vengono in testa sulle prime, con gli algoritmi "di letteratura" sui quali molti studiosi (soprattutto teorici) hanno lavorato negli anni.

Ciao!


Software Failure: Guru Meditation
Forum su Informatica, Elettronica, Robotica e Tecnologia: http://www.nonsoloamiga.com
PM Quote
Avatar
AlesPalla (Normal User)
Rookie


Messaggi: 25
Iscritto: 23/11/2008

Segnala al moderatore
Postato alle 0:03
Giovedì, 26/11/2009
Grazi 1000 per le risposte!!
Ho implementato l'algoritmo di Kane e funziona a meraviglia!! :)


...
PM Quote