Je dois calculer la factorielle de nombres jusqu'à environ 100! Afin de déterminer si une série de données de style bascule de pièces est aléatoire, conformément à Cette entrée Wikipedia sur Probabilité bayésienne. Comme vous pouvez le constater, la formule nécessaire implique 3 calculs factoriaux (mais, notamment, deux de ces calculs factoriels sont calculés en fonction du troisième).
J'ai vu Cette question ici , mais je pense Cet entier va être soufflé assez rapidement. Je pourrais également faire une fonction plus intelligente sur le calcul factorial (c'est-à-dire si j'en ai 11! / (7! 3!), Selon l'exemple Wiki, je pourrais aller à (11 * 10 * 9 * 8) / 3!), Mais cette frappe d'optimisation prématurée pour moi, dans le sens où je veux que cela fonctionne, mais je me fiche de la vitesse (encore).
Alors, quelle est une bonne bibliothèque C #, je peux appeler pour calculer la factorielle afin d'obtenir cette probabilité? Je ne suis pas intéressé par toute la génialité qui peut entrer dans le calcul factoriel, je veux juste le résultat de manière à ce que je puisse le manipuler. Il ne semble pas être une fonction factorielle dans l'espace de nom de mathématiques, d'où la question.
6 Réponses :
Il y a eu un Question précédente sur un similaire sujet. Quelqu'un ici a lié le Fonctions factorielles rapides site Web, qui inclut des explications de l'efficacité algorithmes et même C # code source.
Vérifiez-le maintenant-- Homme, j'aimerais vraiment qu'il y ait eu quelques meilleures approximations - mai-net-work-for tous les implémentations dans le cadre des bibliothèques de base.
Le problème avec ce code est que les téléchargements semblent être tous en Java et je ne suis tout simplement pas intéressé par le travail à convertir de Java en C #. L'auteur a probablement le code C # à télécharger, mais la solution math.net met le résultat dans un double, ce dont j'ai besoin exactement.
Vous pouvez essayer math.net - je n'ai pas utilisé cette bibliothèque, mais ils font la liste factorielle et logarithmique factorielle.
Voir aussi le Identique dans MATH.net numérics , le successeur de la bibliothèque liée liée math.net iridium.
Voulez-vous calculer des facteurs ou des coefficients binomiaux?
On dirait que vous souhaitez calculer les coefficients binomiaux - surtout comme vous le mentionnez 11! / (7! 3!).
là peut Soyez une bibliothèque qui peut faire cela pour vous, mais en tant que programmeur (vraisemblablement), débordement de la pile de visiteurs, il n'y a aucune raison de ne pas écrire un vous-même. Ce n'est pas trop compliqué.
Pour éviter le débordement de la mémoire, n'évaluez pas le résultat jusqu'à ce que tous les facteurs communs soient supprimés.
Cet algorithme doit encore être amélioré , mais vous avez la base d'un bon algorithme ici. Les valeurs de dénominateur doivent être divisées à leurs principaux facteurs pour le meilleur résultat. Comme il se tient, cela fonctionnera pour n = 50 assez rapidement. i peut estimer n = 110, k = 50 (retourne 6x10 ^ 31) mais ne peut pas exécuter n = 120, k = 50.
Et que se passe-t-il quand n ~ = 50 et k ~ = 2? Débordement! J'ai besoin d'une certaine façon de gérer des cas nonitriaux.
Dans ce cas, vous calculez n = 50 et k = 48 comme je l'ai signalé.
d'accord. Qu'est-ce que 48 !? Cela va-t-il s'intégrer dans un entier? Parce que c'est ce que votre dénominateur fait dans ce cas.
Indépendamment de l'algorithme, le résultat de, disons, NCR pour N = 100 et R = 50 déborde d'un nombre de 64 bits. Vous devez revenir à votre problème d'origine car vous ne pouvez pas stocker ce résultat.
Seulement si je n'allais pas avec un algorithme qui utilise quelque chose comme l'approximation de Stirling ou similaire, mettant le résultat en double. La prochaine étape de l'algorithme est une intégration rudimentaire, alors "assez proche" sera tout simplement bien et la perte de précision sur un double est correcte.
using System;
//calculating factorial with recursion
namespace ConsoleApplication2
{
class Program
{
long fun(long a)
{
if (a <= 1)
{
return 1;}
else
{
long c = a * fun(a - 1);
return c;
}}
static void Main(string[] args)
{
Console.WriteLine("enter the number");
long num = Convert.ToInt64(Console.ReadLine());
Console.WriteLine(new Program().fun(num));
Console.ReadLine();
}
}
}
S'il vous plaît lire les autres réponses. Ce n'est pas une solution suffisante, car longtemps n'a pas la capacité de gérer la taille d'un nombre près de 100 !. En tant que tel, une autre méthode (telle que la approximation de Stirling) doit être utilisée à la place.
Désolé, mais une approche récursive n'est en aucun cas efficace.
Les éléments suivants peuvent calculer la factorielle de 5000 en 1 seconde.
public class Number
{
#region Fields
private static long _valueDivision = 1000000000;
private static int _valueDivisionDigitCount = 9;
private static string _formatZeros = "000000000";
List<long> _value;
#endregion
#region Properties
public int ValueCount { get { return _value.Count; } }
public long ValueAsLong
{
get
{
return long.Parse(ToString());
}
set { SetValue(value.ToString()); }
}
#endregion
#region Constructors
public Number()
{
_value = new List<long>();
}
public Number(long value)
: this()
{
SetValue(value.ToString());
}
public Number(string value)
: this()
{
SetValue(value);
}
private Number(List<long> list)
{
_value = list;
}
#endregion
#region Public Methods
public void SetValue(string value)
{
_value.Clear();
bool finished = false;
while (!finished)
{
if (value.Length > _valueDivisionDigitCount)
{
_value.Add(long.Parse(value.Substring(value.Length - _valueDivisionDigitCount)));
value = value.Remove(value.Length - _valueDivisionDigitCount, _valueDivisionDigitCount);
}
else
{
_value.Add(long.Parse(value));
finished = true;
}
}
}
#endregion
#region Static Methods
public static Number operator +(Number c1, Number c2)
{
return Add(c1, c2);
}
public static Number operator *(Number c1, Number c2)
{
return Mul(c1, c2);
}
private static Number Add(Number value1, Number value2)
{
Number result = new Number();
int count = Math.Max(value1._value.Count, value2._value.Count);
long reminder = 0;
long firstValue, secondValue;
for (int i = 0; i < count; i++)
{
firstValue = 0;
secondValue = 0;
if (value1._value.Count > i)
{
firstValue = value1._value[i];
}
if (value2._value.Count > i)
{
secondValue = value2._value[i];
}
reminder += firstValue + secondValue;
result._value.Add(reminder % _valueDivision);
reminder /= _valueDivision;
}
while (reminder > 0)
{
result._value.Add(reminder % _valueDivision);
reminder /= _valueDivision;
}
return result;
}
private static Number Mul(Number value1, Number value2)
{
List<List<long>> values = new List<List<long>>();
for (int i = 0; i < value2._value.Count; i++)
{
values.Add(new List<long>());
long lastremain = 0;
for (int j = 0; j < value1._value.Count; j++)
{
values[i].Add(((value1._value[j] * value2._value[i] + lastremain) % _valueDivision));
lastremain = ((value1._value[j] * value2._value[i] + lastremain) / _valueDivision);
//result.Add(();
}
while (lastremain > 0)
{
values[i].Add((lastremain % _valueDivision));
lastremain /= _valueDivision;
}
}
List<long> result = new List<long>();
for (int i = 0; i < values.Count; i++)
{
for (int j = 0; j < i; j++)
{
values[i].Insert(0, 0);
}
}
int count = values.Select(list => list.Count).Max();
int index = 0;
long lastRemain = 0;
while (count > 0)
{
for (int i = 0; i < values.Count; i++)
{
if (values[i].Count > index)
lastRemain += values[i][index];
}
result.Add((lastRemain % _valueDivision));
lastRemain /= _valueDivision;
count -= 1;
index += 1;
}
while (lastRemain > 0)
{
result.Add((lastRemain % _valueDivision));
lastRemain /= _valueDivision;
}
return new Number(result);
}
#endregion
#region Overriden Methods Of Object
public override string ToString()
{
string result = string.Empty;
for (int i = 0; i < _value.Count; i++)
{
result = _value[i].ToString(_formatZeros) + result;
}
return result.TrimStart('0');
}
#endregion
}
class Program
{
static void Main(string[] args)
{
Number number1 = new Number(5000);
DateTime dateTime = DateTime.Now;
string s = Factorial(number1).ToString();
TimeSpan timeSpan = DateTime.Now - dateTime;
long sum = s.Select(c => (long) (c - '0')).Sum();
}
static Number Factorial(Number value)
{
if( value.ValueCount==1 && value.ValueAsLong==2)
{
return value;
}
return Factorial(new Number(value.ValueAsLong - 1)) * value;
}
}
Il ne fonctionne pas dans 1 seconde sur mon ordinateur;)
Bonjour tout le monde selon cette solution, j'ai ma propre solution où je calcule factorielle des éléments de tableau 1D. Le code est `int [] tableau = nouveau int [5] { 4,3,4,3,8 };
int fac = 1;
int[] facs = new int[array.Length+1];
for (int i = 0; i < array.Length; i++)
{
for (int j = array[i]; j > 0; j--)
{
fac *= j;
}
facs[i] = fac;
textBox1.Text += facs[i].ToString() + " ";
fac = 1;
}`