Torna indietro   Hardware Upgrade Forum > Software > Programmazione

Il futuro delle GPU AMD e NVIDIA tra 20 nanometri e imprevisti
Il futuro delle GPU AMD e NVIDIA tra 20 nanometri e imprevisti
Le prossime generazioni di chip video di AMD e NVIDIA, basati su nuove architetture, sono attesi al debutto per la fine dell'anno ma le difficoltà legate alla tecnologia produttiva a 20 nanometri potrebbero far slittare il tutto
Smartphone e tablet personali al lavoro, ne parliamo con Ipswitch
Smartphone e tablet personali al lavoro, ne parliamo con Ipswitch
Una delle più importanti tendenze avvenute in ambito aziendale negli ultimi anni: il BYOD nasconde interessanti opportunità e benefici, ma anche elementi critici da affrontare adeguatamente
Wi-Fi 802.11ac: reti wireless sempre più veloci
Wi-Fi 802.11ac: reti wireless sempre più veloci
I nuovi dispositivi Wi-Fi in standard 802.11ac vengono pubblicizzati dai produttori con velocità di trasferimento superiori al gigabit. Ma quali solo le prestazioni reali? E quali le possibilità offerte all'utente?
Tutti gli articoli Tutte le news

Vai al Forum
Rispondi
 
Strumenti
Old 22-01-2007, 16:57   #1
robs05
Member
 
Iscritto dal: Jan 2007
Messaggi: 111
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.
robs05 è offline   Rispondi citando il messaggio o parte di esso
Old 22-01-2007, 17:40   #2
yorkeiser
Senior Member
 
L'Avatar di yorkeiser
 
Iscritto dal: Jul 2006
Città: Tristram
Messaggi: 506
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
yorkeiser è offline   Rispondi citando il messaggio o parte di esso
Old 22-01-2007, 18:54   #3
robs05
Member
 
Iscritto dal: Jan 2007
Messaggi: 111
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
robs05 è offline   Rispondi citando il messaggio o parte di esso
Old 23-01-2007, 10:12   #4
yorkeiser
Senior Member
 
L'Avatar di yorkeiser
 
Iscritto dal: Jul 2006
Città: Tristram
Messaggi: 506
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
yorkeiser è offline   Rispondi citando il messaggio o parte di esso
Old 23-01-2007, 11:03   #5
Ziosilvio
Moderatore
 
L'Avatar di Ziosilvio
 
Iscritto dal: Nov 2003
Messaggi: 12518
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:
Originariamente inviato da robs05
se nn chiedo troppo mi avrebbe fatto piacere ricevere il codice
Chiedi troppo: qui non si fanno i compiti altrui.
__________________
Ubuntu è un'antica parola africana che significa "non so configurare Debian" Chi scherza col fuoco si brucia.
Scienza e tecnica: Matematica - Fisica - Chimica - Informatica - Software scientifico - Consulti medici
REGOLAMENTO Gauron = HP dv6 A6-3410MX+HD6750 Win7HP64+Xubuntu12.04

Ultima modifica di Ziosilvio : 23-01-2007 alle 14:16.
Ziosilvio è offline   Rispondi citando il messaggio o parte di esso
Old 23-01-2007, 11:09   #6
robs05
Member
 
Iscritto dal: Jan 2007
Messaggi: 111
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
robs05 è offline   Rispondi citando il messaggio o parte di esso
Old 23-01-2007, 11:19   #7
yorkeiser
Senior Member
 
L'Avatar di yorkeiser
 
Iscritto dal: Jul 2006
Città: Tristram
Messaggi: 506
Quote:
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.
yorkeiser è offline   Rispondi citando il messaggio o parte di esso
Old 23-01-2007, 14:23   #8
Ziosilvio
Moderatore
 
L'Avatar di Ziosilvio
 
Iscritto dal: Nov 2003
Messaggi: 12518
Quote:
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.
Quote:
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).
__________________
Ubuntu è un'antica parola africana che significa "non so configurare Debian" Chi scherza col fuoco si brucia.
Scienza e tecnica: Matematica - Fisica - Chimica - Informatica - Software scientifico - Consulti medici
REGOLAMENTO Gauron = HP dv6 A6-3410MX+HD6750 Win7HP64+Xubuntu12.04

Ultima modifica di Ziosilvio : 23-01-2007 alle 14:29.
Ziosilvio è offline   Rispondi citando il messaggio o parte di esso
Old 23-01-2007, 15:40   #9
yorkeiser
Senior Member
 
L'Avatar di yorkeiser
 
Iscritto dal: Jul 2006
Città: Tristram
Messaggi: 506
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
yorkeiser è offline   Rispondi citando il messaggio o parte di esso
Old 23-01-2007, 16:36   #10
repne scasb
Bannato
 
Iscritto dal: Feb 2003
Messaggi: 948
Metodo classico (di gran lunga piu' veloce dei modelli proposti da Ziosilvio e da yorkeiser):

Codice:
#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.
repne scasb è offline   Rispondi citando il messaggio o parte di esso
Old 23-01-2007, 17:06   #11
Ziosilvio
Moderatore
 
L'Avatar di Ziosilvio
 
Iscritto dal: Nov 2003
Messaggi: 12518
Quote:
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.
Quote:
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.
__________________
Ubuntu è un'antica parola africana che significa "non so configurare Debian" Chi scherza col fuoco si brucia.
Scienza e tecnica: Matematica - Fisica - Chimica - Informatica - Software scientifico - Consulti medici
REGOLAMENTO Gauron = HP dv6 A6-3410MX+HD6750 Win7HP64+Xubuntu12.04
Ziosilvio è offline   Rispondi citando il messaggio o parte di esso
Old 23-01-2007, 17:10   #12
yorkeiser
Senior Member
 
L'Avatar di yorkeiser
 
Iscritto dal: Jul 2006
Città: Tristram
Messaggi: 506
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:
 
 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
yorkeiser è offline   Rispondi citando il messaggio o parte di esso
Old 23-01-2007, 17:28   #13
Ziosilvio
Moderatore
 
L'Avatar di Ziosilvio
 
Iscritto dal: Nov 2003
Messaggi: 12518
Quote:
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...
Quote:
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.
__________________
Ubuntu è un'antica parola africana che significa "non so configurare Debian" Chi scherza col fuoco si brucia.
Scienza e tecnica: Matematica - Fisica - Chimica - Informatica - Software scientifico - Consulti medici
REGOLAMENTO Gauron = HP dv6 A6-3410MX+HD6750 Win7HP64+Xubuntu12.04
Ziosilvio è offline   Rispondi citando il messaggio o parte di esso
Old 23-01-2007, 17:29   #14
yorkeiser
Senior Member
 
L'Avatar di yorkeiser
 
Iscritto dal: Jul 2006
Città: Tristram
Messaggi: 506
Quote:
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

Quote:
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 è offline   Rispondi citando il messaggio o parte di esso
Old 23-01-2007, 17:36   #15
yorkeiser
Senior Member
 
L'Avatar di yorkeiser
 
Iscritto dal: Jul 2006
Città: Tristram
Messaggi: 506
Quote:
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à
yorkeiser è offline   Rispondi citando il messaggio o parte di esso
Old 23-01-2007, 17:51   #16
Ziosilvio
Moderatore
 
L'Avatar di Ziosilvio
 
Iscritto dal: Nov 2003
Messaggi: 12518
Quote:
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...
Quote:
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.
__________________
Ubuntu è un'antica parola africana che significa "non so configurare Debian" Chi scherza col fuoco si brucia.
Scienza e tecnica: Matematica - Fisica - Chimica - Informatica - Software scientifico - Consulti medici
REGOLAMENTO Gauron = HP dv6 A6-3410MX+HD6750 Win7HP64+Xubuntu12.04
Ziosilvio è offline   Rispondi citando il messaggio o parte di esso
Old 23-01-2007, 18:08   #17
yorkeiser
Senior Member
 
L'Avatar di yorkeiser
 
Iscritto dal: Jul 2006
Città: Tristram
Messaggi: 506
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>
#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]);
}
yorkeiser è offline   Rispondi citando il messaggio o parte di esso
Old 23-01-2007, 18:46   #18
repne scasb
Bannato
 
Iscritto dal: Feb 2003
Messaggi: 948
Quote:
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:

Codice:
	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.

Codice:
#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?"<*************":"");
}

Ultima modifica di repne scasb : 23-01-2007 alle 19:12.
repne scasb è offline   Rispondi citando il messaggio o parte di esso
Old 23-01-2007, 19:18   #19
repne scasb
Bannato
 
Iscritto dal: Feb 2003
Messaggi: 948
Quote:
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...).

Ultima modifica di repne scasb : 23-01-2007 alle 19:29.
repne scasb è offline   Rispondi citando il messaggio o parte di esso
Old 23-01-2007, 20:26   #20
cionci
Senior Member
 
L'Avatar di cionci
 
Iscritto dal: Apr 2000
Città: Vicino a Montecatini(Pistoia) Moto:Kawasaki Ninja ZX-9R Scudetti: 29
Messaggi: 62762
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()
{
	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;
}

Ultima modifica di cionci : 23-01-2007 alle 23:38.
cionci è offline   Rispondi citando il messaggio o parte di esso
 Rispondi


Il futuro delle GPU AMD e NVIDIA tra 20 nanometri e imprevisti Il futuro delle GPU AMD e NVIDIA tra 20 nanometr...
Smartphone e tablet personali al lavoro, ne parliamo con Ipswitch Smartphone e tablet personali al lavoro, ne parl...
Wi-Fi 802.11ac: reti wireless sempre più veloci Wi-Fi 802.11ac: reti wireless sempre più ...
Google reinventa lo smartphone con Project Ara: modulare ma non solo per geek Google reinventa lo smartphone con Project Ara: ...
Sniper Elite 3: torna il simulatore di cecchinaggio Sniper Elite 3: torna il simulatore di cecchinag...
Street View: un viaggio nel passato con ...
Apple, beta testing di OS X ora aperto a...
500 milioni di utenti attivi su WhatsApp...
Call of Duty 2014: rilasciato il primo s...
Lytro alza il tiro e presenta "Illum", f...
Apple in cerca di due dirigenti per un s...
Annunciata la BlizzCon 2014
Twitter: nuovi profili utente con più im...
OnePlus One svelato ufficialmente: top d...
Apple rilascia iOS 7.1.1 e protegge Airp...
Samsung Project KQ: Galaxy S5 'Premium' ...
Nuovo Hangouts 2.1 gestisce anche gli SM...
LG, ecco i piani per l'aggiornamento del...
Samsung Gear Fit, già esaurite le scorte...
Codemasters annuncia GRID Autosport: app...
The Bat! Professional Edition
Wireless Wizard
VMware Player
Anti-Malware
The Bat! Home Edition
Dropbox
AIDA64 Extreme Edition
Avant Browser
RAMDisk
Firefox 29
Chromium
AdwCleaner
Comodo Internet Security
Comodo AntiVirus
BurnAware Free
Tutti gli articoli Tutte le news Tutti i download

Strumenti

Regole
Non Puoi aprire nuove discussioni
Non Puoi rispondere ai messaggi
Non Puoi allegare file
Non Puoi modificare i tuoi messaggi

Il codice vB è On
Le Faccine sono On
Il codice [IMG] è On
Il codice HTML è Off
Vai al Forum


Tutti gli orari sono GMT +2. Ora sono le: 06:56.


Powered by vBulletin® Version 3.6.4
Copyright ©2000 - 2014, Jelsoft Enterprises Ltd.
Served by www2v