algoritmo tombola in c. chi mi da una mano?Grazie
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.
|
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 |
grazie mille
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 |
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 :nonsifa:
|
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. Quote:
|
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 |
Quote:
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. |
Quote:
Quote:
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). |
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 :) |
Metodo classico (di gran lunga piu' veloce dei modelli proposti da Ziosilvio e da yorkeiser):
Codice:
#include <stdio.h> |
Quote:
Quote:
E poi, per 90 numeri su un P4 turbo intercooler non è il caso di preoccuparsi troppo. |
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.
Codice:
|
Quote:
Quote:
|
Quote:
Quote:
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) :) |
Quote:
|
Quote:
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... Quote:
Che noi si possa morire di vecchiaia nel frattempo, è un altro discorso. |
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 Codice:
#include <stdlib.h> |
Quote:
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: Codice:
for(i=0;i<TABLE_LEN*K;i++) 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. Codice:
#include <stdio.h> |
Quote:
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...). |
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: Codice:
int estrai_numero() |
Tutti gli orari sono GMT +1. Ora sono le: 03:41. |
Powered by vBulletin® Version 3.6.4
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
Hardware Upgrade S.r.l.