[C#] Combinazione semplice

[pare93]

Ragazzi qualcuno riesce a tradurmi la combinazione semplice (n x) oppure nCx in linguaggio C# ... non riesco proprio a darne fuori
Ricordo che (n x) = n! / (x! * (n - x)!)
Grazie mille

[Rsk]

Originariamente inviato da pare93

Ragazzi qualcuno riesce a tradurmi la combinazione semplice (n x) oppure nCx in linguaggio C# ... non riesco proprio a darne fuori
Ricordo che (n x) = n! / (x! * (n - x)!)
Grazie mille

Cosa non riesci a fare?
Il fattoriale (!) di N è dato dal prodotto dei primi N numeri interi positivi.
Inoltre il fattoriale di zero è 1.
Se realizzi la funzione che calcola il fattoriale hai finito..
Provaci

[pare93]

Ci proverò ancora ma non assicuro niente

[tuccio`]

Originariamente inviato da pare93

Ragazzi qualcuno riesce a tradurmi la combinazione semplice (n x) oppure nCx in linguaggio C# ... non riesco proprio a darne fuori
Ricordo che (n x) = n! / (x! * (n - x)!)
Grazie mille

giusto per la precisione, quello è il binomio di newton, che rappresenta anche il numero di combinazioni semplici di n elementi presi k a k (quindi identificarlo con le combinazioni semplici non è propriamente corretto)

e poi, chiaramente, sarebbe inefficiente calcolare tutti i fattoriali uno per uno, ti conviene cercare un metodo un minimo più furbo, ad esempio sfruttando il fatto che

n!/k! = n * (n - 1) * ... * (n - k + 1)

oppure

puoi prepararti un vettore V di dimensione n+1, in cui poni v[0] = 1 (perché 0! = 1)

e poi calcoli tutte le celle V[i] = i * V[i - 1]

così almeno avrai calcolato tutti i fattoriali che ti servono e potrai calcolare tutto con V[n] / (V[x] * V[n - x])

[pare93]

Si capisco il metodo che vorresti usare ma sinceramente a me sembra troppo lungo e con un grande spreco di memoria.

Domani cerco di sviluppare un algoritmo ... Grazie lo stesso comunque

Inoltre devo dire che la tua idea è molto interessante non ci avrei mai pensato

[tuccio`]

boh sì ma è chiaro che non ti serve a molto in questo caso, ti conviene calcolarli iterativamente

l'unica cosa è stare attenti a non fare prodotti già fatti precedentemente

[pare93]

In che senso non fare prodotti già fatti in precedenza?

Ad ogni modo ci ho pensato ora a mente lucida ... posto il codice che mi è venetuto.

Premetto che non l' ho testato lo stò facendo al momento perchè sono in un computer della scuola

Ricordo la formula che è nCx = n! / x! * (n - x)!

int fattN = n, fattX = x, fattNX = n - x;
double comb;

// Calcolo di n!
for (int i = 1; i <= n; i++)
      fattN *= n - i;

// Calcolo di x!
for (int i = 1; i <= x; i++)
      fattX *= x - i;

// Calcolo di (n - x)!
for (int i = 1; i <= (n - x); i++)
      fattNX *= (n - x) - i;

// Infine calcolo la combinazione semplice
comb = fattN / fattX * fattNX;

Ecco credo sia giusto ma il problema non è finito qui
Infatti io ero partito nel calcolare il valore atteso in una distribuzione binomiale ... ci proverò dai ...

[Kralizek]

non va! così ti fai 3 fattoriali che ti puoi facilmente risparmiare con qualche condizione al contorno ed un po' di semplificazioni

[astorcas]

Mai sentito parlare di memoizzazione (in english memoization)?

Basterebbe l'esempio su wikipedia per chiarirti cosa ti stanno suggerendo gli altri

[tuccio`]

Originariamente inviato da pare93

In che senso non fare prodotti già fatti in precedenza?

Ad ogni modo ci ho pensato ora a mente lucida ... posto il codice che mi è venetuto.

Premetto che non l' ho testato lo stò facendo al momento perchè sono in un computer della scuola

Ricordo la formula che è nCx = n! / x! * (n - x)!

int fattN = n, fattX = x, fattNX = n - x;
double comb;

// Calcolo di n!
for (int i = 1; i <= n; i++)
      fattN *= n - i;

// Calcolo di x!
for (int i = 1; i <= x; i++)
      fattX *= x - i;

// Calcolo di (n - x)!
for (int i = 1; i <= (n - x); i++)
      fattNX *= (n - x) - i;

// Infine calcolo la combinazione semplice
comb = fattN / fattX * fattNX;

Ecco credo sia giusto ma il problema non è finito qui
Infatti io ero partito nel calcolare il valore atteso in una distribuzione binomiale ... ci proverò dai ...

il valore atteso della binomiale di parametri n p (n lanci con probabilità di successo p) è np

basta pensarla come n eventi A1 .. An che indicano che all'estrazione i-esima c'è un successo.. dunque puoi prendere in considerazione le variabili indicatrici degli eventi Ai, che hanno tutti probabilità di successo p e sono scambiabili, quindi la media è np

per quanto riguarda il calcolo del fattoriale (che non serve, se quello che devi fare è la media della binomiale) quando dicevo che non dovresti fare prodotti già fatti intendo dire che per calcolare (n-k)! in pratica fai

1*2*...*(n-k)

e per calcolare n!

1*2*...*(n-k)*..*n! = (n-k)!*...*n

ecco, non vale la pena fare due volte questi prodotti (il discorso si estende anche a k!)

[pare93]

Bè da ma punto di vinta sintattico i duo metodo sono praticamente identici ... sono sompre tre cicli for che vanno da 1 ad n.

Ad ogni modo la speranza matematica in una distribuzione binomiale è data anche dalla sommatoria delle P(X=x) che va da zero ad n.

Quindi avevo pensato anche all' eventualità che l' utente non inserisca 'p' e di conseguenza calcolerei la media con la sommatoria.

Quindi una soluzione logica l' avei già trovata ... scompongo il valore atteso in :
sommatoria della combinazione semplice per la sommatoria della p^x per la sommatoria della q^(n-x). In questo modo risulta molto semplice secondo me tradurla.

Comunque ora ti espongo queste idee ma in questi giorni non ho possibilità di provarla ...