Newsgroup: it.hobby.enigmi
Titolo: cerco algoritmo, sono vicino [Lungo]

allora, stavamo parlando di numeri per convincere mio zio che non ci sono
statistiche "valide" e che anche se ha vinto un paio di volte la perdita a
lungo termine è assicurata. Ora non ricordo come siamo arrivati a parlare di
quante combinazioni ci sono con n numeri, così guardiamo un "prontuario" da
1 a 10 numeri per tutte le combinazioni da estratto a cinquina. Il tizio
(mio zio) chiede, e con 12 numeri? Così mi metto a scrivere un algoritmo per
calcorare i terni con 12 numeri ed in pratica lo trovo, ma non come vorrei,
ovvero:
TOT_NUMERI = 6
X = TOT_NUMERI -2
COMBINAZIONI = X + ((X - 1) * 2) + ((X - 2) * 3) + ((X - 3) * 4)
Questa cosa è apparentemente giusta, nel senso che infatti con 6 numeri
esistono 20 combinazioni di terno, ok. Il mio problema, anzi quello di
questo algoritmo è che non è scalabile, ovvero se i numeri fossero 7 e non
sei dovrei aggiungere un altro pezzo in fondo, seguendo l'andamento di -1 e
+1 come nell'algoritmo sopra. Quello invece che volevo ottenere io era un
algoritmo valido per qualsiasi numero. E' possibile? Ma soprattutto vorrei
capire come cavolo si deve ragionare per fare una cosa del genere :(
Dopo questa resa mi sono messo a fare la stessa cosa con gli ambi, credendo
che fosse più facile ma ottenendo invece lo stesso risultato con identica
problematica. Credo di capire che X vada moltiplicato per un numero
complessivo di volte in base al totale dei numeri da combinare (es.
moltiplicato per 20 se i numeri sono  10 perchè 10 - 2 = 8 * 20 = 160) ed
allo stesso modo la "somma della sottrazione" deve essere calcolata in base
al totale dei numeri (nel caso di 10 numeri è 40, infatti 160 - 40 = 120 ed
è corretto).
Questo premesso, è possibile ottenere un algoritmo su riga singola ovvero
senza necessità di usare il PC per fare il conto? Ad esempio per PC mi sono
scritto questa cosa, che è quanto riportato nel primo algoritmo, dovrebbe
essere corretta anche se necessita di correzioni "convenzionali" per le
variabili:
X = TOT_NUMERI - 2
For i = 1 To X
  T = T + ((X - coe) * i)
  coe = coe + 1
Next i
al termine del ciclo T conterrà il numero delle combinazioni e funziona per
qualsiasi numero, da 3 a n algoritmo piuttosto semplice in definitiva e
"speculare" o quasi a quello per gli ambi, ma al momento non riesco ad
andare oltre e portare questa cosa su singola riga, ma ripeto, che quello
che mi incuriosisce di più è il ragionamento che deve essere fatto, ovvero
dove mi sono fermato, quello che mi manca per il passaggio successivo...
-- 
Ludico.Net
http://www.ludico.net/index.asp?src=5

Non hai bisogno di nessun algoritmo complicato.
(Se ho capito bene il tuo problema).
Basta una calcolatrice scientifica che faccia il fattoriale.
Il numero di combinazioni di k numeri che si possono fare
con n numeri e' uguale a n!/(k! * (n-k)!) dove il ! denota
il fattoriale: 0!=1 1!=1 2!=1*2 3!=1*2*3 4=1*2*3*4. etc.
La formula n!/(k!*(n-k)!) e' meglio nota come "coefficiente binomiale
n su k" e si scrive come una n sopra una k il tutto tra parentesi tonde.
In effetti ponendo n=6 e k=3 viene 6!/(3!*3!)=20
Il motivo e' questo:
il primo numero lo puoi scegliere tra n diversi.
il secondo numero lo puoi scegliere tra n-1 diversi (quelli rimasti)
il terzo numero lo puoi scegliere tra n-2 diversi etc.etc
fino a
il k-esimo numero lo puoi scegliere tra (n-k+1) numeri diversi.
Quindi puoi fare n*(n-1)*(n-2)*...*(n-k+1) "estrazioni" di k numeri
da n numeri.
A questo punto pero' devi considerare che l'ordine non importa
e che quindi una specifica sequenza (per esempio 7 19 43) l'abbiamo
considerata una volta per ogni possibile ordinamento dei suoi membri.
Siccome l'ordine non ci interessa, dobbiamo dividere per il numero
di modi possibile di permutare k numeri. Questo numero e' k!
Quindi abbiamo n*(n-1)*(n-2)*...*(n-k+1) / k!. Per ottnere il risultato
finale basta osservare che per la definizione di fattoriale,
  n*(n-1)*(n-2)*...*(n-k+1) = n! / (n-k)!
Se ti interessano queste cose puoi leggerti un capitolo introduttivo
di qualsiasi testo di combinatorica o matematica discreta o anche di
probabilita' discreta.
ciao,
g.

 Basta una calcolatrice scientifica che faccia il fattoriale.
ho trovato il tasto n! va bene uguale?
non ho assolutamente capito come dovrei fare :( io fai conto
che ho solo un dato (i numeri per la combinazione) mentre
nella formula ne vedo due; n e k dove sbaglio?
non ho poi capito se la formula vale per tutte le serie da 2, 3, 4
numeri ecc... boh.. :(

 il fattoriale: 0!=1 1!=1 2!=1*2 3!=1*2*3 4=1*2*3*4. etc.
ho riprovato, vengono tutte sembra!! ^_^ come è possibile?
esiste il fattoriale come simbolo per PC? Esempio ^ è per le
potenze ma per il fattoriale non saprei :( cmq grazie, faccio
ancora confusione sull'ordine di soluzione, non mi ricordo se
si risolve prima il fattoriale o prima le moltiplicazioni, sono cose
che non ho mai fatto!! E questo mi soddisfa, almeno non ci
sono arrivato per mancanza di mezzi ^^ "pratici" la formula è
"semplice" come esposizione, ricordo che molti anni fa mia
cugina ne chiese una alla sua prof. di qualcosa, credo matematica
o simile, ma era una cosa mostruosa da calcolare...

 esiste il fattoriale come simbolo per PC? 
Di solito no. Pero' se sai programmare e' banale calcolare
il fattoriale. Basta un ciclo, visto che a parte il caso
particolare 0!=1 (per comodita'), in fattoriale di n e'
il prodotto di tutti i numeri da 1 a n.
Per quel che riguarda l'ordine di esecuzione, di solito
quando si scrive si assume che il fattoriale abbia la
precedenza sulle altre operazioni, tipo
4+5! vuol dire 4+(5!)
e
3!*7! vuol dire (3!)*(7!)
ciao,
g.

 il prodotto di tutti i numeri da 1 a n.
perchè il fattoriale di zero è uno??


E' una convenzione. Per calcolare il fattoriale di 0 dovresti 
moltiplicare i numeri da 1 a 0. Siccome 1>0 non avresti niente
da moltiplicare. Siccome non moltiplichi niente la cosa piu'
ragionevole e' assumere per convenzione che il risultato sia l'elemento
neutro della moltiplicazione, ovvero 1.
Inoltre porre 0!=1 aiuta a rendere piu' generali le formule che in casi
estremi contengono 0!.
Per esempio, abbiamo detto che i modi di prendere (senza contare
l'ordinamento) dei sottoinsiemi di k elementi da un insieme di n
elementi sono B(n,k) dove con B(n,k) indico il coefficiente
binomiale "n su k". Come ti ho detto
B(n,k)=n!/(k!*(n-k)!).
Se consideri il caso estremo in cui k=n, cioe' vuoi calcolare il
numero di sottoinsiemi di n elementi di un insieme di n elementi,
ovvero B(n,n) = n!/(n!*0!) vedi bene che la formula torna bene assumendo
0!=1 (infatti il risulato deve fare 1).
ciao,
g.
c