algoritmo tombola in c. chi mi da una mano?Grazie

[robs05]

1. Algoritmo di simulazione del gioco della tombola. L’algoritmo simula 5 giocatori, ognuno con una cartella. Ogni cartella deve essere costruita a caso dall’algoritmo e assegnata a un giocatore. Una cartella della tombola è formata da tre righe, ognuna con 5 numeri; in ogni riga può esserci un solo numero per ogni decina (si ricorda che la tombola considera i numeri da 1 a 90); inoltre, in una cartella non possono esserci numeri duplicati. Dopo aver generato le cartelle, l’algoritmo simula l’estrazione in sequenza (a caso) di un numero dal cestello (ovvero l’algoritmo genera a caso un numero intero tra 1 e 90, evitando di generare due volte lo stesso numero) e termina quando uno dei giocatori fa tombola, visualizzando il nome del giocatore. L’algoritmo visualizza anche il giocatore che ha fatto ambo, il giocatore che ha fatto terno, il giocatore che ha fatto quaterna, il giocatore che ha fatto quintina. Visualizzare le cartelle di tutti i giocatori all’inizio e di tutti i giocatori quando si “fa” ambo, terno, quaterna, quintina e tombola.

[yorkeiser]

Una soluzione potrebbe essere:
fatti una struct che simuli un numero sulla cartella (perlomeno deve contenere un int (che è il numero stesso) e un boolean che ti dice se quel numero è già uscito -> ti ritorna utile per calcolare cinquine e tombole).
Quindi le cartelle, potresti modellarle tramite un array 3x5x5 (3 righe, 5 colonne, 5 giocatori).
Il controllo dei duplicati e delle decine non è difficile dai; per le decine controlli che numero/10 deve essere diverso dagli elementi precedenti, devi solo far variare gli indici

Il flusso dell'applicazione dovrebbe essere all'incirca:

inizializza_cartelle()

estrai_numero () ; -> 1+(rand()%90)

segna_numeri_usciti_sulle_cartelle(int numero_estratto) -> metti a true (o false, come preferisci) il boolean della struct

controlla_cinquine_tombole_e_quantaltro();

if (not tombola) ripeti

[robs05]

se nn chiedo troppo mi avrebbe fatto piacere ricevere il codice,
sto preparando un esame e devo portare questo progetto,
solo che è a breve, fra pochi giorni, io ci riesco a farlo ma nn programmo in c da quasi un anno quindi la realizzazione mi farà perdere un bel pò di tempo,e visto che ho tre esami entro il 4 febbr, mi sarebbe molto d'aiuto avere il codice e studiarlo, srciverlo da solo da capo ma senza spendere troppo tempo
ringrazio anticipatamente, e mi congratulo per il forum e a breve appena mi libero dagli esami sarò un partecipante costante anche per dare una mano agl'altri, perchè è fatto davvero bene.
grazie, spero di ricambiare al più presto

[yorkeiser]

Se conosci il c non avrai sicuramente problemi, è un programmino molto generico e, fidati, più semplice di quel che credi. Se ti ci metti non impieghi più di mezza giornata... Questo forum serve a risolvere problemi, non a fare gli esami agli altri, dal momento che tu comunque non impareresti nulla; se hai problemi specifici chiedi pure, ma non è possibile richiedere il codice intero

[Ziosilvio]

Il gioco è un po' più complicato di quanto sembra.

Le cartelle della tombola hanno nove colonne e tre righe, e su ogni riga devono esserci esattamente cinque numeri, mentre su ogni colonna deve esserci almeno un numero (questa condizione non c'è nella traccia dell'esercizio). Per cui, devi considerare anche l'opzione in cui una casella non contiene nessun numero.
(In realtà, la tombola tradizionale ha 48 cartelle prestabilite; potresti usare quelle.)

Inoltre, questo è un caso in cui ti serve che la probabilità di estrazione dei numeri sia uniformemente distribuita, per cui un brutale "1+(rand()%90)" non va bene.
La cosa più semplice, credo sia mettere i numeri da 1 a 90 in una lista, e poi rimuoverli man mano che vengono estratti. Per estrarre un numero,
- ti metti all'inizio della lista,
- scorri in avanti di un numero di posizioni scelto a caso, e
- estrai quel numero dalla lista.
Se fai così, ti servono un contatore del numero di elementi nella lista, e una funzione che, dato N, ti genera un valore equidistribuito tra 0 ed N-1. Fai un salto nella sottosezione "tutorial" e cerca quello sulle sequenze pseudorandom.

Originariamente inviato da robs05

se nn chiedo troppo mi avrebbe fatto piacere ricevere il codice

Chiedi troppo: qui non si fanno i compiti altrui.

[robs05]

ok grazie, allora adesso finisco di preparare architettura dei calcolatori che ho il 25. quindi ho solo oggi e domani per esercitarmi!
dal 26 in poi posso dedicarmi a implementare l'algoritmo della tombola in c. e magari posto solo per consigli e chiedere conferma di se sto procedendo bene...grazie mille riposterò fra 3 giorni

[yorkeiser]

Originariamente inviato da Ziosilvio

Il gioco è un po' più complicato di quanto sembra.

Le cartelle della tombola hanno nove righe e tre colonne, e su ogni riga devono esserci esattamente cinque numeri, mentre su ogni colonna deve esserci almeno un numero (questa condizione non c'è nella traccia dell'esercizio). Per cui, devi considerare anche l'opzione in cui una casella non contiene nessun numero.
(In realtà, la tombola tradizionale ha 48 cartelle prestabilite; potresti usare quelle.)

Inoltre, questo è un caso in cui ti serve che la probabilità di estrazione dei numeri tra 1 e 90 sia uniformemente distribuita per cui un brutale "1+(rand()%90)" non va bene.
La cosa più semplice, credo sia mettere i numeri da 1 a 90 in una lista, e poi rimuoverli man mano che vengono estratti. Per estrarre un numero,
- ti metti all'inizio della lista,
- scorri in avanti di un numero di posizioni scelto a caso, e
- estrai quel numero dalla lista.
Se fai così, ti servono un contatore del numero di elementi nella lista, e una funzione che, dato N, ti genera un valore equidistribuito tra 0 ed N-1. Fai un salto nella sottosezione "tutorial" e cerca quello sulle sequenze pseudorandom.

Chiedi troppo: qui non si fanno i compiti altrui.

Le cartelle della tombola hanno nove righe?? Confesso di non giocare a tombola da molto tempo, ma le ricordo a tre righe
Per quanto riguarda le caselle nulle, un'idea sarebbe quella di inserirci uno 0, se si vuole mantenere la struttura ad interi.
Per il fatto del tabellone, buona l'idea della lista ma forse un pelino pesante; potresti considerare l'opzione di un array bidimensionale, primo campo uguale al numero 1 - 90, secondo campo lo inizializzi con un numero casuale, e fai un ordinamento dell'array sul campo casuale.

[Ziosilvio]

Originariamente inviato da yorkeiser

Le cartelle della tombola hanno nove righe?? Confesso di non giocare a tombola da molto tempo, ma le ricordo a tre righe

Infatti è stato un lapsus calami. Ho corretto.

buona l'idea della lista ma forse un pelino pesante; potresti considerare l'opzione di un array bidimensionale, primo campo uguale al numero 1 - 90, secondo campo lo inizializzi con un numero casuale, e fai un ordinamento dell'array sul campo casuale.

Affascinante; solo che a quel punto il passo più complesso diventa proprio generare la sequenza pseudorandom dei valori del secondo campo. Dato che l'algoritmo di ordinamento potrebbe essere stabile, il requisito che i valori pseudorandom siano tutti diversi va lasciato.
Vediamo che succede con una tombola con n numeri.
Se uso la lista, faccio la chiamata pseudorandom in tempo O(1) e ciascuna delle O(n) selezioni in tempo O(n): tempo totale O(n^2).
Se uso l'array, la generazione pseudorandom mi richiede di ricontrollare ogni volta tutta la sequenza delle generazioni precedenti, e questo mi costa comunque tempo O(n^2) per n valori; poi faccio l'ordinamento in tempo medio O(n log n), e ciascuna delle O(n) selezioni in tempo costante. Il tempo totale mi pare in ogni caso O(n^2).

[yorkeiser]

Uhm... bella teoria, ma una visione un attimino ingegneristica del problema sarebbe quella di generare dei numeri casuali elevati (supponiamo da 0 a 100000), così puoi tranquillamente evitare il controllo a ritroso sull'uguaglianza: su un tetto di 100.000, senza tirar fuori manuali di calcolo combinatorio, la probabilità che tiri fuori 2 numeri uguali, anche su 90 estrazioni, è MOLTO bassa; anche se succedesse, non inficierebbe di certo il funzionamento del programma. Resta la complessità relativa all'ordinamento, che non è logaritmica ma dal mio punto di vista addirittura quadratica visto che un semplice bubble sort, per soli 90 numeri e su un processore a X Ghz, magari riuscirà ad avere un tempo di esecuzione minore di infinito. Siamo entrambi a complessità n^2, ma resta da vedere se una procedura di swap di due elementi (ordinamento) impiega lo stesso numero di cicli macchina dell'operazione di scorrimento e estrazione dall'albero
Ovviamente anche la tua soluzione resta valida, sarei curioso di vedere un benchmark

[repne scasb]

Metodo classico (di gran lunga piu' veloce dei modelli proposti da Ziosilvio e da yorkeiser):

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

#define TABLE_LEN 80

void main(void)

{
    int i,j,k,l,tmp_val,table_n[TABLE_LEN];
    time_t t;

    srand((unsigned)time(&t));

    for(i=0;i<TABLE_LEN;i++)
	table_n[i]=i+1;

    for(i=0;i<TABLE_LEN;i++)
    {
	j=(double)rand()*TABLE_LEN/(RAND_MAX+1);
	k=(double)rand()*TABLE_LEN/(RAND_MAX+1);	
	tmp_val=table_n[j];
	table_n[j]=table_n[k];
	table_n[k]=tmp_val; 	
    }

    for(i=0;i<TABLE_LEN;i++)
	printf("%d\n",table_n[i]);
}

E' anche possibile pensare qualcosa di molto piu' veloce.

[Ziosilvio]

Originariamente inviato da yorkeiser

una visione un attimino ingegneristica del problema sarebbe quella di generare dei numeri casuali elevati (supponiamo da 0 a 100000), così puoi tranquillamente evitare il controllo a ritroso sull'uguaglianza: su un tetto di 100.000, senza tirar fuori manuali di calcolo combinatorio, la probabilità che tiri fuori 2 numeri uguali, anche su 90 estrazioni, è MOLTO bassa; anche se succedesse, non inficierebbe di certo il funzionamento del programma.

L'errore sta proprio nel punto finale: a robs05 non serve un programma che "fallisce con probabilità bassa", ma glie ne serve uno che riesca sempre.

Resta la complessità relativa all'ordinamento, che non è logaritmica ma dal mio punto di vista addirittura quadratica visto che un semplice bubble sort, per soli 90 numeri e su un processore a X Ghz, magari riuscirà ad avere un tempo di esecuzione minore di infinito.

Un algoritmo corretto, eseguito su un input di grandezza finita, ha sempre tempo di esecuzione finito.
E poi, per 90 numeri su un P4 turbo intercooler non è il caso di preoccuparsi troppo.

[yorkeiser]

Interessante in termini di velocità, ma ti mostro con un semplice output grafico che diminuendo il numero di iterazioni (concetto alla base di questo algoritmo) molti numeri non vai neanche a toccarli (le righe asteriscate, e questo succede ad ogni prova che eseguo; i due numeri rappresentano l'indice+1 nell'array ed il valore finale ivi contenuto). Può capitare che casualmente un numero rimanga nella stessa posizione, ma statisticamente mi sembrano un po' troppi - qui posso fare a meno dei manuali di calcolo combinatorio, in media soltanto un numero non dovrebbe cambiare posizione.

 
 1  3
 2  2  <*************
 3 27
 4 69
 5 71
 6 68
 7  6
 8 25
 9  9  <*************
10 42
11 11  <*************
12 54
13 83
14 24
15 61
16 31
17 43
18 46
19 59
20 47
21  8
22 49
23 17
24 77
25 15
26 53
27 21
28 80
29 26
30 73
31 63
32 32  <*************
33 12
34 30
35 70
36 58
37 87
38 64
39 10
40 16
41 41  <*************
42 45
43 40
44 89
45 22
46  4
47 18
48 33
49 55
50  1
51 51  <*************
52 23
53 28
54 62
55 34
56 56  <*************
57 14
58 65
59 19
60 20
61 29
62 82
63 13
64 81
65 36
66 66  <*************
67 67  <*************
68 79
69 57
70 75
71 86
72 90
73 52
74 74  <*************
75 38
76  7
77 39
78 78  <*************
79 76
80 60
81  5
82 50
83 48
84 84  <*************
85 85  <*************
86 44
87 35
88 88  <*************
89 37
90 72

[Ziosilvio]

Originariamente inviato da yorkeiser

ma ti mostro con un semplice output grafico che diminuendo il numero di iterazioni (concetto alla base di questo algoritmo)

... che però non mi dici quale sia...

molti numeri non vai neanche a toccarli (le righe asteriscate, e questo succede ad ogni prova che eseguo; i due numeri rappresentano l'indice+1 nell'array ed il valore finale ivi contenuto).

Infatti non è necessario che tutti i numeri siano estratti in un "istante" diverso da quello indicato da loro stessi: ossia, può darsi che alla k-esima estrazione venga estratto il numero k, e che tuttavia l'estrazione sia random lo stesso.

[yorkeiser]

Originariamente inviato da Ziosilvio

L'errore sta proprio nel punto finale: a robs05 non serve un programma che "fallisce con probabilità bassa", ma glie ne serve uno che riesca sempre.

Qua ti sbagli tu: non fallisce, semplicemente una volta su 1000 (stimo) può tirarti fuori prima il 67 del 78, mentre i due dovrebbero uscire dall'urna contemporaneamente; se non ti basta puoi ovviare prendendo dei double, al che cominci a sconfinare nell'infinitesimo :> Ricorda che, qualsiasi cosa fai, con un calcolatore puoi sempre e solo approssimare la realtà; la stessa generazione dei numeri random è PSEUDOcasuale, quindi in qualsiasi caso introduci una "distorsione" dalla situazione reale

Originariamente inviato da Ziosilvio

Un algoritmo corretto, eseguito su un input di grandezza finita, ha sempre tempo di esecuzione finito.

Nella teoria sì, per fortuna che poi subentra il mondo reale dei calcolatori, altrimenti sai che noia Un esempio?

double a,b,c,d,e,f,g......
for (a=1;a<MAX;a++)
for (b=1;b<MAX;b++)
for (c=1;c<MAX;c++)
for (d=1;d<MAX;d++)
...
//aggiungi un altro po' di for
printf ("%d %d %d %d %d ...\n",a,b,c,d,e....);

Fino a quanti for e a quale valore di MAX credi che sta roba riesca a reggere in un tempo finito? Eppure l'algoritmo mi pare corretto (fa una semplice esplosione combinatoria) e l'input finito (numeri interi e limitati superiormente)

[yorkeiser]

Originariamente inviato da Ziosilvio

... che però non mi dici quale sia...

Infatti non è necessario che tutti i numeri siano estratti in un "istante" diverso da quello indicato da loro stessi: ossia, può darsi che alla k-esima estrazione venga estratto il numero k, e che tuttavia l'estrazione sia random lo stesso.

L'intervento precedente era relativo all'algoritmo presentato da repne scasb, non al tuo... il tuo mi sembra efficace nell'approssimazione della casualità

[Ziosilvio]

Originariamente inviato da yorkeiser

Qua ti sbagli tu: non fallisce, semplicemente una volta su 1000 (stimo) può tirarti fuori prima il 67 del 78, mentre i due dovrebbero uscire dall'urna contemporaneamente

Perché?
Se non fai alcun controllo, non c'è scritto da nessuna parte che non estrarrai due volte lo stesso numero.
Che questo accada con probabilità bassa, è un altro discorso.

Ma forse sto facendo confusione tra tutti gli algoritmi che si sono accavallati...

Nella teoria sì, per fortuna che poi subentra il mondo reale dei calcolatori, altrimenti sai che noia Un esempio?

double a,b,c,d,e,f,g......
for (a=1;a<MAX;a++)
for (b=1;b<MAX;b++)
for (c=1;c<MAX;c++)
for (d=1;d<MAX;d++)
...
//aggiungi un altro po' di for
printf ("%d %d %d %d %d ...\n",a,b,c,d,e....);

Fino a quanti for e a quale valore di MAX credi che sta roba riesca a reggere in un tempo finito?

Sempre.

Che noi si possa morire di vecchiaia nel frattempo, è un altro discorso.

[yorkeiser]

Non può ripetere lo stesso numero, poichè i random vengono usati solo come seed per l'ordinamento.
Ti posto il codice, magari lo comprendi meglio

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

main()
{
int ordinati;
int array[90][2],i,j,temp;
time_t t;
srand((unsigned)time(&t));

for (i=0;i<90;i++)
{
	array[i][0]=i+1; //numeri
	array[i][1]=rand(); //casuale per ordinare array nel bubble sort
}

//BUBBLE SORT
for (i=0;i<90;i++)
{
	ordinati = 1;
	for (j=0;j<89;j++)
	{
		if (array[j][1]>array[j+1][1])
		{
			ordinati=0;
			temp=array[j][1];
			array[j][1]=array[j+1][1];
			array[j+1][1]=temp;
			temp=array[j][0];
			array[j][0]=array[j+1][0];
			array[j+1][0]=temp;
		}
	}
	if (ordinati==1) exit;
}

//STAMPA DELL'ARRAY
for (i=0;i<90;i++)
	printf("%2d %2d\n",i+1,array[i][0]);
}

[repne scasb]

Originariamente inviato da yorkeiser

Interessante in termini di velocità, ma ti mostro con un semplice output grafico...[CUT]

Ottima osservazione, c'e' pero' da considerare che il limite da te giustamente notato, non sta nell'algoritmo di "mix classico", ma nella 'rand()' in quanto l'output di rand() e' distribuito su RAND_MAX e non su TABLE_LEN. Riscrivendo la funzione rand() con RAND_MAX==TABLE_LEN, l'inconveniente da te menzionato verrebbe assai ridotto (non eliminato(NOTA 1)). Tanto piu' TABLE_LEN differisce da RAND_MAX tanto piu' e' vera la tua osservazione (a causa di rand()).

E' anche utile ricordare che la funzione rand() disponibile per alcuni compilatori C non "brilla" per la capacita' di distribuire in modo uniforme il proprio output e differisce da compilatore a compilatore (meglio da libreria a libreria), per esempio compilando il mio esempio con il Watcom C, ottengo risultati meno negativi da quelli da te riportati.

Per correggere tale comportamento "non ottimale" della funzione rand() e' necessario modificare nel mio codice la seguente riga come segue:

	for(i=0;i<TABLE_LEN*K;i++)

K e' un fattore che dipende dalla bonta' della funzione rand() e da quanto TALBLE_LEN differisce da RAND_MAX, in linea puramente teorica vale 1.

NOTA 1: Ineliminabile in quanto estraendo a caso (nella tombola vera), la probabilita' che l'ennesimo numero estratto sia proprio 'n' e' diversa da zero.

NOTA 2: Con TABLE_LEN==90 ed una funzione rand di media qualita', con K=3 il problema non "dovrebbe" presentarsi.

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

#define TABLE_LEN 90
#define K 3

void main(void)

{
    int i,j,k,tmp_val,table_n[TABLE_LEN];
    time_t t;

    srand((unsigned)time(&t));

    for(i=0;i<TABLE_LEN;i++)
	table_n[i]=i+1;

    for(i=0;i<TABLE_LEN*K;i++)
    {
	j=(double)rand()*TABLE_LEN/(RAND_MAX+1);
	k=(double)rand()*TABLE_LEN/(RAND_MAX+1);	
	tmp_val=table_n[j];
	table_n[j]=table_n[k];
	table_n[k]=tmp_val; 	
    }

    for(i=0;i<TABLE_LEN;i++)
	printf("%2d %2d %s\n",i+1,table_n[i],table_n[i]==i+1?"<*************":"");
}

[repne scasb]

Originariamente inviato da yorkeiser

Non può ripetere lo stesso numero, poichè i random vengono usati solo come seed per l'ordinamento....[CUT]

E' corretto. Se ho ben capito, il fatto che in array[i][1] ci siano due numeri (o piu') uguali generati da rand() non implica che il tutto non funzioni, in quanto tale sequenza random viene utilizzata per randomizzare array[i][0] (l'ordinamento di array[i][1] genera la randomizzazione di arrary[i][0]).

L'unica eccezione sensata che vedo, e' che se la rand() non e' scritta "bene", e genera "parecchi" numeri uguali in array[i][1], allora dopo l'ordinamento in array[i][0] si avranno "parecchie" coppie di numeri consecutivi (10/11, 25/26, 78/79...).

[cionci]

Ragazzi non riesco a capire il problema... Il problema è la ripetizione ?

Basta estrarre un numero fra 0 e (90-numero di estrazioni-1) e poi fare una cosa di questo tipo:

int estrai_numero()
{
	static int estratti[90];
	static int estrazioni = 0;
	
	int i = 0;
	int estratto = estrai_da_0_a_N(89 - estrazioni);

	for(i = 0; i <= estratto; ++i)
		estratto += estratti[i];

	estratti[estratto]++; 
	estrazioni++;
	estratto++; //lo riporto da 1 a 90
  
        return estratto;
}