[C++, Algoritmi] Calcolo binomiale e verifica identità
Ciao a tutti,
un esercizio mi chiede di calcolare la sommatoria del binomiale e verificare che sia uguale a $2^n$ cioè:
$\sum((n!)/(k!(n-k)!))=2^n$ da $k=0$ a $k=n$
per verificare tale identità la prof ci ha suggerito di verificare che il mudulo $|\sum((n!)/(k!(n-k)!)) - 2^n|$ sia minore della precisione macchina, io ho provato nel seguente modo, è corretto??
//calcolo la sommatoria
sommatoria=0;
for(k=0;k<=n;k++){
binomiale=1;
if(k
sommatoria=sommatoria+binomiale;
}
//calcolo 2^n
potenza=1;
for(i=1;i<=n;i++) potenza=potenza*2;
//calcolo il modulo della differenza
sommatoria=fabs(sommatoria-potenza);
//calcolo la precisione macchina
float precisione,a;
a=precisione+1;
while(a!=1){
precisione=precisione/2; a=precisione+1
}
//verifico la disuguaglianza
if(sommatoria
un esercizio mi chiede di calcolare la sommatoria del binomiale e verificare che sia uguale a $2^n$ cioè:
$\sum((n!)/(k!(n-k)!))=2^n$ da $k=0$ a $k=n$
per verificare tale identità la prof ci ha suggerito di verificare che il mudulo $|\sum((n!)/(k!(n-k)!)) - 2^n|$ sia minore della precisione macchina, io ho provato nel seguente modo, è corretto??
//calcolo la sommatoria
sommatoria=0;
for(k=0;k<=n;k++){
binomiale=1;
if(k
sommatoria=sommatoria+binomiale;
}
//calcolo 2^n
potenza=1;
for(i=1;i<=n;i++) potenza=potenza*2;
//calcolo il modulo della differenza
sommatoria=fabs(sommatoria-potenza);
//calcolo la precisione macchina
float precisione,a;
a=precisione+1;
while(a!=1){
precisione=precisione/2; a=precisione+1
}
//verifico la disuguaglianza
if(sommatoria
Risposte
Non riesco a capire queste due righe:
if(k
Potresti usare ad esempio la funzione fattoriale che hai scritto nell'altro post.
Poi il confronto con la precisione macchina che ti chiede la prof. mi sembra superfluo.
La funzione binomiale e l'elevamento a potenza generano solo numeri interi, quindi basta un confronto più blando.
if(k
Potresti usare ad esempio la funzione fattoriale che hai scritto nell'altro post.
Poi il confronto con la precisione macchina che ti chiede la prof. mi sembra superfluo.
La funzione binomiale e l'elevamento a potenza generano solo numeri interi, quindi basta un confronto più blando.
praticamente quei 2 if servono per fare il minor numero possibile di iterazioni in base al valore di k sfruttando il fatto che il binomiale di n su k
è uguale al binomiale di n su n-k
quindi è superfluo il confronto con la precisione macchina, però è esatto?
è uguale al binomiale di n su n-k
quindi è superfluo il confronto con la precisione macchina, però è esatto?
"Lucia":
Ciao a tutti,
un esercizio mi chiede di calcolare la sommatoria del binomiale e verificare che sia uguale a $2^n$ cioè:
$\sum((n!)/(k!(n-k)!))=2^n$ da $k=0$ a $k=n$
l'esercizio esplicita l'utilizzo dell'uguaglianza $((n),(k)) = (n!)/(k!*(n-k!))$?
perchè l'utilizzo della suddetta uguaglianza introduce altri problemi di approssimazione. In particolare, penso non si dovrebbe introdurre altre approssimazioni secondare, perchè lo scopo dell'sercizio primario è di studiare proprio l'approssimazione dell'uguaglianza matematica con le potenze di $2$.
A mio parere penso che la defizione ricorsiva del coefficiente binomiale ed il legame con il triangolo di tartaglia con le somme di interi (invece che moltiplicazioni e divisioni, del fattoriale) sia la cosa migliore per avere risultati più "reali".
la complessità della versione ricorsiva si può abbassare a piacere.
"Lucia":
praticamente quei 2 if servono per fare il minor numero possibile di iterazioni in base al valore di k sfruttando il fatto che il binomiale di n su k
è uguale al binomiale di n su n-k
Si, l'avevo intuito ed è ok.
Ti chiedevo se la formula iterativa funziona... vedo ad esempio un "i/i" che restituisce 1. Forse manca una coppia di parentesi.
Fai delle prove come verifica.
Ad esempio una formula "più funzionante" (da verificare) mi sembra:
a=min(k,(n-k));
binomiale =1;
if (a!=0) for (i=1;i<=a;i++) binomiale = binomiale*(n+1-i)/i;
quindi è superfluo il confronto con la precisione macchina, però è esatto?
Si non riesco a capire la necessità di scomodare la precisione di macchina. Se il prof l'ha chiesta ci sarà un perchè...
Supponi di avere il triangolo di Tartaglia
Altrimenti è anche possibile usare una formula diretta sapendo che
\(\displaystyle \binom{n}{k} = \frac{n-k}{k+1} \binom{n}{k} \)
e sfruttando la simmetria
\(\displaystyle \binom{n}{k} = \binom{n}{n-k} \).
La parte più insensata è il calcolo della precisione della macchina. Che è al contempo sbagliata e inutile. Infatti ti basta usare la macro FLT_EPSILON contenuta in cfloat (o float.h se preferisci lo stile del C). L'errore è invece quello di non aver inizializzato precisione a 1.
Detto questo il test che devi fare è \(\displaystyle \biggl\lvert 2^n - \sum_{k = 1}^n \binom{n}{k}\biggr\rvert < 2^n\varepsilon \) dove \(\displaystyle \varepsilon \) è la precisione della macchina.
0 1 2 3 4 5 ------------ 1 0 0 0 0 0 1 1 0 0 0 0 1 2 1 0 0 0 1 3 3 1 0 0 1 4 6 4 1 0 ...puoi notare che è creato dalla riga precedente dalla trasformazione \(\displaystyle TR_j = TR_{j-1} + TR_{j-1}[i-1] \) in cui si pone \(\displaystyle TR_k[-1] = 0 \) per ogni \(\displaystyle k \). Penso però che abbia senso sfruttare questo metodo solo se ti calcoli ricorsivamente l'intero array di valori. Come metodo è sicuramente il più veloce e numericamente stabile.
Altrimenti è anche possibile usare una formula diretta sapendo che
\(\displaystyle \binom{n}{k} = \frac{n-k}{k+1} \binom{n}{k} \)
e sfruttando la simmetria
\(\displaystyle \binom{n}{k} = \binom{n}{n-k} \).
La parte più insensata è il calcolo della precisione della macchina. Che è al contempo sbagliata e inutile. Infatti ti basta usare la macro FLT_EPSILON contenuta in cfloat (o float.h se preferisci lo stile del C). L'errore è invece quello di non aver inizializzato precisione a 1.
Detto questo il test che devi fare è \(\displaystyle \biggl\lvert 2^n - \sum_{k = 1}^n \binom{n}{k}\biggr\rvert < 2^n\varepsilon \) dove \(\displaystyle \varepsilon \) è la precisione della macchina.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo