Numero di combinazioni

Puoi evitare la ricorsione e il ciclo completo se un'approssimazione è accettabile, puoi usare la Formula di Stirling per approssimare risposta.

Esempio

Opzione1:calcolainmodoricorsivooiterativo(n)

5!=5x4x3x2=120

Opzione2:utilizzal'approssimazionediStirling

5!~sqrt(2*pi*5)*(n/e)^n=sqrt(10*pi)*(5/2.718281828)^5=sqrt(31.41592654)*(1.839397206)^5=5.604991216*21.05608437=118.019168(closeto120)

(Nota:~significaapprossimativamenteedeè numero di Eulero definito 2.718281828)

Questo può sembrare sciocco perché 5! è così piccolo, ma per un numero come 100! l'approssimazione funziona abbastanza bene.

Grande esempio, n = 100:

secondo Google:

100! = 9.33262154 × 10^157

utilizzando Approssimazione di Stirling:

100! = 9.3224838328837612788449900430478 x 10^157

Questo è abbastanza vicino per me:)

Cosa c'è di sbagliato nell'usare la formula:

n!/(k! (n-k)!) .

Non hai bisogno di ricorsione per calcolare un fattoriale.

Ottimizza la formula della combinazione. Se viene chiesto a \ binom {n} {r}, prima impostare r su (r) o (n-r), qualunque sia il più piccolo. Ora usa il normale metodo di scorciatoia per trovare combinazioni senza calcolare fattoriali completi:

(n) (n-1) .... (n-r + 1) [r termini] / r!

Utilizza la formula di Stirling se i numeri sono troppo grandi. Non è necessario ricorrere alla ricorsione, poiché i loop sono più efficienti (anche se meno esteticamente gradevoli) per fattoriali e prodotti continuati.

Per calcolare fattoriale per numeri grandi puoi usare una libreria biginteger o una libreria di precisione arbitraria come link o fai da te (la moltiplicazione a precisione arbitraria è facile, la divisione non è così) utilizzando una matrice di intro non firmati.

Dato che non vuoi farlo in modo ricorsivo, esegui semplicemente i numeri da 1 a n, moltiplicandoli ciascuno in un biginteger che inizializzi con 1.

Quindi per calcolare il numero di combinazioni non permutazioni calcoli n! / k! / (n-k)!

Suppongo che tu possa costruire una semplice funzione per calcolare n! = nx (n-1) x (n-2) x ... x1. Ora, per grandi numeri, potresti dover dividere il tuo algoritmo come segue:

part1: quando il numero di input ha un valore accettabile da utilizzare con la formula sopra. Non sono uno sviluppatore C, quindi non posso dirti quale sia questo valore, per ora lo chiameremo (L). In questo caso, si applica semplicemente la formula precedente.

part2: Quando il numero di input è maggiore del valore accettabile L: La formula c (n, k) = nx (n-1) x (n-2) x .... x (nk)! / ( (nk)! * k!) questo può essere semplificato come:

c (n, k) = nx (n-1) x (n-2) x .... x (n-k + 1) / k! (vedi Risposta correlata )

questa ultima equazione coinvolge valori più piccoli di quelli nell'espressione originale.

se k! nell'espressione precedente è minore o uguale a L, quindi usa la formula regolare.

se k! > L o se nx (n-) x ... x (n-k + 1) > L puoi usare la formula di Sterling come suggerito da @Hunter McMillen