Torna indietro   Hardware Upgrade Forum > Software > Programmazione

L'Ombra di Mordor: Il Signore degli Anelli in salsa Assassin's Creed
L'Ombra di Mordor: Il Signore degli Anelli in salsa Assassin's Creed
Abbiamo provato nella suggestiva Sala Pilastri del Castello Sforzesco di Milano il nuovo titolo di Monolith Productions, la software house già responsabile di alcune pietre miliari della storia dei videogiochi come Blood, Shogo, No One Lives Forever, F.E.A.R. e Condemned. L'Ombra di Mordor potrebbe essere velocemente etichettato come un clone di Assassin's Creed, ma in realtà nasconde diverse novità interessanti e offre molta più profondità sul versante free roaming rispetto alla serie Ubisoft.
NVIDIA GeForce GTX 980: efficienza al primo posto
NVIDIA GeForce GTX 980: efficienza al primo posto
Un mix ideale tra prestazioni e consumi? E' questo l'obiettivo dichiarato dell'architettura Maxwell di NVIDIA, adottata per la GPU GM204 che equipaggia le schede video GeForce GTX 980 e GeForce GTX 970 al debutto quest'oggi sul mercato. Una nuova architettura top di gamma che sorprende per le prestazioni, ma più di tutto ricorda come per andare forte non serva sempre consumare tanto
Disney Infinity 2.0: un livello superiore grazie a Marvel
Disney Infinity 2.0: un livello superiore grazie a Marvel
In commercio dalla giornata di ieri, Disney Infinity 2.0 amplia la struttura e le caratteristiche di gioco del prodotti made in Disney ed è basato su tecnologia Nfc. Dopo 3 milioni di copie vendute, Disney è più che mai intenzionata a colmare il gap rispetto ad Activision e a Skylanders.
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: 12739
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: 12739
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: 12739
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: 12739
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: 12739
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


L'Ombra di Mordor: Il Signore degli Anelli in salsa Assassin's Creed L'Ombra di Mordor: Il Signore degli Anelli in sa...
NVIDIA GeForce GTX 980: efficienza al primo posto NVIDIA GeForce GTX 980: efficienza al primo post...
Disney Infinity 2.0: un livello superiore grazie a Marvel Disney Infinity 2.0: un livello superiore grazie...
Panasonic Lumix FZ1000, bridge super-zoom con sensore MAXI Panasonic Lumix FZ1000, bridge super-zoom con se...
F1 2014: tutte le 'novità' di quest'anno F1 2014: tutte le 'novità' di quest'anno
Square Enix affida Project Flare a Shinr...
Drop test di iPhone 6 e 6 Plus: ecco cos...
Big Data, anche Gartner riscontra cresci...
Bing Image Search aggiornato per utilizz...
Nuovo Microsoft Office: disponibili onli...
Volevate lo speciale TGTech da Colonia s...
Facebook: nuove modifiche per la News Fe...
Wasteland 2 finalmente disponibile
È cinese l'IPO record negli Stati...
iPhone 6 Plus teardown: tutti i segreti ...
Quando EA usava le Polaroid e i soldatin...
Anche Android L blindato per contrastare...
Microsoft licenzia altri 2100 dipendenti...
Amazon spende 4,6 milioni di dollari per...
La serie Final Fantasy XIII in arrivo su...
uTorrent
Iperius Backup
Firefox 32
AIDA64 Extreme Edition
Wireshark
Reg Organizer
Freemake Video Converter
SmartFTP
Nero 2015
HWiNFO64
HWiNFO32
ICQ
RemoveIT Pro
Chromium
Glary Utilities
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: 15:58.


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